Автор Тема: Лекция 5. Нормальные формы формул логики высказываний  (Прочитано 1982 раз)

0 Пользователей и 1 Гость просматривают эту тему.

Онлайн Admin

  • Администратор
  • Сообщений: 5046
  • Поблагодарили: 1576 раз(а)
    • Просмотр профиля
Лекция 5. Нормальные формы формул логики высказываний


В элементарной алгебре рассматриваются тождества (например, правила сокращённого умножения, законы ассоциативности, коммутативности и дистрибутивности операций над числами). Эти тождества позволяют приводить одну и ту же формулу к различным видам. Однако нет стандартного вида, к которому можно привести любую формулу школьной алгебры. В алгебре высказываний ситуация иная. Во-первых, всякую формулу можно выразить через три логические связки - конъюнкцию, дизъюнкцию и отрицание, причём отрицание относится только к пропозициональным переменным. Для этого нужно выразить экиваленцию, импликацию и строгую дизъюнкцию через конъюнкцию, дизъюнкцию и отрицание, а затем воспользоваться законами де Моргана и законом двойного отрицания. Но такие представления формул алгебры высказываний неоднозначны: одну и ту же формулу можно выразить через эти  связки многими способами. Во-вторых, мы докажем, что каждая формула в алгебре высказываний (если она не является противоречием) может быть представлена в совершенной дизъюнктивной нормальной форме. Это особая, стандартная запись формулы, использующая конъюнкцию, дизъюнкцию и отрицание. Всякая формула алгебры высказываний, не являющаяся тавтологией, может быть представлена в другом стандартном виде - совершенной конъюнктивной нормальной форме (тут также используются лишь три упомянутые выше логические операции). Важно, что формулы могут быть представлены в совершенных нормальных формах однозначно. Итак, в отличие от элементарной алгебры, логика высказываний позволяет представить формулы в двух стандартных формулах. Этот замечательный факт используется при решении многих задач.

***

Пусть \(  \large P_1,P_2, \ldots , P_n  \) - некоторые пропозициональные переменные.

Определение 5.1. Элементарной конъюнкцией от переменных \(  \large P_1,P_2, \ldots , P_n  \) называется конъюнкция этих переменных или их отрицаний.

Определение 5.2. Элементарной дизъюнкцией от переменных \(  \large P_1,P_2, \ldots , P_n  \) называется дизъюнкция этих переменных или их отрицаний.

Замечание 5.1. Элементарные конъюнкция и дизъюнкция могут состоять из одной пропозициональной переменной или её отрицания.

Пример 5.1. Следующие формулы логики высказываний являются элементарными конъюнкциями:

\(  \large P_1P_2'P_3,  \ P_1P_2P_3P_4,  \ P_1'P_2'P_3'P_4', \  P'QR,  \ Q  \).

Представленные ниже формулы есть элементарные дизъюнкции:

\(  \large P_1', \ P' \vee Q' \vee R' , \ P_1 \vee P_2 \vee P_3, \ P_1' \vee P_2' \vee P_3  \).

Замечание 5.2. В определениях 5.1 и 5.2 союз "или" употребляется в соединительном смысле: в элементарную конъюнкцию (дизъюнкцию) может одновременно входить и переменная, и её отрицание. Если в элементарную конъюнкцию (дизъюнкцию) входит и переменная, и её отрицание, то вся конъюнкция (дизъюнкция) обращается в нуль (единицу). Рассмотрим некоторую элементарную конъюнкцию от переменных \(  \large P_1,P_2, \ldots, P_n  \). Пусть, например, она имеет вид

