1.3. Формы представления логических функций

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

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

Таблица 1.11

Аргументы			Номер набора	Значение функции
Х1	Х2	Х3
0	0	0	0	0
0	0	1	1	0
0	1	0	2	1
0	1	1	3	1
1	0	0	4	0
1	0	1	5	1
1	1	0	6	0
1	1	1	7	1

Минтерм представляет собой конъюнкцию (логическое произведение) от n переменных, в котором каждая переменная входит один раз в прямой или инверсной форме. Очевидно, что для n переменных существует 2ⁿ минтермов, каждый из которых представляет собой простую функцию n переменных. Минтермы могут быть пронумерованы. Минтерму, обращающемуся в 1 на i-ом наборе значений аргументов функции, присваивается i-ый номер.

Например: для двух переменных существует 4 минтерма:

, , , .

Аналогично, махтерм М представляет дизъюнкцию от n переменных, в которую каждая переменная входит один раз в прямой или инверсной форме. Для n переменных существует 2ⁿ махтермов. Махтерму, обращающемуся в 0 на i-ом наборе значений аргументов функции, присваивается i-ый номер.

Например: для двух переменных существует 4 махтерма:

, , , .

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

Аналитическое представление функции в СДНФ будет равно логической сумме логических произведений значений функции на i-ом наборе на i-ый минтерм. Запись функции будет иметь вид

.

Таким образом, функция представленная таблицей 1.11, запишется в следующем виде

F(X₁,X₂,X₃)=0·m₀+0·m₁+1·m₂+1·m₃+0·m₄+1·m₅+0·m₆+1·m₇ =

= .

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

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

.

Здесь первый член конъюнкции содержит дизъюнкцию (выражение в скобках).