Отношение логического следования в логике предикатов

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

Отношение логического следования в ЛП сохраняет все свойства отношения логического следования в Л В — рефлексивность, несимметричность и транзитивность, но обладает определенной спецификой, которая связана с введением кванторов.

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

Т1. У^(х)фк = (ЕхЪфх\ Т2. |-(х)фх = ^(ЕхЪфх.

Отрицание любого квантора равносильно замене его на противоположный при одновременном отрицании всей области его действия.

Правила подстановки

Если некоторая формула содержит вхождения свободных переменных, то на их место могут подставляться термы. Пусть <Цх/і) обозначает операцию подстановки терма t на место свободной переменной х в формуле фх. Результатом подстановки становится формула ф( по правилу: ф(хА) = фі.

Чтобы подстановка оказалась правильной, необходимо выполнить следующие условия: 1.

Если терм t — предметная константа, то подстановка проводится без ограничений. 2.

Если терм t — предметная переменная, то ни одно вхождение t не должно оказаться связанным в результате подстановки / на место переменной х в формуле фх.

Подстановка {Ex)Pxy{y/z) = (Ex)Pxz является правильной, так как вхождение переменной z не является связанным в формуле (Ех)Рху. Подстановка (Ех)Рху(у/х) = (Ех)Рхх неправильная, потому что терм х, подставленный вместо у, оказался связанным квантором (х). Неправильные подстановки приводят к противоречию. Пусть Рху обозначает отношение «х больше у». Пусть V = «натуральные числа». Тогда формула (Ех)Рхх, полученная в результате неправильной подстановки, означает, что «существует такое натуральное число, которое больше самого себя», что очевидно ложно.