Исчисление предикатов
Исчисление предикатов называют еще теорий первого порядка. В исчислении предикатов, так же как и в исчислении высказываний, на первом по важности месте стоит проблема разрешимости. Но в исчислении высказываний проблема разрешимости состояла в решении вопроса является ли данная сложная функция тождественно истинной, выполнимой или тождественно ложной.
Теперь же вопрос следует поставить иначе. Принимает ли данная функция значение 1 при:
а) любых предметных переменных и любых предикатах,
б) на некотором множестве предметных переменных и любых предикатах,
в) при некоторых значениях предметных переменных и любых предикатах,
г) является ли она тождественно ложной, т.е. невыполнимой?
Таким образом, в логике предикатов, в отличие от логики высказываний, нет эффективного способа для распознавания общезначимости функций.
Поэтому в исчислении предикатов указывается некоторая совокупность формул, которые называются аксиомами и составляют аксиоматическую теорию, и указывается конечное множество отношений между формулами, составляющее правила вывода.
Аксиоматическая теория и правила вывода и составляют исчисления предикатов.
Символами исчисления предикатов или алфавитом исчисления предикатов являются символы предметных переменных, символы предикатов, логические символы (отрицание и импликация), символы кванторов, а также скобки и запятая.
Сформулируем аксиомы исчисления предикатов и правила вывода исчисления предикатов.
Применение предикатов в алгебре
Рассмотрим предикаты, в которых свободной является лишь одна переменная, которую обозначим через х, и обсудим применение предикатов в алгебре.
Типичным примером является уравнение, например, х2-Зх+2=0. Свободная переменная может принимать здесь любое числовое значение. Для некоторых чисел х (а именно х = 1, х = 2) утверждение, содержащееся в этом уравнении, истинно, в остальных оно ложно. В подобных случаях, когда истинность или ложность предиката зависит только от значения, принимаемого свободной переменной х, множество допустимых значений х можно рассматривать как множество логических возможностей U, а множество всех значений этой переменной, при которых высказывание истинно — как его множество истинности.
В приведенном выше примере множество U состоит из всех действительных чисел, а множеством истинности является множество {1,2}.
В результате введения понятия множества истинности для предикатов мы сможем сказать, что решить уравнение — значит найти один элемент или все элементы его множества истинности. При решении системы двух уравнений у нас имеется предикат, представляющий конъюнкцию двух уравнений. Поэтому мы ищем пересечение двух множеств истинности. Если это пересечение пусто, то система уравнений не имеет решений. Такие уравнения называются несовместными, поскольку их множества истинности не имеют общих элементов х.
Понятие множества истинности удобно не только в вопросах, связанных с решением уравнений, но и при рассмотрении неравенств.
Если U — множество действительных чисел, то множество истинности неравенства х < 0 состоит из всех отрицательных действительных чисел. Множество же истинности неравенства х > -3 состоит из всех действительных чисел, больших, чем -3. Если мы потребуем, чтобы эти неравенства выполнялись одновременно, то множеством истинности будет множество, являющееся пересечением двух исходных множеств, т.е. все действительные числа между -3 и 0.
Понятие множества истинности предиката позволяет выяснить, чем разнятся между собой уравнения и тождества. Когда мы решаем уравнение, мы тем самым ищем один из элементов множества истинности этого уравнения или все его элементы. Если же мы доказываем тождество, то тем самым утверждаем, что оно справедливо для всех х. Таким образом, тождество представляет собой уравнение, множеством истинности которого является универсальное множество U, т. е. является логически истинным или тождественно истинным.
Формулы логики предикатов
Наряду с определенными предикатами — для которых истинность или ложность
известны для каждого набора значений свободных предметных переменных, будем рассматривать переменные предикаты, для которых не определены значения. Будем обозначать переменные предикаты большими буквами из конца латинского алфавита с приписанными предметными переменными или без них:
W(х1, х2, ..., хn); U(х,у),....
Применяя к переменным предикатам операции ∧ ; ∨ ; →; ↔; Ї; ∀ ; ∃ , получим формулы логики предикатов,
Формулой логики предикатов называется выражение, составленное из переменных предикатов с помощью логических операций и кванторов и обращающееся в конкретный предикат при подстановке вместо переменных конкретных предикатов.
Пример.
(( ∀ х) W(х, у) ∨ В) → U(z) — формула логики предикатов. Формула логики предикатов называется тавтологией, если при подстановке любых конкретных предикатов она всегда обращается в тождественно истинный предикат.