Понятие конституенты единицы и нуля.

Поставим перед собой задачу аналитической записи в таблице истинности единицы на конкретном наборе, причем запись необходимо осуществить с помощью элементов базиса Буля. Такая возможность имеется, если воспользоваться понятием «Конституента единицы».

  Определение: Конституента единицы – специальная переключательная функция, которая равна единице только на одном наборе переменных.

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

В качестве примера запишем конституенты единицы для функции 2-yx переменных.

n=2, то .

                          

                          

                         

Правило: чтобы записать конституенту единицы n переменных на m-ом наборе необходимо записать конъюнкцию n переменных под ней двоичный эквивалент номера набора m и поставить отрицания под теми переменными, которым в двоичном числе соответствуют нули.

В качестве примера запишем конституанты единицы, 5-ти переменных на 5-ом и 25-ом наборах.

Можно проводить синтез переключательной функции и по нулям. Для этого вводится понятие «Конституенты нуля». Записывается эта конституента через дизъюнкцию входных переменных, с применением инверсии.

Запишем конституанты нуля для 2-ух переменных:

Правило: чтобы записать конституанту нуля n переменных на m-ом наборе необходимо записать дизъюнкцию n переменных под ней двоичной эквивалент номера набора и поставить знаки отрицания над аргументами, которым в двоичном числе соответствует единица.

Пример:

 

Понятие совершенных дизъюнктивных нормальных форм (СДНФ) и совершенных конъюнктивных нормальных форм (СКНФ).

Определение: дизъюнкция конституанты единицы на тех наборах, где функция равна единицы называется (СДНФ). Она единственна для переключательной функции и полностью ее описывает, позволяя в результате получать по своим значением требуемые единицы и нули.

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

. Символ v показывает, что это дизъюнктивная форма.

В качестве примера запишем СДНФ переключательной функции устройства, для голосования.

Полученная функция имеет единицы на 3, 5, 6, 7-ом наборах.

Можно сказать, что синтез схемы завершен.

Остается только заменить логические операции на соответствующие элементы, помня о приоритете операций:

1) Инверсия, если она относится к одному аргументу;

2) Конъюнкция;

3) Дизъюнкция;

В результате схема содержит: три инверсии, четыре конъюнкции и один дизъюнктор. 

Выход дизъюнктора является выходом устройств.

Рисунок 2.2.1

Определение: СКНФ называется конъюнкция конституант нуля на тех наборах, где функция равна нулю.

Запишем СКНФ для нашего примера и построим схему.

СКНФ =

             0 0 0 0 0 1 0 1 0 1 0 0

Рисунок 2.2.2

Как видно в нашем случаи обе схемы имеют одинаковое количество элементов. Это получилось потому, что функция имеет одинаковое количество 0 и 1. Поэтому очевидно, что для сокращения количества элементов в схеме, если функция имеет больше 1 чем 0, то синтез надо проводить по нулям (СКНФ) и наоборот.

 

Переход от СДНФ и СКНФ в базис Шеффера и Вебба.

1. Для перехода в базис Шеффера («И, НЕ») удобно использовать СДНФ или ДНФ. Для этого записывается дизъюнктивная форма, от нее берется двойное отрицание, от одного из отрицаний избавляются по закону Де Моргана, заменяя дизъюнкцию на конъюнкцию.

Пример:

Проведем синтез СДНФ функции двух переменных с номером шесть:

Эта функция равна единице на первом и втором наборе.

СДНФ =  

Рисунок 2.3.1

По записи СДНФ и по возможной реализации в базисе Буля, при сравнении с полученной схеме в базисе Шеффера, видим, что количество использованных элементов не поменялось, просто произошла их унификация.

2. В базис Вебба («ИЛИ, НЕ») проще всего осуществить переход от конъюнктивной нормальной формы.

Проводится это таким же способом: берется двойное отрицание, от СКНФ избавляются от одного из отрицаний по закону Де Моргана, заменяя конъюнкцию на дизъюнкцию.

Рассмотрим переход на примере реализации . Шестая функция равна нулю на нулевом и третьем наборе.

СКНФ=

 

Рисунок 2.3.2

3. Иногда бывает необходимо имея СДНФ, перейти в базис Вебба. В этом случае подход к преобразованию точно такой же – двойное отрицание. Хотя требуются дополнительные преобразования выражения по законам Булевой алгебры.

Для нашего примера проведем такие преобразования.

СДНФ=

В качестве примера построим схему в базисе Шеффера для устройства голосования.

 – запись по единицам

         ^(0, 1, 2, 4) – запись по нулям

Рисунок 2.3.3

III. Минимизация переключательных функций.

⇐ Предыдущая1234567Следующая ⇒

Поделиться: