Тема 2.1. Высказывания и формулы алгебры логики. Нормальные форм. Тема Высказывания и формулы алгебры логики. Нормальные формы алгебры высказываний Аннотация

• Название: Тема Высказывания и формулы алгебры логики. Нормальные формы алгебры высказываний Аннотация
• Дата: 06.10.2022
• Размер: 0.52 Mb.
• Имя файла: Тема 2.1. Высказывания и формулы алгебры логики. Нормальные форм.pdf
• Тип: Документы; #718696

Тема 2.1. Высказывания и формулы алгебры логики. Нормальные
формы алгебры высказываний
Аннотация: Высказывания и логические связки (дизъюнкция, конъюнкция, импликация, эквиваленция). Формулы логики высказываний. Общезначимые, выполнимые и противоречивые формулы.
Логика – это наука, которая учит, как нужно правильно рассуждать, правильно делать умозаключения и выводы, получая в результате правильные высказывания. Создателем традиционной формальной логики был древнегреческий ученый Аристотель (384–
322 гг. до н.э.).
Идея математической логики впервые в ясной форме была выдвинута немецким математиком Лейбницем (1646–1716). Первые научные работы именно по математической логике опубликовали де Морган
(1806–1875) и
Дж. Буль
(1815–1864).
Строгое аксиоматическое изложение логики высказываний и предикатов дал известный немецкий математик Г. Фреге (1848–1925). Высшее развитие математическая логика получила в основополагающем труде «Основания математики» (1910–1913) А. Уайтхеда (1861–1947) и Б. Рассела (1862–1970), а затем в работах немецкого математика Д. Гильберта (1862–1943). Существенный вклад в математическую логику внесли советские математики А.А. Марков
(мл.) и П.С. Новиков.
Основные понятия математической логики
Высказыванием называется предложение, о котором имеет смысл говорить, что оно является истинным или оно является ложным.
Пример: высказывание «Река Волга впадает в Каспийское море» является истинным.
Для удобства высказывания условимся обозначать заглавными латинскими буквами. Например можно считать, что А – это высказывание «Сейчас в Москве идет дождь». Если оно является истинным, то пишут А=1, а если ложно - А=0.
Высказывание будем называть простым (элементарным), если оно рассматривается как некое неделимое целое (аналогично элементу множества).
Сложным
(составным) называется высказывание, составленное из простых с помощью основных логических связок.

В естественном языке (при вербальном описании явления) роль связок при составлении сложных предложений из простых играют следующие грамматические средства: союзы «и», «или»; слова
«если…, то…», «тогда и только тогда, когда» и др.
Логические операции
Логическим связкам соответствуют логические операции над высказываниями: отрицание, конъюнкция, дизъюнкция, импликация,
эквивалентность:
1.
Отрицанием высказывания Р называется высказывание, которое истинно только тогда, когда высказывание Р ложно.
Обозначается

Р или P . Операции соответствует логическая связка
«не».
2.
Конъюнкцией двух высказываний P и Q называется высказывание, истинное тогда и только тогда, когда истинны оба высказывания. Обозначается P&Q или Р

Q. Операции соответствует логическая связка «и».
3.
Дизъюнкцией двух высказываний P и Q называется высказывание, ложное тогда и только тогда, когда оба высказывания ложны.Обозначается P

Q. Операции соответствует логическая связка «или».
4.
Импликацией двух высказываний P и Q называется высказывание, ложное тогда и только тогда, когда высказывание Р
истинно, а Q – ложно. Обозначается P
Q

). Высказывание Р называется посылкой импликации, а высказывание Q – следствием.
Операции соответствует логическая связка «если…,то».
5.
Эквиваленцией двух высказываний P и Q называется высказывание, истинное тогда и только тогда, когда истинности высказываний совпадают. Обозначается Р

Q, или Р

Q, или P
Q

