Мат_Логика(лекции)

МАТЕМАТИЧЕСКАЯ ЛОГИКА

§0. ВВЕДЕНИЕ

Логика – анализ методов рассуждений.

Математическая логика (МЛ) – анализ методов математических рассуждений с использованием математического аппарата. Более узкая цель МЛ – дать точное определение понятия "математическое доказательство".

Отдельные логические законы изучались еще в Древней Греции (Аристотель, IV в. до н.э.). Идея Лейбница: создать науку, которая обозначит все понятия символами и установит над ними новую алгебру. Тогда, по словам Лейбница, истинное утверждение можно будет вычислить.

Дж. Буль в середине XIX в. начал реализовывать эту идею (булевы алгебры).

Хотя элементы логики изучались еще в Древней Греции, как науки математической логики не существовало до начала XX в. Это связано с тем, что считалось: для определения правильности доказательства достаточно интуиции.

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

По своей природе парадоксы можно разделить на логические и семантические или языковые (т.е. связанные со смысловой структурой языка).

Примеры. Парадокс Б.Рассела (1902 г.) (логический). (Его вариант – парадокс "древний парикмахер".)

Рассмотрим множество A всех таких множеств X, что X не есть элемент X. (Пример: X

– множество студентов в группе. Оно не является элементом самого себя, т.к. группа не является студентом. Обратный пример: X – множество всех множеств целых чисел. Оно является элементом самого себя.)

Если A A, то A не является элементом A. С другой стороны, если A A, то по определению A является элементом A – противоречие.

Если A / A, то A является элементом A, т.е. A A – противоречие.

Парадокс Берри (1906 г.) (семантический).

Рассмотрим выражение: "наименьшее натуральное число, которое нельзя назвать посредством меньше, чем тридцати трех слогов". Это выражение определяет натуральное число, назовем его n. По определению, n нельзя назвать посредством меньше, чем 33 слогов. Но приведенное выражение определяет n и содержит 32 слога.

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

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

1

§1. ЛОГИКА ВЫСКАЗЫВАНИЙ (ЛВ)

1.1. Высказывания.

Объектом изучения ЛВ являются высказывания и операции нади ними.

Определение. Высказывание – это законченное предложение, содержащее ложное или истинное утверждение.

Примеры. 1) 2 > 7 – ложное высказывание (л);

2)1 + 3 = 4 – истинное высказывание (и);

3)сумма углов треугольника равна 180◦ – истинное высказывание (и);

4)если две различные прямые на плоскости не параллельны, то они пересекаются – истинное высказывание (и);

5)если две различные прямые в пространстве не параллельны, то они пересекаются – ложное высказывание (л).

Замечание. Не всякое предложение является высказыванием. Например, ”p – простое число ” – не есть высказывание, т.к. p не определено.

1.2. Операции над высказываниями.

В логике высказываний есть операции: p q										(конъюнкция), p q					(дизъюнкция), p¯
(отрицание), p→q				(импликация). Определим их таблицами истинности:
	p	q	p q			p	q	p q			p	q	p→q
	1	1		1		1	1	1			1	1	1			p	p¯
	1	0		0		1	0	1			1	0	0			1	0
	0	1		0		0	1	1			0	1	1			0	1
	0	0		0		0	0	0			0	0	1

Замечание. Есть еще операция p ↔ q (эквиваленция), равная по определению (p→q) (p ← q).

Это примеры функций алгебры логики, т.е. функций от n логических переменных f : {и,л}n→{и,л}.

Пример. Функции f алгебры логики – счетчик f(p1, p2, p3) голосования ("по большинству").

Контрольный вопрос: сколько существует функций алгебры логики от n переменных? Ответ: 22n .

1.3. Формулы ЛВ. Некоторые законы ЛВ.

Определение. Алфавит – это:

1)переменные высказывания p, q, r, p1, q1, r1, ...;

2)логические связки , , ¯, →;

3)вспомогательные символы ( , ).

2

Определение. Формула – это:

1)	символ переменного высказывания – формула;
2)	¯
	если A, B – формулы, то A B, A B, A→B, A – формулы;
3)	других формул нет.

Примеры. 1) (¯p q)→r;

