Реферат: Методические указания к выполнению контрольных заданий и лабораторных работ по дисциплине «Математическая логика и теория алгоритмов»

1 и 2 тема и 1 и 2 контрольные делать дома

МИНИСТЕРСТВО ОБРАЗОВАНИЯ РОССИЙСКОЙ ФЕДЕРАЦИИ
МГАПИ


УТВЕРЖДАЮ

Проректор по УР

____________ Соколов В.В.

«___» ___________ 2002 г.


МЕТОДИЧЕСКИЕ УКАЗАНИЯ
к выполнению контрольных заданий и лабораторных работ

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


Рекомендуется для направления подготовки
дипломированного специалиста

654600 – «Информатика и вычислительная техника»

специальности – 22.02.00.
Автоматизированные системы обработки
информации и управления.


Москва 2002


АННОТАЦИЯ

Методические указания соответствуют программе курса “Математическая логика и теория алгоритмов” для студентов специальности 22.02.03. Приведены краткие сведения по основам логики высказываний, логики предикатов, формальных аксиоматических теорий и теории алгоритмов. Контрольные задания включают упражнения по всем разделам. Приводятся указания к проведению лабораторных работ.


Авторы: Казаков С.А., Правоторова Н.А.

Научный редактор: проф. Петров О.М.

Рецензент:

Рассмотрено и одобрено на заседании кафедры ИТ-7

"__"____________2002 г. Зав. кафедрой __________О.М. Петров

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

доц. Правоторова Н.А.

СОДЕРЖАНИЕ
Введение

Тема 1. Логика высказываний

1.1. Определение высказывания

1.2. Операции над высказываниями. Алгебра высказываний

1.3. Формулы логики высказываний. Равносильность формул

1.4. Запись сложного высказывания в виде формулы логики высказываний

1.5. Нормальные формы

1.6. Тождественно-истинные и тождественно-ложные формулы. Проблема разрешимости

1.7.Формализация рассуждений. Правильные рассуждения

Тема 2. Логика предикатов

2.1. Определение предиката. Кванторы

2.2. Формулы логики предикатов. Равносильность формул

2.3. Приведенные и нормальные формулы

2.4. Выражение суждения в виде формулы логики предикатов

2.5. Интерпретация формулы логики предикатов в виде суждения. Выполнимость. Общезначимость

Тема 3. Формальные аксиоматические теории (исчисления)

3.1. Принципы построения формальных теорий

3.2. Исчисление высказываний

3.3. Исчисление предикатов

3.4. Автоматическое доказательство теорем. Метод резолюций.

Тема 4. Нечеткая логика

4.1. Нечеткие множества

4.2. Нечеткие высказывания

4.3. Нечеткие предикаты

Тема 5 Алгоритмы

5.1. Определение алгоритма

5.2. Машина Тьюринга

5.3. Вычислимые по Тьюрингу функции

Указания к выполнению лабораторных работ

Контрольные задания по курсу “Математическая логика и теория алгоритмов”

Вопросы к экзамену

Список литературы

Краткие сведения о математиках


ВВЕДЕНИЕ

Логика - одна из самых древних наук. Как самостоятельная наука логика оформилась в трудах греческого ученого Аристотеля ( 384 – 322 г. до н. э.) и стала впоследствии называться формальной или Аристотелевой логикой.

С момента своего возникновения и в течение многих веков логика рассматривалась как часть философии. Математическая логика возникла на стыке двух наук: традиционной или философской логики и математики.

Идея построения логики на математической основе была впервые выдвинута Лейбницем (1646 – 1716). Окончательно как раздел математики математическая логика сформировалась в работах Д. Буля (1815 – 1864), Г. Фреге (1848 – 1925), Б. Рассела (1872 – 1970), Д. Гильберта (1862 – 1943).

Математическая логика используется при решении трех групп задач.

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

Во-вторых, это построение формальных теорий (исчислений) для различных математических объектов на основе аксиоматического метода.

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


^ ТЕМА 1. ЛОГИКА ВЫСКАЗЫВАНИЙ

1.1. Определение высказывания


Определение 1.1. Высказыванием называется повествовательное языковое предложение, относительно которого можно сказать истинно оно или ложно.

Пример 1.1.

Следующие утверждения являются высказываниями:

а) Москву основал Юрий Долгорукий.

б) В прямоугольном треугольнике квадрат гипотенузы равен сумме квадратов катетов.

