2.1. Интерпретация формул

Пусть A(x1,x2,…xn) – пропозициональная формула, где x1,x2,…xn – пропозициональные переменные. Конкретный набор значений, который принимают переменные x1,x2,…xn называется интерпретацией.

I(A) – значение формулы в интерпретации I.

В одной интерпретации формула может быть истинной, а в другой – ложной.

Формула, истинная в какой- то интерпретации – выполнимая.

Формула истинная во всех интерпретациях – тавтология (тождественно истинная формула), иначе – противоречие.

Пример 1.

Докажем, что формула является тавтологией.

Пример 2.

Докажем, что формула является выполнимой.