W(х1, х2, ..., хп); U(х,у),

Применяя к переменным предикатам операции ; ; →; ↔; Ї; ; , получим формулы логики предикатов,

Формулой логики предикатов называется выражение, составленное из переменных предикатов с помощью логических операций и кванторов и обращающееся в конкретный предикат при подстановке вместо переменных конкретных предикатов.

Пример.

(( х) W(х, у) В) → U(z) — формула логики предикатов. Формула логики предикатов называется тавтологией, если при подстановке любых конкретных предикатов она всегда обращается в тождественно истинный предикат.

Формулы

Определение формулы лежит в основе так называе­мой логики предикатов первого порядка, в которой разрешается квантифицировать (связывать кванторами) только предметные переменные. Логика предикатов первого порядка включает в себя все формулы логики высказываний, все равносильности исчисле­ния высказываний, а также большинство правил вывода умоза­ключений из классической логики. Поэтому язык логики преди­катов дает возможность анализировать рассуждения естественно­го языка и науки, делать выводы в различных формальных системах.

Так, высказывательная форма является форму­лой. В то же время высказывательная форма не будет формулой, поскольку в формуле переменная х свя­зана квантором существования, тогда как в формуле Q(x) эта же переменная свободна.

В чем ценность формальных теорий?

Для описания каких объектов используется логика предикатов?

Вообще говоря, ценность любой формальной теории заключа­ется в возможности описывать с ее помощью произвольные объек­ты и связи между ними.

Теоремы.

К числу основных равносильностей логики предика­тов относят:

1. .

2. .

3. .

4. .

5. .

6. .

Сформулируем следующие правила.

(1) Формула логики предикатов называется атомарной, т.е. элементарной, если в ней нет связанных переменных.

(2) Пусть F — формула, тогда неF — тоже формула. Свободные и связанные переменные формулы неF — это соответственно свободные и связанные переменные формулы F.

(3) Пусть F и G — формулы, причем в них нет предметных переменных, которые были бы связаны в одной формуле и свободны в другой.

Тогда F G, F G, F → G, F ↔ G — формулы, в которых свободные переменные формул F и G остаются свободными, а связанные — связанными.

(4) Пусть F — формула, содержащая свободную переменную х. Тогда ( х)F, ( х)F — тоже формулы, в которых переменная х связана, а остальные свободные переменные, входящие в F, остаются свободными.

Заметим, что по определению формулы никакая переменная не может быть одновременно свободной и связанной.

Значение формулы определено лишь тогда, когда задана какая-то интерпретация входящих в нее символов.

Под интерпретацией понимают систему М=<М,f>, состоящую из непустого множества М и соответствия f, которое сопоставляет каждой формуле определенный предикат. При заданной интерпретации предметные переменные пробегают множество М, а логические символы и символы кванторов имеют свой обычный смысл.

Равносильные формулы логики предикатов

Пусть формулы F и G имеют одно и то же множество свободных переменных (в частности, пустое). Формулы F и G равносильны в данной интерпретации, если они принимают одинаковые значения на любом наборе свободных переменных, т. е. выражают в данной интерпретации один и тот же предикат.

Формулы F и G равносильны на множестве М, если они принимают одинаковые значения во всех интерпретациях заданных на множестве М.

Формулы F и G равносильны в логике предикатов, если они равносильны на всех множествах (F =G).

Рассмотрим правила перехода от одних формул к другим, им равносильным.

(1) Перенос квантора через отрицание. Пусть W(х) — формула, содержащая свободную переменную х. Тогда справедливы равносильности:

, ,

, .

(2) Вынос квантора за скобки. Пусть формула W(х) содержит свободную переменную х, а формула В не содержит переменной х. Формулы W(х) и В удовлетворяют третьему правилу создания формул. Тогда справедливы равносильности:

, ,

, .

(3) Перестановка одноименных кванторов. Имеем

, .

(4) Переименование связанных переменных. Заменяя связанную переменную формулы W другой переменной, не входящей в эту формулу, в кванторе и всюду в области действия квантора, получим формулу, равносильную W.

Приведенные и нормальные формы в логике предикатов

Рассмотрим способ упрощения формул, опирающийся на приведенные равносильности.

Формулы, в которых из логических символов имеются только символы конъюнкция, дизъюнкция и отрицание, причем символ отрицания встречается над символами предикатов, будем называть приведенными.

Пример.

Формула ( x₁) A₁⁽¹⁾(x₂) ( x₁)не(А₂⁽²⁾(x₂,x₃)) — приведенная;

Формула не( x₂) A₁⁽¹⁾(x₂) → А₂⁽¹⁾(x₁) — неприведенная.

Для любой формулы существует равносильная ей приведенная формула, причем множества свободных и связанных переменных этих формул совпадают.

Такая приведенная формула называется приведенной формой данной формулы.

В логике высказываний мы ввели две нормальные формы — дизъюнктивную нормальную форму и конъюнктивную нормальную форму.

В логике предикатов также имеется нормальная форма, цель которой — упрощение процедуры доказательств.

Приведенная формула называется нормальной, если она не содержит символов кванторов или все символы кванторов стоят впереди (т.е. логические символы и символы предикатов стоят в области действия каждого квантора).

Для любой приведенной формулы существует равносильная ей нормальная формула той же длины (под длиной формулы будем понимать общее число входящих в нее символов предикатов, логических символов и символов кванторов).

Нормальная формула называется нормальной формой данной формулы.

Приведем несколько формул, находящихся в нормальной форме:

, ,

.