Министерство образования и науки
РОССИЙСКОЙ ФЕДЕРАЦИИ
ФЕДЕРАЛЬНОЕ АГЕНСТВО ПО ОБРАЗОВАНИЮ
Московский государственный институт электроники и математики
(Технический университет)
Кафедра «Вычислительные
системы и сети»
Методические указания к семинарам и самостоятельным работам по курсу «Математическая логика и теория алгоритмов» по исчислению предикатов и машинам Тьюринга
Москва 2007
Составитель: доц., канд. тех. наук Л.Е. Захарова
УДК 519.1
Предназначены для изучения исчисления предикатов и машин Тьюринга студентами II курса дневного и вечернего факультета АВТ специальности 22.0101.
Математическая логика и теория алгоритмов: Метод. указания к семинарам и самостоятельным работам по исчислению предикатов и машинам Тьюринга/ Моск. Гос. ин-т электроники и математики; Сост. Л.Е. Захарова. М., 2007. 12 с.
Ил. 6. Библиогр.: 2 назв.
ISBN 5-94506-100-х
Исчисление предикатов
К системе
аксиом исчисления высказываний (ИВ) в
исчислении предикатов (ИП) добавляются
ещё две: А4 и А5 (или
11
и
12).
При решении задач по исчислению
предикатов можно пользоваться одной
из двух систем аксиом ИП (двумя сразу
нельзя):
А1.
А
(В
А)
1.
А
(В
А)
А2.
(А
(В
С))
((А
В)
(А
С))
2.
(А
В)
((А
(В
С))
(А
С))
А3.
(
В
А)
((
В
А)
В)
3.
А
В
А
A4.(
x)А(x)
А(y),
где y
A(x)
4.
А
В
В
A5.А(y)
(
x)А(x),
где y
A(x)
5.
А
(В
(А
В))
6.
А
(А
В)
7.
В
(А
В)
8.
(А
С)
((В
С)
((А
В)
С)
9.
(А
В)
((А
В)
А)
10.
А
А
11.(
x)А(x)
А(y),
где A(x)
не содержит y
12.А(y)
(
x)А(x),
где A(x)
не содержит y
При использовании
системы аксиом
вывод будет короче. Вывод в ИП – это
последовательность формул, где каждая
формула или аксиома, или теорема, или
гипотеза, или получена по правилам
вывода из предыдущих формул. Первое
правило вывода ИП совпадает с правилом
выводаm.p.
из ИВ: если в выводе есть две формулы
вида А
В
и А, то после них в выводе можно писать
формулу В. Считается, что формула В
получена по правилуm.p.
из формул А и А
В.
Правилоm.p.
записывается так: А, А
В
В.
Второе правило
вывода ИП имеет вид: B
А(x)
B
(
x)А(x),
где B
не содержит x.
Второе правило вывода называется
правилом связывания квантором общности.
Третье правило вывода ИП имеет вид:
А(x)
B
(
x)А(x)
B,
где B
не содержит x.
Третье правило вывода называется
правилом связывания квантором
существования. Четвёртое правило вывода
ИП – это правило переименования связанной
переменной: связанную переменную в
формуле можно заменить (в кванторе и во
всех вхождениях в области действия
квантора) другой переменной, не являющейся
свободной в этой формуле.
Выводом формулы
А считается вывод, в котором формула А
является последней. Если в выводе формулы
А отсутствуют гипотезы, то формула А
называется теоремой ИП. Все аксиомы
являются как бы схемами аксиом, в них
вместо формул А, В и С можно корректно
подставить любые формулы. Если формула
А заменяется другой формулой, то сразу
во всей аксиоме. В выводе ИП можно
применять ославленную теорему о дедукции:
если Г, А
В
и существует вывод в ИП, построенный
только с первым правилом вывода ИП
(m.p.),
то Г
А
В.
При тех же
условиях можно применять и два следствия
ослабленной теоремы о дедукции: 1. А
В,
В
С
А
С.
Построим вывод формулы А
С.
1) А
В
– гипотеза № 1; 2) В
С
– гипотеза № 2; 3) А – гипотеза № 3, формулуA
берём гипотезой, имея в виду далее
применить к ней ослабленную теорему о
дедукции; 4) В получена по m.p.
из первого и третьего шагов (из 1) и 3) );
5) С получена по m.p.
из 2) и 4). Вывод формулы С имеет длину
пять. В итоге получили: А
В,
В
С,
А
С.
Применяем ослабленную теорему о
дедукции ИП, переносим формулу А вправо
и получаем: А
В,
В
С
А
С.
Следствие 2: А
(В
С),
В
А
С.
Вывод длиной 5: А
(В
С);
В; А; В
С;
С. Четвёртый шаг получен поm.p.
из первого и третьего шагов, а пятый –
из второго и четвёртого. Получили
А
(В
С),
В, А
С,
применяя ослабленную теорему о дедукции,
получим второе следствие. Следствия
можно считать ещё двумя правилами
вывода. В правилах вывода тоже, как и в
аксиомах, можно корректно одновременно
во всём правиле вывода одну формулу
заменять другой.
При выводе в
ИП можно использовать и 7 теорем: Т1.
А
А.
Т2. А
А.
Т3.
А
(А
В).
Т4. (
В
А)
(А
В).
Т5. (А
В)
(
В
А).
Т6. А
(
В
(А
В)).
Т7. (А
В)
((
А
В)
В).
В теоремах ИП, в том числе и в ослабленной
теореме о дедукции и её следствиях,
формулы С, А и В так же могут быть заменены
другими.
Для примера
получим ещё одно правило вывода:
А,
В
А
В.
В пятую теорему вместо формулы А поставим
формулу В, а вместо В поставим А и получим:
(В
А)
(
А
В).
Теоремы и аксиомы можно вставлять в
любое место вывода. Теперь вывод формулы
В
длиной 5:
А;
В
А;
(В
А)
(
А
В);
А
В;
В.
Четвёртый шаг вывода получен поm.p.
из второго и третьего шагов, а пятый –
из первого и четвёртого. Все три вновь
полученные правила вывода можно
применять, как и правило m.p.,
наряду с ослабленной теоремой о дедукции.
Докажем
общезначимость формулы (
x)(
y)A(x,y)
(
y)(
x)A(x,y),
то есть докажем, что эта формула выводима
в ИП.
1)
(
y)А(x,y)
А(x,z)
(
11).
2)
А(x,z)
(
u)А(u,z)
(
12).
3) А
В,
В
С
А
С
силлогизм, следует из осл. теоремы о
дедукции.
4) (
y)А(x,y)
(
u)А(u,z)
(силлогизм).
5) (
x)(
y)А(x,y)
(
u)А(u,z)
(правило вывода 3).
6) (
x)(
y)А(x,y)
(
z)(
u)А(u,z)
(правило вывода 2).
7) (
x)(
y)А(x,y)
(
y)(
u)А(u,y)
(правило вывода 4).
8) (
x)(
y)А(x,y)
(
y)(
x)А(x,y)
(правило вывода 4).
Теперь получим
(
x)P(x)
(
x)Q(x)
(
x)(P(x)
Q(x)).
1)
(
y)P(y)
P(x)
(
11).
2)
P(x)
(P(x)
Q(x))
(
6).
3)
(
y)P(y)
(P(x)
Q(x))
силлогизм, следует из 1) и 2).
4)
(
y)P(y)
(
x)
(P(x)
Q(x))
правило вывода ИП 2, получено из 3).
5)
(
x)P(x)
(
x)
(P(x)
Q(x))
правило вывода ИП 4, получено из 4).
6)
(
y)Q(y)
Q(x)
(
11).
7)
Q(x)
(P(x)
Q(x))
(
7).
8)
(
y)Q(y)
(P(x)
Q(x))
силлогизм, следует из 6) и 7).
9)
(
y)Q(y)
(
x)
(P(x)
Q(x))
правило вывода ИП 2, получено из 8).
10)
(
x)Q(x)
(
x)
(P(x)
Q(x))
правило вывода ИП 4, получено из 9).
11)
((
x)P(x)
(
x)
(P(x)
Q(x)))
(((
x)Q(x)
(
x)
(P(x)
Q(x)))
(((
x)P(x)
(
x)Q(x))
(
x)(P(x)
Q(x)))
(
8).
12)
((
x)Q(x)
(
x)
(P(x)
Q(x)))
(((
x)P(x)
(
x)Q(x))
(
x)(P(x)
Q(x)))
правило m.p.
5) и 11).
13)
((
x)P(x)
(
x)Q(x))
(
x)(P(x)
Q(x))
правило m.p.
10) и 12).
14) (
x)P(x)
(
x)Q(x)
гипотеза.
15)
(
x)(P(x)
Q(x))
правило m.p.
13) и 14).
Всякую доказанную
в ИП выводимость вида Г
A
можно рассматривать как ещё одно правило
вывода, которое можно присоединить к
уже имеющимся. Например, рассмотрим
аксиому
5
(А
(В
(А
В))),
по ней, имеяA
и B,
получим, применив два раза правило m.p.
А
В.
Назовём это первым правилом произведения.
И наоборот, по аксиомам
3
(А
В
А)
и
4
(А
В
B),
имея А
В,
получимA
и B.
Назовём это вторым правилом произведения.
Получим вывод
A
B
(A~C)
(B~C).
Считая что, A
B
- это A
B
и B
A,
получим (A
B)
(B
A)
((A~C)
(B~C))
((B~C)
(A~C)).
1)
(A
B)
(B
A)
гипотеза.
2)
(A
B)
второе правило произведения.
3)
(B
A)
второе правило произведения.
4)
(A
C)
(C
A)=
(C~A)
гипотеза (для осл. теор. о дедукции).
5)
(A
C)
второе правило произведения.
6)
(C
A)
второе правило произведения.
7)
(C
B)
силлогизм для 6) и 2).
8)
(B
C)
силлогизм для 3) и 5).
9)
(C~B)=
(C
B)
(B
C)
первое правило произведения.
Получили
(A
B)
(B
A);
(C~A)
(C~B). По
ослабленной теореме о дедукции получим
(A
B)
(B
A)
(C~A)
(C~B).
Аналогично получим, взяв гипотезой
(C~B),
A
B)
(B
A)
(C~B)
(C~A).
Применив первое правило произведения,
получим A
B
(A~C)
(B~C).