Главная

Популярная публикация

Научная публикация

Случайная публикация

Обратная связь

ТОР 5 статей:

Методические подходы к анализу финансового состояния предприятия

Проблема периодизации русской литературы ХХ века. Краткая характеристика второй половины ХХ века

Ценовые и неценовые факторы

Характеристика шлифовальных кругов и ее маркировка

Служебные части речи. Предлог. Союз. Частицы

КАТЕГОРИИ:






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




Алфавит исчисления предикатов состоит из предметных переменных x, y, … (возможно, с индексами); предикатных символов P, Q, …; знаков логических операций, ∧, ∨, →; кванторов ∀, ∃; скобок (,).

Для предметных переменных и предикатов могут использоваться индексы. Для каждого предикатного символа указано число мест для аргументов. Например, можно считать, что каждый n-местный предикатный символ задается комбинацией знаков типа P(,,…,), в которой число аргументов указывается числом промежутков между запятыми. Чтобы не загромождать обозначений, мы будем иногда опускать указание на число аргументов.

Дадим определение формулы. Множество формул определяется рекурсивно. Оно является наименьшим подмножеством выражений, удовлетворяющим следующим условиям.

1) Если P(,,…,) – n-местный предикатный символ, а x1,x2,…,xn – предметные переменные, то P(x1,x2,…,xn) – формула, причем все вхождения в нее предметных переменных свободны.

2) если U и V – формулы, то (U), (U∧V), (U∨V), (U→V) – формулы; все вхождения предметных переменных, свободные в исходных формулах, остаются свободными и в построенных.

3) если U – формула, содержащая свободное вхождение переменной x, то ∀xU, ∃xU – формулы; в этих формулах все вхождения переменной x связаны, вхождения остальных переменных свободны или связаны так же, как в формуле U; формулу U называют областью действия квантора.

В этом рекурсивном определении формулы дано также определение свободного и связанного вхождения переменой и области действия квантора. Например, в формуле

(∀x(P(x,y)→Q(y)))∨Q(x)

все вхождения переменной y свободны; вхождение переменной x в первый дизъюнктивный член связано, во второй – свободно. Областью действия квантора является формула P(x,y)→Q(y).

Аксиомы исчисления предикатов содержат все аксиомы исчисления высказываний и следующие две аксиомы:

(P1) ∀xU→U(x/y);

(P2) U(x/y)→∃xU.

Предполагается, что формула U содержит свободные вхождения переменной x, причем ни одно из них не находится в области действия квантора по y; через U(x/y) обозначается формула, полученная из U заменой всех свободных вхождений x на y. В дальнейшем мы будем использовать упрощенные обозначения. Мы будем писать U(x), если формула U содержит свободные вхождения переменной x, а вместо U(x/y) будем писать U(y).

Предположения о вхождениях переменных существенны. Отказ от них может привести к формулам, которые нельзя признать логически верными. Рассмотрим, например, формулу ∃yP(x,y). По аксиоме (P1) мы получим формулу ∀x∃yP(x,y)→∃yP(y,y), допускающую интерпретации, в которых она не является истинной.

Правила вывода:

(MP) правило заключения – то же, что и в исчислении высказываний;

(G) если формула V(x) содержит свободные вхождения переменной x, а формула U их не содержит, то

U→V(x) |− U→∀xV(x);

(E) если формула U(x) содержит свободные вхождения переменной x, а формула V их не содержит, то

U(x)→V |− ∃xU(x)→V.

Правило (G) называется правилом обобщения или ∀-введения, правило (E) – правилом ∃-введения.

В качестве примера вывода в исчислении предикатов докажем правило переименования связанных переменных.

Теорема. Если формула U(x) не содержит свободных вхождений переменной y и содержит свободные вхождения переменной x, не попадающие в область действия квантора по y, то из формулы ∀xU(x) выводится формула ∀yU(y).

Доказательство. Укажем вывод:

(1) ∀xU(x);

(2) ∀xU(x)→U(y);

(3) ∀xU(x)→∀yU(y);

(4) ∀yU(y).

Комментарии: (1) – гипотеза; (2) – аксиома (P1); (3) – получено из (2) по правилу обобщения; (4) – получено из (1) и (3) по правилу заключения.􀀀

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

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

Теорема. Исчисление предикатов полно: всякая общезначимая предикатная формула выводима в исчислении предикатов.􀀀






Не нашли, что искали? Воспользуйтесь поиском:

vikidalka.ru - 2015-2024 год. Все права принадлежат их авторам! Нарушение авторских прав | Нарушение персональных данных