.
Операции соответствует логическая связка «тогда и только тогда».
Таблицы истинности для всех указанных связок (операций) приведены ниже:
P
Q
P
Р

Q
P

Q
P
Q

P
Q

0 0
1 0
0 1
1 0
1 1
0 1
1 0
1 0
0 0
1 0
0 1
1 0
1 1
1 1

Очень часто студентов удивляет, что в импликации если посылка ложна, то сама импликация сразу истинна, т.е. из ложного высказывания можно доказать все что угодно. Однажды одна из студенток Бертрана Рассела спросила: «Что, неужели из того, что
2х2=5 можно доказать, что Вы – Папа Римский?» - «Да!», ответил
Рассел и провел несложное доказательство. Давайте рассмотрим похожий пример: докажем, что мы сейчас с вами в Нью-Йорке.
Рассмотрим две переменные a и b, и пусть они будут равными.
Проведем несложные математические преобразования:
a
b

Умножим обе части равенства на одно и то же число (a):
2
a
ab

Отнимем от обеих частей равенства одно и то же число (b
2
):
2 2
2
a
b
ab
b



Воспользуемся формулами, известными с седьмого класса:


 

a
b a
b
b a
b




Разделим обе части равенства на одно и то же число


a
b

:
a
b
b
 
Поскольку
a
b

, то
b
b
b
 
или
2b
b

Опять поделим обе части равенства на одно и то же число (b):
2=1.
Москва и Нью-Йорк это два города, но поскольку 2=1, то это один и тот же город, т.е. мы с вами в Нью-Йорке!
Безусловно, в данном доказательстве есть ошибка (в четвертой строке нельзя делить на


a
b

, поскольку это ноль, а делить на ноль нельзя)! Но если мы с вами примем, что на ноль делить можно, то мы с вами в Нью-Йорке!
Формулы алгебры высказываний
Пропозициональной
переменной
(или переменным элементарным высказыванием) называется произвольное высказывание, конкретный вид которого неизвестен. Другими словами, это переменная, принимающая значения во множестве высказываний. Дадим строгое определение формулы алгебры
высказываний.
1. Пропозициональные переменные и логические константы есть формулы.

2. Если
1
F ,
2
F – формулы, то


1 2
F
F

,


1 2
F
F

,


1 2
F
F

,


1 2
F
F

,
 
1
F
также являются формулами.
3. Других формул, кроме описанных в пунктах 1 и 2, нет.
Определения такого типа называются индуктивными: сначала определяются самые простые формулы, затем указывается, как из простых строятся более сложные.
Чтобы избежать нагромождения скобок, условимся, что при отсутствии скобок логические операции выполняются в следующем порядке:

,

,

,

,

Кроме того, внешние скобки в формуле писать не обязательно.
Подформулой формулы называется всякая ее часть, которая сама является формулой.
Формула называется выполнимой (опровержимой), если существует такой набор высказываний, который обращает эту формулу в истинное (ложное) высказывание.
Формула называется
тождественно
истинной,
или
тавтологией (тождественно ложной, или противоречием), если она обращается в истинное (ложное) высказывание при всех наборах значений переменных.
Формулы называются равными, если они принимают одинаковые значения на одних и тех же наборах значений переменных.
Тавтологии играют важную роль в логике, на некоторых из них основаны способы логических умозаключений. С другой стороны, свойства логических операций также выражаются через тавтологии.

Теорема
(свойства операции конъюнкции и дизъюнкции)
Следующие формулы являются тавтологиями:
законы идемпотентности:
(
)
;
(
)
;
X
X
X
X
X
X




законы коммутативности:
(
)
(
);
(
)
(
);
X
Y
Y
X
X
Y
Y
X






законы ассоциативности:
(
(
))
((
)
);
X
Y
Z
X
Y
Z





(
(
))
((
)
) ;
X
Y
Z
X
Y
Z





законы поглощения:
(
(
))
; (
(
))
;
X
X
Y
X
X
X
Y
X






