23.04.2024 / Нормальные формы и ЭК/ДК

Логические нормальные формы

Простая конъюнкция (элементарная)

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

Простая дизъюнкция (элементарная)

Это дизъюнкция одной или нескольких переменных, где каждая переменная входит не более одного раза, либо сама, либо ее отрицание.

Дизъюнктивная нормальная форма (ДНФ)

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

Конъюнктивная нормальная форма (КНФ)

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

Задача

Пусть дана таблица истинности для некоторой логической функции $F(X,Y)$. Наша задача состоит в том, чтобы перейти от таблицы истинности к формуле и на ее основе построить функциональную схему.

Проблема

Как перейти от таблицы истинности к формуле, чтобы построить функциональную схему?

Решение

Для решения этой задачи мы используем алгоритмы получения СДНФ и СКНФ.

Совершенные нормальные формы

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

Это ДНФ, где каждый элементарный конъюнкт содержит все переменные данного списка, либо сами, либо их отрицания, причем в одном и том же порядке.

Совершенная конъюнктивная нормальная форма (СКНФ)

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

Теорема алгебры логики

Любую функцию можно представить в виде СДНФ и СКНФ, за исключением констант 0 и 1.

Решение

Мы можем использовать алгоритмы получения СДНФ и СКНФ для нахождения соответствующих нормальных форм.

Алгоритм получения СДНФ по таблице истинности

1. Отметить строки таблицы истинности, в последнем столбце которых стоит 1.

2. Выписать для каждой отмеченной строки конъюнкцию всех переменных, где если значение в данной строке равно 1, то в конъюнкцию включается сама эта переменная, если равно 0, то ее отрицание.

3. Связать все полученные конъюнкции в дизъюнкцию.

Пример

Пусть у нас есть таблица истинности:

| X | Y | F |
|---|---|---|
| 0 | 0 | 1 |
| 0 | 1 | 0 |
| 1 | 0 | 1 |
| 1 | 1 | 1 |

Отметим строки, где F = 1: 1-я и 3-я строки.

Для 1-й строки: $( X \land \neg Y )$, для 3-й строки: $( X \land Y )$.

Таким образом, СДНФ для данной функции: $( (X \land \neg Y) \lor (X \land Y) )$.

Алгоритм получения СКНФ по таблице истинности

1. Отметить строки таблицы истинности, в последнем столбце которых стоит 0.

2. Выписать для каждой отмеченной строки дизъюнкцию всех переменных, где если значение в данной строке равно 0, то в дизъюнкцию включается сама эта переменная, если равно 1, то ее отрицание.

3. Связать все полученные дизъюнкции в конъюнкцию.

Пример

Пусть у нас есть таблица истинности:

| X | Y | F |
|---|---|---|
| 0 | 0 | 1 |
| 0 | 1 | 0 |
| 1 | 0 | 0 |
| 1 | 1 | 0 |

Отметим строки, где F = 0: 2-я, 3-я и 4-я строки.

Для 2-й строки: $( X \lor Y )$, для 3-й строки: $( \neg X \lor Y )$, для 4-й строки: $( \neg X \lor \neg Y )$.

Таким образом, СКНФ для данной функции:$( (X \lor Y) \land (\neg X \lor Y) \land (\neg X \lor \neg Y)$ ).