48

Пермский Государственный Технический Университет

Кафедра Информационных технологий и автоматизированных систем

Викентьева О. Л.

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

конспект лекций

для студентов специальностей АСУ, ЭВТ, КЗИ

Пермь, 2007 г.

Введение

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

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

Пример 1.

П1: Все люди смертны.

П2. Сократ – человек.

З: Сократ смертен.

Пример 2.

П1: Все граждане России имеют право на образование.

П2: Иванов – гражданин России.

З: Иванов имеет право на образование.

Оба эти вывода имеют одну и ту же форму:

Все А есть В;

С есть А;

Следовательно, С есть В.

В этих рассуждениях нам не интересна истинность или ложность отдельных посылок. Нам важно знать вытекает ли истинность заключения из истинности посылок.

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

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

1.1. Понятие высказывания

Рассмотрим логику высказываний, которая лежит в основе всех других разделов математической логики (МЛ) и необходима для их понимания.

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

Основным объектом логики высказываний служат простые высказывания. Высказывание – это предложение, о котором можно сказать истинно оно или ложно.

Примеры.

1. Число 100 делится на 5.

2. Число 3 больше числа 5.

3. Луна больше Земли.

4. Сегодня светит солнце.

5. Вечером мы пойдем в кино.

Из простых высказываний с помощью некоторого числа логических операций можно построить сложные высказывания.

1. Число 100 делится на 5 и число 100 делится на 10.

2. Неверно, что 3 больше 5.

3. Сегодня мы пойдем в кино или мы пойдем в театр.

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

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

1.2. Логические операции

Для изучения логических операций введем следующую систему обозначений:

• простые высказывания будем обозначать буквами a,b,c, …,x,y,z;

• значения истинности будем обозначать 1 – истинно, 0 – ложно.

Действия логических операций будем представлять в виде таблиц истинности.

1. Отрицание или инверсия ( – не)

Пример.

а: 7 делится на 5 без остатка.

а: Неверно, что 7 делится на 5 без остатка.

а	а
0	1
1	0

Эта таблица и принимается в качестве определения операции отрицания.

2. Конъюнкция ( ,, ·, логическое И )

Действие операции определяется следующим образом: сложное высказывание аbистинно только в том случае, когда оба высказывания (а иb) имеют значение истинно.

а	b	аb
0	0	0
0	1	0
1	0	0
1	1	1

Примеры.

а. 6 делится на 3 без остатка (1);

b. 10 больше 5 (1);

с. 7 делится на 3 без остатка (0);

d. 3 больше 7 (0);

a&b=1

a&c=0

c&d=0

3. Дизъюнкция (,+,логическое ИЛИ)

Действие операции определяется следующим образом: сложное высказывание ав ложно только в том случае, когда оба высказывания (а и в) ложны.

a	b	ab
0	0	0
0	1	1
1	0	1
1	1	1

Примеры.

аb=1

ac=1

cd=0