УПП_Дискретная математика-1. Международный консорциум Электронный университет Московский государственный университет экономики, статистики и информатики

• Название: Международный консорциум Электронный университет Московский государственный университет экономики, статистики и информатики
• Дата: 09.02.2023
• Размер: 6.65 Mb.
• Имя файла: УПП_Дискретная математика-1.doc
• Тип: Учебно-практическое пособие; #929287
• страница: 7 из 19

Нормальные формы формул алгебры высказываний
Если в какой – либо логической ситуации данная формула принимает значение «истинно», она называется выполнимой. К классу выполнимых формул относятся такие формулы, множество истинности которых не пусто. В противном случае формула называется невыполнимой.

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

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

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

Определение 2. Элементарной суммой (или основной дизъюнкцией) называется дизъюнкция элементарных высказываний или их отрицаний.
Элементарная конъюнкция «k» и элементарная дизъюнкция «d» над множеством переменных могут быть записаны формулами:



,

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

 _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. 
   Заменить знак отрицания, относящийся к выражениям типа или , знаками отрицания, относящимся к отдельным переменным высказываниям на основании формул:
   

=  ,

=  .

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

Упражнение 2.2.3
Пусть . Построим КНФ для этой формулы.

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

( B)(  );

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

;

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

;

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

;

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

,

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

Используя свойства AA=A и AA=A, упростим КНФ для S:
S= .
Теорема 3. Формула алгебры высказываний является тождественно истинной тогда и только тогда, когда каждый множитель ее КНФ содержит пару слагаемых, одно из которых является элементарным высказыванием, а другое – его отрицанием.

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

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

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

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



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

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

В упражнении 2.2.1 . Преобразуем S к виду КНФ.



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

1. 
   Она не содержит двух одинаковых слагаемых.
   
2. 
   Ни одно слагаемое не содержит одновременно двух одинаковых сомножителей.
   
3. 
   Ни одно слагаемое не содержит одновременно некоторого высказывания и его отрицания.
   
4. 
   Каждое слагаемое содержит в качестве сомножителя либо переменное высказывание, либо его отрицание для всех переменных, входящих в формулу.
   

Это определение является конструктивным, т.е. позволяет для каждой формулы алгебры высказываний, приведенной к ДНФ, построить ее СДНФ.
Упражнение 2.2.5
.
Задана ДНФ. Приведем ее к СДНФ.

1. 
   Первое и последние слагаемые одинаковы. На основании свойства операции дизъюнкции АА=А одно из одинаковых слагаемых можно отбросить.
   
2. 
   АСС=АС.
   
3. 
   .
   

Получим .

Теперь выполнили условия 1 – 3. Чтобы выполнить условие 4, поступим следующим образом:

;

.

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

Теперь условие 4 выполнено, но появились одинаковые слагаемые. Исключив их, получим:
.
Определение 6. Совершенной конъюнктивной нормальной формой данной формулы алгебры высказываний (СКНФ) называется такая ее КНФ, которая удовлетворяет следующим свойствам:

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

Определение СКНФ также является конструктивным.
Упражнение 2.2.6
Дана КНФ: .

Построить СКНФ.

1. 
   АВВ=АВ.
   
2. 
   (АВ)(АВ)=АВ.
   
3. 
   , следовательно, .
   
4. 
   .
   

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

Из определений и теорем 3, 4 следует, что тождественно истинная формула не имеет СКНФ, а тождественно ложная – СДНФ.

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

Совершенные нормальные формы могут быть применены для установления равносильности двух заданных формул алгебры высказываний. Для этого нужно обе формулы привести к СКНФ или СДНФ и убедить в их совпадении. Например, формулы
и равносильны:

.
Полной элементарной конъюнкцией называется конъюнкция, удовлетворяющая свойствам 2, 3, 4 определения 5. Аналогично, полной элементарной суммой называется элементарная дизъюнкция, удовлетворяющая свойствам 2, 3, 4 определения 6.

Поэтому совершенные нормальные формы можно определить так:

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

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

Каждая полная элементарная конъюнкция на одном наборе значений переменных высказываний, ее составляющих, обращается в 1: переменное высказывание, входящее без знака отрицания, принимает значение 1, а со знаком отрицания – 0. Этот набор значений элементарных составляющих называется единицей данной полной элементарной конъюнкции. Так, единицей полной элементарной конъюнкции является (1, 0,1).