в) 2 2 = 5.

Высказывания а) и б) истинны, а высказывание с) ложно.

Пример 1.2.

Следующие утверждения не являются высказываниями:

а) a + b = 2.

б) Математика – интересный предмет.

В логике высказываний нас интересует не суть высказывания, а его истинность или ложность. Мы говорим, что существуют два истинностных значения: истина и ложь (И и Л). Двухэлементное множество {И, Л} есть множество истинностных значений. Высказывания будем обозначать большими буквами: A, B, C, X, Y,.. Выражение А = И означает, что высказывание А истинно, а X = Л означает, что высказывание X ложно.


^ 1.2. Операции над высказываниями. Алгебра высказываний


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

Отрицанием высказывания А называется высказывание А, которое истинно тогда и только тогда, когда высказывание ^ А ложно. Чтобы составить отрицание А достаточно в разговорном языке сказать “неверно, что А”.

Пример 1.3.

А = “Каспаров – чемпион мира по шахматам”.

А = “Неверно, что Каспаров – чемпион мира по шахматам”.

Отрицание определяется следующей таблицей истинности (таблица 1.1):

Таблица 1.1
А

А

Л

И

И

Л


Конъюнкцией двух высказываний А и B называется высказывание А&B, истинное тогда и только тогда, когда истинны оба высказывания А и B. В разговорной речи конъюнкции соответствует союз “и”.

Пример 1.4.

А = “Треугольник прямоугольный”.

B = “Треугольник равнобедренный”.

А&B = “Треугольник прямоугольный и равнобедренный”.

Конъюнкция определяется следующей таблицей истинности (таблица 1.2):


Таблица 1.2

АB

А&B

Л Л

Л И

И Л

И И

Л

Л

Л

И


Дизъюнкцией двух высказываний А и B называется высказывание АÚB, ложное тогда и только тогда, когда ложны оба высказывания А и B. В разговорной речи конъюнкции соответствует союз “или”.

Пример 1.5.

А = “Иванов юрист”.

B = “Иванов экономист”.

АÚB = “Иванов юрист или экономист”.

Дизъюнкция определяется следующей таблицей истинности (таблица 1.3):


Таблица 1.3

АB

AÚB

Л Л

Л И

И Л

И И

Л

И

И

И


Импликацией двух высказываний А и B называется высказывание А B, ложное тогда и только тогда, когда А истинно, а B ложно. Импликации соответствуют следующие выражения разговорной речи: “А влечет за собой B”; или “из А следует B”; или “если А, то B”.

Пример 1.6.

А = “Треугольник равносторонний”.

B = “В треугольнике все углы равны”.

А B = “Если треугольник равносторонний, то все углы равны”.

Импликация определяется следующей таблицей истинности (таблица 1.4):


Таблица 1.4

АB

АB

Л Л

Л И

И Л

И И

И

И

Л

И


Импликация играет важную роль в логике высказываний. При учете смыслового содержания высказывания (а не только значений истинности), оборот “если, то” подразумевает причинно-следственную связь. Истинность импликации означает лишь то, что, если истинна посылка, то истинно и заключение. При ложной посылке заключение всегда истинно. Так, истинными являются следующие импликации: “Если в доме 5 этажей, то Иванов живет в квартире 50”; “Если идет снег, то 2 2 = 5”.

Пример 1.7.

Рассмотрим четыре высказывания:

A = “Дважды два четыре” = И;

B = “Дважды два пять” = Л;

C = “Снег белый” = И;

D – “Снег черный” = Л.

Образуем четыре импликации:

А C = “Если дважды два четыре, то снег белый” = И И = И;

B C = “Если дважды два пять, то снег белый” = Л И = И;

А D = “Если дважды два четыре, то снег черный” = И Л = Л;

B D = “Если дважды два пять, то снег черный” = Л Л = И.

Эквивалентностью двух высказываний А и B называется высказывание А  B, истинное тогда и только тогда, когда оба высказывания А и B одновременно истинны или ложны. Говорят, что А эквивалентно B или A имеет место тогда и только тогда, когда имеет место B.

Пример 1.8.

А = “Треугольник равнобедренный”.

B = “В треугольнике углы при основании равны”.

А  B = “Треугольник является равнобедренным тогда и только тогда, когда углы при основании равны”.

Эквивалентность определяется следующей таблицей истинности (таблица 1.5):

Таблица 1.5

АB

АB

Л Л

Л И

