Математическая логика и теория алгоритмов

 

Лабораторные  работы по курсу 

«Математическая логика и теория алгоритмов»

 

Лабораторная  работа № 1. Логика высказываний

 

Цель  работы – научиться переводить выражения на естественном языке на язык логики высказываний. Научиться проверять логическое следствие.

 

Порядок выполнения

1. Ознакомиться с методическими указаниями
2. Решить цикл задач для самостоятельной работы.
3. Формализовать и решить задачу (номер задачи соответствует номеру бригады).
4. Придумать и решить аналогичную п.3 задачу. Задача должна содержать не менее 1-й импликации и хотя бы одну конъюнкцию или дизъюнкцию, и не менее 3-х логических переменных.
5. Проверить правильность решения задач из п.3 и 4 на ЭВМ (программа tautology.rb).
6. Оформить отчет.

 

Методические  указания

Высказывание  – это повествовательное предложение, о котором можно сказать истинно оно или ложно. Рассмотрим следующие предложения.

А. «Число Ö2 является иррациональным».

Б. «Неверно, что  число Ö2 является иррациональным».

В. «Если число Ö2 является иррациональным, то число Ö2+1 также является иррациональным».

Г. «Который час?»

Д. «Идите решать задачу к  доске»

Первые три  предложения являются высказываниями, последние два – нет. Высказывания А и В истинны, высказывание Б  – ложно. Более точно, значение истинности высказываний А и В есть истина, а значение истинности высказывания Б есть ложь. В дальнейшем истину будем обозначать цифрой 1, а ложь – цифрой 0.

Проанализируем  высказывания А-В с точки зрения их «внутреннего строения». Высказывание А можно назвать простым. А  высказывания Б и В – составными, полученными из простых высказываний А и E=«число Ö2+1 является иррациональным». Этот простой пример показывает, что в языке (в данном случае, в русском языке) существуют способы построения одних высказываний из других. Эти способы мы будем называть операциями. В естественных языках (в том числе и в русском языке) существует много таких операций. Мы выделим в качестве основных пять операций.

Определение. Пусть X и Y – некоторые высказывания. Тогда высказывания:

1) «X и Y» называется  конъюнкцией высказываний X и Y;

2) «X или Y» называется  дизъюнкцией высказываний X и Y;

3) «не X» называется  отрицанием высказывания X;

4) «если X, то Y» называется  импликацией высказываний X и Y;

5) «X тогда  и только тогда, когда Y»  называется эквиваленцией высказываний X и Y.

 

Высказывание  Б из вышеприведенного примера является отрицанием высказывание А, а высказывание В – импликацией высказываний А и Е. Введем следующие обозначения  для операции: & – конъюнкция, Ú – дизъюнкция, Ø – отрицание, ® – импликация, « – эквиваленция. Так, Б=ØА, В=А®Е. Символы &, Ú, Ø, ®, « называются связками.

Зависимость значения истинности новых высказываний определяется таблицей истинности связок – таблицей 1.1.

Таблица 1.1

X	Y	X&Y	XÚY	ØX	X®Y	X«Y
1	1	1	1	0	1	1
1	0	0	1	0	0	0
0	1	0	1	1	1	0
0	0	0	0	1	1	1

 

Прокомментируем таблицы истинности дизъюнкции и  импликации. В русском языке союз «или» понимается в двух смыслах: разделительном – или то, или другое, но не оба, и соединительном – или то, или другое, или оба. Как мы видим из таблицы 1.1 мы союз «или» будем понимать в соединительном смысле. Перейдем к импликации. Если дана импликация X®Y, то высказывание X называется посылкой импликации, а Y – заключением. Если посылка X импликации ложна, то вся импликация X®Y истинна (см. третью и четвертую строки таблицы 1.1). Это свойство импликации часто формулируют в виде следующего принципа: «из ложного утверждения(имеется в виду X) следует все что угодно (имеется в виду Y)». В силу этого следующее высказывание «если 2×2=5, то p – иррациональное число» является истинным, поскольку оно представляет собой импликацию, посылка которой ложна. Подчеркнем, что при этом не надо искать доказательство или опровержение того, что p – иррациональное число. Аналогично, первая и третья строки таблицы 1.1 показывают нам. Что если заключение Y импликации истинно, то вся импликация X®Y также истинна. Это свойство импликации тоже формулируют в виде принципа: «истинное утверждение (имеется в виду Y) следует из чего угодно (имеется в виду X)». Из этого принципа сразу следует истинность высказывания «если p – иррациональное число, то 2×2=4», поскольку оно представляет собой импликацию с истинным заключением.