Законы де Моргана:
(
)
(
);
(
)
(
).
X
Y
X
Y
X
Y
X
Y


   


   
Доказательство
элементарно построением таблицы

истинности.
Предикаты
В каждом высказывании всегда можно выделить субъект (то, о чём говорится) и предикат – то, что говорится о данном субъекте. В то же время часто встречаются выражения, грамматически имеющие форму высказываний, но вместо конкретных субъектов содержащие переменные величины. Такое выражение можно получить из любого высказывания, заменив в нём субъект на переменную величину.
Одноместным предикатом на множестве M называется всякое предложение, содержащее переменную x , такое, что при замене x любым предметом из M получается высказывание.
Множество M называется областью определения предиката;
x
– предметная переменная. Для предикатов используются обозначения:
 
P x
,
 
Q y
,
 
R z
, … .
Областью
истинности предиката
 
P x
называется подмножество
P
J
M

, задаваемое равенством
 


|
1
P
J
a
M
P a



Заметим, что иногда вместо записи
 
1
P a

употребляется более короткая запись:
 
P a
. Действительно, для предиката
0
x

обычно не пишут
5 0
1


, а пишут короче: 5 0

Предикат
 
P x
называется тождественно истинным, если
P
J
M

, тождественно ложным, если
P
J
 
, выполнимым, если
P
J
 
, опровержимым, если
P
J
M

Говорят, что на множествах
1
M ,
2
M ,…,
n
M задан n -местный
предикат, если задано предложение


1 2
,
,
,
n
P x x
x
, содержащее переменные
1
x ,…,
n
x и превращающееся в высказывание при замене каждого
i
x элементом
i
i
a
M

,
1, 2,
,
i
n

. В том случае, если
1 2
n
M
M
M
M




, говорят, что предикат


1 2
,
,
,
n
P x x
x
задан на множестве M .
Пример: Выражение
2
x
y

– двухместный предикат, определённый на множестве действительных чисел R.
Областью истинности предиката


1 2
,
,
,
n
P x x
x
, заданного на множествах
1
M ,
2
M ,…,
n
M , называется множество







1 1
1 1
,
,
|
,
,
,
,
,
1
P
n
n
n
n
J
a
a
a
M
a
M
P a
a




Нормальные формы алгебры высказываний
Для каждой булевой можно указать равносильную ей формулу, содержащую из логических связок лишь отрицание, конъюнкцию и дизъюнкцию. Для этого нужно, используя равносильности выразить все имеющиеся в формуле импликации и эквивалентности через отрицание, конъюнкцию и дизъюнкцию. Так, для формулы




X
X
Y
Y
 


равносильной ей формулой, не содержащей логических связок

и

, будет, например, формула




X
X
Y
Y
    

Выразить данную формулу через отрицание, конъюнкцию и дизъюнкцию возможно не одним способом, а многими. К примеру, рассматриваемая формула равносильна также следующим формулам, содержащим из логических связок лишь ,


и
:

,
X
Y
 
,
X
Y

(X Y)
(
),
Y
Y

  
(X
)
Y,
Y
  
(X
)
((X
)
),
Y
X
Y
  
 

(X
)
(X Y)
(
)
Y
X
Y
  

  
Конъюнктивным одночленом от переменных
1 2
,
,...,
n
X X
X называется конъюнкция этих переменных или их отрицаний. Здесь
«или» употребляется в неисключающем смысле, т.е. в конъюнктивный одночлен может входить одновременно и переменная, и ее отрицание. Приведем несколько примеров конъюнктивных одночленов:
1 1
,
X
X

1 2
3
X ,
X
X
 

2 1
3 2
5
X
X
X
X
X
  
 

Дизъюнктивным одночленом от переменных
1 2
,
,...,
n
X X
X называется дизъюнкция этих переменных или их отрицаний (и здесь союз «или» употребляется в неисключающем смысле). Приведем примеры дизъюнктивных одночленов:
1 2
3
,
X
X
X
 

