Законы логики.

Существуют формулы, которые принимают значение И независимо от того, какие значения принимают входящие в них атомы. Например,

Такие формулы играют особую роль в логике.

ОПРЕДЕЛЕНИЕ. Формула логики высказываний, которая принимает значение «истина» при любом распределении значений входящих в эту формулу атомов, называется тождественно истинной формулой, тавтологией или законом логики.

Существуют формулы, которые принимают значение «ложь» независимо от того, какие значения принимают входящие в них атомы. Например,

ОПРЕДЕЛЕНИЕ. Формула логики высказываний, принимающая значение «ложь» при любом распределении значений входящих в эту формулу атомов, называется тождественно ложной формулой или противоречием.

Легко убедиться, что если А — противоречие, то будет тавтологией, и наоборот. Например, формула тождественно ложна, а — тавтология.

Существуют формулы, которые принимают как значение И, так и значение в зависимости от того, какие значения принимают входящие в них атомы. Например,

Запись означает, что формула A есть тавтология; например, . Этот закон носит название закона исключенного третьего.

ТЕОРЕМА 1.1. Если А и — тавтологии, то В — тавтология.

Доказательство. Пусть — тавтологии. Допустим, что для какого-либо распределения истинностных значений атомов, входящих в А и В, формула В принимает значение «ложь». Так как А — тавтология, то при том же распределении истинностных значений атомов формула A принимает значение И. Следовательно, формула получит значение A, что противоречит предположению о том, что (А —> В) есть тавтология.

Значит, формула В принимает значение И при любом распределении истинностных значений ее атомов.

ТЕОРЕМА 1.2. Пусть А — формула, содержащая атомы а В — формула, получающаяся из А одновременной подстановкой формул вместо соответственно. Если. А — тавтология, то и В — тавтология.

Доказательство. Пусть задано произвольное распределение истинностных значений атомов, входящих в В. Для этого распределения значений атомов формулы примут соответственно истинностные значения . Если атомам придать соответственно значения то в результате истинностное значение формулы А совпадет со значением формулы В при заданном распределении значений атомов, входящих в В. Так как, по условию, A — тавтология, то В при заданном распределении значений атомов принимает значение «истина», т. е. В тоже тавтология.

Эта теорема показывает, что любая подстановка в тавтологию приводит к тавтологии.

Ниже (в теореме 1.3) приведены часто встречающиеся законы логики.

ТЕОРЕМА 1.3. Следующие формулы являются тавтологиями:

Тавтологические импликации:

Тавтологические эквиваленции:

Тавтологии, выражающие одни операции через другие:

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

Рассмотрим, к примеру, закон силлогизма:

Заметим, что на основании законов ассоциативности можно опускать скобки, посредством которых осуществляется группировка членов многочленных конъюнкций и дизъюнкций. Из закона двойного отрицания следует, что при желании всегда можно избежать двух подряд стоящих знаков «1» и более.