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