2 2
,
X
X

1 2
3 1
4 2
X
X
X
X
X
X

 
  

Дизъюнктивной нормальной формой называется дизъюнкция конъюнктивных одночленов, т.е. выражение вида
1 2
p
K
K
K

 
, где все
i
K ,
1, 2,..., p
i

, являются конъюнктивными одночленами (не обязательно различными). Аналогично конъюнктивной нормальной
формой называется конъюнкция дизъюнктивных одночленов
1 2
q
D
D
D

 
, где все
j
D
,
1, 2,...,q
j

, дизъюнктивными одночленами (не обязательно различными). Будем также называть

дизъюнктивной (конъюнктивной) нормальной формой указанные выражения при
1
p

(
1
q

).
Очевидно, что у данной формулы F существует неограниченно много как дизъюнктивных, так и конъюнктивных нормальных форм.
Одни из них более громоздкие и сложные, другие — более простые.
Алгоритм построения нормальной формы:
1. Избавиться от операций импликации и эквиваленции по формулам X
Y
X
Y
   
и

 

X
Y
X
Y
X
Y
 

   
2. Убрать отрицания, стоящие над операциями по законам де
Моргана:


X
Y
X
Y


   
и


X
Y
X
Y


   
3. Снять двойные отрицания:
X
X
 
4. Далее рекомендуем для ДНФ заменить «

» на «+», а «

» на
« » (для КНФ заменить «

» на «+», а «

» на « ») после чего раскрыть скобки по обычным правилам математики.
Подсказка: первая буква показывает, что заменить на «плюс».
5. Вернуть знаки логических операций из пункта 4.
Совершенные нормальные формы
Среди множества дизъюнктивных (равно как и конъюнктивных) нормальных форм, которыми обладает данная формула алгебры высказываний, существует уникальная форма: она единственна для данной формулы. Это так называемая совершенная дизъюнктивная нормальная форма (среди конъюнктивных форм — совершенная конъюнктивная нормальная форма).
Одночлен (конъюнктивный или дизъюнктивный) от переменных
1 2
,
,...,
n
X X
X называется совершенным, если в него от каждой пары
i
X ,
i
X



1, 2,..., n
i

входит только один представитель (
i
X или
i
X

).
Нормальная форма (дизъюнктивная или конъюнктивная) от переменных
1 2
,
,...,
n
X X
X называется совершенной от этих переменных, если в нее входят лишь совершенные одночлены
(конъюнктивные или дизъюнктивные соответственно) от
1 2
,
,...,
n
X X
X .
Приведем пример совершенной конъюнктивной нормальной формы от трех переменных
1 2
3
,
,
:
X X
X

 
 

1 2
3 1
2 3
1 2
3
X
X
X
X
X
X
X
X
X


  
 

 
 
Рассмотрим способ приведения формулы алгебры высказываний к совершенной нормальной форме.

Если формула задана таблицей своих значений, то для случая
СДН-формы эта формула имеет следующий вид:






1 1
1 1
,..., X
X
,...,
0
n
a
n
n
n
F X
X
F





 

, где
,если
1,
,если
0.
X
X
X





 



По сути, эта формула описывает правило (алгоритм) отыскания совершенной дизъюнктивной нормальной формы для данной формулы: нужно выбрать все те наборы значений ее переменных, на которых формула принимает значение 1; для каждого такого набора выписать совершенный конъюнктивный одночлен, принимающий значение 1 на этом наборе и только на нем; полученные совершенные конъюнктивные одночлены соединить знаками дизъюнкции. Для случая СКН-формы эта формула имеет вид






1 1
1 1
,..., X
X
,
,...,
0
n
n
n
n
F X
X
F






 

где
,если
0,
,если
1.
X
X
X





 



