Учебное пособие: Дискретная математика
Рис. 3. Упорядоченные наборы аргументов
3.6 Построение формул алгебры логики по заданной таблице истинности
Пусть F – двоичная функция от n переменных. Предположим, что F не равна тождественно нулю. Пусть T1, T2,…, Tk – все точки ее определения, в которых F=1. Можно доказать, что справедлива следующая формула:
,
где 
, j=1,2,…, k,
Построить функцию F можно и по-другому. Если функция F не равна тождественно единице и S1, S2,…, Sm – все точки области ее определения, в которых F=0, то справедлива формула:
,
где 
, j=1,2,…, m.
Из
приведенных формул видно, что любую двоичную функцию можно записать, используя
лишь операции ¬, 
, 
.
Основная
конъюнкция – это конъюнкция основных высказываний переменных или их отрицаний.
Например, 
.
Основная
дизъюнкция – это дизъюнкция основных высказываний переменных или их отрицаний.
Например, 
.
Конъюнктивной нормальной формой (КНФ) данной формулы называется формула, равносильная данной и представленная в виде конъюнкции основных дизъюнкций. Например, (A+B) (A+C+B) (D+A).
Дизъюнктивной нормальной формой (ДНФ) данной формулы называется формула, равносильная данной и представленная в виде дизъюнкции основных конъюнкций. Например, AB+C+AC.
Теорема 1. Для того чтобы формула алгебры высказываний была тождественно истинной, необходимо и достаточно, чтобы ее КНФ содержала в каждой элементарной дизъюнкции некоторое высказывание и его отрицание.
Теорема 2. Для того чтобы формула алгебры высказываний была тождественно ложной, необходимо и достаточно, чтобы ее ДНФ содержала в каждой элементарной конъюнкции некоторое высказывание и его отрицание.
Совершенные дизъюнктивные, конъюнктивные и полиномиальные нормальные формы представления переключательных (логических) функций. Многообразие формул, посредством которых может быть выражена любая логическая функция, определяет многообразие форм логических функций, т. е. способов их записи путем применения к переменным и их группам элементарных логических операций. Наиболее удобными для практического использования оказываются совершенные нормальные формы представления сложных логических функций. В алгебре логики доказывают, что любая логическая функция F (A, B, C,…, N) может быть представлена только одной совершенной дизъюнктивной нормальной формой (кроме константы нуль) или только одной совершенной конъюнктивной нормальной формой (кроме константы единица).
Пусть функция X=F (A, B, C) задана таблицей 4. Запись функции Х в виде логической суммы (дизъюнкции) логических произведений (конъюнкций) переменных, для которых значение функции Х равно 1, и является совершенной дизъюнктивной нормальной формой (СДНФ) представления логической функции.
Таблица 4
| A | B | C | X |
| 0 | 0 | 0 | 0 |
| 0 | 0 | 1 | 1 |
| 0 | 1 | 0 | 1 |
| 0 | 1 | 1 | 0 |
| 1 | 0 | 0 | 1 |
| 1 | 0 | 1 | 0 |
| 1 | 1 | 0 | 0 |
| 1 | 1 | 1 | 1 |
СДНФ логической функции следует находить в такой последовательности:
1) составить произведения переменных для строк таблицы истинности, в которых Х равна 1. Если значение переменной (А, В или С) в строке равно 0, то в произведении записывается отрицание этой переменной;
2) написать сумму произведений, для которых функция Х равна 1. Полученная сумма и является СДНФ. В общем виде
, (1)
Это правило называют правилом записи переключательной функции по единицам. Согласно этому правилу, данные табл. 4 описываются аналитическим выражением, связывающим все наборы переменных, для которых Х=1, в виде:
. (2)
Запись функции Х в виде логического произведения (конъюнкции) логических сумм (дизъюнкций) переменных, для которых функция Х равна 0, является совершенной конъюнктивной нормальной формой (СКНФ) представления логической функции.
Для табл. 4 аналитическое выражение в СДНФ, связывающее все наборы переменных, для которых Х=0, имеет вид:
. (3)
Для представления логической функции Х в СКНФ произведем операцию отрицания левой и правой частей равенства (3)
и на основании законов двойного отрицания и инверсии
. (4)
СКНФ логической функции, согласно (4), следует находить в такой последовательности:
1) составить логические суммы переменных для строк таблицы истинности, в которых функция Х равна 0. Если значение переменной (А, В или С) в строке равно 1, то в сумме записывается отрицание этой переменной;
2) написать логическое произведение составленных логических сумм. Полученное произведение и является СКНФ. В общем виде:
, (5)
где Fi – сложные дизъюнкции.
Это правило также называют правилом построения переключательной функции по нулям.
Кроме представления функций в виде СДНФ и СКНФ используют и совершенную полиномиальную нормальную форму СПНФ. Вместо дизъюнкции может быть записана функция сложения по модулю два (сумма Жегалкина):
, (6)
где Fi – сложные конъюнкции.
Существует специальная таблица, в которой все элементарные логические операции от двух аргументов представлены в двух совершенных нормальных формах.
Нормальные формы представления переключательной функции иногда называют стандартными (табл. 5).
Таблица 5
| f |
A 0011 B 0101 |
Название функции | Обозначение функции | СДНФ | СКНФ |
|
f0 |
0000 | Константа нуль | 0 | Не имеет |
|
|
f1 |
0001 | Логическое произведение, конъюнкция |
|
|
|
|
f2 |
0010 | Функция запрета по В |
|
|
|
|
f3 |
0011 | Переменная А |
|
|
|
|
f4 |
0100 | Функция запрета по А |
|
|
|
|
f5 |
0101 | Переменная В |
|
|
|
|
f6 |
0110 | Сумма по мо дулю 2, логическая неравнозначность |
|
|
|
|
f7 |
0111 | Логическое сложение, дизъюнкция |
|
|
|
|
f8 |
1000 | Операция (стрелка) Пирса, операция Вебба |
|
|
|
|
f9 |
1001 | Эквивалентность, логическая равнозначность |
|
|
|
|
f10 |
1010 | Инверсия В |
|
|
|
|
f11 |
1011 | Импликация от В к А |
|
|
|
|
f12 |
1100 | Инверсия А |
|
|
|
|
f13 |
1101 | Импликация от А к В |
|
|
|
|
f14 |
1110 | Операция (штрих) Шеффера |
|
|
|
|
f15 |
1111 | Константа единица | 1 |
|
Не имеет |
