Законы алгебры логики

Видео: Лекция 1: Функции алгебры логики

Современные компьютеры, основанные на «древних» электронно-вычислительных машинах, в качестве базовых принципов работы опираются на определенные постулаты. Они называются законы алгебры логики. Впервые подобная дисциплина была описана (конечно, не столь подробно, как в современном виде) древнегреческим ученым Аристотелем.

Видео: Лекция: Основы алгебры логики - законы алгебры логики

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

С тем чтобы лучше разобраться в теме, разберем понятия, которые помогут в дальнейшем узнать законы алгебры логики.

Пожалуй, основной термин в изучаемой дисциплине – высказывание. Это некое утверждение, которое не может быть одновременно ложным и истинным. Ему всегда присуща лишь одна из этих характеристик. При этом условно принято истинности придавать значение 1, ложности – 0, а само высказывание называть некой латинской буквой: A, B, C. Иначе говоря, формула A=1 означает, что высказывание А истинно. С высказываниями можно поступать самым различным образом. Вкратце рассмотрим те действия, которые можно с ними совершать. Отметим также, что законы алгебры логики невозможно усвоить, не зная этих правил.

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

Видео: Законы алгебры логики

2. Конъюнкция. Результатом подобного действия, совершаемого с двумя высказываниями, станет новое высказывание, истинное лишь в случае, когда оба исходных высказывания истинны. Используется операция «и», символ «^».

3. Импликация. Операция «если А, то В». Результатом является высказывание, ложное лишь в случае истинности А и ложности В. Применяется символ «->».

4. Эквиваленция. Операция «A тогда и только тогда В, когда». Данное высказывание истинно в случаях, когда обе переменные имеют одинаковые оценки. Используется символ «<->».

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

Теперь подробным образом рассмотрим основные законы алгебры логики:

1. Коммутативный или переместительный гласит, что перемена мест логических слагаемых в операциях конъюнкции или дизъюнкции на результате не сказывается.

Видео: Начала Булевой алгебры

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

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

4. Закон де Моргана (инверсии или отрицания). Отрицание операции конъюнкции равносильно дизъюнкции отрицания исходных переменных. Отрицание от дизъюнкции, в свою очередь, равно конъюнкции отрицания тех же переменных.

5. Двойное отрицание. Отрицание некоего высказывания дважды дает в результате исходное высказывание, трижды – его отрицание.

6. Закон идемпотентности выглядит следующим образом для логического сложения: x v x v x v x = x- для умножения: x^x^x^=x.

7. Закон непротиворечия гласит: два высказывания, если они противоречивы, одновременно быть истинными не могут.

8. Закон исключения третьего. Среди двух противоречивых высказываний одно – всегда истинное, другое – ложное, третьего не дано.

9. Закон поглощения можно записать таким образом для логического сложения: x v (x^y)=x, для умножения: x^ (x v y)=x.

10. Закон склеивания. Две соседние конъюнкции способны склеиться, образовав конъюнкцию меньшего ранга. При этом та переменная, по которой исходные конъюнкции склеивались, исчезает. Пример для логического сложения:

(x^y) v (-x^y)=y.

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

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