12.Предикаты

Предикат — любое математическое высказывание, в котором есть, по меньшей мере, одна переменная. Предикат является основным объектом изучения логики первого порядка.

Предикат (n-местный, или n-арный) — это функция с множеством значений {0,1} (или «ложь» и «истина»), определённая на множестве M = M1хM2х…хMn.Таким образом, каждый набор элементов множества M он характеризует либо как «истинный», либо как «ложный». Одноместный предикат определяет отношение принадлежности некоторому множеству. Предикат — один из элементов логики первого и высших порядков. Начиная с логики второго порядка, в формулах можно ставить кванторы по предикатам. Предикат называют тождественно-истинным и пишут:

P (x1, …, xn) = 1

если на любом наборе аргументов он принимает значение 1.Предикат называют тождественно-ложным и пишут:

P (x1, …, xn) = 0

если на любом наборе аргументов он принимает значение 0.

Предикат называют выполнимым, если хотя бы на одном наборе аргументов он принимает значение 1.Так как предикаты принимают только два значения, то к ним применимы все операции булевой алгебры, например: отрицание, импликация, конъюнкция, дизъюнкция и т. Д

13.Кванторы

Квантор — общее название для логических операций, ограничивающих область истинности какого-либо предиката. Чаще всего упоминают:

Квантор всеобщности (читается: «для всех…», «для каждого…» или «каждый…», «любой…», «для любого…»).

Квантор существования (читается: «существует…» или «найдётся…»).

В математической логике приписывание квантора к формуле называется связыванием или квантификацией.

В многозначных логиках также вводятся и другие кванторы, например, квантор плюральности (квантор Решера) (обозначается перевёрнутой M, читается «для большинства …»).

Высказывание для любого x P(x) означает, что область значений переменной x включена в область истинности предиката P(x). («При всех значениях (x) утверждение верно»).

Высказывание существует x P(x) означает, что область истинности предиката P(x) непуста. («Существует (x) при котором утверждение верно»).

14.Система аксиом в исчислении предикатов

Как и в случае исчисления высказываний, при построении исчисления предикатов недостаточно указать лишь способ записи формул. Необходимо задать еще правила преобразования формул, выражаемые аксиомами. В число аксиом исчисления предикатов включаются все 11 аксиом исчисления высказываний.

А1: A-> (B ->A);

A2: ((A-> (B ->C)) -> ((A->B) -> (A->C)));

A3: A/\ B ->A;

A4: A/\ B ->B;

A5: A -> (B -> (A /\ B));

A6: A -> (A\/ B);

A7: B -> (A\/ B);

A8: (A->C) -> ((B-> C) -> ((A \/ B) -> C));

A9: -A -> (A->B);

A10: (A ->B) -> ((A-> -B) -> -A);

A11: A \/ -A.

Первые четыре группы аксиом представляют собой не что иное, как аксиомы исчисления высказываний. К ним добавляются еще две новые аксиомы, составляющие группу V. Этим и исчерпывается система аксиом исчисления предикатов.

1. Для любого xA -> A[t/x],

2. A[t/x] -> существует xA,

где A[t/x] — формула, полученная в результате подстановки терма t вместо каждой свободной переменной x, встречающейся в формуле A.

Правил вывода 2:

Modus ponens: A, A->B делить на / B

Правило обобщения A делить на / для любого x A

Нетрудно видеть, что каждая выводимая формула исчисления предикатов является в то же время и тождественно истинной в наивном теоретико-множественном смысле. Во-первых, очевидно, что аксиомы исчисления предикатов тождественно истинны. Во-вторых, применение правил вывода исчисления предикатов к тождественно истинным формулам приводит к тождественно истинным формулам. Это очевидно для правила заключения. Для правил переименования свободных и связанных переменных это также очевидно.