Дискретная математика - предикатная логика
Логика предикатов имеет дело с предикатами, которые являются предложениями, содержащими переменные.
Предикатная логика - определение
Предикат - это выражение одной или нескольких переменных, определенных в некоторой конкретной области. Предикат с переменными можно сделать предложением, либо присвоив значение переменной, либо определив ее количественно.
Ниже приведены некоторые примеры предикатов:
- Пусть 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) $