Законы преобразования алгебры логики.

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

Эти законы являются основными потому, что в логике они играют особо важную роль, являются наиболее важными. Они позволяют упрощать логические выражения и строить умозаключения и доказательства. Первые из вышеперечисленных законов были выявлены и сформулированы Аристотелем, а закон достаточного основания - Г. Лейбницем.

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

Закон непротиворечия: невозможно, чтобы одно и то же в одно и то же время было и не было присуще одному и тому же в одном и том же отношении. То есть невозможно что-либо одновременно утверждать и отрицать.

Закон исключенного третьего: из двух противоречащих суждений одно истинно, другое ложно, а третье не дано.

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

Последний закон говорит о том, доказательство чего-либо предполагает обоснование именно и только истинных мыслей. Ложные же мысли доказать нельзя.

Формулы этого закона нет, так как он имеет только содержательный характер.

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

В алгебре высказываний логические законы выражаются в виде равенства эквивалентных формул.

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

Основными законами являются четыре:

Закон тождества:

А = А

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

Например:

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

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

   То есть если высказывание А – истинно, то его отрицание не А должно быть ложным (и наоборот). Тогда их произведение будет всегда ложным.

А * не А = 0 - вторая формула закона непротиворечия.

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

Закон исключенного третьего.

В один и тот же момент времени высказывание может быть либо истинным, либо ложным, третьего не дано.

Истинно либо А, либо не А.  А + не А = 1

Закон двойного отрицания.

Если отрицать дважды некоторое высказывание, то в результате получается исходное высказывание. 

Законы идемпотентности:

А + А = А                                               

А * А = А

 Законы коммутативности:

А + В = В + А

А * В = В * А

 Законы ассоциативности:

А + (В + С) = (А + В) + С

А * (B * C) = (A * B) * C

 Законы дистрибутивности:

А + (В * С) = (А + В) * (А + С)

(дистрибутивность дизъюнкции относительно конъюнкции)

А * (В + С) = (А * B) + (А * С)

(дистрибутивность конъюнкции относительно дизъюнкции).

 Законы поглощения

А + (А * В) = А

А * (А + В) = А

 Законы де Моргана

Словесные формулировки законов де Моргана:

Замена операций импликации и эквивалентности:

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

 Вместо импликации: 

Для замены операции эквивалентности:

Интересны и следующие правила:

Свойства констант:

1)    не 0 = 1 – отрицание лжи есть истина.

     А + 0 = A

     А + 1 = 1

2)    не 1 = 0 – отрицания истины есть ложь.

     А * 0 = 0

     А * 1 = A