Тавтологии алгебры логики

(тождественно ложной) на множестве М, если при всякой

подстановке вместо предикатных переменных любых

конкретных предикатов, заданных на этом множестве, она

превращается в ТИ (ТЛ) предикат.

Классификация формул логики предикатов

Формула логики предикатов называется: общезначимой,

или тавтологией ( противоречием), если при всякой

подстановке вместо предикатных переменных любых

конкретных предикатов, заданных на любых множествах,

она превращается в ТИ (соответственно ТЛ) предикат.

Пример. Формула является противоречием,

т. е. тождественно ложной.

От противного: пусть на некотором множестве М имеется

предикат A(х), такой, что эта формула превращается в

истинное высказывание при некотором aM:

Тогда A(a) ложно, а из истинности (y)A(y) следует, что A(a)

истинно. Противоречие. Следовательно данная формула  ТЛ.

Тавтологии логики предикатов

Простейшие тавтологии логики предикатов получаются из

тавтологий алгебры высказываний, и тавтологии алгебры

высказываний образуют часть тавтологий логики предикатов.

Теорема 1. Всякая формула, получающаяся из тавтологии

алгебры высказываний заменой входящих в нее логических

переменных произвольными предикатными переменными,

является тавтологией логики предикатов.

Тавтологии вынесения квантора за знак операции отрицания

Теорема 2. (законы де Моргана для кванторов). Следующие

формулы логики предикатов являются тавтологиями

1.

2.

Выражение кванторов одного через другой

Следствие из теоремы 2:

1. .

2. .

Тавтологии 1 и 2 вытекают из теоремы 2 по закону

двойного отрицания.

Тавтологии переноса кванторов через  и 

Теорема 3. Следующие формулы логики предикатов

являются тавтологиями:

• .