Она описывает следующее правило (алгоритм) отыскания совершенной конъюнктивной нормальной формы для данной формулы: нужно выбрать все те наборы значений ее переменных, на которых формула принимает значение 0. Для каждого такого набора выписать совершенный дизъюнктивный одночлен, принимающий значение 0 на этом наборе и только на нем. Полученные совершенные дизъюнктивные одночлены соединить знаками конъюнкции.
Пример:
Пусть, например, формула


, ,
F X Y Z
задана следующей таблицей своих значений:
X Y
Z


, ,
F X Y Z
0 0
0 1
0 0
1 0
0 1
0 1
0 1
1 1
1 0
0 1
1 0
1 0
1 1
0 0

1 1
1 1
Таким образом, она принимает значения 1 на следующих наборах значений своих переменных (или при следующих конкретизациях):


0,0,0 ,


0,1,0 ,


0,1,1 ,


1,0,0 ,


1,1,1 .
Запишем предыдущую формулу разложения в СДН-форму для случая
3
n

и применим ее в нашей ситуации:







 


 
 


 


 
 

0 0
0 0
1 0
0 1
1 1
0 0
1 1
1
, ,
, ,
1
F X Y Z
X
Y
Z
F
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



  























          
   

    
 
Пример: Для формулы


, ,
F X Y Z
из предыдущего примера найдем ее СКН-форму. Для этого сначала отметим все те наборы значений переменных, на которых она принимает значение 0:


0,0,1 ,


1,1,0 ,


1,0,1 .
Теперь запишем формулу разложения в СКН-форму для случая
3
n

и применим ее в нашей ситуации:







 
 


 
 

0 0
1 1
0 1
1 1
0
, ,
, ,
0
F X Y Z
X
Y
Z
F
X
Y
Z
X
Y
Z
X
Y
Z
X
Y
Z
X
Y
Z
X
Y
Z



  

















            
Еще раз обращаем внимание на то, что для каждой формулы алгебры высказываний СДН-форма единственна и СКН-форма единственна (если они существуют). СДН-форма отмечает все те наборы значений пропозициональных переменных, на которых данная формула принимает значение 1, а СКН-форма отмечает все те наборы значений пропозициональных переменных, на которых данная формула принимает значение 0.
Тем не менее, необходимо отчетливо осознавать, что две полученные формулы равносильны.

Второй способ приведения формул алгебры высказываний к совершенной нормальной форме основан на равносильных преобразованиях данной формулы. В этом случае формула должна быть задана в аналитической форме. Для приведения формулы к совершенной нормальной форме нужно сначала привести ее к дизъюнктивной (или конъюнктивной) нормальной форме. Затем нужно продолжить равносильные преобразования полученных нормальных форм, с тем, чтобы довести их до совершенства используя равенства

 
 

X
X
Y
Y
X
Y
X
Y


 



 
и

 
 

X
X
Y
Y
X
Y
X
Y


 



 
Пример: пусть получена ДНФ от функции трех переменных

 

X
Y
X
Y
Z
 

  
. Построить СДНФ.
Решение:

 







X
Y
X
Y
Z
X
Y
Z
Z
X
Y
Z
 

  

  
 

  


 
 

X
Y
Z
X
Y
Z
X
Y
Z
  

   

  
В заключение отметим, что одной из сфер применения нормальных форм является та, где требуется получить аналитическое выражение для формулы алгебры высказываний, которая задана своей таблицей значений (таблицей истинности), т.е. про которую известно, на каких наборах она принимает значение 0, а на каких 1.
Вопросы для самоконтроля:
1. Высказывания. Примеры. Виды высказываний.
2. Операции над высказываниями (дизъюнкция, конъюнкция, импликация, эквиваленция).
3. Формулы логики высказываний.
Общезначимые, выполнимые и противоречивые формулы.
4. Тавтологии алгебры высказываний. Примеры.
5. Понятие предиката. Область истинности предиката.
6. Нормальные формы. Алгоритм приведения к ДНФ и КНФ.
7. Совершенные формы. Примеры.