Студопедия
Случайная страница | ТОМ-1 | ТОМ-2 | ТОМ-3
АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатика
ИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханика
ОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторика
СоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансы
ХимияЧерчениеЭкологияЭкономикаЭлектроника

Функционально полные базисы.

Читайте также:
  1. АНАЛИЗ ФУНКЦИОНАЛЬНОЙ МОДЕЛИ ОБЪЕКТА
  2. Взаимосвязь общелитературных (общеязыковых) и функционально-речевых (стилистич) норм. Динамическая теория нормы.
  3. Взаимосвязь управления проектами, управления инвестициями и функционального менеджмента
  4. Г) Происходит отторжение функционального слоя эндометрия.
  5. Глава 10. Полные хотят худеть быстрее и без насилия над собой
  6. Задание 9. Прочитайте предложения. К какому функциональному стилю они относятся? Охарактеризуйте употреблённые в них предлоги и предложные сочетания.
  7. Классификация информационных систем по функциональному признаку

В предыдущих разделах рассматривались возможности представления переключательных функций и эквивалентных преобразований формул, записанных с помощью операций конъюнкции, дизъюнкции и отрицания. Однако такой способ аналитического представления переключательных функций не является единственным. Современные технологии позволяют строить логические схемы из элементов, выполняющих операции, отличные от конъюнкции, дизъюнкции и отрицания. Естественно сформулировать следующую задачу: с помощью каких операций можно представить любую переключательную функцию и какими свойствами должны обладать операции, допускающие такое представление.

Приведенные формулы позволяют сформулировать следующие утверждения:

1. Каждая булева функция от n переменных, отличная от константы 0, имеет единственную СДНФ.

2. Каждая булева функция от п переменных, отличная от константы 1, имеет единственную СКНФ.

Эти утверждения называютсятеоремой о функциональной полноте.

Прежде чем приступить к решению поставленной задачи, необходимо уточнить два вопроса:

1. каким образом должно строиться представление произвольной переключательной функции с помощью некоторого подмножества операций?

2. как следует подходить к выбору операций, включаемых в это подмножество?

Для ответа на первый вопрос воспользуемся общим положением о том, что формулу любой сложности можно построить с помощью двух действий: суперпозиции функций и подстановки переменных.

Определение: Пусть имеется некоторое множество В переключательных функций. Назовем множество В Функциональным базисом, а входящие в него функции - базисными. Определим понятие формулы над функциональным базисом:

· выражение f(x1,...,xn), где f ∈ В, есть формула над В;

если f(x1,...,xm) - базисная функция, а выражения F1,...,Fm являются символами переменных либо формулами, то суперпозиция f(F1,...,Fm) также есть формула над В.

Определение: Принцип подстановки заключается в следующем: если a = b, то в любой формуле, содержащей a, вместо а можно подставить b, и в результате будет получена эквивалентная формула.

Ответ на второй вопрос заключается в том, что в базис B целесообразно включать "простейшие" операции (функции), зависящие по возможности от меньшего числа аргументов. Такими функциями, очевидно, являются функции одной и двух переменных.

 

УПРАЖНЕНИЕ 8.3.1

1. Сколько нужно сделать операций склеивания, чтобы получить конъюнкцию ранга 3 из конъюнкций ранга 7?

2. Проверьте, является ли совокупность кодов {0z01, z111, 1z10} покрытием функции f(x1, x2, x3, x4) = { 1,5,7,10,14,15} ?

3. Может ли ранг СкДНФ совпадать с рангом МДНФ?

 

УПРАЖНЕНИЕ 8.3.2

1. Постройте гиперкуб для 4 переменных, соединяя ребрами одноименные вершины двух трехмерных кубов.

2. Выделите вершины построенного гиперкуба, определяющие функцию f1(x1, x2, x3, x4) = {0,1,5,7,8,10,12,14,15}, а затем все грани размерности 3 и 2.



 

УПРАЖНЕНИЕ 8.3.3

Найдите с помощью табличного метода множество минималей для следующих функций:

· f1(x1, x2, x3, x4) из упражнения 3.2 (п.2);

· f2(x1, x2, x3, x4, x5) = {1,5,10,14,17,19,21,23,26,27,30,31};

· f3(x1, x2, x3, x4, x5) = {0,1,4,5,9,10,11,16,18,24,25,26,27}.

 

УПРАЖНЕНИЕ 8.3.4

Построить, используя алгоритм последовательного извлечения экстремалей, минимальные покрытия для следующих функций из упражнения 3.3:

· f1(x1, x2, x3, x4);

· f2(x1, x2, x3, x4, x5);

· f3(x1, x2, x3, x4, x5),

· используя построенные ранее СкДНФ.

 

УПРАЖНЕНИЕ 8.3.5

Постройте неизбыточные покрытия, применяя способ ветвления для следущих функций:

· f4(x1, x2, x3, x4)= { 0,1,5,7,8,10,14,15};

· f5(x1, x2, x3, x4, x5) =

· = {0,1,2,3,4,5,6,7,12,13,14,15,16,17,18,19,24,25,26,27,28,29,30,31};

· f6(x1, x2, x3, x4, x5) = {8,10,11,12,13,14,15,24,25,26,27,28,29,31},

а затем с помощью алгебраического представления таблицы покрытий найдите МДНФ этих функций и сравните полученные результаты.

 

УПРАЖНЕНИЕ 8.3.6

Используя карты Карно, найдите МДНФ функций:

· f4(x1, x2, x3, x4) = { 0,1,5,7,8,10,14,15};

· f5(x1, x2, x3, x4, x5) = {0,1,2,3,4,5,6,7,12,13,14,15,16,17,18,19,24,25,26,27,28,29,30,31};

· f6(x1, x2, x3, x4, x5) = {8,10,11,12,13,14,15,24,25,26,27,28,29,31},
а затем сравните полученные результаты с результатами упражнения 8.3.5.

Загрузка...

 


Дата добавления: 2015-07-07; просмотров: 299 | Нарушение авторских прав


<== предыдущая страница | следующая страница ==>
Лекция № 12| Полиномы Жегалкина

mybiblioteka.su - 2015-2021 год. (0.018 сек.)