Совершенные конъюнктивная и дизъюнктивная нормальные формы

Конъюнкт – конъюнкция некоторых переменных или их отрицаний.

Дизъюнкт – дизъюнкция некоторых переменных или их отрицаний.

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

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

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

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

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

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

A	B	C	F
0	0	0	0
0	0	1	0
0	1	0	0
0	1	1	1
1	0	0	0
1	0	1	1
1	1	0	1
1	1	1	1

Построение СДНФ по таблице истинности

Выписать совершенные конъюнкции и связать их через дизъюнкцию.

Моделирование схемы СДНФ

Схемотехническое представление  изображено ниже.

Построение СКНФ по таблице истинности

Выписать совершенные дизъюнкции и связать их через конъюнкцию.

Моделирование схемы СКНФ

Схемотехническое представление  изображено ниже.

СДНФ	СКНФ

 

Логические законы и правила

· Коммутативный

,

·

,

· Дистрибутивный

,

·

· Закон идемпотентности

,

,

,

· ,

,

,

· Правило склеивания

,

· Правило свертки

,

· Правило поглощения

,

· Законы де Моргана

,

,

· Правило раскрытия импликации

· Правила раскрытия эквивалентности

,

· Правило раскрытия строгой дизъюнкции

Лекция №5