И Л

И И

И

Л

Л

И


Высказывания вместе с определенными для них операциями образуют алгебру высказываний.


^ 1.3. Формулы логики высказываний. Равносильность формул


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

1. Любая высказывательная переменная, а также константы И, Л есть формула.

2. Если A и B – формулы, то А, AÚB, A&B, АB, АB есть формулы.

3. Ничто, кроме указанного в пунктах 1 – 2, не есть формула.

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

Равносильность формул A и B будем обозначать следующтм образом: A  B.

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

При доказательстве равносильности формул можно использовать принцип двойственности.

Символы &, Ú называются двойственными.

Формула ^ F* называется двойственной формуле F, если она получена из F одновременной заменой всех символов &, Ú на двойственные.

Например, F = AÚ (B&C);

F* = A & (BÚ C).

Принцип двойственности.

Если F G, то F* G

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

Для любых формул A, B, C справедливы следующие равносильности:

1. Коммутативность.

а) A&B B&A (для конъюнкции);

б) AÚB  BÚA (для дизъюнкции).

2. Ассоциативность.

а) A&(B&C)  (A&C)&C (для конъюнкции);

б) AÚ (BÚC)  (AÚB)ÚC (для дизъюнкции).

3. Дистрибутивность.

а) A&(BÚC)  A&BÚA&C (для конъюнкции относительно дизъюнкции);

б) AÚ(B&C)  (AÚB)&(AÚC) (для дизъюнкции относительно конъюнкции).

4. Закон де Моргана.

а) (A&B) Ú B (отрицание конъюнкции есть дизъюнкция отрицаний);

б) (AÚB) A& B (отрицание дизъюнкции есть конъюнкция отрицаний).

5. Идемпотентность.

а) A&A  A (для конъюнкции);

б) AÚA  A (для дизъюнкции).

6. Поглощение.

а) A&(AÚB)  A (1– ый закон поглощения);

б) AÚA&B  A (2– ой закон поглощения).

7. Расщепление (склеивание).

а)A&B Ú A&(B)  A (1–ый закон расщепления);

б) (AÚB) & (AÚB)  A (2–ой закон расщепления).

8. Двойное отрицание.

(A)  A.

9. Свойства констант.

а)A&И  A; б) A&Л  Л; в)AÚИ  И; г) AÚ Л  A; д) Л И; е) И Л.

10. Закон противоречия.

A& A  Л.

11. Закон “исключенного третьего”.

AÚ A  И.

12. AB AÚB (A&B).

13. A~B  (AB)&(BA)  (A&B) Ú (A& ¬B) АÚ B)&( AÚB).

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

Справедливы также обобщенные законы дистрибутивности и обобщенные законы де Моргана:

14. (A1ÚA2Ú...ÚAn)&(B1ÚB2Ú...ÚBm) 

A1&B1ÚA1&B2Ú...ÚA1&BmÚ...ÚAn&B1ÚAn&B2Ú...ÚAn&Bm.

15. (A1&A2&...&An) Ú (B1&B2&...&Bm) 

(A1ÚB1)&(A1ÚB2)&...&(A1ÚBm)&...&(AnÚB1)&(AnÚB2)&...&(AnÚBm).

16. (A1&A2&...&An) A1ÚA2Ú...ÚAn.

17. (A1ÚA2Ú...ÚAn) A1&A2&...&An

В равносильностях 1 – 17 в качестве A, B, Ai, Biмогут быть подставлены любые формулы и, в частности, переменные.

Пример 1.9.

Доказать равносильность формул логики высказываний:

(АB) & (A Ú B)  B.

Преобразуем левую часть, последовательно используя равносильности 12, 14, 10, 5а, 9г, 6б:

(АB) & (A Ú B) А Ú B) & (A Ú B) А & A Ú А &B Ú B & А Ú B & B  А &B Ú B &А Ú B  B.

Равносильность доказана.


^ 1.4. Запись сложного высказывания в виде формулы логики высказываний


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

Пример 1.10.

Рассмотрим простые высказывания:.

^ A = "Будет холодное лето".

B = "Будет дождливое лето".

C = "Будет засушливое лето".

D = "Будет хороший урожай".

Формула (A&B Ú C)  D соответствует сложному высказыванию:

''Если будет холодное и дождливое или засушливое лето, урожай будет плохим".