Формулы логики высказываний, интерпретация

Определение. Атомарными формулами логики высказываний называются буквы U,V,W,X,Y,Z с индексами и без них, а также символы истины 1 и лжи 0.

 

Определение. Формулами логики высказываний называются

1) атомарные формулы;

2) выражения  вида (F)&(G), (F)Ú(G), Ø(F), (F)®(G), (F)«(G), где F и G – формулы логики высказываний.

Это определение относится к так называемым индуктивным определениям. Такие определения вводят сначала базовые объекты (в нашем случае – атомарные формулы) и способы порождения новых объектов из уже полученных (в нашем случае – применение операций).

Приведем пример. Буквы X,Y,Z – атомарные формулы. В силу первого пункта определения эти буквы являются формулами логики высказываний, а в силу второго формулами являются выражения (X)&(Y), ((X)&(Y))®(Z). Мы видим, что если следовать строго определению, в формуле надо писать много скобок. Это неудобно для восприятия формулы. Чтобы уменьшить количество скобок условимся, во первых, атомарные формулы в скобки не заключать, во вторых, ввести приоритет (силу связывания) для связок. Будем считать, что Ø имеет наивысший приоритет, & и Ú имеют одинаковый приоритет, который выше, чем y® и «. Последние две связки имеют одинаковый приоритет. Используя эти соглашения формулу ((X)&(Y))®(Z) можно записать так: X&Y®Z. Отметим, что поскольку мы не упорядочили & и Ú по силе связывания, то выражение X&YÚZ не является формулой. Надо в этом выражении поставить скобки, определяющие порядок выполнения операций. Получатся две формулы (X&Y)ÚZ и X&(YÚZ).

Обозначим через А – множество атомарных, а через F – множество всех формул логики высказываний.

Определение. Интерпретацией называется функция

j:A®{0,1}

такая, что j(0)=0, j(1)=1.

Используя таблицы  истинности связок, интерпретацию можно  расширить на множество всех формул. Приведем пример. Пусть j(X)=1, j(Y)=0, j(Z)=1, F=XÚY®Z, G=X&Y«X&Z. Тогда j(F)=1, j(G)=0.

Рассмотрим задачу “О молодом человеке”, решение которой состоит в использовании выразительных возможностей логики высказываний: “Если я поеду автобусом, а автобус опоздает, то я пропущу назначенное свидание. Если я пропущу назначенное свидание и начну огорчаться, то мне не следует ехать домой. Если я не получу работу, то я начну огорчаться и мне следует поехать домой. Следовательно, если я поеду автобусом, а автобус опоздает, то я получу эту работу”. Задача состоит в том, чтобы перевести э т о рассуждение на язык логики высказываний, т.е. представить его в виде последовательности четырех формул (поскольку рассуждение содержит четыре предложения). Обозначим высказывание “я поеду автобусом” буквой X, “автобус опоздает” – буквой Y, “я пропущу свидание” – Z, “я начну огорчаться” – U, “мне следует ехать домой” – V, “я получу работу” – W. Тогда приведенные в рассуждении предложения можно записать в виде следующих формул: X&Y → Z, Z&U → ¬V, ¬W → U&V, X&Y → W.

Равносильность  и законы логики высказываний

Нетрудно привести примеры формул, которые «выражают одно и то же». Таковы, например, формулы XÚY и YÚX. Подобные формулы мы будем называть равносильными.

Определение. Формулы F и G называются равносильными, если для любой интерпретации j выполняется равенство j(F)=j(G).

