4. Функциональные схемы и структурные формулы логических устройств

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

НЕ

Х

Х & Y

Х  Y

инвертор

конъюнктор

дизъюнктор

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

Пример 4. По заданной структурной формуле (логической функции) F(A,B) = B & A  B & A построить функциональную (логическую) схему.

Решение. Построение надо начинать с операции, которая должна выполняться последней. В данном случае это логическое сложение, значит, на выходе логической схемы должен быть дизъюнктор. На него сигналы подаются от двух конъюнкторов, на которые, в свою очередь подаются один входной сигнал нормальный и один инвертированный (инверторов).

НЕ

A

B & A

B & A

F(A,B) ) = B & A  B & A

НЕ

B

5. Совершенная дизъюнктивная нормальная форма (сднф), совершенная конъюнктивная нормальная форма(скнф)

Логические функции можно задать с помощью: 1)формулы,2)таблицыистинности. По формуле легко восстановить таблицу. На практике при конструировании электронных устройств возникает обратная задача – от таблицы истинности перейти к формуле, чтобы на ее основе построить функциональную схему.

Переменные структурной формулы соответствуют входам функциональной схемы. Значения переменных в таблице истинности соответствуют значениям входов функциональной схемы.

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