Основы алгебры логики: операции и приоритет

Фундамент логического блока: пять операций, их приоритет и таблицы истинности.

Алгебра логики оперирует высказываниями, которые либо истинны (1), либо ложны (0). Логические операции комбинируют такие значения по строгим правилам, заданным таблицами истинности.

Пять операций ЕГЭ

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

Таблицы истинности операций

Это нужно знать наизусть. Особое внимание импликации — она ломает интуицию: «из лжи следует что угодно», поэтому при A=0 импликация всегда истинна.

from itertools import product

print("A B | НЕ A  A И B  A ИЛИ B  A->B  A==B")
for A, B in product([0, 1], repeat=2):
    not_a = int(not A)
    konj  = int(A and B)
    disj  = int(A or B)
    impl  = int((not A) or B)      # импликация = НЕ A ИЛИ B
    equ   = int(A == B)
    print(f"{A} {B} |   {not_a}     {konj}      {disj}       {impl}     {equ}")

Вывод:

A B | НЕ A  A И B  A ИЛИ B  A->B  A==B
0 0 |   1     0      0       1     1
0 1 |   1     0      1       1     0
1 0 |   0     0      1       0     0
1 1 |   0     1      1       1     1

Импликация через ИЛИ — главный приём

Запомните тождество, которое спасает в задании 15: A → B = ¬A ∨ B. Любую импликацию можно заменить дизъюнкцией с отрицанием первого аргумента. Это упрощает выражения и позволяет считать импликацию в Python, где готовой операции «→» нет:

# импликация в Python: A -> B эквивалентно (not A) or B
def impl(a, b):
    return (not a) or b

print("0 -> 0 =", int(impl(0, 0)))
print("0 -> 1 =", int(impl(0, 1)))
print("1 -> 0 =", int(impl(1, 0)))   # единственный ложный случай
print("1 -> 1 =", int(impl(1, 1)))

Вывод:

0 -> 0 = 1
0 -> 1 = 1
1 -> 0 = 0
1 -> 1 = 1

Приоритет операций

Когда в выражении нет скобок, операции выполняются в строгом порядке. Перепутать приоритет — самая частая логическая ошибка:

1. Отрицание (¬, НЕ) — самое сильное.
2. Конъюнкция (∧, И).
3. Дизъюнкция (∨, ИЛИ).
4. Импликация (→).
5. Эквивалентность (≡) — самая слабая.

То есть выражение A ∨ B ∧ C читается как A ∨ (B ∧ C), а ¬A ∧ B — как (¬A) ∧ B. В Python приоритет совпадает по сути: not сильнее and, and сильнее or.

Полезные тождества

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

Проверим закон Де Моргана программой — пусть машина подтвердит, что левая и правая части совпадают на всех наборах:

from itertools import product

ok = True
for A, B in product([0, 1], repeat=2):
    left  = int(not (A and B))         # НЕ(A И B)
    right = int((not A) or (not B))    # НЕ A ИЛИ НЕ B
    if left != right:
        ok = False
print("закон Де Моргана выполняется на всех наборах:", ok)

Вывод:

закон Де Моргана выполняется на всех наборах: True

Упрощение выражений: зачем это нужно

В заданиях 2 и особенно 15 формулы бывают громоздкими. Прежде чем строить таблицу или запускать перебор, выражение полезно упростить — это снижает риск ошибки и иногда сразу даёт ответ. Главные приёмы: заменить импликацию на ¬A ∨ B, «раскрыть» отрицание скобки по Де Моргану, убрать двойное отрицание. Покажем на примере, что упрощённая и исходная формулы совпадают на всех наборах — это и есть критерий правильного упрощения:

from itertools import product

# исходное: НЕ (A -> B)  =  НЕ ((НЕ A) ИЛИ B)
# по Де Моргану и двойному отрицанию это A И (НЕ B)
ok = True
for A, B in product([0, 1], repeat=2):
    original    = int(not ((not A) or B))   # НЕ(A -> B)
    simplified  = int(A and (not B))        # A И НЕ B
    if original != simplified:
        ok = False
print("НЕ(A -> B) равно A И НЕ B на всех наборах:", ok)

Вывод:

НЕ(A -> B) равно A И НЕ B на всех наборах: True

Этот факт стоит запомнить: отрицание импликации ¬(A → B) = A ∧ ¬B. Импликация ложна ровно тогда, когда посылка истинна, а следствие ложно — что и описывает A ∧ ¬B.

Тождественно истинные и ложные выражения

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

from itertools import product

def F(A, B):
    return ((not A) or B) or (A and not B)   # (A->B) ИЛИ (A И НЕ B)

vals = [int(F(A, B)) for A, B in product([0, 1], repeat=2)]
print("значения на всех наборах:", vals)
if all(vals):
    print("тождественно истинно (тавтология)")
elif not any(vals):
    print("тождественно ложно")
else:
    print("выполнимо, но не тавтология")

Вывод:

значения на всех наборах: [1, 1, 1, 1]
тождественно истинно (тавтология)

Типичные ловушки

• Импликация при A=0. Если посылка ложна, импликация истинна — независимо от B. Это контринтуитивно, но именно так.
• Приоритет. Без скобок И выполняется раньше ИЛИ. Не читайте слева направо.
• Эквивалентность слабее импликации. В выражении A → B ≡ C сначала вычисляется A → B, потом эквивалентность с C.
• Отрицание импликации. Запомните: ¬(A → B) = A ∧ ¬B, а не ¬A ∧ B.

Итог

• Пять операций: НЕ, И, ИЛИ, импликация (→), эквивалентность (≡).
• Ключевое тождество: A → B = ¬A ∨ B; импликация ложна только при 1 → 0.
• Приоритет: НЕ → И → ИЛИ → импликация → эквивалентность.