Убедимся в том, что формулы F=X®Y и G=ØXÚY равносильны. Ясно, что если интерпретации j и y совпадают на X и Y, то j(F)=y(F) и j(G)=y(G). Следовательно, для проверки равенства j(F)=j(G) из определения равносильности надо рассмотреть лишь интерпретации, которые различаются на X и Y (а таких интерпретаций четыре) и вычислить соответствующие значения j(F) и j(G). Другими словами, надо составить совместную таблицу истинности формул F и G (см. таблицу 1.2).

Таблица 1.2

X	Y	F=X®Y	ØX	G=ØXÚY
1	1	1	0	1
1	0	0	0	0
0	1	1	1	1
0	0	1	1	1

 

В таблице 1.2 для  удобства вычисления значения интерпретаций  на G введен промежуточный столбец ØX. Мы видим, что столбцы формул F и G совпадают. Это означает, что формулы F и G равносильны.

Определение. Формула F называется тождественно истинной (или общезначимой или тавтологией) если для любой интерпретации j выполняется равенство j(F)=1.

Например, формула F=X&Y®X является тождественно истинной. Для проверки равенства j(F)=1 не надо рассматривать все интерпретации, а лишь четыре, которые различаются на атомарных формулах X и Y. Для таких интерпретаций надо вычислить значение формулы F, т.е. составить таблицу истинности формулы F (см. таблицу 1.3).

Таблица 1.3

X	Y	X&Y	F=X&Y®X
1	1	1	1
1	0	0	1
0	1	0	1
0	0	0	1

 

Мы видим, что  столбец формулы F состоит из одних единиц. Это означает, что формула F тождественно истинна.

 

Теорема 1.1. Формулы F и G равносильны тогда и только тогда, когда формула F«G является тождественно истинной.

 

 

Логическое следствие

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

Определение. Формула G называется логическим следствием формул F₁,F₂,…,F_k, если для любой интерпретации j из того, что j(F₁)=j(F₂)=…=j(F_k)=1 следует, что j(G)=1.

Рассмотрим следующую задачу: выяснить, логично ли рассуждение “О молодом человеке” приведенное выше. Напомним, что это рассуждение мы перевели на язык логики высказываний, т.е. представили в виде последовательности формул: F1 = X&Y → Z, F2 = Z&U → ¬V, F3 = ¬W →U&V, F4 = X&Y → W. Это означает, что поставленная задача переходит в следующую задачу: выяснить, будет ли формула F4 логическим следствием формул F1 , F2 , F3? Чтобы ответить на этот вопрос, предположим, что при некоторой интерпретации ϕ формула F4 принимает значение 0, а формулы F1 , F2 , F3 – значение 1. Если ϕ (F4) = 0, то ϕ (X) = ϕ (Y) =1 и ϕ (W) = 0. Из того, что ϕ (F1) = ϕ (F3) = 1, следуют равенства ϕ (Z) = ϕ (U) = ϕ (V) = 1. Но это противоречит тому, что ϕ (F2) = 1. Полученное противоречие показывает, что если ϕ (F1) = ϕ (F2) = ϕ (F3) = 1, то ϕ (F4) = 1, т.е. что формула F4 является логически следствием формул F1 , F2 , F3 и рассуждение молодого человека логично.

Приведем пример. Докажем, что формула G=Y®X не является логическим следствием формул F₁=XÚY, F₂=X®Y, F₃=Y. Для этого построим совместную таблицу истинности формул F₁,F₂,F₃ и G.

Таблица 1.4

X	Y	F1=XÚY	F2=X®Y	F3=X	G=Y®X
1	1	1	1	1	1
1	0	1	0	0	1
0	1	1	1	1	0
0	0	0	1	0	1

 

Мы видим (см. таблицу 1.4), что если взять интерпретацию j, для которой j(х)=0, j(y)=1, (т.е. взять третью строку таблицы), то j(F₁)=j(F₂)=j(F₃)=1, но j(G)=0. Следовательно, формула G не является логическим следствием формул F₁,F₂,F₃.