Методические указания к семинарам и самостоятельным работам по курсу «Математическая логика и теория алгоритмов» - umotnas.ru o_O
Главная
Поиск по ключевым словам:
страница 1страница 2страница 3
Похожие работы
Название работы Кол-во страниц Размер
Учебная программа Дисциплины б5 «Математическая логика и теория алгоритмов» 1 127.27kb.
Методические указания к лабораторным работам по курсу «Теория информациии... 3 447.96kb.
Методические указания для студентов очного и заочного отделения к... 6 1434.03kb.
Вопросы по курсу: Математическая логика и теория алгоритмов (2 курс) 1 30.21kb.
Программа дисциплины Математическая логика и теория алгоритмов для... 1 200.2kb.
Вопросы к экзамену по курсу «Математическая логика и теория алгоритмов» 1 65.92kb.
Рабочая программа дисциплины Математическая логика и теория алгоритмов 1 113.32kb.
Методическое пособие Задания и методические указания к контрольным... 3 474.04kb.
Программа-минимум кандидатского экзамена по специальности 01. 1 37.49kb.
Кафедра: информатики и методики преподавания математики фио разработчиков... 1 50.04kb.
Методические указания по их проведению, вопросы к экзамену, перечень... 1 196.83kb.
Билет №18 Производные правила вывода: правило одновременной подстановки... 1 23.86kb.
Викторина для любознательных: «Занимательная биология» 1 9.92kb.

Методические указания к семинарам и самостоятельным работам по курсу «Математическая - страница №1/3



МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ

РОССИЙСКОЙ ФЕДЕРАЦИИ
ФЕДЕРАЛЬНОЕ АГЕНСТВО ПО ОБРАЗОВАНИЮ
Московский государственный институт электроники и математики

(Технический университет)

Кафедра «Вычислительные

системы и сети»



Методические указания к семинарам и самостоятельным работам по курсу «Математическая логика и теория алгоритмов» по исчислению предикатов и машинам Тьюринга



Москва 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), где yA(x) 4. АВВ



A5.А(y)(x)А(x), где yA(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. Назовём это вторым правилом произведения.



Получим вывод AB(A~C)(B~C). Считая что, AB - это AB и BA, получим (AB)(BA) ((A~C) (B~C)) ((B~C) (A~C)).

1) (AB)(BA) гипотеза.

2) (AB) второе правило произведения.

3) (BA) второе правило произведения.

4) (AC)(CA)= (C~A) гипотеза (для осл. теор. о дедукции).

5) (AC) второе правило произведения.

6) (CA) второе правило произведения.

7) (CB) силлогизм для 6) и 2).

8) (BC) силлогизм для 3) и 5).

9) (C~B)= (CB) (BC) первое правило произведения.

Получили (AB)(BA); (C~A) (C~B). По ослабленной теореме о дедукции получим (AB)(BA) (C~A) (C~B). Аналогично получим, взяв гипотезой (C~B), AB)(BA) (C~B) (C~A). Применив первое правило произведения, получим AB(A~C)(B~C).



следующая страница >>