Язык логики высказываний удобен для записи математических утверждений. Всякая теорема имеет вид импликации: А^ B (прямая теорема); B А (обратная теорема); B А (противоположная теорема).

Пример 1.11.

A = “Треугольник прямоугольный”.

B = “Квадрат одной стороны равен сумме квадратов двух других сторон”

АB (прямая теорема) = “Если треугольник прямоугольный, то квадрат одной стороны равен сумме квадратов двух других сторон”.

B А (обратная теорема) = “Если квадрат одной стороны равен сумме квадратов двух других сторон, то треугольник прямоугольный”.

B А (противоположная теорема) = “Если квадрат одной стороны не равен сумме квадратов двух других сторон, то треугольник не прямоугольный”.

В данном случае все три теоремы верны.

Равносильность АB B А есть основание метода доказательства от противного. Например, для доказательства теоремы : “Если треугольник равнобедренный, то углы при основании равны” (А B) достаточно доказать теорему: “Если углы при основании не равны, то треугольник не равнобедренный” (B А).

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

Пример 1.12.

Дано высказывание “Если политик обещает невыполнимое, то он обманывает людей”:

а) записать его в виде формулы логики высказываний;

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

Введем следующие высказывания:

^ A = ”Политик обещает невыполнимое”.

B = “Политик обманывает людей”.

Данное нам высказывание может быть записано в виде формулы: АB.

Построим отрицание высказывания, воспользовавшись равносильностью 12:

(АB) A&B.

На естественном языке это может быть выражено следующим образом:

“Политик обещает невыполнимое, но он не обманывает людей”.


^ 1.5. Нормальные формы


В алгебре высказываний используют две нормальные фор­мы: дизъюнктивную и конъюнктивную нормальные формы формулы (ДНФ и КНФ).

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

F = K1Ú K2Ú K3Ú . . ., где Ki= A&B&C& . . ..

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

F = D1 & D2 & D3 & . . . , где Di = AÚBÚCÚ . . ..

Наибольшее распространение в логике высказываний по­лучили формулы вида КНФ, элементарные дизъюнкции которых Di принято называть дизъюнктами, а члены каждого дизъюнкта A, B, C – атомами.

Пример 1.13.

Указать, в каких нормальных формах находятся следующие формулы логики высказываний.

a) A – ДНФ и КНФ

b) (AÚB)&C – КНФ

c) A Ú BÚ C – ДНФ и КНФ

d) (AÚB)&(AÚC) – КНФ

e) AÚB&C – ДНФ

f) A& B& C – ДНФ и КНФ

g) A&B Ú A&C – ДНФ

Для каждой формулы логики высказываний функции F имеется равносильная ей дизъюнктивная нормальная форма (ДНФ) и конъюнктивная нормальная форма (КНФ).

^ Алгоритм приведения формул логики высказываний к ДНФ (КНФ).

Шаг 1. Все подформулы F вида A  B (т.е. содержащие импликацию) заменяем на AÚB или на (A&B) (в соответствии с равносильностью 12 раздела 1.3).

Шаг 2. Все подформулы F вида A ~ B (т.е. содержащие эквивалентность) заменяем на (A&B) Ú (A&B) или на (AÚB)&(AÚB) (в соответствии с равносильностью 13).

Шаг 3. Все отрицания, стоящие над сложными подформулами, опускаем по законам де Моргана (в соответствии с равносильностями 4, 19, 20).

Шаг 4. Устраняем все двойные отрицания над формулами (в соответствии с равносильностью 8).

Шаг 5. Осуществляем раскрытие всех скобок по закону дистрибутивности конъюнкции относительно дизъюнкции для ДНФ (в соответствии с равносильностями 3а и 17) или по закону дистрибутивности дизъюнкции относительно конъюнкции для КНФ (в соответствии с равносильностями 3б и 18).

Шаг 6. Для получения более простой формулы целесообразно использовать равносильности 5, 6, 7, 9, 10, 11.

Пример 1.14.

Дана формула F = (A&B)&(AÚB).

Привести формулу к виду ДНФ:

1) F = (AÚB)&(AÚB);

2) F = (A&A) Ú (A&B) Ú (B&A) Ú (B&B);

3) F = (A&B) Ú (B&A).

Пример 1.15.

Дана формула F = (A (BÚC)) D.

Привести формулу к виду КНФ:

1) F = (AÚ(BÚC)) D ;

2) F = (AÚ(BÚC))ÚD ;

3) F = (A&(B)& C)ÚD ;

