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

ВВЕДЕНИЕ

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

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

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

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

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

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

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

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

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

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

Пример 1.1.

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

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

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

в) 2 2 = 5.

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

Пример 1.2.

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

а) a + b = 2.

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

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

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

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

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

F = K₁Ú K₂Ú K₃Ú . . ., где K_i = A&B&C& . . ..

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

F = D₁ & D₂ & D₃ & . . . , где D_i = AÚBÚCÚ . . ..

Наибольшее распространение в логике высказываний по­лучили формулы вида КНФ, элементарные дизъюнкции которых D_i принято называть дизъюнктами, а члены каждого дизъюнкта 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. Если в элементарную конъюнкцию K_i формулы F не входит ни переменная A, ни ее отрицание A, то на основании 1- го закона расщепления (равносильность 7а) заменяем K_i на (K_i & A ) Ú (K_i &ØA).

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

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

Пример 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. Выбираем в таблице все наборы переменных A₁, A₂, ... , A _n, для которых значение F равно И.

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

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

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

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

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

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

Шаг 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).

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

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

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

Определение 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) º И.

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

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

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

1 Символы исчисления высказываний включают в себя: а) знаки логических операций Ø, É; б) буквы X_i с целыми положительными индексами i; в) скобки и запятую – ( , ).

2. Формулами исчисления высказываний являются:

а) все переменные X_i;

б) если A и B – формулы, то ØA – формула и A É B – формула.

Хотя для исчисления высказываний выбраны только два логических символа Øи É и только два типа формул ØA и A É B, можно с помощью следующих известных равносильностей ввести и другие логические символы и формулы:

A & B º Ø(A É ØB);

A Ú B º ØA É B;

A ~ B º Ø(( A ÉB) É Ø( B É A )).

3. Аксиомы исчисления высказываний. Существуют различные системы аксиом исчисления высказываний, обладающие свойствами непротиворечивости, независимости и полноты. Будем использовать следующую систему аксиом:

А1. A É (B É A);

А2. (A É (B É C)) É ((A É B) É (A É C));

А3. (ØB É ØA) É ((ØB É A) ÉB).

Непосредственной проверкой можно убедиться, что аксиомы есть тождественно-истинные формулы. Например, для аксиомы А1:

A É (B É A) º ØA Ú ØB Ú A º И.

4. Правило вывода в исчислении высказываний одно – modus ponens (m. p.) – правило заключения:

, или A, AÉB ├ B.

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

Пример 3.1.

Если в правиле modus ponens переменную B заменить формулой A&B, получим правило вывода

.

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

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

Пример 3.2.

Построим вывод формулы A ├ B ÉA.

(1) A – гипотеза;

(2) A É (B É A) – аксиома А1;

(3) B É A – из (1) и (2) по m. p.

Очевидно, что любую равносильную формулу можно рассматривать как правило вывода. Например, закон де Моргана может быть представлен как следующее правило вывода: . Равносильность A É B º ØB É ØA порождает закон контрапозиции: .

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

1. Введение конъюнкции: .

2. Удаление конъюнкции: и .

3. Отрицание конъюнкции: .

4. Введение дизъюнкции: и .

5. Удаление дизъюнкции: и .

6. Отрицание дизъюнкции: .

7. Введение импликации: .

8. Удаление импликации: (m. p.) и .

9. Отрицание импликации: .

10. Введение эквивалентности: .

11. Удаление эквивалентности: и .

12. Введение отрицания: .

13. Удаление отрицания: .

14. Закон контрапозиции: .

Для построения выводов в исчислении высказываний полезной оказывается следующая теорема.

Теорема дедукции (без доказательства). Пусть Г – множество формул, A и B – формулы, и имеет место вывод: Г, A ├ B. Тогда имеет место следующий вывод: Г ├ A É B.

Таким образом, если нужно вывести формулу вида A É B из множества формул (возможно, пустого), можно использовать дополнительное допущение A.

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

Правило силлогизма (транзитивный вывод).

A ÉB, B ÉC ├AÉC.

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

Пример 3.3.

а) Обосновать вывод A É (B É C), A&B ├ C.

(1) A É (B É C) – гипотеза;

(2) A&B – гипотеза;

(3) A – из (2) и правила удаления конъюнкции;

(4) B É C – из (1), (3) и m. p.

(5) B – из (2) и правила удаления конъюнкции;

(6) C – из (4), (5) и m. p.

б) Обосновать правильность следующего рассуждения, построив вывод:

