Вхождение переменных

Подставить переменную с вместо переменной x в формулу А(x) означает заменить все свободные вхождения переменной x в А переменной с.

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

Пример. Определить, свободна ли z для t в формуле

A(t)=P(t,x) t P(t,x) z P(z,t).

Найдем A(z), получим:

A(z)=P(z,x) t P(t,x) z P(z,z).

Первое и четвертое вхождения z получены в результате подстановки z вместо t в A(t), но первое вхождение z свободно, четвертое же связано. Значит, z не свободна для t в A(t).

Квантификация многоместных высказывательных форм

В процессе квантификации высказывательной формы Q(x1, x2, xi, …, xn) по переменной xi эта i-я

переменная связывается одним из кванторов, а n-местная высказывательная форма превраща- ется в (n-1)-местную.

Если кванторы одноимённы (1 – 4), то их порядок не играет роли и полученные

высказывания эквивалентны:
1) x y(Q(x, y))	2) y x(Q(x, y))
3) x y(Q(x, y))	4)	y x(Q(x, y))

Если кванторы разноимённы (5 – 6), то их порядок в полученном высказывании принципиально важен:

5)	x y(Q(x, y))	6)	x y(Q(x, y))
7)	y x(Q(x, y))	8)	y x(Q(x, y))

Интерпретация формул логики предикатов

Интерпретация формул логики предикатов

х(Р(х) Q(x))

Интерпретация формул логики предикатов

Аналитические правила в логике предикатов

T		T xP x		F		F xP x
						F P x
		T P x
		F xP x		T		T xP x
F
		~				~
		F P x				T P x

Метод аналитических таблиц

F x A x xA x

T x A x	, F xA x
T A x	T x A x
F A x	T A x

{FA,TA}-формула общезначима

Перевод выражений русского языка на предикатный язык

Пример

Запишем с помощью формул логики предикатов утверждение:

Все студенты изучают некоторый иностранный язык.

P(x)={x – студент}

Q(x)={x – иностранный язык} R(x, y)={x изучает y}x(P(x) y(Q(y) R(x,y)))