Классификация формул

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

Подстановка в формулу вместо переменных каких-либо их значений называется конкретизацией формулы.

Формула называется выполнимой, если некоторая ее конкретизация является истинным высказыванием. То есть формула выполнима, если существуют такие конкретные высказывания А, В, …, С, что .

Формула называется тождественно истинной или тавтологией, если любая ее конкретизация является истинным высказыванием.

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

Формула называется тождественно ложной или противоречием, если любая ее конкретизация является ложным высказыванием.

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