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

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

(3.2)

Выражение (3.2) записано с использованием операций логического сложения (дизъюнкции), логического умножения (конъюнкции) и логического отрицания (инверсии), которые выполняют простейшие логические элементы ИЛИ, И и НЕ соответственно. Для каждого единичного набора составляется логическое произведение входных переменных, в которое переменная входит с инверсией при нулевом ее значении на данном наборе. Эти логические произведения объединяются затем знаком логического сложения (+ или Ú).

На рис. 3.2 представлены таблицы истинности и условные графические обозначения двухвходовых логических элементов. Кроме указанных выше, на практике широко используются элементы И-НЕ, ИЛИ-НЕ, Исключающее ИЛИ. Логическая функция последнего (функция «неравнозначность» или сумма по модулю два) в СДНФ записывается в виде

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

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

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

1. Составить минтермы для строк таблицы истинности, на которых функция F равна 1. Если значение переменной в этой строке равно 0, то в минтерме записывается отрицание этой переменной.

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