Пусть A(x1, …, xn) — пропозициональная формула, где x1, …, xn — входящие в нее пропозициональные переменные. Конкретный набор истинности значений, приписанных переменным x1, …, xn, называется интерпретацией формулы А. Формула может быть истинной (иметь значение И) при одной интерпретации и ложной (иметь значение Л) при другой интерпретации. Значение формулы А в интерпретации I будем обозначать I(A). Формула, истинная при некоторой интерпретации, называется выполнимой. Формула, истинная при всех возможных интерпретациях, называется общезначимой (или тавтологией). Формула, ложная при всех возможных интерпретациях, называется невыполнимой (или противоречием).
Пример.
AÚØA – тавтология. A&ØA – противоречие, A® ØA – выполнимая формула, она истинна при I(A)=Л.