матлогика_методичка. Методические указания к выполнению практических работ Омск Издательство Омгту 2009

• Название: Методические указания к выполнению практических работ Омск Издательство Омгту 2009
• Анкор: матлогика_методичка.doc
• Дата: 04.05.2017
• Размер: 0.58 Mb.
• Имя файла: матлогика_методичка.doc
• Тип: Методические указания; #7036
• страница: 3 из 14

1.3. Отыскание нормальных форм формул логики высказываний

Формулы алгебры высказываний могут быть приведены к нормальным формам: дизъюнктивной и конъюнктивной.

Конъюнктивным (дизъюнктивным) одночленом от переменных Х₁, Х₂,…,Х_n называется конъюнкция (дизъюнкция) этих переменных или их отрицаний. Дизъюнктивной (конъюнктивной) нормальной формой называется произвольная дизъюнкция (конъюнкция) конъюнктивных (дизъюнктивных) одночленов. Сокращенная запись: ДН-форма (или ДНФ) и КН-форма (или КНФ) соответственно. Одночлен от некоторых переменных называется совершенным, если каждая из этих переменных входит в него ровно один раз, со знаком отрицания или без него.

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

Например, (X₁X₂Х₃)(Х₁Х₃)Х₂ – дизъюнктивная (но не совершенная) нормальная форма от трех переменных Х₁, Х₂, Х₃, а (Х₁Х₂)(Х₁Х₂)(Х₁Х₂) – совершенная конъюнктивная нормальная форма от двух переменных Х₁ и Х₂.

Для того чтобы формулу равносильными преобразованиями привести к ДНФ, нужно руководствоваться следующим алгоритмом:

1. 
   избавиться от операции импликации и эквивалентности, выразив их через логические связки ,  и  по законам: XYXY, XY (XY)(YX);
   
2. 
   довести знаки отрицания до независимых переменных, используя законы де Моргана: (XY) XY, (XY)XY;
   
3. 
   применяя закон дистрибутивности (XY)Z(XZ)(YZ) , преобразовать формулу к дизъюнкции конъюнктивных одночленов;
   
4. 
   постоянно избавляться от двойных отрицаний: ХХ.
   

Пример 1.1.

Привести равносильными преобразованиями формулу (XZ)(XY) к дизъюнктивной нормальной форме.

Решение. Преобразуем формулу к ДНФ, руководствуясь приведенными правилами:

(ХZ)(XY) (XZ)(XY)X(Z(XY)) X((ZX)(ZY))( XZX)(XYZ) (XZ)(XYZ).

Пример 1.2.

Привести равносильными преобразованиями формулу примера 1.1 к конъюнктивной нормальной форме.

Решение. Формулу равносильными преобразованиями можно привести к КНФ, руководствуясь приведенными четырьмя правилами, с той лишь разницей, что в правиле 3) следует использовать другой (двойственный) закон дистрибутивности: (XY)Z(ХZ)(YZ).

Преобразуем данную формулу:

(ХZ)(XY)(XZ)(XY)(XZ)(XYZ)((XZ)X)

((XZ)Y)((XZ)Z)X((XY)(ZY))Z(X(XY))((ZY)Z)XZ.

Пример 1.3.

Применяя равносильные преобразования, найти СДНФ для формулы из примера 1.1

Решение. Чтобы привести формулу к СДНФ, нужно сначала равносильными преобразованиями привести ее к какой-нибудь ДНФ (см. пример 1.1). При этом нужно убрать члены дизъюнкции, содержащие переменную вместе с ее отрицанием, а из одинаковых членов дизъюнкции удалить все, кроме одного. Если какой-либо конъюнктивный одночлен в ДНФ содержит не все переменные из числа входящих в исходную формулу, то его умножают на единицы, представляемые в виде дизъюнкций X_iX_i каждой недостающей переменной X_iс ее отрицанием X_i (закон исключенного третьего). Затем раскрывают скобки внутри каждого такого конъюнктивного одночлена, применяя закон дистрибутивности конъюнкции относительно дизъюнкции. Наконец, если среди членов полученной дизъюнкции окажутся одинаковые конъюнктивные одночлены, то из каждой серии таковых следует оставить по одному.

Приведем данную формулу к СДНФ, начав преобразования с ДНФ, полученной при решении примера 1.1:

(ХZ)(XY)(XZ)(XYZ)((XZ)(YY))(XYZ) (XZY)(XZY)(XYZ) (XYZ)(XZY).

Пример 1.4.

Применяя равносильные преобразования, найти СКНФ для формулы из примера 1.2.

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

Приведем данную формулу к СКНФ, начав преобразование с КНФ, полученной при решении примера 1.2:

(ХZ)(XY)XZ(X(YY))(Z(XX))(XY)(XY)

(XZ)(XZ)(XY(ZZ))(XY(ZZ))(XZ(YY))

(XZ(YY))(XYZ)(XYZ)(XYZ)(XYZ) (XYZ)(XYZ)(XYZ)(XYZ) (XYZ)(XYZ)(XYZ)(XYZ)(XYZ)(XYZ).