4) F = (AÚD)&(BÚD)&(CÚD).

Если каждая элементарная конъюнкция (или элементарная дизъюнкция) формулы содержат символы всех переменных, то такая формула называется совершенной. Есть совершенные дизъюнктивные нормальные формы формулы (СДНФ) и совершенные конъюнктивные нормальные формы формулы (СКНФ).

Пример 1.16.

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

a) ^ X&Y&Z – СДНФ и КНФ;

b) X&Y&Z Ú X&Y&Z – СДНФ;

c) XÚYÚZ – СКНФ и ДНФ;

d) X&Z – ДНФ и КНФ;

e) (XÚYÚZ)& (XÚYÚZ) – СКНФ;

f) XÚYÚZ – СКНФ и ДНФ;

g) (XÚY)&(XÚZ) – КНФ.

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

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

^ Алгоритм приведения формулы булевой функции к СДНФ

Шаг 1. Используя алгоритм построения ДНФ, находим формулу F, являющуюся ДНФ данной формулы.

^ Шаг 2. Если в элементарную конъюнкцию Ki формулы F не входит ни переменная A, ни ее отрицание A, то на основании 1- го закона расщепления (равносильность 7а) заменяем Ki на (Ki & A ) Ú (Ki &A).

Шаг 3. В каждой элементарной конъюнкции переставляем конъюнктивные члены так, чтобы для каждого i (i = 1, ..., n) на i-ом месте была либо переменная Ai, либо ее отрицание Ai.

Шаг 6. Устраняем возможные повторения конъюнктивных членов согласно закону идемпотентности для дизъюнкции: Ki Ú Ki  Ki .

Пример 1.17.

F = A&BÚA&C&DÚA&B&C&D.

Преобразовать формулу к виду СДНФ:

1) F = A&B&CÚA&B&CÚA&B&C&DÚA&B&C&DÚ A&B&C&D;

2) F = (A&B&C&D)Ú(A&B&C&D)Ú(A&B&C&D)Ú(A&B&C&D)Ú (A&B&C&D)Ú (A&B&C&D)Ú (A&B&C&D).

Алгоритм нахождения СКНФ полностью повторяет алгоритм нахождения СДНФ, если произвести двойственную замену & на Ú и Ú на &.

Пример 1.18.

F = (AÚB)) &(AÚBÚCÚD).

Преобразовать формулу к виду СКНФ:

1) F = (AÚBÚC) &(AÚBÚC) &(AÚBÚCÚD);

2) F = (AÚBÚCÚD)&(AÚBÚCÚD)&(AÚBÚCÚD) &(AÚBÚCÚD) &(AÚBÚCÚD).

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

^ Алгоритм представления логической функции, заданной таблицей, формулой в СДНФ.

Шаг 1. Выбираем в таблице все наборы переменных A1, A2, ... , A n, для которых значение F равно И.

Шаг 2. Для каждого такого набора (строки таблицы) составляем конъюнкцию переменных, причем в эту конъюнкцию переменная Ai записывается без изменений (т. е Ai), если ее значение равно “И” и со знаком отрицания (т. е Ai), если ее значение равно “Л”.

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

Для получения формулы в СКНФ следует воспользоваться следующим алгоритмом.

^ Алгоритм представления логической функции, заданной таблицей, формулой в СКНФ

Шаг 1. Выбираем в таблице все наборы переменных A1, A2, ... , A n, для которых значение F равно Л

Шаг 2. Для каждого такого набора (строки таблицы) составляем дизъюнкцию переменных, причем в эту дизъюнкцию переменная Ai записывается без изменений (т. е Ai), если ее значение равно “Л” и со знаком отрицания (т. е Ai), если ее значение равно “И”.

Шаг 3. Составляем конъюнкцию всех полученных дизъюнкций. В результате получится формула данной функции в СКНФ.

Пример 1.19.

Записать СДНФ и СКНФ для функции, заданной таблицей истинности (таблица 1.6):

Таблица 1.6

А B C

F(A,B,C)

Л Л Л

Л Л И

Л И Л

Л И И

И Л Л

И Л И

И И Л

И И И

И

Л

Л

И

И

Л

Л

И


a) Формула СДНФ:

F(A,B,C) = А&B&C Ú А&B&C Ú А&B&C Ú А&B&C;

b) Формула СКНФ:

F(A,B,C) = (AÚBÚC) &(AÚBÚC) & (AÚBÚC) &(AÚBÚC).