Аналогично каждая полная элементарная дизъюнкция на одном наборе значений переменных высказываний, ее составляющих, обращается в 0: переменное высказывание, входящее без знака отрицания, принимает значение 0, а со знаком отрицания – 1. Этот набор значений элементарных составляющих называется нулем данной полной элементарной дизъюнкции. Так, нулем полной элементарной дизъюнкции является (1, 1,0).

Эти сведения непосредственно используются в следующем разделе данного учебного пособия.
Построение формулы алгебры высказываний
по заданной логической функции
Рассмотрим задачу, обратную той, о которой шла речь в разделах 2.1, 2.2 – построение функции для некоторой формулы алгебры высказываний. Задана некоторая функция f(x₁, x₂, ... x_n), нужно построить для нее формулу S. Задача эта неоднозначна, существует множество равносильных между собой формул, соответствующих этой функции. Будем строить совершенную нормальную форму. При этом учтем, что полная элементарная дизъюнкция имеет единственный ноль, а полная элементарная конъюнкция – единственную единицу. Решение задачи рассмотрим на примере.
Таблица 2.3.1

x	y	z	f
1	1	1	1
1	1	0	0
1	0	1	0
1	0	0	1
0	1	1	0
0	1	0	1
0	0	1	0
0	0	0	0

Пусть задана некоторая функция трех аргументов f(1,1,1)=f(1,0,0)=f(0,1,0)=1. Это значит, что на наборах (1,1,1), (1,0,0), (0,1,0) функция принимает значение 1, а на остальных наборах – 0.

Построим S в виде совершенной дизъюнктивной нормальной формы. Так как S не тождественно ложна, это можно сделать. СДНФ состоит из стольких слагаемых, сколько единиц содержит функция. Первому значению 1 соответствует слагаемое xyz, принимающее значение 1 при х=1, y=1, z=1. Второму значению 1 соответствует слагаемое , принимающее значение 1 при х=1, y=0, z=0. Аналогично третье слагаемое, соответствующее 1, стоящей в шестой строке таблицы f, есть . Следовательно, . Итак:

1. 
   Совершенная дизъюнктивная нормальная форма содержит столько слагаемых, сколько единиц имеет функция.
   
2. 
   Эти единицы соответствуют тем наборам переменных, при которых каждое слагаемое (элементарная конъюнкция) обращается в единицу, т.е. переменным, входящим в элементарную конъюнкцию без знака отрицания, соответствует значение 1, а со знаком отрицания – 0.
   

Чтобы написать СКНФ по заданной функции, нужно выбрать все значения 0, встречающиеся в ней, и рассмотреть наборы значений переменных, отвечающие этим нулям. В заданном примере таблица содержит пять нулей. Первому значению 0 отвечает сомножитель , обращающийся в 0 при х=1, y=1, z=0. Второму – при х=1, y=0, z=1 и т.д. В результате получим



Итак:

1. 
   СДНФ содержит столько сомножителей, сколько нулей имеет истинностная таблица.
   
2. 
   Эти нули соответствуют тем наборам переменных, при которых каждый сомножитель (каждая элементарная сумма) обращается в 0, т.е. переменным, входящим в элементарную сумму без знака отрицания, соответствует значение 0, а со знаком отрицания – 1.
   

Заметим, что, используя список основных равносильных формул, полученные выражения для S упрощают, если это возможно.
Моделирование алгебры высказываний
с помощью релейно-контактных схем
Релейно-контактная схема представляет собой устройство из проводников и контактов, связывающих полюса источника тока. Контакты могут быть размыкающими и замыкающими. Каждый контакт подключен к некоторому реле. Когда реле находится под током, все подключенные к нему замыкающие контакты замкнуты, а размыкающие – разомкнуты.

Каждому реле можно поставить в соответствие значение 1, если оно находится под током, и 0, если нет. Все замыкающие контакты, подключенные к реле х, будем обозначать x₁, ... x_n, а размыкающие – .

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

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


т.е. дизъюнкция моделируется параллельным соединением проводников, конъюнкция – последовательным.

Упражнение 2.3.1
Построить функцию проводимости следующей схемы:


Рис. 2.3.1
Функция проводимости для такой схемы задается, очевидно, следующей таблицей:
Таблица 2.3.2