2) (((p→q q) (r p¯)).

Упрощение записи: важнее , важнее →.

Определение подформулы формулы A:

1.Если A -переменное высказывание, то подформулой формулы A является она сама.

2.Если A имеет вид A = A1 A2, где {, , →}, и подформулы A1 и A2 определены, то подформулами формулы A являются по определению все подформулы формул A1 и A2, а также формула A.

3.Если A имеет вид A1 и подформулы формулы A1 определены, то подформулами формулы A будут она сама и множество подформул формулы A1.

Пример: множеством подформул формулы (¯p q→r) является следующе множество:

{p¯ q→r, p¯ q→r, p¯ q, r, p,¯ q, p, }

Определение глубины подформулы формулы A:

1.Подформула, равная A, имеет глубину 0.

2.Если подформула вида A1 A2, где {, , →}, имеет глубину K, то подформулы A1 и A2 имеют глубину K + 1.

3. Если подформула вида ¯ имеет глубину , то подформула имеет глубину .

A K A K + 1

Пример: Дана формула: A = p q¯ → r. Укажем глубину ее подформул: A имеет глубину 0, p q,¯ r имеют глубину 1, p, q¯ имеют глубину 2, q имеет глубину 3.

1.4. Тавтологии.

Определение Тавтологии (тождественно истинные формулы, законы логики) - это формулы, принимающие значение "И" при любых истинностных значениях входящих в них переменных высказываний.

Примеры основных тавтологий (законов логики):

1)p p¯ – закон исключенного третьего;

2)p→(q→p);

3)(p→q)→((q→r)→(p→r)) – закон силлогизма;

4)(p→q)→(¯q→p¯) – закон контрапозиции;

5)(p→q) ↔ p¯ q;

6)A A ↔ A, A A ↔ A – законы идемпотентности;

3

7)A B ↔ A B, A B ↔ A B – законы де Моргана;

8)A ↔ A – закон двойного отрицания;

9)(A→(B→C)) ↔ (B→(A→C)) – закон перемены посылок;

10)A B ↔ B A, A B ↔ B A – законы коммутативности;

11)A (B C) ↔ (A B) C, A (B C) ↔ (A B) C – законы ассоциативности;

12)A (B C) ↔ (A B) (A C), A (B C) ↔ (A B) (A C) – законы дистрибутивности.

1.5. Равносильность формул.

Определение Равносильные формулы – такие, которые принимают одинаковые значения при любых входящих в них значениях переменных высказываний. Обозначаются равносильные формулы так: A = B (иногда также A ≡ B или A B).

Примеры.

p¯ q = p→q;

p q = q p; p q = q p;

p q = p¯ q¯;

p q = p¯ q¯;

p¯ = p;

p = p ≡ p,

p p = p;

(p q) r = p (q r);

(p q) r = p (q r);

p (q r) = p q p r;

p (q r) = (p q) (p r).

1.6. Правила получения новых равносильностей из старых.

1. Правило подстановки. Если A(p) = B(p), где A(p) и B(p) – формулы, содержащие переменную p, а C – произвольная формула, то A(C) = B(C), где A(C) – формула, полученная заменой всех вхождений переменной p на формулу C, и аналогично для B(C).

Краткая запись:

A(p) = B(p)

A(C) = B(C)

2. Правило замены.

A(p) – формула, B = B0

A(B) = A(B0)

Пример: упростить формулу p¯ q→p q.

p¯ q→p q = p¯ q p q = p¯ q¯ p q p q¯ p q = p (¯q q) = p.

Ответ: p¯ q→p q = p.

4

§2. ПРЕДСТАВЛЕНИЕ ФУНКЦИЙ ЛОГИКИ ВЫСКАЗЫВАНИЙ ФОРМУЛАМИ

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

Определение. Конъюнкция (дизъюнкция) простейших высказываний называется элементарной.

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

p,	α = 1;	00 = 1, 01 = 0, 10 = 0, 11 = 1.
Обозначения. Для α {0, 1} полагаем pα = p,¯	α = 0;

Теорема 1. Всякую функцию алгебры логики f(p1, ..., pn) можно представить в виде (СДНФ)

f(p1, ..., pn) =		_{	0,1	}	n p1σ1 p2σ2 ... pnσn f(σ1, ..., σn) =: f˜(p1, ..., pn).
	(σ1,...,σk)
Доказательство. Для произвольного набора (α1, ..., αn) {0, 1}n имеем
						f˜(α1, ..., αn) =
