Законы логики и упрощение логических выражений

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

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

Основные операции

Напомним обозначения: И (конъюнкция, «и»), ИЛИ (дизъюнкция, «или»), НЕ (отрицание). Истину обозначим 1, ложь — 0.

Основные законы

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

Эти два закона особенно важны, потому что позволяют «вносить» отрицание внутрь скобок, меняя операцию на противоположную:

НЕ(A И B) = (НЕ A) ИЛИ (НЕ B)
НЕ(A ИЛИ B) = (НЕ A) И (НЕ B)

Словами: отрицание «и» превращается в «или» отрицаний, и наоборот. Это помогает упрощать условия вроде «не (идёт дождь и холодно)».

Пример упрощения

Упростим выражение A И B ИЛИ A И НЕ B. Вынесем общий множитель A по распределительному закону:

A И B ИЛИ A И НЕ B
= A И (B ИЛИ НЕ B)
= A И 1
= A

Здесь мы использовали закон исключённого третьего: B ИЛИ НЕ B = 1, а конъюнкция с единицей даёт сам множитель. Сложное выражение свернулось до одной переменной.

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

Особые значения

• A И 1 = A, A И 0 = 0;
• A ИЛИ 1 = 1, A ИЛИ 0 = A;
• A И НЕ A = 0 (противоречие);
• A ИЛИ НЕ A = 1 (исключённое третье).

Частые ошибки. При применении де Моргана не забывайте менять «и» на «или» (и наоборот) и ставить отрицание над каждой переменной. Сначала выполняется отрицание, затем «и», затем «или» — соблюдайте приоритет операций. Проверять упрощение удобно таблицей истинности.

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

Кратко о главном

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