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

Определения

Для упрощения структуры сложных логических рассуждений введем специальные обозначения для некоторых часто встречающихся выражений. Условимся обозначать выражение “для всякого x свойство R выполнено” как x R (x), а выражение “существует по крайней мере один x, обладающий свойством (предикатом) R ” – как x R (x). В выражениях x R (x) и x R (x) обозначения x и x будем соответственно называть квантором всеобщности и квантором существования.

(Чистое) исчисление предикатов (первого порядка) – это формальная теория K, в которой определены следующие компоненты:

связки	основные	Ø ®
	дополнительные	&
служебные символы		(,)
кванторы	всеобщности	"
	существования	$
предметные	константы	a, b, …,a 1, b 1, …
	переменные	x, y, …,x 1, y 1, …
предметные	предикаты	P, Q, …
	функторы	f, g, …

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

<формула>::= <атом>|

Ø<формула>|

(<формула>®<формула>)|

"<переменная> <формула>|

$<переменная> <формула>

<атом>::= <предикат> (<список терминов>)

<список терминов>::= <терм> | <терм>, <список терминов>

<терм>::= <константа> |

<переменная> |

<функтор>(< список терминов>)

Пример

" x (Р (х)® $ у Q (x, y))

Логическое следование и логическая эквивалентность

Формула В является логическим следствием формулы А (обозначение: А В), если формула В выполнена на любом наборе в любой интерпретации, на котором выполнена формула А. Формулы А и В логически эквивалентны (обозначение: А=В), если они являются логическим следствием друг друга. Имеют место следующие логические следования и эквивалентности:

1.

2.

3.

4.

5.

6.

7.

8.

где формула С не содержит никаких вхождений переменной х.

Дата добавления: 2014-12-27