- •5 Элементы математической логики
- •5.1 Основные понятия математической логики
- •5.2 Логические переменные и логические функции. Алгебра логики
- •5.3 Основные равносильности алгебры логики
- •5.4 Функционально полные системы операций
- •5.5 Совершенные дизъюнктивные и конъюнктивные нормальные формы
- •5.5.1 Совершенные дизъюнктивные нормальные формы
- •5.5.2 Совершенные конъюнктивные нормальные формы
- •5.6 Минимизация формул алгебры логики
- •5.6.1 Минимальные днф
- •5.6.2 Минимальные кнф
- •5.8Основные понятия логики предикатов
- •5.9 Операции над предикатами
- •5.10 Кванторы
- •5.11 Операции с кванторами
5.5.1 Совершенные дизъюнктивные нормальные формы
Будем называть элементарной конъюнкцией конъюнкцию отдельных переменных, некоторые из которых могут иметь знаки отрицания. Например, формулы X1&X2&X3 или - элементарные конъюнкции. ФормулыилиX1&(X2X3) не являются элементарными конъюнкциями.
Дизъюнктивная нормальная форма (ДНФ) некоторой формулы – это эквивалентная данной формуле дизъюнкция элементарных конъюнкций.
Совершенная дизъюнктивная нормальная форма (СДНФ) некоторой формулы – это ее ДНФ, где в каждой элементарной конъюнкции содержатся все переменные данной формулы.
Основные действия при представлении заданной формулы в виде СДНФ следующие:
1) выразить заданную формулу, используя только операции дизъюнкции, конъюнкции и отрицания (как показано в подразделе 5.4);
2) используя законы де Моргана, свести все операции отрицания к отдельным переменным;
3) используя основные равносильности алгебры логики (в основном - закон дистрибутивности), получить ДНФ;
4) используя операцию развертывания (будет рассмотрена ниже), получить СДНФ.
Пример 5.4 – Построить СДНФ для следующей формулы:
(X1 X3) → ((X1 & X2) ↓ (X1 & ))
Решим задачу в порядке, указанном выше.
Представление формулы через операции дизъюнкции, конъюнкции и отрицания. Используем следующие формулы:
A → B = B
A ↓ B = &
Используя эти формулы, можно записать исходную формулу в следующем виде:
Как видно, в формуле используются только операции дизъюнкции, конъюнкции и отрицания.
Приведение операций отрицания к отдельным переменным. Используя закон де Моргана, полученную формулу можно записать в следующем виде:
Получение ДНФ. В данном случае первая часть формулы, , уже представляет собой элементарную конъюнкцию, что и требуется для ДНФ. Вторую часть формулы требуется преобразовать. Применяем закон дистрибутивности:
=
=
=
Учитывая, что ,, получим:
Учитывая, что A 0 = A, а также что A & B = B & A, можно записать:
Эта формула представляет собой ДНФ, т.е. дизъюнкцию элементарных конъюнкций. В данном случае имеются четыре элементарные конъюнкции: ,,,. Полученная формула – ДНФ, но не СДНФ, так как не во всех элементарных конъюнкциях содержатся все три переменные. В данном случае первая, третья и четвертая элементарные конъюнкции содержат только по две переменные, а вторая – только одну. В первой элементарной дизъюнкции не хватает переменнойX2, во второй – переменных X2 и X3, в третьей – X3, в четвертой – X5.
Получение СДНФ. Для этого применяется операция развертывания. Пусть в некоторой элементарной конъюнкции (обозначим ее как A) не хватает некоторой переменной B. Элементарная конъюнкция A заменяется на A & 1 (так как A & 1 = A). Затем, так как , записываем формулуA & 1 как . Далее применяем свойство дистрибутивности:. Таким образом, исходная элементарная конъюнкцияA заменяется на две элементарные конъюнкции, в одной из которых содержится недостающая переменная B, а в другой – ее отрицание. Эта операция выполняется со всеми элементарными конъюнкциями, пока все они не будут содержать все переменные, имеющиеся в формуле, т.е. пока не будет получена СДНФ.
Применим операцию развертывания к рассматриваемому примеру. Выполним развертывание первой элементарной конъюнкции, где не хватает переменной X2:
Выполним развертывание второй элементарной конъюнкции (). Здесь, где не хватает двух переменных -X2 и X3, поэтому операцию развертывания потребуется применить дважды:
=
=
=
=
Аналогично выполним развертывание третьей и четвертой элементарной конъюнкции:
Таким образом, все операции развертывания выполнены. Вместо ДНФ можно записать следующую формулу:
Учитывая, что A A = A, можно переписать эту формулу без повторяющихся элементарных конъюнкций:
Эта формула – СДНФ для выражения (X1X3) → ((X1 & X2)↓(X1 & )). Хотя СДНФ получилась длиннее, чем исходное выражение, но она имеет стандартный вид: состоит только из элементарных конъюнкций, причем каждая из них содержит все переменные формулы.
Примечание – Чтобы убедиться, что СДНФ построена правильно, можно составить таблицу истинности для исходной формулы и для СДНФ. Обе формулы при одинаковых значениях переменных (в данном случае – переменных X1, X2, X3) должны принимать одинаковые значения.
Элементарные конъюнкции, составляющие СДНФ, называются конституентами единицы. Каждая из них принимает значение 1 (истина) только при одном наборе переменных. Например, =1 только приX1=0, X2=1, X3=0 (так как только при этих значениях переменных = = 1&1&1=1). Таким образом, рассматриваемая в данном примере формула принимает значение, равное 1, при четырех наборах значений переменных. Эти наборы следующие: X1=0, X2=1, X3=0; X1=0, X2=0, X3=0; X1=0, X2=1, X3=1; X1=0, X2=0, X3=1. При остальных наборах значений переменных формула принимает значение 0.