Замечание. Т. к. всего строк в таблице функции 2n, то, если число дизъюнктивных членов в СДНФ равно p, а число конъюнктивных членов в СКНФ равно q, то p+q=2n.

Так, для функции, рассмотренной в примере 1.19, n = 3, p = 4, q = 4, p + q = 8 = 23.


^ 1.6. Тождественно-истинные и тождественно-ложные формулы. Проблема

разрешимости


Определение 1.3. Формула называется тождественно-истинной (тавтологией), если для любых наборов переменных она принимает значение И.

Определение 1.4. Формула называется тождественно-ложной, если для любых наборов переменных она принимает значение Л.

Определение 1.5. Формула называется выполнимой, если для некоторых наборов переменных она принимает значение И.

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

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

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

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

Пример 1.20.

Доказать, что формула F = (АB) ((C Ú А) (C Ú B)) является тождественно-истинной.

Последовательно применяя равносильные преобразования, приведем нашу формулу к КНФ:

(АB) ((CÚА) (CÚB)) (АB) Ú ((CА) (CÚB)) (А&B) Ú (CÚА) Ú (C Ú B)(А&B) Ú (C&А) Ú (CÚB) (А Ú C)& (АÚ А) &(BÚC) &(BÚА) Ú (CÚB) (АÚC)&(BÚC)&(BÚА) Ú (CÚB) (АÚCÚCÚB)&(BÚCÚCÚB)&(BÚАÚCÚB).

В первую дизъюнкцию входят C и C. Во вторую – B и B, C и C. в третью – B и B. Следовательно, на основании теоремы 1.1 можно утверждать, что исходная формула является тождественно-истинной.

Так как всякой формуле соответствует таблица истинности, то тождественная истинность или тождественная ложность формулы может быть установлена двумя путями:

1) приведением с помощью равносильных преобразований к КНФ или ДНФ;

2) составлением таблицы истинности.

Пример 1.21.

Установить, является ли тождественно-истинной данная формула логики высказываний: F(A, B) = (А&(АB)) B.

1) Последовательно применяя равносильные преобразования, приведем нашу формулу к КНФ:

(А&(АB)) B (А&(АÚB)  B (А&(АÚB)  B АÚ(АÚB)ÚB АÚ(А&B)ÚB (АÚB) ÚА&B (АÚBÚА)&(АÚBÚB).

В первую дизъюнкцию входят A и A. Во вторую – B и B, поэтому формула является тождественно истинной, F(A, B)  И.

2) Составим таблицу истинности F(A, B) (таблица 1.7):


Таблица 1.7

АB

АB

А&(АB)

(А&(АB))B

Л Л

Л И

И Л

И И

И

И

Л

И

Л

Л

Л

И

И

И

И

И



Из таблицы 1.7 видно, что F(A, B)  И.


^ 1.7.Формализация рассуждений. Правильные рассуждения


Рассуждение – это построение нового высказывания D на основании уже имеющихся высказываний P1, P2, ... , Pn. Высказывания P1, P2, ... , Pn называются посылками, а высказывание D – заключением.

Определение 1.6. Рассуждение называется правильным, если из конъюнкции посылок следует заключение, т. е. формула P1& P2& ... & Pn  D тождественно-истинна.

Таким образом, если все посылки истинны (т. е. их конъюнкция равна И), то истинное заключение соответствует правильному рассуждению, а ложное заключение – неправильному. При ложности хотя бы одной из посылок независимо от истинностного значения заключения рассуждение будет правильным.

Схематически рассуждение изображается следующим образом:

P1, P2, ... , Pn

D

Пример 1.22.

Проверить правильность следующих рассуждений:

а) “Если книга сложная, то она неинтересная. Эта книга интересная. Значит, она несложная”.

Введем высказывания: А = “Книга сложная”; ^ B = “Книга интересная”. Схема рассуждения имеет вид:

А  B, B

А

Докажем, что формула ((А  B) & B) А является тождественно-истинной. Приведем эту формулу к КНФ и воспользуемся теоремой 1.1:

((А  B)&B)  А ((А  B)& B) Ú A  (A & B) ÚBÚ A  (А ÚB Ú A)&(AÚ B Ú B)  И.

Значит, рассуждение правильное.

б) “Если будет хорошая погода, я пойду гулять. Если будет плохая погода, я буду читать книгу. Погода будет хорошая. Следовательно, я не буду читать книгу”.

