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

Определение. Формула логики предикатов называется выполнимой (опровержимой) на множестве M, если при некоторой подстановке вместо предикатных переменных конкретных предикатов, заданных на множестве M, она превращается в выполнимый (опровержимый) предикат.

Т.е. формула выполнима (опровержима) на M, если существует истинная (ложная) ее интерпретация.

Определение. Формула логики предикатов называется тождественно истинной (тождественно ложной) на множестве M, если при любой подстановке вместо предикатных переменных любых конкретных предикатов, заданных на этом множестве, она превращается в тождественно истинный (тождественно ложный) предикат.

Определение. Формула логики предикатов называется общезначимой или тавтологией (тождественно ложной или противоречием), если при любой подстановке вместо предикатных переменных конкретных предикатов, заданных на каких угодно множествах, она превращается в тождественно истинный (тождественно ложный) предикат.

Тавтология F обозначается .

Значение формулы логики предикатов

Логическое значение формулы логики предикатов определяется, когда задано множество M, на котором определены входящие в эту формулу предикаты.

Логическое значение зависит от трех видов переменных:

1. Значений входящих в формулу переменных высказываний (пропозициональных переменных) – нульместных предикатных переменных;

2. Значений предикатных переменных;

3. Значений свободных предметных переменных из множества M.

Пример

Рассмотрим формулу , в которой двухместный предикатP(x, y) определен на множестве M M, где . В эту формулу входит:

P(x, y) – переменный предикат;

x, y, z – предметные переменные;

y, z – связанные переменные;

x – свободная переменная.

Возьмем вместо P(x, y) фиксированный предикат , свободной переменной придадим значение.

Тогда при предикатпринимает значение ложь.

Импликация при всехпринимает значение истина, т.е. высказываниеимеет значение истина.

§ 10. Тавтологии (равносильности) логики предикатов

Теорема. Всякая формула, получающаяся из тавтологии алгебры высказываний заменой входящих в нее пропозициональных переменных произвольными предикатными переменными, является тавтологией логики предикатов.

Теорема 1. Законы де Моргана для кванторов.

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

1. 

2. 

Доказательство

Докажем тождественную истинность первой формулы.

Данная формула замкнута, т.е. не имеет свободных предметных переменных. Поэтому подставим в эту формулу вместо предикатной переменной любой конкретный одноместный предикат, определенный на некотором множествеМ=>получим высказывание

(*)

-тавтология

Для доказательства его истинности (*) нужно убедиться, что обе части эквивалентности одновременно истинны или одновременно ложны. В самом деле, высказывание истинно тогда и только тогда, когда высказываниеложно, что возможно, на основании определения, тогда и только тогда, когда предикат-опровержим:

Далее, опровержимость предиката означает выполнимость предиката, что равносильно истинности высказывания(по определению)

Итак, высказывание истинно тогда и только тогда, когда высказываниеистинно. Следовательно, высказывание (*) истинно, что и доказывает тождественную истинность первой формулы.

Следствие. (из закона двойного отрицания и теоремы 1). Выражение кванторов друг через друга.

1. 

2. 

Теорема 2. Законы пронесения кванторов через конъюнкцию и дизъюнкцию.

1. 

2. 

1. 

2. 

Теорема 3. Законы пронесения кванторов через импликацию.

1. 

2. 

3. 

4. 

Теорема 4. Законы удаления квантора общности и введения квантора существования.

а).

б).

Теорема 5. Законы коммутативности для кванторов.

1. 

2. 

3.