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

1.

Принцип математической индукции
Пусть P n такое утверждение, что
1) P 1 И,
2) для каждого k , если P k =И, то P k 1 =И.
Тогда P n истинно для любого натурального числа n .
P 1 k P k P k 1 nP n
Принцип математической индукции для целых чисел
Пусть P n такое утверждение, что
1) P j И,
2) для каждого k j , если P k =И, то P k 1 =И.
Тогда P n истинно для каждого n j .
1

2.

Метод «бесконечного спуска»
Используется для доказательства того, что все натуральные числа не
обладают заданным свойством.
Предположим, что
1) T – некоторое множество натуральных чисел, для которых верно
доказываемое утверждение.
2) Если n T , то существует m такое, что m n и m T .
Тогда T .
Предположим, что k1
, обладающее заданным свойством. Потом обра-
зуем второе натуральное число k2 , тоже обладающее этим свойством, но такое, что k2 k1 . Аналогично, образуем натуральное число k3 , обладающее
заданным свойством, и такое, что k3 k2 k1 . Таким образом, получаем бесконечно убывающую последовательность k1 k2 k3 ... натуральных чисел.
Эта последовательность возникла из предположения о том, что существует
натуральное число, которое меньше произвольного фиксированного числа и
обладает заданным свойством. Значит, предположение ошибочно.
2

3.

Пример.
Докажем, что не существуют натуральные числа p и q такие, что
p 2 3q 2 .
Предположим, что для некоторых натуральных чисел p и q выполняется равенство
p 2 3q 2 .
Тогда k p 3k . Следовательно,
p 2 9k 2 3q 2 ,
а значит,
k p и 3k 2 q 2 .
Аналогично, получаем, что существует число m q такое, что
q 3m и k 2 3m 2 .
Методом бесконечного спуска получаем требуемое утверждение.
3

4.

Исчисление предикатов
Алфавит – те же символы, что и в логике предикатов.
Понятие формулы – совпадает с понятием формулы в логике предикатов.
Аксиомы:
1…10 – аксиомы Клини исчисления высказываний;
11) xA(x) A(y) ( -схема);
12) A(y) xA(x) ( -схема).
Система правил вывода:
A, A B
1)
modus ponens (m.p.);
B
C A x
2)
правило обобщения ( -правило);
C yA y
3)
A x C
правило введения ( -правило).
yA y C
4) Правило переименования связанной переменной. Связанную переменную формулы
A можно заменить (в кванторе и во всех вхождениях в области действия квантора)
другой переменной, не являющейся свободной в A.
Понятия вывода, теоремы и доказательства определяются в исчислении предикатов
4
точно так же, как и в любой аксиоматической теории.

5.

Теорема 6. Аксиомы исчисления предикатов – общезначимые формулы.
Теорема 7. Формула, получающаяся из общезначимой
по любому из правил вывода 1–3, является общезначимой.
Теорема 8. Любая выводимая в исчислении предикатов
формула общезначима.
Теорема 9. Исчисление предикатов непротиворечиво.
Теорема Гёделя. Всякая общезначимая формула выводима в исчислении предикатов.
Теорема о дедукции. Если , A B, то A B,
где – последовательность формул A1, A2,..., An.
5

6.

Пример. Вывод x A x x A x .
1.
2.
3.
4.
5.
6.
7.
8.
9.
x A x
посылка,
A y x A x -схема,
x A x A y x A x акс. 1, A x A x , B A y ,
A y x A x m.p. 1 и 3,
A y x A x A y x A x A y
A y x A x A y
акс. 9, A A y , B x A x ,
m.p. 2 и 5,
A y m.p. 4 и 6,
A y x A x A y акс. 1, A A y , B x A x ,
x A x A y
m.p. 7 и 8,
10. x A x x A x -правило к 9 x y, y x ,
11. x A x
m.p. 1 и 10.
6

7.

Пример. Построить вывод x y A A .
2.
3.
4.
5.
1.
посылка,
x y A
x y A y A
-схема, A x yA ,
y A m.p. 1 и 2,
y A A
-схема, A x A ,
m.p. 3 и 4.
A
7

8.

Универсальная конкретизация
xP x P y (аксиома 11 -схема)
Из истинности xP x следует истинность P y для произвольного y
из универсума.
C P y
Универсальное обобщение
( -правило);
C xP x
Если произвольное y из универсума обеспечивает истинность P y ,
то делаем вывод, что xP x истинно.
Экзистенциональная конкретизация
Из истинности xP x следует, что существует конкретное y такое,
что P y истинно.
P y xP x (аксиома 12 -схема)
Из существования конкретного y из универсума, для которого P y
истинно, делаем вывод, что xP x истинно.
Экзистенциональное обобщение
8

9.

Аксиомы равенства
E1 x x x .
E2 x y если x y , то y x .
E3 x y z если x y и y z , то x z .
Аксиомы целых чисел
I1. Множество замкнуто относительно операций сложения и умножения:
x y x y и x y .
I2. x y z p если x y и z p , то x z y p и x z y p .
I3. Множество
x y
коммутативно относительно операций сложения и умножения:
x y y x и x y y x.
I4. Множество ассоциативно относительно операций сложения и умножения:
x y z x y z x y z и x y z x y z .
I5. Умножение целых чисел дистрибутивно относительно сложения:
x y z z x y z x z y .
I6. Существуют нейтральный элемент сложения (0) и нейтральный элемент умножения (1).
x x 0 x и x x 1 x
I7. Существуют обратный элемент относительно сложения.
x !y x x y 0 .
I8. Мультипликативное свойство сокращения.
x y z если z 0 и z x z y , то x y .
9

