В логике высказываний известно много общезначимых формул, которые также называются законами логики высказываний. Основными законами являются следующие:
· законы идемпотентности:
o x Ù x = x
o x Ú x = x
· x Ù 1 = x
· x Ú 1 = 1
· x Ù 0 = 0
· x Ú 0 = x
· x Ù Ø x = 0 – закон противоречия
· x Ú Ø x = 1 – закон исключения третьего
· Ø Ø x = x – закон снятия двойного отрицания
· законы поглощения
o x Ù (y Ú x) = x
o x Ú (y Ù x) = x
Доказательство этих и последующих законов элементарно осуществляется с помощью построения таблиц истинности или простейших логических рассуждений.
Следующая группа законов представляет взаимосвязь между логическими операциями:
· (x º y) = (x ® y) Ù (y ® x)
· x ® y = Ø x Ú y
· законы Де Моргана
o Ø (y Ú x) = Ø y Ù Ø x
o Ø (y Ù x) = Ø y Ú Ø x
Замечательным следствием приведенных выше законов является следующий факт. Любую логическую формулу можно заменить равносильной ей, но содержащую только две логические операции: конъюнкцию или отрицание или дизъюнкцию или отрицание. Дальнейшее исключение логических операций, очевидно, невозможно, то есть приведенные пары представляют минимальный базис для построения правильно построенных формул. Однако существует операция, с помощью которой можно представить любую логическую связку. Эта операция получила название «штрих Шеффера» и определяется следующим образом:
|
|
х | у | х | у |
0 | 0 | 1 |
0 | 1 | 1 |
1 | 0 | 1 |
1 | 1 | 0 |
На основании этого определения можно ввести следующие законы, выражающие взаимосвязь операции «штрих Шеффера» и других логических связок:
· Ø x = x | x
· x Ù y = (x | y) | (x | y)
Также следует отметить, что x | y = Ø (x Ù y).
К основным законам алгебры логики также относятся следующие:
· коммутативные законы
o х Ù y = y Ù х
o х Ú y = y Ú х
· дистрибутивные законы
o х Ù (y Ú z) = (х Ù y) Ú (х Ù z)
o х Ú (y Ù z) = (х Ú y) Ù (х Ú z)
· ассоциативные законы
o х Ù (y Ù z) = (х Ù y) Ù z
o х Ú (y Ú z) = (х Ú y) Ú z
Еще одним важным законом алгебры логики является закон двойственности. Пусть формула A содержит только операции конъюнкции, дизъюнкции и отрицания. Для операции конъюнкции двойственной считается дизъюнкция, а для дизъюнкции – конъюнкция. Тогда по определению формулы A и A* называются двойственными, если формула A* получается из A путем замены в ней каждой операции на двойственную. Например, для формулы (х Ú y) Ù z двойственной формулой будет (х Ù y) Ú z. Для двойственных формул справедлива следующая теорема: если формулы A и B равносильны, то равносильны и двойственные им формулы, то есть A* = B*. Данную теорему оставим без доказательства.
|
|
С помощью законов логики можно осуществлять равносильные преобразования. Такие преобразования используются для доказательств, приведения формул к заданному виду, упрощения формул.
Под сложностью формул обычно понимается количество символов, используемых для ее записи. То есть формула α проще формулы b, если α содержит меньше букв и логических операций. Например, для формулы (Ø (x Ú y) ® x Ú y) Ù y можно записать следующую цепочку преобразований, приводящих ее к более простому виду:
(ØØ (x Ú y) Ú x Ú y) Ù y = (x Ú y Ú x Ú y) Ù y = (x Ú y) Ù y = y.