Введем высказывания: ^ А = “Будет хорошая погода”; B = “Я пойду гулять”. C = “Я буду читать книгу”. Схема рассуждения имеет вид:

А  B, A  С, A.

С

Найдем КНФ формулы ((А  B) & (A  С) & A) C:

((А  B) & (A  С) & A) C ((А  B) & (A  С) & A) ÚC (А  B) Ú (A  С) ÚA) ÚC А & B Ú A & С ÚA ÚC А & B Ú A ÚC (А Ú A ÚC) & (B Ú A ÚC) B Ú A ÚC.

Полученная КНФ нашей формулы не содержит одновременно какой-либо переменной и ее отрицания. Следовательно, формула не является тождественно-истинной, а рассуждение не является правильным.




^ Контрольные вопросы к теме 2


1. Как называется сложное высказывание,

а) истинное тогда и только тогда, когда все составляющие его простые высказывания истинны?

б) истинное тогда и только тогда, когда составляющие его простые высказывания либо вместе истинны, либо вместе ложны?

в) истинное тогда и только тогда, когда истинно хотя бы одно из составляющих его простых высказываний?

г) ложное тогда и только тогда, когда первое простое высказывание истинно, а второе ложно?

Варианты ответа: 1 – дизъюнкция; 2 – конъюнкция; 3 – импликация; 4 – эквивалентность.

2. Какое из следующих утверждений верно:

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

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

в) Рассуждение является правильным, если конъюнкция посылок и заключения является тождественно-истинной формулой.

3. Какие из следующих утверждений верны:

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

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

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

^ ТЕМА 2. ЛОГИКА ПРЕДИКАТОВ

2.1. Определение предиката. Кванторы


Определение 2.1. Предикатом P(x1, x2, ... , xn) называется функция, аргументы которой определены на некотором множестве М, x1, x2, ... , xnM, а сама она принимает два значения: И (истина) и Л (ложь). Таким образом, предикат осуществляет отображение М {И, Л}.

Переменные x1, x2, ... , xnназываются предметными переменными, а множество M – предметной областью.

Если все переменные x1, x2, ... , xn принимают конкретные значения, то предикат есть не что иное, как высказывание, Таким образом, высказывание является частным случаем предиката. Можно сказать, что предикат есть высказывание, зависящее от параметров.

Пример 2.1.

а) P(x) = “x – четное число”. Здесь М – множество целых чисел, xM.

б) A(x, y, z) = “x, y, z лежат на одной окружности”. Здесь М – множество точек плоскости, x, y, z M

в) B(x, y) = “x старше y”. Здесь M – множество людей, x, yM.

Предикат от n переменных называется n-местным предикатом. Высказывание есть 0-местный предикат.

Как видно из примера 2.1, одноместный предикат отражает свойство некоторого объекта, а многоместный предикат выражает отношение между многими объектами.

Над предикатами можно производить обычные логические операции и получать при этом другие предикаты. Таким образом можно говорить об алгебре предикатов.

Пример 2.2.

Пусть A(x) – предикат “x делится на 3”, а B(x) – предикат “x делится на 2”. Тогда A(x) Ú B(x) – предикат “x делится на 3 или на 2”, а A(x) & B(x) – предикат “x делится на 3 и на 2”.

Кроме операций логики высказываний, в логике предикатов используются особые логические символы – кванторы (были введены немецким математиком Г. Фреге).

^ Квантор общности. Пусть P(x) – некоторый предикат, определенный для каждого x  М. Тогда выражение xP(x) является истинным высказыванием, если P(x) истинно для всякого x  М и ложным в противном случае. Символ x называется квантором общности. Выражение xP(x) читается: “Для всех x имеет место P(x)”. В обычной речи квантору общности соответствуют слова: все, всякий, каждый, любой. Возможно отрицание квантора общности: xP(x): “Не для всех x имеет место P(x)”.

Пример 2.3.

Пусть P(x) – предикат “x – четное число”. Тогда xP(x) есть высказывание “Всякое x – четное число" = “Все числа – четные", которое истинно на множестве M четных чисел и ложно, если М содержит хотя бы одно нечетное число, например, если M – множество целых чисел. Отрицание xP(x) есть высказывание “Не всякое x – четное число" = “Не все числа – четные", которое истинно на множестве целых чисел и ложно на множестве четных чисел.