10.

Теорема. Если n – четно, то n2 тоже четно.
10

11.

Теорема. Если n – четно, то n2 тоже четно.
Предположим, что n – (произвольное) четное целое число.
По определению четного целого числа существует целое число L такое,
что n=2L.
Если целые числа равны, то равны квадраты этих чисел, так что n2=(2L)2.
Но (2L)2=2(2L2), поэтому n2=2(2L2) и n2=2k для некоторого целого числа k
(а именно k=2L2). По определению четного целого числа n2 – четное число.
11

12.

1
2
3
4
5
6
7
a – целое число
a – четное
n (n – четное k n=2k)
a – четное k a=2k
k a=2k
a=2L для некоторого L
x y z p (x=y и z=p xz=yp)
a2=(2L)2 и (2L)2=2(2L2)
12
a2=2(2L2)
фиксированный элемент
посылка
определение четного числа
3 и универсальная конкретизация n a
m.p. 2, 4
5 и экзистенциональная конкретизация k= L
аксиома I2
7 и универсальная конкретизация
x a, y 2L, z a, p 2L
m.p. 6, 8
аксиома E3 (транзитивность равенства)
свойство ассоциативности и коммутативности целых чисел
(шаги пропущены для краткости)
10 (транзитивность равенства) и
универсальная конкретизация
x a2, y (2L)2, z 2(2L)2
8
a=2L a2=(2L)2
13 a2=(2L)2 и (2L)2=2(2L2)
9, 11 и закон конъюнкции
14 a2=2(2L2)
m.p. 12, 13
14 и экзистенциональное обобщение для фиксированного элемента (2L)2
определение четного числа
16 и универсальная конкретизация для фиксированного числа a2
m.p. 15, 17
2,18 и то, что ( p q ( p q) – тавтология)
12
1, 19 и универсальное обобщение
9 a2=(2L)2
10 x y z (x=y и y=z x=z)
11 (2L)2 = 2(2L2)
15 k a2=2k
16
17
18
19
20
x ( k x=2k x – четное)
k a2=2k a – четное
a2 – четное
a – четное a2 – четное
n (n – четное n2 – четное )
A, B
Aи B

13.

10
x y z (x=y и y=z x=z)
аксиома E3 (транзитивность равенства)
11.1
11.2
11.3
11.4
x y z ((x y) z = x (y z))
x y ( x y = y x)
x y (x=y y=x)
x y z p (x=y и z=p xz=yp)
11.5
(2 L) (2 L) = 2 (L (2 L))
11.6
L (2 L) = (2 L) L
11.7
(2 L) L = 2 L2
аксиома I4 (ассоциативность умножения)
аксиома I3 (коммутативность умножения)
аксиома E2 (коммутативность равенства)
аксиома I2
11.1 (ассоциативность умножения) и
универсальная конкретизация x 2, y L, z 2L
11.2 (коммутативность умножения) и
универсальная конкретизация x L, y 2L
11.1 (ассоциативность умножения) и
универсальная конкретизация x 2, y L, z L
11.8
L (2 L) = (2 L) L и (2 L) L = 2 L2
L (2 L) = (2 L) L и (2 L) L = 2 L2
L (2 L) = 2 L2
11.10 L (2 L) = 2 L2
11.11 x x=x
11.12 2 = 2
11.9
11.13 2 (L (2 L)) = 2 (2 L2)
(2 L) (2 L) = 2 (L (2 L)) и
2 (L (2 L)) = 2 (2 L2)
(2 L) (2 L) = 2 (L (2 L)) и
2 (L (2 L)) = 2 (2 L2)
11.15
(2 L) (2 L) = 2 (2 L2)
11
(2 L) (2 L) = 2 (2L2)
11.14
11.6, 11.7 и закон конъюнкции
A, B
Aи B
10 (транзитивность равенства) и универсальная конкретизация
x L (2 L), y (2 L) L, z 2 L2
m.p. 11.8, 11.9
аксиома E1
11.11 и универсальная конкретизация x 2
11.4 и универсальная конкретизация
x 2, y 2, z L (2 L), p 2L2
11.5, 11.13 и закон конъюнкции
A, B
Aи B
10 (транзитивность равенства) и универсальная конкретизация
x (2 L) (2 L) , y 2 (L (2 L)), z 2 (2 L2)
m.p. 11.14, 11.15
13

14.

Теорема. Если n2 – четно, то n тоже четно.
Докажем по закону контрапозиции, т.е. докажем утверждение
«Если n – не является четным числом, то n2 тоже не является четным числом.»
Предположим, что n – (произвольное) нечетное целое число.
По определению нечетного целого числа существует целое число L такое, что
n = 2L+1.
Следовательно,
n2 = (2L+1) 2=.4L2+4L+1=2(2L2+2L)+1.
Таким образом, n2=2k+1 для некоторого целого числа k (а именно k=2L2+2L.
По определению нечетного целого числа n2 – нечетное число.
14