Дискретная математика - логика предикатов
Predicate Logic имеет дело с предикатами, которые представляют собой предложения, содержащие переменные.
Логика предикатов - определение
Предикат - это выражение одной или нескольких переменных, определенных в некоторой конкретной области. Предикат с переменными можно превратить в предложение, присвоив переменной значение или количественно оценив переменную.
Ниже приведены несколько примеров предикатов -
- Пусть 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 $ и $ \ exists x Y $ также являются wff
Истинное и ложное значения - это wffs
Каждая атомарная формула - это wff
Все связки, соединяющие wffs, являются wffs
Квантификаторы
Переменная предикатов количественно определяется кванторами. В логике предикатов есть два типа квантификаторов - универсальный квантификатор и экзистенциальный квантификатор.
Универсальный квантификатор
Универсальный квантификатор утверждает, что утверждения в его области верны для каждого значения конкретной переменной. Обозначается символом $ \ forall $.
$ \ forall x P (x) $ читается, поскольку для любого значения x P (x) истинно.
Example - «Человек смертен» можно преобразовать в пропозициональную форму $ \ forall x P (x) $, где P (x) - предикат, который означает, что x смертен, а вселенная дискурса - это все люди.
Экзистенциальный квантификатор
Квантификатор существования утверждает, что утверждения в его области верны для некоторых значений конкретной переменной. Обозначается символом $ \ exists $.
$ \ exists x P (x) $ читается как для некоторых значений x, P (x) истинно.
Example - «Некоторые люди нечестны» можно преобразовать в пропозициональную форму $ \ exists x P (x) $, где P (x) - предикат, который означает, что x - нечестный, а вселенная дискурса - это некоторые люди.
Вложенные квантификаторы
Если мы используем квантификатор, который появляется в рамках другого квантификатора, он называется вложенным квантификатором.
Example
$ \ forall \ a \: \ exists 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) = ( а + б) + в $
Note - $ \ forall \: a \: \ exists b \: P (x, y) \ ne \ exists a \: \ forall b \: P (x, y) $