x	y	z	f(x,y,z)
1	1	1	1
1	1	0	1
1	0	1	1
1	0	0	0
0	1	1	1
0	1	0	1
0	0	1	1
0	0	0	0

По данной логической функции построим формулу – СКНФ:

Упростим это выражение: .

Построим более простую схему, имеющую ту же функцию проводимости, что и исходная:


Y

Z


Рис. 2.3.2

Чтобы упростить релейно-контактную схему, не обязательно строить ее функцию проводимости. Можно написать соответствующую данной схеме формулу и упростить. Затем построить схему электрической цепи, моделирующую эту упрощенную формулу. Так, для электрической цепи, приведенной в данном примере, .
Упражнение 2.3.2
Построить наиболее простую релейно-контактную схему по заданной функции проводимости f(x,y,z): f(0,1,0) =
= f(1,1,0) = f(1,1,1)=0.
Строим СКНФ: , т.к. эти сомножители обращаются в «0» на указанных наборах функции: (1,1,1), (1,1,0), (0,1,0).

Далее упрощаем формулу S:



Рис. 2.3.3

2.3. Исчисление высказываний
Символы, формулы, аксиомы исчисления высказываний.
Правила вывода
Рассмотрим формальную аксиоматическую систему, в некотором смысле адекватную алгебре высказываний. Назовем эту систему исчислением высказываний.

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

Символы исчисления высказываний состоят из знаков трех категорий:

Большие латинские буквы А, В, С, ... X, Y, Z, ..., которые назовем переменными высказываниями.

Символы операций исчисления , , , ^ (знак конъюнкции, дизъюнкции, следования и отрицания).

Скобки ( ).

Других символов система исчисления высказываний не содержит.

Формулой в исчислении высказываний является некоторая последовательность символов. Но не всякая последовательность символов есть формула. Например, последовательности А→В (С→) и (А В) не являются формулами. Определение формулы в исчислении высказываний задается следующим образом:

1. 
   Всякое переменное высказывание есть формула.
   
2. 
   Если ,  есть формулы, то выражения вида (), , , (), () также являются формулами.
   

Зададим в исчислении высказываний класс исходных истинных формул-аксиом.

