Формулы логики предикатов

Наряду с определенными предикатами - для которых истинность или ложность известны для каждого набора значений свободных пред­метных переменных, будем рассматривать переменные предикаты, для которых не определены значения. Будем обозначать переменные преди­каты большими буквами из конца латинского алфавита с приписанными предметными переменными или без них:

W(x_l, …,x_п); U(х,у), ...

Применяя к переменным предикатам операции ˄,˅,→,↔, , по­лучим формулы логики предикатов, т. е. формулой логики предикатов называется выражение, составленное из переменных предикатов с помо­щью логических операций и кванторов и обращающееся в конкретный предикат при подстановке вместо переменных конкретных предикатов.

Например, «(( x)W(x, у) ˅ В) → U(z)» - формула логики предикатов.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

( х)W(х), ( х)W(х),

( х)W(х), ( х)W(х).

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

( х)(W(х) ˄ В) ( х)W(х) ˄ В, ( х)(W(х) ˄ В) ( х)W(х) ˄ В,

( x)(W(x) ˅ В) ( x)W(x) ˅ В, ( x)(W(x) ˅ В) ( x)W(x) ˅ В.

( х)( у)W(х, у) ( у)( х)W(х, у),

( x)( y)W(x, у) ( y)( x)W(x, у).

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