Дискретная математика — предикатная логика

Логика предикатов имеет дело с предикатами, которые являются предложениями, содержащими переменные.

Предикатная логика — определение

Предикат — это выражение одной или нескольких переменных, определенных в некоторой конкретной области. Предикат с переменными можно сделать предложением, либо присвоив значение переменной, либо определив ее количественно.

Ниже приведены некоторые примеры предикатов:

• Пусть E (x, y) обозначает «x = y»
• Пусть X (a, b, c) обозначает «a + b + c = 0»
• Пусть M (x, y) обозначает «x женат на y»

Хорошо сформированная формула

Хорошо сформированная формула (wff) — это предикат, содержащий любое из следующего:

• Все пропозициональные константы и пропозициональные переменные являются wffs

• Если x — переменная, а Y — wff, то $\ forall x Y$ и $\ существующие x Y$ также являются wff

• Истинное значение и ложные значения являются wffs

• Каждая атомная формула является WFF

• Все соединения, соединяющие wffs, являются wffs

Все пропозициональные константы и пропозициональные переменные являются wffs

Если x — переменная, а Y — wff, то $\ forall x Y$ и $\ существующие x Y$ также являются wff

Истинное значение и ложные значения являются wffs

Каждая атомная формула является WFF

Все соединения, соединяющие wffs, являются wffs

Кванторы

Переменная предикатов определяется количественно квантификаторами. Существует два типа квантификаторов в логике предикатов — универсальный квантификатор и экзистенциальный квантификатор.

Универсальный квантификатор

Универсальный квантификатор утверждает, что операторы в его области действия верны для каждого значения конкретной переменной. Обозначается символом $\ forall$.

$\ forall x P (x)$ читается как для каждого значения x, P (x) верно.

Пример — «Человек смертен» может быть преобразован в пропозициональную форму $\ forall x P (x)$, где P (x) — предикат, обозначающий x, смертный, а вселенная дискурса — все люди.

Экзистенциальный квантификатор

Экзистенциальный квантификатор утверждает, что операторы в его области истинны для некоторых значений определенной переменной. Обозначается символом $\ exist$.

$\ существует x P (x)$ читается как для некоторых значений x, P (x) верно.

Пример — «Некоторые люди нечестны» можно преобразовать в пропозициональную форму $\ exist x P (x)$, где P (x) — предикат, который обозначает, что x нечестен, а во вселенной дискурса — некоторые люди.

Вложенные квантификаторы

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

пример

•  forall a existbP(x,y)$\ forall \ a \: \ exist b \: P (x, y)$, где $P (a, b)$ обозначает $a + b = 0$

•  forall a forallb forallcP(a,b,c)$\ forall \ a \: \ forall \: b \: \ forall \: c \: P (a, b, c)$, где $P (a, b)$ обозначает $a + (b + c) = ( a + b) + c$

 forall a existbP(x,y)$\ forall \ a \: \ exist b \: P (x, y)$, где $P (a, b)$ обозначает $a + b = 0$

 forall a forallb forallcP(a,b,c)$\ forall \ a \: \ forall \: b \: \ forall \: c \: P (a, b, c)$, где $P (a, b)$ обозначает $a + (b + c) = ( a + b) + c$

Примечание —  foralla СуществуетbP(x,y) ne существуетa forallbP(x,y)$\ forall \: a \: \ Существует b \: P (x, y) \ ne \ существует a \: \ forall b \: P (x, y)$