Если число целое, то оно рациональное, Если число рациональное, то оно действительное. Число целое. Значит, оно действительное.

Сначала формализуем наше рассуждение, введя следующие высказывания:

A = “число целое”.

B = “число рациональное”.

C = “число действительное”.

Нужно построить следующий вывод: A É B, B É C, A ├ C.

Построим этот вывод.

(1) A É B – гипотеза;

(2) B É C – гипотеза;

(3) A – гипотеза;

(4) A É C – из (1) и (2) по правилу силлогизма;

(5) C – из (3) и (4) по m. p.

в) Обосновать правильность следующего рассуждения, построив вывод:

Если бы Иван был умнее Петра, он решил бы эту задачу. Иван не решил эту задачу. Значит, он не умнее Петра.

Формализуем наше рассуждение, введя следующие высказывания:

A = “Иван умнее Петра”.

B = “Иван решил эту задачу”.

Построим следующий вывод: A É B, ØB ├ ØA.

(1) A É B – гипотеза;

(2) ØB – гипотеза;

(3) ØB É ØA – из (1) по закону контрапозиции;

(4) ØA – из (3) и (2) по m. p.

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

Исчисление предикатов определяется следующим образом.

1. Символы исчисления предикатов включают в себя: а) символы предметных переменных x₁, x₂,…, x_n, …; б) символы предметных констант a₁, a₂,…, a_n, …; в) символы или имена предикатов A , A ,…A , …; г) символы или имена функций f , f ,…f , …; д) знаки логических операций Ø, É; е) символы кванторов ", $ ; ж) скобки и запятую – ( , ) ,.

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

2. Понятие формулы исчисления предикатов определяется в два этапа [4].

1) Термы:

а) предметные переменные x₁, x₂,…, x_n, ... и константы a₁, a₂,…, a_n, …;

б) если fⁿ – имя функции, а t₁, t₂,…, t_n – термы, то fⁿ(t₁, t₂,…, t_n) – тоже терм.

2) Формулы:

а) если Aⁿ – имя предиката, а t₁, t₂,…, t_n – термы, то Aⁿ(t₁, t₂,…, t_n) – формула; все вхождения переменных в формулу Aⁿ(t₁, t₂,…, t_n) являются свободными;

б) если A(x) – формула, содержащая свободное вхождение переменной x, то выражения с кванторами "xA(x), $xA(x) – формулы;

в) если A и B – формулы, то ØA, AÉB – формулы, в которых свободные переменные формул A и B остаются свободными, а связанные переменные формул A и B остаются связанными.

Так же, как и в исчислении высказываний, можно ввести знаки других логических операций (&, Ú, ~), используя соответствующие равносильности.

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

Подстановка терма y в формулу A(x) называется правильной, если и только если:

а) y является предметной константой;

б) у является предметной переменной, и все вхождения y, полученные в результате подстановки, оказываются свободными в полученной в результате подстановки формуле. Например, в формулу "y(P(x, y) É Q(x)) вместо x можно подставить либо константу a: "y(P(a, y) É Q(a)), либо переменную z: "y(P(z, y) É Q(z)), но нельзя подставить переменную y, так как после подстановки получим формулу: "y(P(y, y) É Q(y)), в которой переменная y оказывается связанной.

3. Аксиомы исчисления предикатов.

А1. A É (B É A).

А2. (A É (B É C)) É ((A É B) É (A É C)).

А3. (ØB É ØA) É ((ØB É ØA) ÉB).

А4. "xA(x) É A(y), где формула A(x) не содержит переменной y.

А5. A(x) É $yA(y), где формула A(x) не содержит переменной y.

4. Правил вывода в исчислении предикатов четыре:

П1 – modus ponens (m. p.) – правило заключения:

;

П2 – правило связывания квантором общности:

, где формула B не содержит переменной x;

П3– правило связывания квантором существования:

, где формула B не содержит переменной x;

П4 – правило переименования связанной переменной. Связанную переменную в формуле A можно заменить (в кванторе и во всех вхождениях в области действия квантора) другой переменной, не являющейся свободной в A. Например, для формулы "xF(x) É $xG(x) применяя правило переименования, получим формулу "yF(y) É $zG(z).

Для правил П2 и П3 условие, что формула B не содержит переменной x, является существенным. Это подтверждает следующий пример.

Пример 3.4.

Даны два предиката: B(x) = "x делится на 6"; A(x) = "x делится на 3".

