Нормальные формы формул алгебры высказываний

Полные системы связок

 

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

Используя формулы, равносильные импликации и двойной импликации, получим, что дизъюнкция, конъюнкция, отрицание образуют полную систему связок. Используя закон де Моргана, приходим к тому, что (Ú-), (Ù-) - полные системы связок.

В самом деле из трех связок Ú, Ù, ^¾ можно исключить дизъюнкцию: или конъюнкцию: .

 

 

Упражнение 9

Проиллюстрировать полноту связок (Ú, ^¾) на примерах:

 

Очевидно, в данных формулах нужно заменить все связки, кроме (Ú, ^¾).

 

а) Преобразуем S₁:

 

Применяя формулу поглощения получим

 

, т.е. .

 

б) , где по закону де Моргана, так же как и

, т.е.

 

Формула S₂ стала более громоздкой, но представлена только двумя связками: Ú, ^¾.

 

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

 

Нормальные формы формул алгебры высказываний

Если в какой - либо логической ситуации данная формула принимает значение “истинно”, она называется выполнимой. К классу выполнимых формул относятся такие формулы, множество истинности которых не пусто. В противном случае формула называется невыполнимой.

Установить тот факт, что данная формула является выполнимой, можно с помощью истинностных таблиц. Нужно построить истинностную таблицу данной формулы и убедиться в том, что она содержит не одни нули. В противном случае формула является невыполнимой, тождественно ложной.

При большом числе переменных истинностные таблицы громоздки. Установить тип формулы (невыполнима - тождественно ложна, выполнима – тавтология или переменное высказывание, принимающее в одних ситуациях значение “истинно”, в других - “ложно”) удобнее с помощью так называемых нормальных форм.

Определение 1. Элементарным произведением (или основной конъюнкцией) называется конъюнкция элементарных высказываний или их отрицаний.

Определение 2. Элементарной суммой (или основной дизъюнкцией) называется дизъюнкция элементарных высказываний или их отрицаний.

Элементарная конъюнкция “k” и элементарная дизъюнкция “d” над множеством переменных могут быть записаны формулами:

 

,

где i_kÎ{1,2,... n} для всех

d _kÎ{0,1}, причем

 

Пусть сложное высказывание состоит из 4 ^х элементарных, обозначенных соответственно A, B, C, D. Элементарные дизъюнкции и элементарные конъюнкции могут быть составлены соответственно и элементарных высказываний.

Так имеем K₁=A D, K₂= BC , K₃= - некоторые из элементарных конъюнкций, соответственно d₁= ÚBÚ Ú , d₂=AÚ ÚC - некоторые из элементарных дизъюнкций. В дальнейшем будем пользоваться большими латинскими буквами для обозначения переменных.

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

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

 

Так, элементарная сумма AÚBÚCÚ тождественно истинна, элементарное произведение ABC тождественно ложно.

Определение 3. Формула, равносильная данной формуле алгебры высказываний и являющаяся дизъюнкцией элементарных произведений, называется дизъюнктивной нормальной формой данной формулы и обозначается ДНФ.

 

Пример: ABCÚB Ú .

Определение 4. Формула, равносильная данной формуле алгебры высказываний и являющаяся конъюнкцией элементарных произведений, называется конъюнктивной нормальной формой данной формулы и обозначается КНФ.

 

Пример: (BÚ Ú )(AÚB)B.

Для каждой формулы алгебры высказываний можно найти множество дизъюнктивных и конъюнктивных нормальных форм. Для этого нужно:

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

A®B= ÚB,

A«B=( ÚB)(AÚ )=ABÚ .

2. Заменить знак отрицания, относящийся к выражениям типа или , знаками отрицания, относящимся к отдельным переменным высказываниям на основании формул:

= Ú ,

=AÙB.

3. Избавиться от знаков двойного отрицания на основании равенства =A.

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

Упражнение

Пусть . Построим КНФ для этой формулы.

1) избавимся от знаков импликации, получим:

( ÚB)«( Ú );

2) избавимся от знака двойной импликации:

;

3) избавимся от знака отрицания, относящегося к выражениям, состоящим более чем из одной переменной:

;

 

4) избавимся от двойных и тройных отрицаний:

;

5) применим законы дистрибутивности:

,

.

Получим S= . Это КНФ для данной формулы S.

Используя свойства AÚA=A и AA=A, упростим КНФ для S:

S= .

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

Теорема 4. Формула алгебры высказываний является тождественно ложной тогда и только тогда, когда каждое слагаемое (т. е. каждое элементарное произведение) ее ДНФ содержит пару сомножителей, один из которых есть элементарное высказывание, другой - его отрицание.

Теоремы 3,4 позволяют решить вопрос о выполнимости любой формулы алгебры высказываний.

Нужно построить для этой формулы ее ДНФ или ее КНФ. Если построена ДНФ и оказывается, что она удовлетворяет условиям теоремы 4, то формула является невыполнимой. Можно построить КНФ для отрицания исходной формулы. Если окажется, что она удовлетворяет условиям теоремы 3, то исходная формула невыполнима, т. к. ее отрицание тождественно истинно. В остальных случаях формулы являются выполнимыми.

 

Упражнение

 

Установить тип формулы S= .

Определим КНФ для отрицания S:

.

КНФ для не удовлетворяет условию теоремы 3, следовательно, S – выполнима, то есть , так как .

Обратимся к вопросу о правильности рассуждений. Чтобы убедиться в том, что рассуждение верно, нужно либо преобразовать импликацию S= P₁ÙP₂Ù...ÙP_n®Q к КНФ и удостовериться в том, что она удовлетворяет условиям теоремы 3, либо преобразовать к ДНФ и убедиться в том, что она удовлетворяет условиям теоремы 4.

 

. Преобразуем S к виду КНФ.

Конъюнктивная нормальная форма удовлетворяет условиям теоремы 3, каждый сомножитель есть тождественно истинное высказывание, а также и их произведение, что и требовалось получить.