6. Бинарный фал. Синтез логических схем.

ФАЛ двух аргументов (бинарные): Всего таких функций . Другое название этих функций - двоичные бинарные (двухоперандные, двухразрядные) шифраторы с унарным (одноразрядным) выходом.

Основные этапы проектирования (синтеза) схем: 1)Представление функций, выполняемой схемой, в виде таблицы истинности или СКНФ (СДНФ). 2)Минимизация логической функции. 3)Перевод функции в базис, в котором будет строиться схема. 4)Построение схемы в выбранном базисе.

Составление ф-ций СКНФ и СДНФ сожжет быть представлено в виде таблицы истинности, в виде формулы. Таблица истинности – совокупность всех возможных комбинаций на входе цифрового устройства. СДНФ – в каждой конъюнкте представлены все литералы по одному роду. СКНФ – в каждой дизъюнкте представлены все литералы по одному роду. Литерал – формула или её логич отрицание.

9. Правила эквивалентности булевой алгебры.

Закон де Моргана: х у=х у; х у=х у.

Закон дистрибутивности: х (у z)=(x y) (x z); x (y z)=(x y) (x z); x (y z)=(x y) (x z).

Закон коммуникативности: x y=y x, где { , , ,~, ,|}.

Закон ассоциативности: (x y) z=x (y z), где { , , ,~}.

Закон идемпотенции: x x=x, где { , }.

Закон поглощения: х (х у)=х (х у)=х.

Закон Блейка-Порецкого: х (х у)=х у; х (х у)=х у.

Закон силлогизма: (х у) (y z)=x z.

Закон склеивания: (х у) (х у)=у; (х у) (х у)=у.

При минимизации используют таблицы эквивалентности и следующие операции.

Операция неполного склеивания: .

Операция обобщенного склеивания: .

Операция поглощения: .

Операция развертывания — умножение каждого произведения на выражение вида .

7.Представление фал. Таблица истинности. Сднф

ФАЛ может быть представлена (задана) одним из следующих способов:

1. В виде таблицы истинности. Например,

2. В виде формулы. Например, .

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

Литерал - формула или ее логическое отрицание.

Элементарная дизъюнкция (дизъюнкт) - дизъюнкция литералов. Например, .

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

Совершенная дизъюнктивная нормальная форма (СДНФ) — ДНФ, в которой в каждом конъюнкте представлены все литералы по одному разу. Например, . Каждый конъюнкт устанавливает функцию в 1.

8. Скнф. Получение сднф по скнф

Литерал - формула или ее логическое отрицание.

Элементарная конъюнкция (конъюнкт) - конъюнкция литералов. Например, .

Конъюнктивная нормальная форма (КНФ) — форма, в которой булева формула имеет вид конъюнкции нескольких дизъюнктов. Например, .

Совершенная конъюнктивная нормальная форма (СКНФ) — КНФ, в которой в каждом дизъюнкте представлены все литералы по одному разу. Например, . Каждый дизъюнкт устанавливает функцию в 0.

Рассмотрим способ получения СДНФ из СКНФ и обратно.

Запишем две формы одной и той же функции: . Видно, что общее число членов в этих двух формах равно сумме нулей и единиц функции, то есть равно . Если в исходной форме функции, записанной в СКНФ или СДНФ, содержится членов, то в другой ее форме (т.е. СДНФ или СКНФ) их будет . Так как в функцию мы включаем дизъюнктивные (конъюнктивные) члены и берем их по наборам, на которых функция или обращается в 0 (в 1), то для перехода от одной формы задания функции к другой нужно выписать все недостающие члены и поставить над каждой переменной отрицание, а также заменить знаки конъюнкции на дизъюнкцию и обратно. Практический смысл перехода заключается в том, что можно определить, реализация какой формы потребует меньший объем оборудования.