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

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

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

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

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

  • Пусть 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

Кванторы

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

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

Универсальный квантификатор утверждает, что операторы в его области действия верны для каждого значения конкретной переменной. Обозначается символом $ \ 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 \: \ exist b \: P (x, y) $, где $ P (a, b) $ обозначает $ a + b = 0 $

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

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