\(  \large P_1 \cdot P_1' \cdot F(P_2, P_3, \ldots , P_n)  \).

Тогда, учитывая закон противоречия и равносильность \(  \large P \cdot 0 \simeq  0 \), получим:

\(  \large P_1 \cdot P_1' \cdot F(P_2, P_3, \ldots , P_n) \simeq 0 \cdot F(P_2,P_3, \ldots , P_n) \simeq 0   \).

Аналогично:

\(  \large P_1 \vee P_1' \vee F(P_2, P_3, \ldots , P_n) \simeq 1 \vee F(P_2,P_3, \ldots , P_n) \simeq 1  \).

Использовали закон исключённого третьего и равносильность \(  \large P \vee 1 \simeq 1  \).
 
Сказали спасибо: Alexey, freeman

Онлайн Admin

  • Администратор
  • Сообщений: 5046
  • Поблагодарили: 1576 раз(а)
    • Просмотр профиля
Определение 5.3. Дизъюнктивной нормальной формой (ДНФ) называется дизъюнкция элементарных конъюнкций.

Определение 5.4. Конъюнктивной нормальной формой (КНФ) называется конъюнкция элементарных дизъюнкций.

Замечание 5.3. ДНФ (КНФ) может состоять из одной-единственной элементарной конъюнкции (дизъюнкции).

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

1) \(  \large P \vee (QR) \vee (P'R) \vee Q  \);

2) \(  \large (P_1P_2') \vee (P_2P_3') \vee (P_1'P_2'P_3)  \);

3) \(  \large (PR) \vee (PQ) \vee (R'Q')  \);

4) \(  \large P_1P_2P_3'P_4'P_5  \).

Задача 5.1. Представить формулу

\(  \large (P \vee Q') \to (R' \vee Q)  \)

в дизъюнктивной нормальной форме.

Решение. Сначала избавимся от импликации:

\(  \large (P \vee Q') \to (R' \vee Q) \simeq (P \vee Q')' \vee R' \vee Q  \).

Далее воспользуемся одним из законов де Моргана:

\(  \large (P \vee Q')' \vee R' \vee Q \simeq (P' Q'') \vee R' \vee Q  \).

Осталось воспользоваться законом двойного отрицания:
.
\(  \large (P' Q'') \vee R' \vee Q \simeq (P' Q) \vee R' \vee Q  \).

Итак, получили дизъюнкцию элементарных конъюнкций. Значит, данная формула есть ДНФ исходной формулы.

Замечание 5.4. Представление формулы логики высказываний в ДНФ неоднозначно. Рассмотрим, например, формулу из предыдущей задачи. Было показано, что

\(  \large (P \vee Q') \to (R' \vee Q) \simeq (P'Q) \vee R' \vee Q  \).

Преобразуем полученную дизъюнктивную нормальную форму равносильным образом. Сначала используем равносильность \(  \large P \simeq P \cdot 1  \). Имеем:

\(  \large (P'Q) \vee R' \vee Q \simeq (P'Q) \vee R' \vee (Q \cdot 1)  \).

Теперь используем закон исключённого третьего:

\(  \large (P'Q) \vee R' \vee (Q \cdot 1) \simeq (P'Q) \vee R' \vee (Q \cdot ( R \vee R'))  \).

Наконец, используем дистрибутивный закон:

\(  \large (P'Q) \vee R' \vee (Q \cdot ( R \vee R'))  \simeq (P'Q) \vee R' \vee (Q  R) \vee (QR')   \).

Последняя формула также является дизъюнктивной нормальной формой формулы

\(  \large (P \vee Q') \to (R' \vee Q)   \).

Применим один из законов поглощения:

\(  \large (P'Q) \vee (Q  R) \vee R' \vee  (R'Q) \simeq (P'Q) \vee (Q  R) \vee R'   \).

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

\(  \large (P \vee Q') \to (R' \vee Q)  \).

Замечание 5.5. Поскольку ДНФ может включать в себя лишь отрицание, конъюнкцию и дизъюнкцию, то для приведения произвольной формулы логики высказываний к ДНФ обычно нужно выполнить следующие действия:

1) избавиться от строгой дизъюнкции, импликации и эквиваленции, выразив их через отрицание, конъюнкцию и дизъюнкцию;

2) довести знаки отрицания до пропозициональных переменных, используя законы де Моргана;

3) избавиться от двойных отрицаний, используя соответствующий закон логики высказываний;

4) преобразовать формулу к дизъюнкции элементарных конъюнкций, используя дистрибутивные законы.
 
Сказали спасибо: Alexey

Онлайн Admin

  • Администратор
  • Сообщений: 5046
  • Поблагодарили: 1576 раз(а)
    • Просмотр профиля
Пример 5.3. Формулы классической логики высказываний, которые перечислены ниже, представлены в конъюнктивной нормальной форме:

1) \(  \large P'(P' \vee Q \vee R)  \);

2) \(  \large (P \vee R) (P' \vee Q' \vee R)  \);

3) \(  \large (P \vee Q \vee R) (P' \vee Q \vee R')  \);

4) \(  \large P_1 \vee P_2' \vee P_3  \);

5) \(  \large (P_1 \vee P_2 \vee P_3) (P_1 \vee P_2')(P_2' \vee P_3)  \).\(  \large   \)

Задача 5.2. Привести формулу

\(  \large (P_1 \vee P_3)' (P_1 \to P_2)  \)

к конъюнктивной нормальной форме.

Решение. Сначала используем один из законов де Моргана:

\(  \large (P_1 \vee P_3)' (P_1 \to P_2) \simeq (P_1'P_3')(P_1 \to P_2)  \).

Теперь избавимся от импликации:

\(  \large (P_1'P_3')(P_1 \to P_2) \simeq (P_1'P_3')(P_1' \vee P_2)  \).

Воспользуемся одним из законов поглощения:

\(  \large P_3'(P_1' (P_1' \vee P_2))  \simeq P_3' P_1'  \).

Это и есть КНФ.

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

\(  \large P_3'P_1' (P_1' \vee P_2)  \).

Это конъюнктивная нормальная форма. После применения закона поглощения также получаем конъюнктивную нормальную форму, состоящую из двух элементарных дизъюнкций (отрицаний пропозициональных переменных \(  \large P_1  \) и \(  \large P_3  \)).

Замечание 5.7. Так как КНФ может включать из логических связок только конъюнкцию, дизъюнкцию и отрицание, то алгоритм приведения произвольной формулы к конъюнктивной нормальной форме аналогичен соответствующему алгоритму для дизъюнктивной нормальной формы:

1) выразить строгую дизъюнкцию, импликацию и эквиваленцию через другие операции классической логики высказываний;

2) применяя законы де Моргана, сделать так, чтобы отрицание относилось лишь к пропозициональным переменным;

3) исключить двойные отрицания, используя закон двойного отрицания;

4) преобразовать формулу логики высказываний к конъюнкции элементарных дизъюнкций, применяя один из законов дистрибутивности.
 
Сказали спасибо: Alexey

Онлайн Admin

  • Администратор
  • Сообщений: 5046
  • Поблагодарили: 1576 раз(а)
    • Просмотр профиля
Определение 5.5. Дизъюнктивная нормальная форма от переменных \(  \large P_1,P_2, \ldots , P_n  \) называется совершенной от этих переменных, если:

1) все элементарные конъюнкции различны;

2) любая элементарная конъюнкция содержит все эти переменные;

3) никакая элементарная конъюнкция не содержит двух одинаковых переменных;

4) никакая элементарная конъюнкция не содержит переменную вместе с её отрицанием.

Замечание 5.8. Далее часто будем использовать следующее сокращение: СДНФ (совершенная дизъюнктивная нормальная форма).

Пример 5.4. Перечисленные ниже формулы логики высказываний являются СДНФ от переменных \(  \large P,Q,R  \):

1) \(  \large (PQR) \vee (P' QR) \vee (P'Q'R')  \);

2) \(  \large (P'QR') \vee (PQ'R)  \);

3) \(  \large PQR'  \).

Пример 5.5. Следующие формулы не являются СДНФ от переменных \(  \large P_1,P_2,P_3,P_4  \):

1) \(  \large (P_1P_2P_3P_4') \vee (P_1'P_2P_3'P_4) \vee (P_1'P_2P_3' P_4)  \);

2) \(  \large (P_1P_2'P_3) \vee (P_1' P_2 P_3 P_4) \vee (P_1'P_2' P_3' P_4)  \);

3) \(  \large (P_1P_1P_2 P_3P_4) \vee (P_1'P_2P_3 P_4') \vee (P_1'P_2'P_3 P_4)  \);

4) \(  \large (P_1P_1'P_2P_3P_4) \vee (P_1P_2' P_3' P_4) \vee (P_1'P_2P_3' P_4)  \).

Первая формула не является СДНФ, поскольку она содержит две одинаковые  элементарные конъюнкции \(  \large P_1'P_2P_3' P_4  \). Вторая формула включает в себя элементарную конъюнкцию \(  \large P_1P_2'P_3  \), где отсутствует переменная \(  \large P_4  \). Третья формула содержит элементарную конъюнкцию \(  \large P_1P_1P_2P_3P_4  \), где переменная \(  \large P_1  \) встречается дважды. Наконец, четвёртая формула содержит элементарную конъюнкцию \(  \large P_1P_1'P_2P_3P_4  \), где встречается переменная \(  \large P_1  \) и её отрицание.

Определение 5.6. Конъюнктивная нормальная форма от переменных \(  \large P_1,P_2, \ldots , P_n  \) называется совершенной от этих переменных, если:

1) все элементарные дизъюнкции различны;

2) всякая элементарная дизъюнкция содержит все эти переменные;

3) никакая элементарная дизъюнкция не включает в себя двух одинаковых переменных;

4) никакая элементарная дизъюнкция не содержит одновременно и переменную, и её отрицание.

Замечание 5.9. Как и в случае с совершенной дизъюнктивной нормальной формой, применительно к совершенной конъюнктивной нормальной форме будем использовать сокращение, состоящее из четырёх букв, - СКНФ.

Пример 5.6. Данные формулы логики высказываний являются СКНФ от переменных \(  \large P_1,P_2,P_3  \):

1) \(  \large (P_1 \vee P_2 \vee P_3')(P_1 \vee P_2' \vee P_3)(P_1' \vee P_2' \vee P_3)  \);

2) \(  \large (P_1 \vee P_2 \vee P_3)(P_1' \vee P_2' \vee P_3')  \);

3) \(  \large P_1 \vee P_2 \vee P_3'  \).

Пример 5.7. Представленные ниже формулы не являются СКНФ от переменных \(  \large P,Q,R  \):

1) \(  \large (P \vee Q \vee R)(P' \vee Q' \vee R)(P \vee Q \vee R)  \);

2) \(  \large (P \vee Q' \vee R)(Q \vee R')(P' \vee Q \vee R)  \);

3) \(  \large (P \vee Q \vee R')(P \vee Q \vee R \vee R) (P' \vee Q' \vee R)  \);

4) \(  \large (P' \vee P \vee Q \vee R)(P \vee Q' \vee R')  \).

Первая формула не является совершенной конъюнктивной нормальной формой, так как включает в себя две одинаковые элементарные дизъюнкции \(  \large P \vee Q \vee R  \). Вторая формула имеет в своём составе элементарную дизъюнкцию \(  \large Q \vee R'  \), где отсутствует пропозициональная переменная \(  \large P  \). Третья формула содержит элементарную дизъюнкцию \(  \large P \vee Q \vee R \vee R  \), где переменная \(  \large R  \) встречается два раза. Четвёртая включает в себя элементарную дизъюнкцию \(  \large P' \vee P \vee Q \vee R  \), где одна из переменных встречается вместе с её отрицанием.
 
Сказали спасибо: Mysterious Light, Alexey, freeman

Онлайн Admin

  • Администратор
  • Сообщений: 5046
  • Поблагодарили: 1576 раз(а)
    • Просмотр профиля
Докажем теорему существования для совершенной дизъюнктивной нормальной формы. Что значит "доказать теорему существования"? Это значит, доказать, что тот или иной объект найдётся хотя бы в одном экземпляре. В данном случае мы докажем, что для любой выполнимой формулы логики высказываний найдётся СДНФ. Для этого нам понадобится вспомогательная теорема о дизъюнктивном разложении формулы по всем переменным, которая доказывается с помощью метода математической индукции.

***

Теорема 5.1. Для каждой формулы логики высказываний от переменных \(  \large P_1,P_2, \ldots , P_n  \) справедливо следующее дизъюнктивное разложение по всем переменным:

\(  \large F(P_1,P_2, \ldots , P_n) \simeq    \)

\(  \large \simeq (P_1' \wedge P_2' \wedge \ldots \wedge P_n' \wedge  F(0,0, \ldots , 0)) \vee  \)

\(  \large  \vee  (P_1' \wedge P_2' \wedge \ldots \wedge P_n \wedge F(0,0, \ldots , 1)) \vee \ldots  \)

\(  \large \ldots \vee  (P_1 \wedge P_2 \wedge \ldots \wedge P_n \wedge F(1,1, \ldots , 1))   \).

Доказательство. Данная теорема доказывается индукцией по числу пропозициональных переменных, участвующих в разложении.

1) Пусть \(  \large k=1  \). Докажем, что

\(  \large F(P_1,P_2, \ldots , P_n) \simeq (P_1' \wedge F(0,P_2, \ldots , P_n)) \vee (P_1 \wedge F(1,P_2, \ldots , P_n))  \).

Положим \(  \large P_1=0  \). Тогда имеем:

\(  \large F(0,P_2, \ldots , P_n) \simeq   \)

\(  \large \simeq (0' \wedge F(0,P_2, \ldots , P_n)) \vee (0 \wedge F(1,P_2, \ldots , P_n))   \)

\(  \large \simeq (1 \wedge F(0,P_2, \ldots , P_n)) \vee (0 \wedge F(1,P_2, \ldots , P_n))   \)

\(  \large  \simeq F(0, P_2 , \ldots , P_n) \vee 0 \simeq F(0, P_2, \ldots , P_n)  \).

Здесь последовательно использовали определение отрицания, равносильности \(  \large P \wedge 1 \simeq P   \), \(  \large P \wedge 0 \simeq 0  \) и \(  \large P \vee 0 \simeq P  \).

Теперь положим \(  \large P_1 =1  \). В этом случае имеем:

\(  \large F(1,P_2, \ldots , P_n) \simeq    \)

\(  \large \simeq  (1' \wedge F(0,P_2, \ldots , P_n)) \vee (1 \wedge F(1,P_2, \ldots , P_n)) \simeq    \)

\(  \large \simeq (0 \wedge F(0,P_2, \ldots , P_n)) \vee (1 \wedge F(1,P_2, \ldots , P_n)  \simeq  \)

\(  \large \simeq 0 \vee F(1,P_2, \ldots, P_n) \simeq F(1, P_2, \ldots , P_n)
  \).

Здесь снова использовали определение отрицания и те же самые равносильности.

База индукции доказана.

2) Предположим, что при \(  \large n=k  \) выполняется равносильность

\(  \large F(P_1,P_2, \ldots , P_k) \simeq    \)

\(  \large \simeq (P_1' \wedge P_2' \wedge \ldots \wedge P_k' \wedge  F(0,0, \ldots , 0)) \vee  \)

\(  \large  \vee  (P_1' \wedge P_2' \wedge \ldots \wedge P_k \wedge F(0,0, \ldots , 1)) \vee \ldots  \)

\(  \large \ldots \vee  (P_1 \wedge P_2 \wedge \ldots \wedge P_k \wedge F(1,1, \ldots , 1))   \).

3) Пусть \(  \large n=k+1  \). Докажем, что

\(  \large F(P_1,P_2, \ldots , P_k, P_{k+1}) \simeq    \)

\(  \large \simeq (P_1' \wedge P_2' \wedge \ldots \wedge P_k' \wedge P_{k+1}' \wedge   F(0,0, \ldots ,0, 0)) \vee  \)

\(  \large  \vee  (P_1' \wedge P_2' \wedge \ldots \wedge P_k' \wedge P_{k+1} \wedge F(0,0, \ldots ,0, 1)) \vee \ldots  \)

\(  \large \ldots \vee  (P_1 \wedge P_2 \wedge \ldots \wedge P_k \wedge P_{k+1} \wedge  F(1,1, \ldots , 1,1))   \).

Разложим формулу \(  \large F(P_1,P_2, \ldots , P_k, P_{k+1})  \) по переменной \(  \large P_{k+1}  \). Это возможно, согласно пункту 1 (база индукции). Имеем:

\(  \large F(P_1,P_2, \ldots, P_k, P_{k+1}) \simeq (P_{k+1}' \wedge F(P_1,P_2, \ldots , P_k,0)) \vee (P_{k+1} \wedge F(P_1,P_2, \ldots , P_k,1))  \).

Учитывая пункт 2 (предположение индукции), получим, во-первых,

\(  \large F(P_1, P_2, \ldots , P_k,0) \simeq   \)

\(  \large \simeq (P_1' \wedge P_2' \wedge \ldots \wedge P_k' \wedge  F(\underbrace{0,0, \ldots ,0, 0}_{k+1 \ раз})) \vee  \)

\(  \large  \vee  (P_1' \wedge P_2' \wedge \ldots \wedge P_k \wedge F(\underbrace{0,0, \ldots , 1,0}_{k+1 \ раз})) \vee \ldots  \)

\(  \large \ldots \vee  (P_1 \wedge P_2 \wedge \ldots \wedge P_k \wedge F(\underbrace{1,1, \ldots , 1,0}_{k+1 \ раз}))   \),

а во-вторых,

\(  \large F(P_1, P_2, \ldots , P_k,1) \simeq   \)

\(  \large \simeq (P_1' \wedge P_2' \wedge \ldots \wedge P_k' \wedge  F(\underbrace{0,0, \ldots ,0, 1}_{k+1 \ раз})) \vee  \)

\(  \large  \vee  (P_1' \wedge P_2' \wedge \ldots \wedge P_k \wedge F(\underbrace{0,0, \ldots , 1,1}_{k+1 \ раз})) \vee \ldots  \)

\(  \large \ldots \vee  (P_1 \wedge P_2 \wedge \ldots \wedge P_k \wedge F(\underbrace{1,1, \ldots , 1,1}_{k+1 \ раз}))   \).

Следовательно,

\(  \large F(P_1,P_2, \ldots , P_{k+1}) \simeq    \)

\(  \large \simeq (P_1' \wedge P_2' \wedge \ldots \wedge P_{k+1}' \wedge  F(0,0, \ldots , 0)) \vee  \)

\(  \large  \vee  (P_1' \wedge P_2' \wedge \ldots \wedge P_{k+1} \wedge F(0,0, \ldots , 1)) \vee \ldots  \)

\(  \large \ldots \vee  (P_1 \wedge P_2 \wedge \ldots \wedge P_{k+1} \wedge F(1,1, \ldots , 1))   \).

Итак, делаем вывод, что разложение справедливо для любого натурального числа \(  \large n  \). На этом теорема доказана.
 

Онлайн Admin

  • Администратор
  • Сообщений: 5046
  • Поблагодарили: 1576 раз(а)
    • Просмотр профиля
Замечание 5.10. Запись

\(  \large \underset{F(\alpha_1, \alpha_2 , \ldots , \alpha_n)=1}{ \vee } \ ( P_1^{\alpha_1} \wedge P_2^{\alpha_2} \wedge \ldots \wedge P_n^{\alpha_n})  \)

обозначает дизъюнкцию всех конъюнкций

\(  \large  P_1^{\alpha_1} \wedge P_2^{\alpha_2} \wedge \ldots \wedge P_n^{\alpha_n}  \),

где \(  \large P_i^{\alpha_i}=P_i  \), если \(  \large \alpha_i=1  \), \(  \large P_i^{\alpha_i}=P_i'  \), если \(  \large \alpha_i=0  \), когда индексы дизъюнктирования пробегают все наборы \(  \large (\alpha_1, \alpha_2, \ldots, \alpha_n)  \), на которых формула \(  \large F(P_1,P_2, \ldots , P_n)  \) принимает значение "истина".

***

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

***

Теорема 5.2. Любую выполнимую формулу логики высказываний от переменных \(  \large P_1,P_2, \ldots, P_n  \) можно представить в совершенной дизъюнктивной нормальной форме:

\(  \large F(P_1,P_2, \ldots , P_n) \simeq \underset{F(\alpha_1, \alpha_2 , \ldots , \alpha_n)=1}{ \vee } \ ( P_1^{\alpha_1} \wedge P_2^{\alpha_2} \wedge \ldots \wedge P_n^{\alpha_n})  \).

Доказательство. Согласно теореме 5.1, любую формулу, зависящую от пропозициональных переменных \(  \large P_1, P_2, \ldots , P_n  \), можно представить в виде дизъюнктивного разложения по всем переменным:

\(  \large F(P_1,P_2, \ldots , P_n) \simeq    \)

\(  \large \simeq (P_1' \wedge P_2' \wedge \ldots \wedge P_n' \wedge  F(0,0, \ldots , 0)) \vee  \)

\(  \large  \vee  (P_1' \wedge P_2' \wedge \ldots \wedge P_n \wedge F(0,0, \ldots , 1)) \vee \ldots  \)

\(  \large \ldots \vee  (P_1 \wedge P_2 \wedge \ldots \wedge P_n \wedge F(1,1, \ldots , 1))   \).

Если формула \(  \large F(P_1,P_2, \cdots , P_n)  \) является тождественно ложной, то, согласно определению,

\(  \large F(0,0, \cdots, 0) = F(0,0, \cdots, 1) = \ldots = F(1,1, \cdots , 1)=0  \).

Значит, учитывая, что \(  \large P \wedge 0 \simeq 0  \),

дизъюнктивное разложение этой формулы тривиально:

\(  \large F(P_1,P_2, \ldots , P_n) \simeq 0 \vee 0 \vee \ldots \vee 0  \).

Следовательно, тождественно ложная формула не имеет СДНФ.

Пусть \(  \large F(P_1,P_2, \ldots, P_n)  \) - выполнимая формула логики высказываний. Если

\(  \large F(\alpha_1, \alpha _2, \ldots, \alpha_n)=0  \),


то соответствующий член дизъюнкции равен нулю, поскольку \(  \large P \wedge 0 \simeq 0  \). Значит, его можно опустить, так как \(  \large P \vee 0 \simeq P  \). Итак, в разложении остаются лишь те элементарные конъюнкции, что соответствуют тем наборам \(  \large (\alpha_1, \alpha_2, \ldots, \alpha_n)  \), где

\(  \large F(\alpha_1, \alpha _2, \ldots, \alpha_n)=1  \).


Покажем, что мы получили СДНФ. Согласно условию теоремы, все элементарные конъюнкции, входящие в разложение, имеют вид

\(  \large P_1^{\alpha_1} \wedge P_2^{\alpha_2} \wedge \ldots \wedge P_n^{\alpha_n}  \).

Поскольку либо \(  \large \alpha_i=0  \), либо \(  \large \alpha_i=1  \), то в состав конъюнкции входит либо \(  \large P_i'  \), либо \(  \large P_i  \) (\(  \large i=1,2, \ldots, n  \)). Значит, все эти конъюнкции различны. Очевидно, что каждая из них содержит все пропозициональные переменные, никакая из них не содержит двух одинаковых переменных и переменную вместе с её отрицанием. Итак, имеем совершенную дизъюнктивную нормальную форму.

Теорема доказана.
 

Онлайн Admin

  • Администратор
  • Сообщений: 5046
  • Поблагодарили: 1576 раз(а)
    • Просмотр профиля
Итак, мы доказали, что всякая формула, не являющаяся тождественно ложной, может быть представлена в СДНФ. Но возможно ли, что у одной и той же формулы будет два различных представления в СДНФ? Оказывается, нет. Представление в совершенной дизъюнктивной нормальной форме не только существует, но и единственно. Этот важный факт доказывается в следующей теореме. Такие теоремы называются теоремами единственности (всё просто: там доказывается, что некоторый объект существует только в одном экземпляре).

***

Теорема 5.3. Представление формулы логики высказываний в совершенной дизъюнктивной нормальной форме единственно.

Доказательство. Пусть \(  \large F  \) - формула, зависящая от переменных \(  \large P_1,P_2, \ldots, P_n  \), и пусть \(  \large K_1,K_2, \ldots, K_q  \), \(  \large L_1, L_2, \ldots, L_s  \) - элементарные конъюнкции от тех же переменных.  Предположим, что формула \(  \large F  \) имеет два представления в СДНФ:

\(  \large F(P_1,P_2, \ldots, P_n) \simeq K_1 \vee K_2 \vee \ldots \vee K_q  \),

\(  \large F(P_1,P_2, \ldots, P_n) \simeq L_1 \vee L_2 \vee \ldots \vee L_s  \).

Тогда, поскольку это представления одной и той же формулы логики высказываний, имеет место равносильность

\(  \large K_1 \vee K_2 \vee \ldots \vee K_q \simeq L_1 \vee L_2 \vee \ldots \vee L_s  \).

Пусть

\(  \large K_1 \equiv P_1^{\alpha_1} \wedge P_2^{\alpha_1} \wedge \ldots \wedge P_n^{\alpha_n}  \).

Положим \(  \large P_i=\alpha_i, \ i=1,2, \ldots, n  \). Покажем, что в данном случае вся конъюнкция \(  \large K_1  \) обращается в единицу. Во-первых, очевидно, что

\(  \large K_1 = \alpha_1^{\alpha_1} \wedge \alpha_2^{\alpha_1} \wedge \ldots \wedge \alpha_n^{\alpha_n}  \).

Во-вторых, если \(  \large \alpha_i=1  \), то \(  \large \alpha_i^{\alpha_i}=\alpha_i=1  \), если \(  \large \alpha_i=0  \), то \(  \large \alpha_i^{\alpha_i}=\overline{\alpha_i}=\overline{0}=1  \).

Итак,

\(  \large K_1 =1 \wedge 1 \wedge \ldots \wedge 1=1  \).

Значит, при \(  \large P_i=\alpha_i, \ i=1,2, \ldots, n  \)

\(  \large L_1 \vee L_2 \vee \ldots \vee L_s=1  \),

так как \(  \large 1 \vee K_2 \vee \ldots \vee K_q=1  \).

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

\(  \large L_1=P_1^{\beta_1} \wedge P_2^{\beta_2} \wedge \ldots \wedge P_n^{\beta_n} =1 \).

Следовательно, так как \(  \large P_i=\alpha_i  \),

\(  \large \alpha_1^{\beta_1} \wedge \alpha_2^{\beta_2} \wedge \ldots \wedge \alpha_n^{\beta_n} =1  \).

Тогда

\(  \large \alpha_1^{\beta_1}= \alpha_2^{\beta_2} = \ldots = \alpha_n^{\beta_n} =1  \).

А это возможно лишь в одном случае:

\(  \large \alpha_1=\beta_1, \ \alpha_2 = \beta_2, \ \ldots \ , \alpha_n=\beta_n  \).

Значит,

\(  \large L_1=K_1  \).

Мы доказали, что элементарная конъюнкция \(  \large K_1  \) встречается среди элементарных конъюнкций \(  \large L_1, L_2, \ldots, L_s  \). Точно так же можно доказать, что всякую элементарную конъюнкцию \(  \large K_1,K_2, \ldots, K_q  \) можно встретить среди элементарных конъюнкций \(  \large L_1, L_2, \ldots, L_s  \), и наоборот. Следовательно, \(  \large q=s  \), значит, разложения \(  \large K_1 \vee K_2 \vee \ldots \vee K_q  \) и \(  \large L_1 \vee  L_2 \vee \ldots \vee L_s  \) совпадают, учитывая коммутативность дизъюнкции (совпадают с точностью до перестановки членов дизъюнкции).

Теорема доказана.

Замечание 5.11. Из доказательства теоремы существования совершенной дизъюнктивной нормальной формы вытекает алгоритм отыскания этой формы с помощью истинностной таблицы:

1) выбрать все те наборы значений пропозициональных переменных, на которых формула принимает значение "истина";

2) для каждого такого набора выписать элементарную конъюнкцию, которая принимает значение "истина" на этой наборе и только на нём;

3) полученные элементарные конъюнкции соединить знаками дизъюнкции.

Замечание 5.12. Очевидно, СДНФ формулы логики высказываний можно найти и без таблицы истинности - для этого можно воспользоваться равносильными преобразованиями и определением СДНФ. Примерная последовательность действий в данном случае такова:

1) привести формулу к ДНФ;

2) убрать члены дизъюнкции, которые содержат пропозициональную переменную вместе с её отрицанием (используется закон противоречия и правило \(  \large P \vee 0 \simeq P  \));

3) из одинаковых членов дизъюнкции удалить все, кроме одного (используется идемпотентность дизъюнкции);

4) в каждой элементарной конъюнкции, которая содержит не все пропозициональные переменные, добавить логическую единицу (применяется закон исключённого третьего и правило \(  \large P \cdot 1 \simeq P  \));

5) раскрыть скобки внутри каждой такой элементарной конъюнкции, используя соответствующий дистрибутивный закон;

6) убрать одинаковые члены дизъюнкции, если таковые появятся (снова применяется идемпотентность данной пропозициональной связки).
 

Онлайн Admin

  • Администратор
  • Сообщений: 5046
  • Поблагодарили: 1576 раз(а)
    • Просмотр профиля
Докажем теорему существования СКНФ для опровержимой формулы логики высказываний, а затем теорему единственности. Как и в случае с СДНФ, для доказательства теоремы существования понадобится вспомогательная теорема и введение некоторых обозначений. Доказательства всех этих теорем аналогичны доказательству теорем о СДНФ.

***

Теорема 5.4. Для каждой формулы логики высказываний от \(  \large n  \) переменных справедливо следующее конъюнктивное разложение по всем переменным:

\(  \large F(P_1,P_2, \ldots , P_n) \simeq  \)

\(  \large \simeq (P_1 \vee P_2 \vee \ldots \vee P_n \vee F(0,0, \ldots , 0)) \wedge  \)

\(  \large  \wedge (P_1 \vee P_2 \vee \cdots \vee P_n' \vee F(0,0, \ldots , 1)) \wedge \ldots  \)

\(  \large \ldots \wedge (P_1' \vee P_2' \vee \ldots \vee P_n' \vee F(1,1, \ldots , 1))  \).

Доказательство. Снова используем метод математической индукции (по числу переменных, участвующих в разложении).

1) Пусть \(  \large k=1  \). Нужно доказать, что

\(  \large F(P_1,P_2, \ldots , P_n) \simeq (P_1 \vee F(0, P_2, \ldots , P_n)) \wedge (P_1' \vee F(1,P_2, \ldots , P_n))  \).

При \(  \large P_1=0  \) имеем:

\(  \large F(0,P_2, \ldots , P_n) \simeq (0 \vee F(0, P_2, \ldots , P_n)) \wedge (0' \vee F(1,P_2, \ldots , P_n))  \).

Используем равносильность \(  \large P \vee 0 \simeq P  \) и определение отрицания. Получим:

\(  \large (0 \vee F(0, P_2, \ldots , P_n)) \wedge (0' \vee F(1,P_2, \ldots , P_n)) \simeq  \)

\(  \large \simeq F(0, P_2, \ldots , P_n) \wedge (1 \vee F(1,P_2, \ldots , P_n))  \).

Поскольку \(  \large P \vee 1 \simeq 1  \), \(  \large P \wedge 1 \simeq P  \), то

\(  \large F(0, P_2, \ldots , P_n) \wedge (1 \vee F(1,P_2, \ldots , P_n)) \simeq F(0, P_2, \ldots , P_n) \wedge 1 \simeq F(0, P_2, \ldots , P_n)   \).

При \(  \large P_1=1  \) получим:

\(  \large F(1,P_2, \ldots , P_n) \simeq (1 \vee F(0, P_2, \ldots , P_n)) \wedge (1' \vee F(1,P_2, \ldots , P_n))  \).

Используя равносильности \(  \large P \vee 1 \simeq 1  \), \(  \large P \vee 0 \simeq P  \), \(  \large P \wedge 1 \simeq P  \), а также определение отрицания, имеем:

\(  \large (1 \vee F(0, P_2, \ldots , P_n)) \wedge (1' \vee F(1,P_2, \ldots , P_n))  \simeq   \)

\(  \large \simeq 1 \wedge (0 \vee F(1,P_2, \ldots , P_n)) \simeq   \)

\(  \large \simeq 1 \wedge F(1,P_2, \ldots , P_n) \simeq   \)

\(  \large \simeq F(1,P_2, \ldots , P_n)  \).

Тем самым мы доказали базу индукции. Переходим к предположению индукции.

2) Предположим, что при \(  \large n=k  \) справедливо разложение

\(  \large F(P_1,P_2, \ldots , P_k) \simeq  \)

\(  \large \simeq (P_1 \vee P_2 \vee \ldots \vee P_k \vee F(0,0, \ldots , 0)) \wedge  \)

\(  \large  \wedge (P_1 \vee P_2 \vee \cdots \vee P_k' \vee F(0,0, \ldots , 1)) \wedge \ldots  \)

\(  \large \ldots \wedge (P_1' \vee P_2' \vee \ldots \vee P_k' \vee F(1,1, \ldots , 1))  \).

3) Докажем, что при \(  \large n=k+1  \) выполняется равносильность

\(  \large F(P_1,P_2, \ldots , P_k, P_{k+1}) \simeq  \)

\(  \large \simeq (P_1 \vee P_2 \vee \ldots \vee P_k \vee P_{k+1} \vee F(0,0, \ldots , 0,0)) \wedge  \)

\(  \large  \wedge (P_1 \vee P_2 \vee \cdots \vee P_k \vee P_{k+1}' \vee F(0,0, \ldots 0, 1)) \wedge \ldots  \)

\(  \large \ldots \wedge (P_1' \vee P_2' \vee \ldots \vee P_k' \vee P_{k+1}' \vee F(1,1, \ldots 1, 1))  \).

Сначала запишем разложение формулы \(  \large F(P_1,P_2, \ldots , P_k, P_{k+1})  \) по переменной \(  \large P_{k+1}  \). База индукции позволяет нам сделать это. Имеем:

\(  \large F(P_1,P_2, \ldots , P_k, P_{k+1}) \simeq (P_{k+1} \vee F(P_1,P_2, \ldots , P_k,0)) \wedge (P_{k+1}' \vee F(P_1,P_2, \ldots, P_k,1)) \).

Теперь используем предположение индукции:

а) \(  \large F(P_1,P_2, \ldots, P_k, 0) \simeq   \)

\(  \large \simeq (P_1 \vee P_2 \vee \ldots \vee P_k \vee F(\underbrace{0,0, \ldots , 0,0}_{k+1 \ раз})) \wedge   \)

\(  \large \wedge  (P_1 \vee P_2 \vee \ldots \vee P_k' \vee F(\underbrace{0,0, \ldots , 1,0}_{k+1 \ раз})) \wedge \ldots  \)

\(  \large \ldots \wedge (P_1' \vee P_2' \vee \ldots \vee P_k' \vee F(\underbrace{1,1, \ldots , 1,0}_{k+1 \ раз}))    \);

б) \(  \large F(P_1,P_2, \ldots, P_k, 1) \simeq   \)

\(  \large \simeq (P_1 \vee P_2 \vee \ldots \vee P_k \vee F(\underbrace{0,0, \ldots , 0,1}_{k+1 \ раз})) \wedge   \)

\(  \large \wedge  (P_1 \vee P_2 \vee \ldots \vee P_k' \vee F(\underbrace{0,0, \ldots , 1,1}_{k+1 \ раз})) \wedge \ldots  \)

\(  \large \ldots \wedge (P_1' \vee P_2' \vee \ldots \vee P_k' \vee F(\underbrace{1,1, \ldots , 1,1}_{k+1 \ раз}))    \).

Значит,

\(  \large F(P_1,P_2, \ldots , P_{k+1}) \simeq  \)

\(  \large \simeq (P_1 \vee P_2 \vee \ldots  \vee P_{k+1} \vee F(0,0, \ldots ,0)) \wedge  \)

\(  \large  \wedge (P_1 \vee P_2 \vee \cdots \vee P_{k+1}' \vee F(0,0, \ldots ,  1)) \wedge \ldots  \)

\(  \large \ldots \wedge (P_1' \vee P_2' \vee \ldots  \vee P_{k+1}' \vee F(1,1, \ldots , 1))  \).

Следовательно, разложение имеет место для всякого натурального \(  \large n  \).

Теорема доказана.
 

Онлайн Admin

  • Администратор
  • Сообщений: 5046
  • Поблагодарили: 1576 раз(а)
    • Просмотр профиля
Замечание 5.13. Введём обозначение

\(  \large \underset{F(\alpha_1, \alpha_2 , \ldots , \alpha_n)=0}{ \wedge } \ ( P_1^{\overline{\alpha_1}} \vee P_2^{\overline{\alpha_2}} \vee \ldots \vee P_n^{\overline{\alpha_n}})  \)

обозначает конъюнкцию всех дизъюнкций

\(  \large P_1^{\overline{\alpha_1}} \vee P_2^{\overline{\alpha_2}} \vee \ldots \vee P_n^{\overline{\alpha_n}}  \),

где \(  \large P_i^{\overline{\alpha_i}}=\overline{P_i}  \), если \(  \large \alpha_i=1  \), \(  \large P_i^{\overline{\alpha_i}}=P_i  \), если \(  \large \alpha_i=0  \), когда индексы конъюнктирования пробегают все наборы \(  \large (\alpha_1, \alpha_2, \ldots, \alpha_n)  \), на которых формула \(  \large F(P_1,P_2, \ldots , P_n)  \) принимает значение "ложь".

Теорема 5.5. Всякая опровержимая формула логики высказываний имеет следующее представление в совершенной конъюнктивной нормальной форме:

\(  \large F(P_1,P_2, \ldots, P_n) \simeq \underset{F(\alpha_1, \alpha_2 , \ldots , \alpha_n)=0}{ \wedge } \ ( P_1^{\overline{\alpha_1}} \vee P_2^{\overline{\alpha_2}} \vee \ldots \vee P_n^{\overline{\alpha_n}})  \).

Доказательство. Учитывая теорему 5.4, каждую формулу, которая зависит от переменных \(  \large P_1,P_2, \ldots, P_n  \), можно представить в виде конъюнктивного разложения по всем переменным:

\(  \large F(P_1,P_2, \ldots , P_n) \simeq  \)

\(  \large \simeq (P_1 \vee P_2 \vee \ldots \vee P_n \vee F(0,0, \ldots , 0)) \wedge  \)

\(  \large  \wedge (P_1 \vee P_2 \vee \cdots \vee P_n' \vee F(0,0, \ldots , 1)) \wedge \ldots  \)

\(  \large \ldots \wedge (P_1' \vee P_2' \vee \ldots \vee P_n' \vee F(1,1, \ldots , 1))  \).

Пусть формула \(  \large F  \), зависящая от пропозициональных переменных \(  \large P_1,P_2, \ldots , P_n  \), является тавтологией. Тогда, в силу определения,

\(  \large F(0,0, \ldots, 0) = F(0,0, \ldots , 1) = \ldots = F(1,1, \ldots , 1)=1  \).

Следовательно, разложение тривиально, так как

\(  \large P \vee 1 \simeq 1  \), \(  \large P \wedge 1 \simeq P  \).

Оно имеет вид

\(  \large F(P_1,P_2, \ldots , P_n) \simeq 1 \wedge 1 \wedge \ldots \wedge 1  \).

Значит, тождественная истинная формула логики высказываний не имеет СКНФ.

Пусть \(  \large F(P_1,P_2, \ldots, P_n)  \) - опровержимая формула. Если \(  \large F( \alpha_1, \alpha_2, \ldots , \alpha_n)=1  \), то соответствующий член конъюнкции равен единице, так как \(  \large P \vee 1 \simeq 1  \). Следовательно, его можно опустить, поскольку \(  \large P \wedge 1 \simeq P  \). Значит, в разложении будут участвовать только те элементарные дизъюнкции, которые соответствуют тем наборам , где \(  \large F( \alpha_1, \alpha_2, \ldots , \alpha_n)=0  \). Итак, получили совершенную конъюнктивную нормальную форму. Согласно условию теоремы, каждая элементарная дизъюнкция, которая входит в разложение, имеет вид

\(  \large P_1^{\overline{\alpha_1}} \vee P_2^{\overline{\alpha_2}} \vee \ldots \vee P_n^{\overline{\alpha_n}}  \).

Так как либо \(  \large \alpha_i=0  \), либо \(  \large \alpha_i=1  \), то в состав дизъюнкции входит либо \(  \large P_i  \), либо \(  \large \overline{P_i}  \) (\(  \large i=1,2, \ldots , n  \)). Следовательно, все дизъюнкции различны. Ясно, что каждая из них включает все пропозициональные переменные, никакая из них не содержит двух  одинаковых переменных и переменную вместе с отрицанием этой же переменной.

Теорема доказана.
 

Онлайн Admin

  • Администратор
  • Сообщений: 5046
  • Поблагодарили: 1576 раз(а)
    • Просмотр профиля
Теорема 5.6. Представление формулы логики высказываний в СКНФ единственно.

Доказательство. Пусть:

1) \(  \large F(P_1,P_2, \ldots, P_n)  \) - некоторая формула;

2) \(  \large D_1,D_2, \ldots , D_q,E_1, E_2, \ldots , E_s  \) - элементарные конъюнкции от переменных \(  \large P_1,P_2, \ldots, P_n  \).

Предположим, что формула \(  \large F  \) имеет два представления в СКНФ:

\(  \large F(P_1,P_2, \ldots, P_n) \simeq D_1 \wedge D_2 \wedge \ldots \wedge D_q  \);

\(  \large F(P_1,P_2, \ldots, P_n) \simeq E_1 \wedge E_2 \wedge \ldots \wedge E_s  \).

Значит, учитывая, что выше записаны представления одной и той же формулы, справедлива равносильность

\(  \large D_1 \wedge D_2 \wedge \ldots \wedge D_q \simeq E_1 \wedge E_2 \wedge \ldots \wedge E_s  \).

Пусть

\(  \large D_1 \equiv P_1^{\overline{\alpha_1}} \vee P_2^{\overline{\alpha_2}} \vee \ldots \vee P_n^{\overline{\alpha_n}}  \).

Положим \(  \large P_i = \alpha_i, \ i=1,2, \ldots , n  \). Покажем, что в этом случае вся элементарная дизъюнкция \(  \large D_1  \) становится равной нулю. Во-первых, как мы писали выше

\(  \large D_1 \equiv P_1^{\overline{\alpha_1}} \vee P_2^{\overline{\alpha_2}} \vee \ldots \vee P_n^{\overline{\alpha_n}}  \).

Значит,

\(  \large D_1 \equiv \alpha_1^{\overline{\alpha_1}} \vee \alpha_2^{\overline{\alpha_2}} \vee \ldots \vee \alpha_n^{\overline{\alpha_n}}  \).

Во-вторых, если \(  \large \alpha_i=1  \), то \(  \large \alpha_i^{\overline{\alpha_i}}=\overline{\alpha_i}=\overline{1}=0  \), если \(  \large \alpha_i=0  \), то \(  \large \alpha_i^{\overline{\alpha_i}}=\alpha_i=0  \).

Итак,

\(  \large D_1= 0 \vee 0 \vee \ldots \vee 0  \).

Следовательно, при \(  \large P_i = \alpha_i, \ i=1,2, \ldots, n  \),

\(  \large E_1 \wedge E_2 \wedge \ldots \wedge E_s=0  \),

так как

\(  \large 0 \wedge D_2 \wedge \ldots \wedge D_q=0  \).

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

\(  \large E_1 =P_1^{\overline{\beta_1}} \vee P_2^{\overline{\beta_2}} \vee \ldots \vee P_n^{\overline{\beta_n}}=0   \).

Значит, так как \(  \large P_i= \alpha_i  \),

\(  \large \alpha_1^{\overline{\beta_1}} \vee \alpha_2^{\overline{\beta_2}} \vee \ldots \vee \alpha_n^{\overline{\beta_n}}=0  \).

Тогда

\(  \large \alpha_1^{\overline{\beta_1}}= \alpha_2^{\overline{\beta_2}} = \ldots = \alpha_n^{\overline{\beta_n}}=0  \).

Следовательно,

\(  \large \alpha_1 = \beta_1, \  \alpha_2 = \beta_2,  \ldots , \alpha_n= \beta_n  \).

Итак,

\(  \large E_1=D_1  \).

Было доказано, что элементарная дизъюнкция \(  \large D_1  \) встречается среди элементарных дизъюнкций \(  \large E_1,E_2, \ldots, E_s  \). Аналогично можно доказать, что любую элементарную дизъюнкцию \(  \large D_1,D_2, \ldots, D_q  \) можно встретить среди элементарных дизъюнкций \(  \large E_1,E_2, \ldots, E_s  \), и наоборот. Значит, \(  \large q=s  \), следовательно, разложения \(  \large D_1 \wedge D_2 \wedge \ldots \wedge D_q  \) и \(  \large E_1 \wedge E_2 \wedge \ldots \wedge E_s  \) совпадают, учитывая, что конъюнкция коммутативна (они одинаковы с точностью до перестановки членов конъюнкции). На этом теорема доказана.
 
Замечание 5.14. Используя доказательство теоремы существования совершенной конъюнктивной нормальной формы, выведем алгоритм отыскания СКНФ с помощью таблицы истинности:

1) выбрать все те наборы значений переменных, на которых формула логики высказываний принимает значение "ложь";

2) для всякого такого набора записать элементарную дизъюнкцию, принимающую значение "ложь" на данном наборе и только на нём;

3) полученные элементарные дизъюнкции соединить знаками конъюнкции.

Замечание 5.15. СКНФ можно найти с помощью равносильных преобразований. Примерная последовательность действий в этом случае такова:

1) привести формулу к КНФ;

2) убрать члены конъюнкции, которые содержат пропозициональную переменную вместе с её отрицанием (используется закон исключённого третьего и правило \(  \large P \wedge 1 \simeq P  \));

3) из одинаковых членов конъюнкции удалить все, кроме одного (используется идемпотентность конъюнкции);

4) в каждой элементарной дизъюнкции, которая содержит не все пропозициональные переменные, добавить логический нуль (применяется закон противоречия и правило \(  \large P \vee 0 \simeq P  \));

5) раскрыть скобки внутри каждой такой элементарной дизъюнкции, используя соответствующий дистрибутивный закон;

6) убрать одинаковые члены конъюнкции, если таковые появятся (снова применяется идемпотентность данной пропозициональной связки).

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

Онлайн Admin

  • Администратор
  • Сообщений: 5046
  • Поблагодарили: 1576 раз(а)
    • Просмотр профиля
Задача 5.3. Найти СДНФ формулы \(  \large ((P \to Q) \vee R') \to (P \vee (P \leftrightarrow Q))  \) двумя способами.

Решение. Сначала используем равносильные преобразования. Прежде всего, упростим посылку этой импликации. Используя равносильность \(  \large P \to Q \simeq P' \vee Q  \), получим:

\(  \large (P \to Q) \vee R' \simeq P' \vee Q \vee R'  \).

Теперь упростим заключение. Сначала избавимся от эквиваленции:

\(  \large P \vee (P \leftrightarrow Q) \simeq P \vee ((P \to Q)(Q \to P))  \).

Избавимся от импликации:

\(  \large P \vee ((P \to Q)(Q \to P)) \simeq P \vee ((P' \vee Q)(Q' \vee P))  \).

Воспользуемся дистрибутивным законом:

\(  \large P \vee ((P' \vee Q)(Q' \vee P)) \simeq   \)

\(  \large \simeq P \vee (P'Q') \vee (QQ') \vee (P'P) \vee (QP)  \).

Применим закон противоречия:

\(  \large P \vee (P'Q') \vee (QQ') \vee (P'P) \vee (QP) \simeq   \)

\(  \large \simeq P \vee (P'Q') \vee 0 \vee 0 \vee (QP)  \).

Используем правила действий с логическими константами:

\(  \large P \vee (P'Q') \vee 0 \vee 0 \vee (QP) \simeq  \)

\(  \large \simeq P \vee (PQ) \vee (P'Q')    \).

Применяем закон поглощения:

\(  \large P \vee (PQ) \vee (P'Q') \simeq P \vee (P'Q')  \).

Используем дистрибутивность дизъюнкции относительно конъюнкции:

\(  \large P \vee (P'Q') \simeq (P \vee P')(P \vee Q')  \).

Вспомним про закон исключённого третьего:

\(  \large (P \vee P')(P \vee Q') \simeq 1 \cdot (P \vee Q')  \).

Применяя правило \(  \large P \cdot 1 \simeq P  \), завершаем упрощение:

\(  \large 1 \cdot (P \vee Q') \simeq P \vee Q'  \).

Значит, исходная формула равносильна

\(  \large (P' \vee Q \vee R') \to (P \vee Q')  \).

Избавимся от импликации:

\(  \large (P' \vee Q \vee R') \to (P \vee Q') \simeq   \)

\(  \large \simeq (P' \vee Q \vee R')' \vee P \vee Q'  \).

Следующий шаг - применение закона де Моргана:

\(  \large (P' \vee Q \vee R')' \vee P \vee Q' \simeq   \)

\(  \large \simeq (P''Q' R'') \vee P \vee Q'  \).

Используем закон двойного отрицания:

\(  \large (P''Q' R'') \vee P \vee Q' \simeq P \vee (PQ'R) \vee Q'  \).

Применяя закон поглощения, получаем ДНФ:

\(  \large P \vee (PQ'R) \vee Q' \simeq P \vee Q'  \).

Осталось довести ДНФ до совершенства. Применяем закон \(  \large P \cdot 1 \simeq P  \):

\(  \large P \vee Q' \simeq (P \cdot 1 \cdot 1) \vee (1 \cdot Q' \cdot 1)   \).

Используя закон исключённого третьего, получим:

\(  \large (P \cdot 1 \cdot 1) \vee (1 \cdot Q' \cdot 1)  \simeq   \)

\(  \large \simeq (P \cdot (Q \vee Q')(R \vee R')) \vee ((P \vee P')Q' (R \vee R'))  \).

Раскрываем скобки, используя дистрибутивный закон:

\(  \large (P \cdot (Q \vee Q')(R \vee R')) \vee ((P \vee P')Q' (R \vee R')) \simeq   \)

\(  \large \simeq (PQR) \vee (PQ'R) \vee (PQR') \vee (PQ'R') \vee  \)

\(  \large \vee (PQ'R) \vee (P'Q'R) \vee (PQ'R') \vee (P'Q'R')  \).

Убираем одинаковые члены дизъюнкции, используя идемпотентный закон:

\(  \large \simeq (PQR) \vee (PQ'R) \vee (PQR') \vee (PQ'R') \vee  \)

\(  \large \vee (PQ'R) \vee (P'Q'R) \vee (PQ'R') \vee (P'Q'R') \simeq   \)

\(  \large  (PQR) \vee (PQ'R) \vee (PQR') \vee (PQ'R') \vee (P'Q'R) \vee (P'Q'R') \).

Получили совершенную дизъюнктивную нормальную форму.

Выполним проверку, составив таблицу истинности:

\( \begin{array}{|c|c|}
\hline
P &  Q &  R &  P \to Q & R' & (P \to Q) \vee R' & P \leftrightarrow Q & P \vee (P \leftrightarrow Q) &  ((P \to Q) \vee R') \to (P \vee (P \leftrightarrow Q)) \\
\hline
0 &  0 &  0 & 1 & 1 & 1 & 1 & 1 & 1 \\
\hline
0 & 0 & 1 & 1  & 0 & 1 & 1 & 1 & 1\\
\hline
0 & 1 & 0 &  1 & 1 & 1 & 0 & 0 & 0 \\
\hline
0 & 1 & 1 & 1 & 0 & 1 & 0 & 0 & 0 \\
\hline
1 & 0 & 0 & 0 & 1 & 1 & 0 & 1 & 1  \\
\hline
1 & 0 & 1 & 0 & 0 & 0 & 0 & 1 & 1  \\
\hline
1 & 1 & 0 &1 & 1 & 1 & 1 & 1 & 1  \\
\hline
1 & 1 & 1 & 1 & 0 & 1 & 1 & 1 & 1\\
\hline
\end{array}  \)

Используя истинностную таблицу, найдём элементарные конъюнкции, которые соответствуют тем наборам значений пропозициональных переменных, на которых формула принимает значение "истина":

\(  \large P'Q'R' , \ P'Q' R, \ P Q'R' , \ PQ'R, \ PQR', \ PQR  \).

Значит, совершенная дизъюнктивная нормальная форма формулы имеет вид

\(  \large (PQR) \vee (PQR') \vee (PQ'R) \vee (PQ'R') \vee (P'Q' R) \vee (P'Q'R')  \).

Как видим, получен тот же самый результат, что и при использовании основных законов логики высказываний.
 

Онлайн Admin

  • Администратор
  • Сообщений: 5046
  • Поблагодарили: 1576 раз(а)
    • Просмотр профиля
Задача 5.4. Найти формулу \(  \large F  \), зависящую от трёх пропозициональных переменных, если известно, что

\(  \large F(0,0,0)=F(0,1,0)=F(1,1,1)=1  \),

а во всех остальных случаях она принимает значение, равное нулю. Упростить полученную формулу, используя основные равносильности логики высказываний.

Решение. Поскольку в условии задачи даны наборы значений переменных, на которых формула принимает значение \(  \large 1  \), используем СДНФ. Для каждого такого набора выпишем элементарную конъюнкцию, принимающую значение \(  \large 1  \) на этом наборе и только на нём, и объединим эти конъюнкции знаками дизъюнкции. Итак, искомая формула имеет вид

\(  \large  (P'Q'R') \vee (P'QR')  \vee (PQR)  \).

Упростим эту формулу. Рассмотрим первые две элементарные конъюнкции. Пропозициональные переменные \(  \large P  \) и \(  \large R  \) входят в них с отрицанием, а пропозициональная переменная \(  \large Q  \) входит в первую конъюнкцию с отрицанием, а во вторую - без него. В этот момент, учитывая имеющийся опыт равносильных преобразований, нам должна прийти мысль о применении дистрибутивного закона,

\(  \large (P'Q'R') \vee (P' QR') \simeq P'R' (Q' \vee Q)  \).

Затем надлежит использовать закон исключённого третьего и правила действий с логическими постоянными:

\(  \large P'R' (Q' \vee Q)  \simeq P'R' \cdot 1 \simeq P'R'  \).

После проведённых равносильных преобразований формула имеет следующий вид:

\(  \large (P'R') \vee (PQR)  \).

Получили дизъюнктивную нормальную форму. Можно ли ещё упростить формулу? Да, можно. Для дальнейших преобразований вспомним второй закон де Моргана и равносильность \(  \large P \to Q \simeq P' \vee Q  \). Эти логические законы мы будем применять не слева направо, а наоборот, справа налево. Имеем:

\(  \large (P'R') \vee (PQR) \simeq  \)

\(  \large \simeq (P \vee R)' \vee (PQR) \simeq   \)

\(  \large \simeq (P \vee R) \to (PQR)  \).
 

Онлайн Admin

  • Администратор
  • Сообщений: 5046
  • Поблагодарили: 1576 раз(а)
    • Просмотр профиля
Задача 5.5. Найти совершенную конъюнктивную нормальную форму формулы с помощью равносильных преобразований и табличным способом:

\(  \large (P_1 \leftrightarrow P_2) \to (P_1P_3)  \).

Решение. Преобразуем посылку данной импликации. Сначала выразим эквиваленцию через импликацию и конъюнкцию:

\(  \large P_1 \leftrightarrow P_2 \simeq (P_1 \to P_2)(P_2 \to P_1)  \).

Теперь избавимся от импликации:

\(  \large (P_1 \to P_2)(P_2 \to P_1) \simeq (P_1' \vee P_2)(P_2' \vee P_1)  \).

Раскроем скобки, используя закон дистрибутивности:

\(  \large (P_1' \vee P_2)(P_2' \vee P_1) \simeq   \)

\(  \large \simeq (P_1'P_2') \vee (P_2P_2') \vee (P_1P_1') \vee (P_1P_2)  \).

Применим закон противоречия:

\(  \large (P_1'P_2') \vee (P_2P_2') \vee (P_1P_1') \vee (P_1P_2) \simeq  \)

\(  \large \simeq (P_1'P_2') \vee 0 \vee 0 \vee (P_1P_2)   \).

Избавимся от нулей, используя закон \(  \large P \vee 0 \simeq P  \):

\(  \large (P_1'P_2') \vee 0 \vee 0 \vee (P_1P_2) \simeq   \)

\(  \large \simeq (P_1'P_2') \vee  (P_1P_2)   \).

Значит,

\(  \large (P_1 \leftrightarrow P_2) \to (P_1P_3) \simeq  \)

\(  \large \simeq ((P_1'P_2') \vee (P_1P_2)) \to (P_1P_3)   \).

Продолжим преобразования, чтобы получить КНФ. Сначала выразим импликацию через дизъюнкцию и отрицание:

\(  \large ((P_1'P_2') \vee (P_1P_2)) \to (P_1P_3) \simeq   \)

\(  \large \simeq ((P_1'P_2') \vee (P_1P_2))' \vee (P_1P_3)  \).

Следом используем один из законов де Моргана:

\(  \large ((P_1'P_2') \vee (P_1P_2))' \vee (P_1P_3) \simeq  \)

\(  \large  \simeq ((P_1'P_2')'  (P_1P_2)') \vee (P_1P_3)  \).

Теперь применим другой закон де Моргана:

\(  \large ((P_1'P_2')'  (P_1P_2)') \vee (P_1P_3) \simeq   \)

\(  \large \simeq ((P_1'' \vee P_2'')(P_1' \vee P_2')) \vee (P_1P_3)  \).

Используем закон двойного отрицания:

\(  \large ((P_1'' \vee P_2'')(P_1' \vee P_2')) \vee (P_1P_3) \simeq   \)

\(  \large \simeq ((P_1 \vee P_2)(P_1' \vee P_2')) \vee (P_1P_3)  \).

Раскроем скобки, используя закон дистрибутивности:

\(  \large ((P_1 \vee P_2)(P_1' \vee P_2')) \vee (P_1P_3) \simeq  \)

\(  \large \simeq (P_1 \vee P_2 \vee P_1)(P_1 \vee P_2 \vee P_3)(P_1' \vee P_2' \vee P_1)(P_1' \vee P_2' \vee P_3)  \).

Применим идемпотентность дизъюнкции и закон исключённого третьего:

\(  \large (P_1 \vee P_2 \vee P_1)(P_1 \vee P_2 \vee P_3)(P_1' \vee P_2' \vee P_1)(P_1' \vee P_2' \vee P_3) \simeq   \)

\(  \large \simeq (P_1 \vee P_2 )(P_1 \vee P_2 \vee P_3)(P_2' \vee 1 )(P_1' \vee P_2' \vee P_3)  \).

Используем правила \(  \large P \vee 0  \), \(  \large P \vee 1 \simeq 1  \) и \(  \large P \cdot 1 \simeq P  \):

\(  \large (P_1 \vee P_2 )(P_1 \vee P_2 \vee P_3)(P_2' \vee 1 )(P_1' \vee P_2' \vee P_3)  \simeq   \)

\(  \large \simeq (P_1 \vee P_2 \vee 0 )(P_1 \vee P_2 \vee P_3)(P_1' \vee P_2' \vee P_3)   \).

Вспомним про закон противоречия:

\(  \large (P_1 \vee P_2 \vee 0 )(P_1 \vee P_2 \vee P_3)(P_1' \vee P_2' \vee P_3) \simeq  \)

\(  \large \simeq  (P_1 \vee P_2 \vee (P_3P_3') )(P_1 \vee P_2 \vee P_3)(P_1' \vee P_2' \vee P_3)  \).

Раскроем скобки:

\(  \large (P_1 \vee P_2 \vee (P_3P_3') )(P_1 \vee P_2 \vee P_3)(P_1' \vee P_2' \vee P_3) \simeq   \)

\(  \large \simeq (P_1 \vee P_2 \vee P_3 ) (P_1 \vee P_2 \vee P_3')(P_1 \vee P_2 \vee P_3)(P_1' \vee P_2' \vee P_3)  \).

Применим закон идемпотентности конъюнкции и избавимся от одной из двух одинаковых элементарных дизъюнкций:

\(  \large (P_1 \vee P_2 \vee P_3 ) (P_1 \vee P_2 \vee P_3')(P_1 \vee P_2 \vee P_3)(P_1' \vee P_2' \vee P_3) \simeq  \)

\(  \large \simeq (P_1 \vee P_2 \vee P_3 ) (P_1 \vee P_2 \vee P_3')(P_1' \vee P_2' \vee P_3)  \).

Мы получили СКНФ. Теперь найдём её табличным способом:

\( \begin{array}{|c|c|}
\hline
P_1 &  P_2 &  P_3 &  P_1 \leftrightarrow P_2 & P_1P_3 & (P_1 \leftrightarrow P_2) \to (P_1 P_3) \\
\hline
0 &  0 &  0 & 1 & 0 & 0  \\
\hline
0 & 0 & 1 & 1  & 0 & 0 \\
\hline
0 & 1 & 0 &  0 & 0 & 1  \\
\hline
0 & 1 & 1 & 0 & 0 & 1  \\
\hline
1 & 0 & 0 & 0 & 0 & 1   \\
\hline
1 & 0 & 1 & 0 & 1 & 1   \\
\hline
1 & 1 & 0 &1 & 0 & 0   \\
\hline
1 & 1 & 1 & 1 & 1 & 1\\
\hline
\end{array}  \)

Запишем элементарные дизъюнкции, соответствующие наборам значений пропозициональных переменных, на которых формула принимает значение "ложь". Имеем:

\(  \large P_1 \vee P_2 \vee P_3, \ P_1 \vee P_2 \vee P_3' , \ P_1' \vee P_2' \vee P_3  \).

Итак, СКНФ формулы имеет следующий вид:

\(  \large (P_1 \vee P_2 \vee P_3)( P_1 \vee P_2 \vee P_3' ) ( P_1' \vee P_2' \vee P_3)  \).

Результат, очевидно, тот же, что и при использовании равносильных преобразований.
 

Онлайн Admin

  • Администратор
  • Сообщений: 5046
  • Поблагодарили: 1576 раз(а)
    • Просмотр профиля
Задача 5.6 Решить задачу 5.4 другим способом.

Решение. Поскольку

\(  \large F(0,0,0)=F(0,1,0)=F(1,1,1)=1  \),

то

\(  \large F(0,0,1)=F(0,1,1)=F(1,0,0)=F(1,0,1)= F(1,1,0)=0  \).

Найдём формулу, применяя на сей раз СКНФ:

\(  \large  (P \vee Q \vee R')(P \vee Q' \vee R') (P' \vee Q \vee R)(P' \vee Q \vee R') (P' \vee Q' \vee R)  \).

Внимательно посмотрев на первые две скобки, понимаем, что здесь надлежит применить дистрибутивный закон, закон противоречия, а также одно из правил действий с постоянной "нуль". Имеем:

\(  \large (P \vee Q \vee R')(P \vee Q' \vee R') \simeq   \)

\(  \large \simeq P \vee R' \vee (QQ') \simeq P \vee R' \vee 0 \simeq P \vee R'  \).

Точно таким же преобразованиям подвергнем третью и четвёртую скобки:

\(  \large  (P' \vee Q \vee R)(P' \vee Q \vee R') \simeq  \)

\(  \large \simeq P' \vee Q \vee (RR') \simeq P' \vee Q \vee 0 \simeq P' \vee Q   \).

После упрощения исходная формула примет вид

\(  \large (P \vee R')(P' \vee Q)(P' \vee Q' \vee R)  \).

Займёмся равносильными преобразованиями двух последних элементарных дизъюнкций. Вынесем за скобки отрицание пропозициональной переменной \(  \large P  \), используя соответствующий дистрибутивный закон:

\(  \large (P' \vee Q)(P' \vee Q' \vee R) \simeq P' \vee (Q(Q' \vee R))  \).

Раскроем скобки, применяя закон дистрибутивности конъюнкции относительно дизъюнкции, закон противоречия и правила действий с логическими постоянными:

\(  \large  P' \vee (Q(Q' \vee R)) \simeq P' \vee (QQ') \vee (Q R) \simeq   \)

\(  \large \simeq P' \vee 0 \vee (QR) \simeq P' \vee (QR)  \).

Исходная формула предстанет в следующей форме:

\(  \large (P \vee R')(P' \vee (QR))  \).

Снова воспользуемся дистрибутивностью конъюнкции относительно дизъюнкции:

\(  \large (P \vee R')(P' \vee (QR))  \simeq \)

\(  \large  \simeq (PP') \vee (R'P') \vee (PQR) \vee (R'QR)  \).

Далее вступают в действие закон противоречия и правило действий с константами классической логики высказываний. Имеем:

\(  \large (PP') \vee (R'P') \vee (PQR) \vee (R'QR) \simeq   \)

\(  \large \simeq 0 \vee (R'P') \vee (PQR) \vee (0 \cdot Q) \simeq   \)

\(  \large \simeq (P'R') \vee (PQR) \vee 0 \simeq (P'R') \vee (PQR)  \).

Окончательно:

\(  \large (P'R') \vee (PQR) \simeq (P \vee R) \to (PQR)  \).

Видим, что получили ту же самую формулу. Но второй способ, очевидно, гораздо более трудоёмок. Это и понятно, поскольку во второй раз мы использовали тот факт, что формула принимает значение, равное нулю, на пяти наборах значений переменных, а в первый раз речь шла только о трёх наборах (на них формула принимала значение, равное единице). Поэтому, если требуется найти формулу логики высказываний и известно, что на таких-то наборах значений пропозициональных переменных она равна нулю, а на таких-то - единице, то если меньше единиц, следует применять СДНФ, а если меньше нулей, - СКНФ. Но в любом случае есть два способа решения такого рода задач.