§ 3. Основные виды формул алгебры высказываний. Законы формул алгебры высказываний.

Определение 1,2. Формула алгебры высказываний F(x_i) называется выполнимой (опровержимой), если она хотя бы один раз принимает значение истины (лжи) при каком-либо наборе значений переменных х_i, входящих в нее. Например, формула из § 2, для которой составлена таблица, является и выполнимой и опровержимой, так как из последнего столбца таблицы следует, что она принимает не менее 1 значения истины (6) и не менее одного значения лжи (2).

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

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

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

Среди тождественно-истинных формул алгебры высказываний важную роль в математической логике и ее приложениях играют так называемые законы алгебры высказываний. Рассмотрим основные из них.

1. Закон исключения третьего. х , то есть для любого высказывания имеет место одно из двух, либо оно истинно, либо ложно, третье места не имеет.

2. Закон отрицания противоречия. , то есть неверно, что одновременно имеет место некоторое высказывание и его отрицание.

3. Закон двойного отрицания. , то есть отрицать отрицание некоторого высказывания это все равно, что утверждать это высказывание.

4. Закон тождества , то есть всякое высказывание есть логическое следствие самого себя.

5. Закон контрапозиции , то есть импликация двух высказываний эквивалентна обратной импликации их отрицаний. Данный закон позволяет устанавливать равносильность различных видов теорем.

6. Закон силлогизма .

Данный закон является правилом вывода, лежащим в основе большинства методов доказательств предложений.

7. Закон приведения к абсурду .

Данный закон является правилом вывода, лежащим в основе доказательства предложений методом от противного.

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