Исчисление предикатов и язык Prolog

Атомарные утверждения являются уникальными и в силу этого обладают существенным недостатком: они не позволяют обобщать. Мы не можем применять правила, написанные для одного объекта, к другим объектам. Кроме того, в пропозициональной логике нет возможности создавать сложные объекты, обладающие свойствами, а также задавать связи между объектами. Для преодоления этих недостатков создана логика предикатов. Предикат — это утверждение, которое может иметь аргументы. Число аргументов называется арностью предиката. Если арность равна нулю, то такой предикат является атомом.

Перепишем рассмотренную выше программу с использованием предикатов с аргументами в скобках.

windy (volkhov).

windy (kronstadt).

rainy (Petersburg).

umbrella_useless (Site) windy (Site), rainy (Site).

we_are_in (Petersburg) we_are_in (kronstadt).

we_are_in (kronstadt).

Теперь мы видим, что объекты приобретают свойства. В Волхове ветрено, а в Кронштадте дождливо. В правиле umbrella_useless появились переменные, которые в языке Prolog должны начинаться с прописной буквы.

В отличие от пропозициональной логики число состояний в логике предикатов с п переменными равно не 2″, a s^ll_y где s — среднее число состояний каждой переменной. Если хотя бы одна из переменных — действительное число, то количество состояний становится бесконечным, что делает невозможным доказательства на основе таблиц истинности.

Для первых примеров исчисления высказываний в логике первого порядка мы используем числа Пеано. Между десятичными числами и числами Пеано устанавливается следующее соответствие:

Определим правила для определения четности чисел Пеано. Предикат even имеет арность (число аргументов), равную 1, и устанавливает четность аргумента:

Первое правило evz устанавливает, что нуль — четное число. Это правило не имеет условия и поэтому является аксиомой. Второе правило evs утверждает, что число р (р (N)) является четным, если N четно. Здесь N является схематической переменной правила логического вывода: каждый экземпляр правила, в котором N заменяется конкретным значением, представляет собой верное рассуждение. Других правил для определения четности здесь нет, следовательно, мы можем думать, что эти два правила определяют предикат even исчерпывающим образом. Приведем простой пример дедукции, из которой вытекает четность числа 4:

Здесь мы использовали правило evs дважды: один раз при N = О, второй — при N = р (р (0)). Данный пример иллюстрирует доказательство в логике первого порядка с использованием хорошо знакомого метода перебора вариантов.