Формулы алгебры логики. Тавтологии.

 

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

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

Определение 1: Формулами исчисления высказываний являются:

а) каждая пропозиционная буква;

б) если и - формулы, то формулами являются также , , , , , .

Выражения, перечисленные в пункте б), называются соответственно отрицанием формулы , конъюнкцией, дизъюнкцией, импликацией, эквивалентностью, сложением по модулю 2 формул и .

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

Для уменьшения числа скобок в формулах принято пропозиционные буквы и отрицание в скобки не заключать. Затем, как и в алгебре, принята приоритетность операций в такой последовательности: Ї, , , , .

Так, например, выражение является формулой, в которой все скобки можно опустить. А в выражении скобки опускать нельзя.

Определение 2: Формулы исчисления высказываний, образованные из пропозиционных букв , ,..., , логических операций и скобок, будем обозначать . Если в этой формуле заменить пропозиционные буквы , ,..., соответственно высказываниями , ,..., , то получим составное высказывание , которое назовём логическим значением формулы при , ,..., .

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

 

л	л	л	и	и	и
л	л	и	и	и	и
л	и	л	и	и	и
л	и	и	и	и	и
и	л	л	и	л	и
и	л	и	и	и	и
и	и	л	л	л	л
и	и	и	л	и	и

 

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

Определение 3: Формула исчисления высказываний называется тавтологией (или тождественно истинной формулой), если её значения есть «истина» для всех наборов значений пропозиционных переменных, входящих в эту формулу.

Нахождение тавтологий – это основная задача логики высказываний, так как они выражают законы логического мышления.

Для произвольной формулы легко проверить, является ли она тавтологией. Для этого составляют таблицу истинности этой формулы, или проверяют с помощью рассуждений. Например, для рассмотренной формулы можно выяснить, когда обе части дизъюнкции и будут ложными. Первая часть ложна, когда . Вторая часть принимает ложное значение, когда , . Таким образом, , значит, формула не является тавтологией.

Теорема 1: Следующие формулы исчисления высказываний являются тавтологиями:

1) - закон исключенного третьего;

2) - закон отрицания противоречия;

3) - закон двойного отрицания;

4) ,

5) ,

6) ,

7) - законы упрощения;

8) ,

9) - законы коммутативности конъюнкции и дизъюнкции;

10) ,

11) - законы ассоциативности операций и ;

12) ,

13) - законы дистрибутивности;

14) ,

15) - законы де Моргана;

16) - закон тождества;

17) - закон контрапозиции;

18) - правило цепного заключения;

19) ,

20) ,

21) - свойства рефлексивности, симметричности и транзитивности операции ↔ соответственно;

22) - закон противоречия.

Доказательство: Эту теорему можно доказать, построив таблицу истинности для каждой тавтологии. При этом для любого набора значений пропозиционных переменных, входящих в формулу (т. е. для каждой строки таблицы), формула должна принимать значение «истина».

Докажем некоторые из перечисленных тавтологий.

(1) Действительно, по определению отрицания, для любого высказывания , либо оно, либо его отрицание истинно. И, следовательно, дизъюнкция истинна, т. к. одна из её компонент обязательно будет истинной. Первое утверждение теоремы доказано.

(7) Пусть и – некоторые высказывания. Если конъюнкция истинна, то и высказывание истинно. Таким образом, для любых двух высказываний значение импликации не может быть ложью. Значит это тавтология.

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

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

Остальные утверждения теоремы доказываются аналогично.

Определение 4: Формула исчисления высказываний называется тождественно ложной (или противоречием), если при любом наборе значений пропозиционных переменных, входящих в эту формулу, она принимает значение «ложь».

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

Определение 5: Формула исчисления высказываний называется выполнимой, если существует такой набор значений пропозиционных переменных, входящих в эту формулу, при котором формула принимает значение «истина».

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

Определение 6: Формулы и называются равносильными (логически эквивалентными), если при любом наборе значений пропозиционных переменных формулы и принимают одинаковые истинностные значения.

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

 

Зависимости между различными логическими операциями:

1) ,

2) ,

3) ,

4) ,

5) ,

6) ,

7) ,

8) ,

9) .

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

Докажем выборочно некоторые равносильности.

(4) Построим таблицу истинности для данной формулы:

 

и	и	л	и	и
и	л	л	л	л
л	и	и	и	и
л	л	и	и	и

 

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

Таким образом, равносильные формулы будут иметь одинаковые таблицы истинности и наоборот, формулы, таблицы истинности которых совпадают, равносильны. Этим можно пользоваться на практике для установления равносильности формул.

Докажем это же утверждение (4) с помощью рассуждений.

Пусть и – произвольные высказывания. Импликация ложна в одном случае, когда , . Дизъюнкция ложна, если оба высказывания и – ложны, т. е. , . Таким образом, и оба ложны тогда и только тогда, когда , . В остальных случаях оба высказывания всегда истинны. Значит, при любом наборе значений пропозиционных переменных данные формулы принимают одинаковые истинностные значения, т. е. эквивалентны.

Остальные равносильности можно доказать аналогично.

Теорема 2: (Условие равносильности формул исчисления высказываний):

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