I.	1.	А(ВА);
	2.	(А (ВС))((АВ)(АС);
II.	1.	АВА;
	2.	АВВ;
	3.	(АВ)((АС)(АВС));
III.	1.	ААВ;
	2.	ВАВ;
	3.	(АС)((ВС)(АВС)).
IV.	1.	;
	2.	;
	3.	.

Правила вывода позволяют из данной системы аксиом получать другие истинные формулы исчисления высказываний. Назовем формулу исчисления высказываний ложной, если ее отрицание истинно. Будем обозначать истинные формулы буквой R, ложные – F.

К основным правилам вывода относятся два:

1. 
   Правило заключения.
   

Если  и () – истинные формулы, то  также истинна. Это предложение можно записать в виде

.

2. 
   Правило подстановки
   

Пусть некоторая формула  содержит переменное высказывание А. Тогда, заменив высказывание А всюду, где оно встречается, любой формулой , получим истинную формулу. Это предложение записывается в виде .
Формула называется выводимой в исчислении высказываний, если ее можно получить, применяя правила вывода к аксиомам исчисления высказываний. Утверждение, что формула  выводима, записывают так:

├.

Процесс получения формул из аксиом исчисления высказываний называется формальным выводом. Формальный вывод состоит из указания того, какие правила, в каком порядке и к каким формулам применяется для выведения данной формулы.
Упражнение 2.3.3
Докажем, что выводима формула АА, т.е. АА.

1. 
   Запишем аксиому 2 из группы I.
   

(А (ВС))((АВ)(АС).

2. 
   Применим к ней правило подстановки , т.е.
   

.

3. 
   Заметим, что  есть истинная формула, как аксиома из группы I, т.е. имеем истинные формулы  и . Применим правило заключения и получим (АВ)(АА).
   
4. 
   Применим правило подстановки к полученной формуле, заменив высказывание В на :
   

.

5. 
   Но , есть аксиома 2 из группы IV. Применим к полученной формуле правило заключения , т.е. -АА.
   

Говорят, что формула  выводима из формул ₁, ₂, ..., _n, если формулу  можно вывести путем правила заключения, приняв за исходные формулы ₁, ₂, ..., _n и все истинные в исчислении высказываний формулы. Выводимость формулы  из формул ₁, ₂, ..., _n записывают в виде ₁, ₂, ..., _n, .

Теорема дедукции

Если формула  выводима из формул ₁, ₂, ..., _n, то выводимой является формула ₁(₂(...(_n)...)), т.е.

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

1. 
   Правило силлогизма. Если формулы () и () истинны, то формула (), т.е.
   

;

2. 
   Правило перестановки посылок. Если формула ( ()) истинна, то истинной является формула ( ()), т.е. ;
   
3. 
   Правило соединения посылок. Если истинной является формула (()), то истинной будет формула (), т.е. .
   

Проблемы непротиворечивости, полноты,
независимости аксиом исчисления высказываний

Используем алгебру высказываний как некоторую модель исчисления высказываний. Формулы исчисления высказываний будем трактовать как формулы алгебры высказываний. Для этого все буквы, входящие в алфавит исчисления высказываний, будем считать переменными высказываниями в содержательном смысле, т.е. переменными, принимающими значения И и Л. Символы алфавита , , , ^, - будем понимать как логические связки алгебры высказываний.
При этом справедлива следующая теорема.
Все аксиомы исчисления высказываний есть тождественно истинные формулы алгебры высказываний. Все формулы, выводимые из аксиом исчисления высказываний, есть тождественно истинные формулы алгебры высказываний.

Доказательство первой части теоремы можно провести непосредственной проверкой.

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

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

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

Проблема непротиворечивости состоит в том, что следует выяснить, является данное исчисление непротиворечивым.

Если в исчислении можно вывести некоторую формулу  и ее отрицание , то такое исчисление будет противоречивым. Если логическое исчисление противоречиво, в нем будет выводима любая формула. Такое исчисление не представляет ценности, т.к. оно не способно отображать в себе различие между истиной и ложью.

Для доказательства непротиворечивости логического исчисления достаточно найти в нем хотя бы одну невыводимую формулу. В исчислении высказываний проблема непротиворечивости решается так.
Теорема I. Исчисление высказываний непротиворечиво.

Справедливость этого утверждения следует из предыдущей теоремы. В самом деле, пусть  – некоторая выводимая в исчислении высказываний формула. Следовательно, она тождественно истинна, если ее рассматривать как содержательную формулу алгебры высказываний. Тогда – тождественно ложна, т.е. не выводима при всех значениях входящих в нее переменных. Следовательно,  и не могут быть вместе выводимыми в исчислении высказываний.

Итак, любая выводимая формула в исчислении высказываний является тождественно истинной, если эту формулу исчисления высказываний рассматривать как содержательную формулу алгебры высказываний. Возникает обратная задача.

Будет ли любая тождественно истинная формула алгебры высказываний выводима из аксиом исчисления высказываний.

Эта задача представляет собой проблему полноты исчисления высказываний в широком смысле.

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

Для исчисления высказываний проблема полноты решается положительно.
Теорема II. Система исчисления высказываний является полной.

Не менее важным является определение полноты логической системы в узком смысле слова. Логическое исчисление называется полным в узком смысле слова, если добавление к системе аксиом некоторой невыводимой в этом исчислении формулы делает исчисление противоречивым. Исчисление высказываний является полным также в узком смысле слова.

Для любой логической системы возникает проблема независимости аксиом данного исчисления. Зададимся вопросом, можно ли какую-либо аксиому исчисления вывести из остальных аксиом с помощью правил вывода данной системы. Если это возможно, то аксиому, выводимую из других аксиом, можно вычеркнуть из списка аксиом данного исчисления. Аксиома, невыводимая из остальных аксиом, называется независимой из этих аксиом. Система аксиом, в которой ни одна аксиома не выводима из остальных, называется независимой системой аксиом.

Эта проблема для исчислений решается положительно.

Теорема III. Система аксиом исчисления высказываний независима.

Проблема независимости системы аксиом логического исчисления является весьма важной математической проблемой, приводящей иногда к вопросу о замене какой-либо аксиомы ее отрицанием. В качестве примера можно привести вопрос о независимости пятого постулата Евклида в системе аксиом геометрии, вопрос о независимости аксиомы Цермело в системе аксиом теории множеств. Вопросы эти имели большое значение в развитии математики.