Рекомендуемая литература. Упражнения.
Четкое изложение основных концепций теории доказательств в математической логике читатель найдет в работе Эндрюса [Andrews, 1986].
Я также рекомендую познакомиться с книгой [Quine, 1979] – переизданием классического труда, опубликованного впервые еще в 1940 году.
Достаточно обширное введение в проблематику автоматического формирования суждений содержится в книге Робинсона [Robinson, 1979].
Более популярное изложение этого материала с упором на проблематику искусственного интеллекта можно найти в работе [Genesereth and Nilsson, 1987, Chapters 1-5].
Обсуждение проблем математической логики в контексте искусственного интеллекта содержится в статье Хейеса и Мичи [Hayes and Michie, 1984].
Новой работой в этой области является книга Гинзберга [Ginsberg, 1993].
Упражнения
Упражнение 1
Выразите с помощью логики предикатов следующие утверждения.
I) Каждый студент использует какой-нибудь компьютер, и по крайней мере один компьютер используется каждым студентом. (Используйте только предикаты СТУДЕНТ, КОМПЬЮТЕР и ИСПОЛЬЗУЕТ.)
II) Каждый год некоторые студенты-мужчины проваливают каждый экзамен, но каждый студент-женщина сдает какой-нибудь экзамен. (Используйте только предикаты СТУДЕНТ, МУЖЧИНА, ЖЕНЩИНА, СДАЕТ, ЭКЗАМЕН, ГОД.)
Ill) Каждый мужчина любит какую-нибудь женщину, которая любит другого мужчину. (Используйте только предикаты МУЖЧИНА, ЖЕНЩИНА, ЛЮБИТ и =.)
IV) Не существует двух философов, которые любили бы одну и ту же книгу. (Используйте только предикаты ФИЛОСОФ, КНИГА, ЛЮБИТ и =.)
Упражнение 2
Выразите предложения упр. 1 в форме фразы.
Упражнение 3
Имеет ли смысл выразить следующие цитаты с помощью логики предикатов? Покажите, в чем состоит сложность такого преобразования в каждом конкретном случае.
I) Ни один человек не является островом. (Джон Донн (John Donne))
II) Человек, который живет где-нибудь, живет везде. (Тацит)
III) Прошлое – это иная страна. В нем все происходит по-другому. (Л. П. Хартли (L. P. Hartley))
Упражнение 4
Следующая формула утверждает, что кто-то бреет себя сам или парикмахер бреет кого-то:
бреет) X, X), бреет (парикмахер, X) ←
I) Используя обратную стратегию, покажите, что из этой формулы следует:
бреет (парикмахер, парикмахер) <-
II) То же самое покажите с помощью прямой стратегии.
III) Как вы понимаете в том же контексте следующую фразу:
← бреет(У, Y), бреет (парикмахер, У)
IV) Покажите, что следующие фразы противоречивы.
Для этого достаточно показать, что из них следует пустая фраза:
бреет(Х, X), бреет (парикмахер, X) <-< – бреет(У, Y), бреет (парикмахер, Y)
Упражнение 5
Ниже представлены правило поиска неисправности и описание конкретной ситуации.
Если компьютер не включается и напряжение в сети питания в норме, то оборван шнур питания или неисправен блок питания. Мой компьютер не включается. Напряжение в сети питания в норме. Шнур питания не оборван.
I) Выразите эти предложения в форме логики предикатов.
II) Постройте конъюнктивную нормальную форму.
III) Используя прямую стратегию доказательства, покажите, что утверждение "Неисправен блок питания" логически вытекает из приведенного набора фактов. То же самое покажите с использованием обратной стратегии доказательства.