^ Квантор существования. Пусть P(x) – некоторый предикат, x  М. Тогда выражение xP(x) является истинным высказыванием, если P(x) истинно хотя бы для одного x  М и ложным в противном случае. Символ x называется квантором существования. Выражение xP(x) читается: “Существует x, для которого имеет место P(x)”. В обычной речи квантору существования соответствуют слова: некоторый, несколько. Возможно отрицание квантора существования: xP(x): “Не существует x, для которого имеет место P(x)”.

Кванторы существования и общности называются двойственными кванторами.

Пример 2.4.

Пусть, как и в примере 2.3, P(x) – предикат “x – четное число”. Тогда xP(x) есть высказывание “Некоторые x – четные числа” = “Существуют четные числа”, которое истинно на множестве M, содержащем хотя бы одно четное число и ложно, если М содержит только нечетные числа. Высказывание xP(x) = “Неверно, что некоторые x – четные числа” = “Не существует четных чисел” истинно на множестве M, содержащем только нечетные числа и ложно, если М содержит хотя бы одно четное число.

Буква x, стоящая справа от квантора, называется кванторной переменной и должна присутствовать обязательно. Переменная, стоящая под знаком квантора, называется также связанной переменной. Несвязанная переменная называется свободной. Выражения xP(x) и xP(x) не зависят от x и имеют вполне определенные значения. Поэтому переименование связанной переменной, т. е. переход, например, от выражения xP(x) к yP(y) не меняет его истинностного значения.

Кванторы могут применяться и к многоместным предикатам. При этом число свободных переменных уменьшается на единицу. Одноместный предикат при связывании переменной квантором становится 0-местным предикатом, т. е. высказыванием.


^ 2.2. Формулы логики предикатов. Равносильность формул


Определение 2.2. Формула логики предикатов определяется индуктивно следующим образом:

1. Любая формула логики высказываний есть формула логики предикатов.

К новым формулам логики предикатов относятся следующие выражения:

2. Если x, y, z, ... – предметные переменные, то предикаты P(x), Q(x, y), ... , а также выражения с кванторами xP(x), xR(x), xyQ(x, y), ... есть формулы.

3. Если A и B – формулы, то A, AÚB, A&B, AB, AB есть формулы, в которых свободные переменные формул A и B остаются свободными, а связанные переменные формул A и B остаются связанными.

4. Ничто, кроме указанного в пунктах 1 – 3, не есть формула.

Пусть ^ A – формула, содержащая свободную переменную x. Тогда xA, xA – формулы, причем в первом случае A является областью действия квантора общности, а во втором – областью действия квантора существования.

Пример 2.5.

1. Следующие выражения являются формулами логики предикатов:

а) A & B C, где A, B, C – высказывания.

б) xyQ(x, y, z) & xyP(x, y, u).

Проанализируем последовательно это выражение.

Предикат Q(x, y, z) – формула;

Выражение xyQ(x, y, z) – формула; переменные x, y – связанные, переменная z – свободная.

Предикат P(x, y, u) – формула.

Выражение xyP(x, y, u) – формула; переменные x, y – связанные, переменная u – свободная.

Выражение xyQ(x, y, z) & xyP(x, y, u) – формула; переменные x, y – связанные, переменные z, u – свободные.

2. Выражение xyP(x, y, z) Q(x, y, z) формулой не является. Действительно, выражение xyP(x, y, z) есть формула, в которой переменные x и y связанные, а переменная z свободная. Выражение Q(x, y, z) также формула, но в ней все переменные x, y, z свободные.

Определение 2.3. Формулы F и G, определенные на некотором множестве М, называются равносильными на этом множестве, если при любых подстановках констант вместо переменных они принимают одинаковые значения.

Определение 2.4. Формулы, равносильные на любых множествах, будем называть просто равносильными.

Переход от одних формул к равносильным им другим формулам логики предикатов может быть произведен по следующим правилам:

1. Все равносильности, имеющие место для логики высказываний, переносятся на логику предикатов.

Пример 2.6.

а) x(A(x) yB(y))x(A(x) Ú yB(y)).

б) xA(x) (B(z)xC(x)) (xA(x)) Ú B(z) Ú xC(x).

в) (xA(x) yB(y))C(z)  (xA(x)  yB(y)) Ú C(z) ((xA(x)) Ú yB(y) Ú C(z)xA(x) & (yB(y)) Ú C(z).

2.Перенос квантора через отрицание.

Пусть A – формула, со