Описание всех лабораторных работ

14

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

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

Лабораторная работа № 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

Прокомментируем таблицы истинности дизъюнкции и импликации. В русском языке союз «или» понимается в двух смыслах: разделительном – или то, или другое, но не оба, и соединительном – или то, или другое, или оба. Как мы видим из таблицы 1.1 мы союз «или» будем понимать в соединительном смысле. Перейдем к импликации. Если дана импликация XY, то высказывание X называется посылкой импликации, а Y – заключением. Если посылка X импликации ложна, то вся импликация XY истинна (см. третью и четвертую строки таблицы 1.1). Это свойство импликации часто формулируют в виде следующего принципа: «из ложного утверждения(имеется в виду X) следует все что угодно (имеется в виду Y)». В силу этого следующее высказывание «если 22=5, то  – иррациональное число» является истинным, поскольку оно представляет собой импликацию, посылка которой ложна. Подчеркнем, что при этом не надо искать доказательство или опровержение того, что  – иррациональное число. Аналогично, первая и третья строки таблицы 1.1 показывают нам. Что если заключение Y импликации истинно, то вся импликация XY также истинна. Это свойство импликации тоже формулируют в виде принципа: «истинное утверждение (имеется в виду Y) следует из чего угодно (имеется в виду X)». Из этого принципа сразу следует истинность высказывания «если  – иррациональное число, то 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 – множество всех формул логики высказываний.

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

A{0,1}

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

Используя таблицы истинности связок, интерпретацию можно расширить на множество всех формул. Приведем пример. Пусть (X)=1, (Y)=0, (Z)=1, F=XYZ, G=X&YX&Z. Тогда (F)=1, (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 называются равносильными, если для любой интерпретации  выполняется равенство (F)=(G).

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

Таблица 1.2

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

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

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

Таблица 1.3

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

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

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

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

Определение. Формула G называется логическим следствием формул F₁,F₂,…,F_k, если для любой интерпретации  из того, что (F₁)=(F₂)=…=(F_k)=1 следует, что (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 и рассуждение молодого человека логично.