α1	α2				αn	(α1	,_...,αn6)	σ1	σk	σn
= f(α1, ..., αn) α1								, ..., σn) α1	... αk	... αn ) =
	α2 ... αn (						f(σ1

(σ1,...,σn)=

= f(α1, ..., αn).

(Здесь использованы равенство

α1 α2α2 ... αnαn = 1 1 ... 1 = 1

и равенства

f(σ1, ..., σn) α1σ1 ... αkσk ... αnσn = 0, (σ1, ..., σn) 6= (α1, ..., αn)

верные в силу того, что для (σ1, ..., σn) 6= (α1, ..., αn) существует k, 1 ≤ k ≤ n, такое, что

αkσk = 0.)

Пример.

p1	p2	p3	f(p1, p2, p3)
1	1	1	1
1	1	0	0
1	0	1	1
1	0	0	0
0	1	1	1
0	1	0	0
0	0	1	1
0	0	0	1

f = p1 p2 p3 p1 p¯2 p3 p¯1 p2 p3 p¯1 p¯2 p3 p¯1 p¯2 p¯3 = p2 p3 p¯2 p3 p¯1 p¯2 p¯3 = p3 p¯1 p¯2 p¯3.

5

Другой вариант теоремы 1:
f(p1, ..., pn) =	_ n	(p1σ1 ... pnσn ).	(A)
f(σ1,		)=1
	...,σ

Переходя к отрицаниям, получаем из теоремы 1 следующую теорему.

Теорема 2. (об СКНФ) Всякую функцию логики высказываний f(p1, ..., pn) можно представить в виде (называемом совершенной конъюнктной нормальной формой – СКНФ):

f = f(σ		σ¯		σ¯		σ¯		σ¯	p,	если si = 0;
	,...,σ	)=0(p1	1	p2	2	... pnn ),	p		= p,¯	если si = 1.
1	^ n

Доказательство. Перейти к отрицаниям в формуле (A).

§3. ПОЛНЫЕ СИСТЕМЫ ФУНКЦИЙ ЛОГИКИ ВЫСКАЗЫВАНИЙ

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

Пример: Система {¯, , } является полной – см. теорему 1 выше.

Предложение 1. Системы {¯, }, {¯, }, {¯, →} – полные.

Доказательство.

			¯	¯			{¯, } – полная система;
A B = (A				B)
			¯	¯			{¯, } – полная система;
A B = (A				B)
A		¯		B
		B = A					{¯, →} – полная система.
A	B = A→B¯
			→

Определение. Функция ( | ), задаваемая таблицей

A	B	( | )
1	1	0
1	0	1
0	1	1
0	0	1

называется штрихом Шеффера.

Определение. Функция ( ↓ ), задаваемая таблицей

A	B	( ↓ )
1	1	0
1	0	0
0	1	0
0	0	1

называется стрелкой Пирса.

Предложение 2. Системы ( | ) и ( ↓ ) – полные.

6

Доказательство.

(i) Система ( | ) полна, так как

¯ | | | |

A = A A, A B = (A A) (B B).

(i) Система ( ↓ ) полна, так как

¯ ↓ ↓ ↓ ↓

A = A A, A B = (A A) (B B).

Обозначения: (i) A B читается "если A, то B".

(ii) Если формула A является тавтологией, то пишут |= A.

Пример.
|= p p¯	– закон исключенного третьего;
|= (p→q)↔(¯q→p¯)	– закон контрапозиции;
|= (p→q)↔(¯p q).

7

§4. ЛОГИЧЕСКОЕ СЛЕДОВАНИЕ

Определение. Пусть даны формулы A = A(p1, ..., pn) и B = B(p1, ..., pn). Говорят, что формула B логически следует из формулы A, если при всех значения переменных p1, ..., pn, при которых формула A принимает значение И, формула B также принимает значение И.

Обозначение: A |= B.

Замечание 1. Нетрудно проверить, что (i) A |= B тогда и только тогда, когда |= A→B;

(ii) A = B A |= B.

Примеры:

1. (p→q) |= (q→r)→(p→r);
2. (p→q) |= (p r→q r);
¯
3. A B→C |= A→B C.
¯	¯	¯
Действительно, A B→C |= A B C |= A	B C |= A→B C.

Аналогично предыдущему определению дается

Определение. Пусть даны формулы A1 = A1(p1, ..., pn), ..., Am = Am(p1, ..., pn), B =

B(p1, ..., pn). Говорят, что формула B логически следует из формул A1, ..., Am, если при всех значения переменных p1, ..., pn, при которых фломулы A1, ..., Am принимают значения И, формула B также принимает значение И.

Обозначение: A1, ..., Am |= B.

Замечание 2. Нетрудно проверить, что (i) если A1, ..., Am |= B1, ..., A1, ..., Am |= Bn и

B1, ..., Bn |= C, то A1, ..., Am |= C;

|¯ | ¯

(ii)если A = B, то B = A.

Примеры:
1. A→B, B→C |= A→C;
				¯		¯	¯
2. F →G, K→H, H G |= F →K.
Действительно,
		¯		¯				K.¯
F	K→H |= H→K					= F	→
	→	G, G	→	H = F	→	H |
				|

§5. ИСЧИСЛЕНИЕ ВЫСКАЗЫВАНИЙ (ИВ) КАК ФОРМАЛЬНАЯ АКСИОМАТИЧЕСКАЯ ТЕОРИЯ

5.1. Аксиоматический метод в математике.

Построение математических теорий как аксиоматических теорий проводилось с древних времен. При этом в теории выделялись основные (неопределяемые) понятия и свойства этих понятий задавались системой аксиом. Примером такой аксиоматической теории может служить геометрия Евклида. Методы доказательств в этих теориях первоначально были интуитивными, непосредственно в теории не задавались. Язык этих теорий тоже оставался произвольным. Парадоксы, открытые в конце XIX века (типа вышеупомянутых)

8

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

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

План построения формальной аксиоматической теории таков:

1.Определяется алфавит теории.

2.Определяются формулы теории, т.е. слова, построенные в заданном алфавите.

3.Задается система аксиом как некоторая конечная совокупность формул теории.

4.Определяются правила доказуемости.

5.Дается определение доказуемых формул теории, т.е. теорем.

Это определение формализуется следующим образом:

1.Всякая аксиома – доказуемая формула.

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

Пример формальной аксиоматической теории – исчисление высказываний.

5.2. Исчисление высказываний (ИВ) как формальная аксиоматическая теория.

Исчисление высказываний – пример формальной аксиоматической теории.

Алфавит ИВ – это буквы: A, B, C, ..., логические связки: , ,¯, →, скобки: ( ). Формулы (слова) ИВ получаются применением логических связок к буквам алфавита.

Аксиомы ИВ – это формулы A1 – A10:

A1 : A→(B→A)

A2 : (A→B)→((A→(B→C))→(A→C))

A3 : A→(B→A B)

A4 : (A→C)→((B→C)→(A B→C))

A5 : A B→A

A6 : A B→B

A7 : A→A B

A8 : B→A B

A9 : (A→B)→((A→B)→A)

A10 : A→A

Правила доказуемости (правила вывода) в ИВ таковы:

1. Правило подстановки: пусть A(p1, ..., pn) – формула, содержащая переменные p1, ..., pn и B1, ..., Bn – формулы. Тогда говорят, что формула A(B1, ..., Bn) получена подстановкой формул B1, ..., Bn в формулу A.

(Здесь иногда используется обозначение: A(B1, ..., Bn) = ABp11......pBnn .)

2. Правило заключения (модус поненс, modus ponens, MP):

Пусть даны две формулы A и A→B. Тогда говорят, что формула B получена по правилу вывода из формул A и A→B, и обозначают это так: A, A→B ` B.

9

5.3. Доказуемые (выводимые) формулы.

1.По определению аксиомы – доказуемые формулы.

2.Формулы, полученные из доказуемых подстановкой или по правилу заключения(МР), доказуемы.

3.Других доказуемых формул нет.

Обозначение доказуемой формулы A:

` A.

Пример 1: ` (A→A).

Доказательство.

1.

(A

→

(B

→

A)) ((A

→

((B

→

A)

→

A)) (A

→

A));

A B→A,

A

;

→

→

1 B

C

2. A→(B→A);

A1;

3.

(A→((B→A)→A))→(A→A);

MP (1, 2);

4.

A

→

((B

→

A)

→

A);

A B→A;

1 B

5.

A→A;

MP (3, 4).

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

(Напомним, что тавтологией называется формула ИВ, принимающая значение И при любых значениях входящих в нее переменных. Обозначение тавтологии A: |= A.

Теорема 1. Всякая доказуемая формула ИВ является тавтологией:

` A |= A.

Доказательство (схема).

(1)Проверим, что все аксиомы A1 − A10 являются тавтологиями (с помощью таблиц истинности).

(2)Проверяем, что формула, полученная из доказуемых формул посредством правил доказуемости, является тавтологией.

Определение. Говорят, что формула A выводима из формулA1, ..., Am, и

обозначают это так:

A1, ..., Am ` A,

если A получается последовательным применением правил доказуемости к формулам A1, ..., Am и аксиомам либо доказуемым формулам. При этом формулы A1, ..., Am называются посылками, а формула A – заключением.

Замечание. Из этого определения непосредственно следует, что

A` AB	` B,
`

т.е.всякая формула, выводимая из доказуемой формулы, доказуема.

Пример 2. A ` A.

Доказательство.

10