Тогда B(x) É A(x) = "Если x делится на 6, то x делится на 3" = И для всех x.

Однако B(x) É "xA(x) = "Если x делится на 6, то все x делятся на 3" не всегда истинно. Таким образом, применение правила П2 неправомерно, если B зависит от x.

Если же к формуле B(x) É A(x) применить правило П3, то получим $xB(x) É A(x). После применения правила П2 получим $xB(x) É "xA(x) = "Если некоторые x делится на 6, то все x делятся на 3" = Л. Таким образом, применение правила П3 также неправомерно, если B зависит от x.

Для исчисления предикатов верны правила вывода 1 – 14 исчисления высказываний (раздел 3.2).

Дополнительные правила вывода для исчисления предикатов следующие:

1. Введение квантора общности: , где A(y) – результат правильной подстановки переменной y вместо x в A(x).

2. Удаление квантора общности: , где A(y) – результат правильной подстановки терма y вместо x в A(x).

3. Отрицание квантора общности: .

4. Введение квантора существования: , где A(y) – результат правильной подстановки терма y вместо x в A(x).

5. Удаление квантора существования: , где A(x) – результат правильной подстановки переменной x вместо y в A(y).

6. Отрицание квантора существования: .

Верна также теорема дедукции. Если Г – множество формул, A и B – формулы, и Г, A „B. Тогда Г „ A É B.

Сформулируем без доказательства важные утверждения для исчисления предикатов

Теорема 3.1. Аксиомы исчисления предикатов – общезначимые формулы.

Теорема 3.2. Любая выводимая в исчислении предикатов формула является общезначимой.

Пример 3.5.

Обосновать правильность рассуждения, построив вывод.

а) Всякое нечетное натуральное число является разностью квадратов двух натуральных чисел. 5 – натуральное число. Следовательно, 5 – разность квадратов двух натуральных чисел

Пусть M – множество натуральных чисел. Введем предикаты:

A(x) = “x – нечетное число”.

B(x) – “x – разность квадратов двух чисел”.

Требуется построить вывод:

"x(A(x) É B(x)), A(5) ├ B(5).

Построим вывод.

(1) "x(A(x) É B(x)) – гипотеза;

(2) A(5) – гипотеза;

(3) A(5) É B(5) – из (1) и удаления ";

(4) B (5) – из (2) и (3) по m. p.

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

Сначала формализуем наше рассуждение, введя следующие предикаты:

A(x) = “x – словарь”.

B(x) = “x – полезен”.

C(x) = “x высоко ценится”.

Требуется построить следующий вывод:

"x(A(x) É B(x)), "x(B(x) É C(x)) ├ "x(A(x) É C(x)).

Построим этот вывод.

(1) "x(A(x) É B(x)) – гипотеза;

(2) "x(B(x) É C(x)) - гипотеза;

(3) A(y) É B(y) – из (1) и удаления ";

(4) B(y) É C(y) – из (2) и удаления ";

(5) A(y) É C(y) – из (3) и (4) по правилу силлогизма;

(6) "x(A(x) É C(x)) – из (5) и введения ".

в) Всякий совершеннолетний человек, находящийся в здравом уме, допускается к голосованию. Джон не допущен к голосованию. Значит, он либо несовершеннолетний, либо не находится в здравом уме.

Формализуем наше рассуждение, введя следующие предикаты:

A(x) = “x – совершеннолетний”.

B(x) = “x находится в здравом уме”.

C(x) = “x допущен к голосованию”.

Введем константу d, обозначающую имя "Джон".

Требуется построить следующий вывод:

"x(A(x)&B(x) É C(x)), ØC(d)) ├ ØA(d) Ú ØB(d).

Построим этот вывод.

(1) "x(A(x)&B(x) É C(x)) - гипотеза;

(2) ØC(d)) - гипотеза;

(3) A(d)&B(d) É C(d) - из (1) и удаления ";

(4) ØC(d)) É Ø(A(d)&B(d)) – из (3) и правила контрапозиции;

(5) ØC(d)) É ØA(d) Ú ØB(d) – из (4) и отрицания конъюнкции;

(7) ØA(d) Ú ØB(d) – из (2) и (5) по m. p.

(8)

ВВЕДЕНИЕ

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

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

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

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

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

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

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

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

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

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

Пример 1.1.

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

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

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

в) 2 2 = 5.

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

Пример 1.2.

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

а) a + b = 2.

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

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

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

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

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

Пример 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
Л Л Л И И Л