Шпаргалка Логика и таблицы истинности

Логика — основа информатики и обязательная часть ЕГЭ и ОГЭ. Здесь собраны все логические операции, таблицы истинности, законы алгебры логики, приоритет операций, а также приёмы для заданий №2 и №15 ЕГЭ: логические уравнения, подсчёт числа решений и диаграммы Эйлера-Венна для поисковых запросов.

Логические значения и переменные

Логическая (булева) величина принимает только два значения: истина (1, True, «да») или ложь (0, False, «нет»). В заданиях ЕГЭ почти всегда используют обозначения 1 и 0. Логические переменные обычно обозначают буквами A, B, C, x, y, z.

Высказывание — это утверждение, о котором можно сказать, истинно оно или ложно. Например, «5 > 3» истинно (1), «2 > 7» ложно (0).

НЕ — отрицание (¬, инверсия)

Отрицание меняет значение на противоположное. Обозначения: ¬A, Ā, not A, !A. Читается «не A». Это унарная операция (применяется к одному операнду).

A	¬A
0	1
1	0

Двойное отрицание возвращает исходное значение: ¬¬A = A.

И — конъюнкция (∧, логическое умножение)

Конъюнкция истинна только когда оба операнда истинны. Обозначения: A ∧ B, A · B, A && B, A and B. Похожа на умножение: A ∧ B = 1, только если A = 1 и B = 1.

A	B	A ∧ B
0	0	0
0	1	0
1	0	0
1	1	1

ИЛИ — дизъюнкция (∨, логическое сложение)

Дизъюнкция ложна только когда оба операнда ложны. В остальных случаях истинна. Обозначения: A ∨ B, A + B, A || B, A or B.

A	B	A ∨ B
0	0	0
0	1	1
1	0	1
1	1	1

Импликация (→, следование)

Импликация A → B читается «если A, то B» (из A следует B). Она ложна в единственном случае: когда A = 1, а B = 0 («из истины не может следовать ложь»). Запомните строку 1 → 0 = 0 — на ней «ловят» большинство ошибок.

A	B	A → B
0	0	1
0	1	1
1	0	0
1	1	1

Ключевая формула ЕГЭ: A → B = ¬A ∨ B. Любую импликацию можно заменить дизъюнкцией отрицания первого аргумента со вторым. Это главный приём для задания №15.

Эквиваленция (↔, равнозначность)

Эквиваленция A ↔ B истинна, когда значения операндов совпадают (оба 0 или оба 1). Обозначения: A ↔ B, A ≡ B, A ~ B.

A	B	A ↔ B
0	0	1
0	1	0
1	0	0
1	1	1

Полезные равенства: A ↔ B = (A → B) ∧ (B → A) и A ↔ B = ¬(A ⊕ B).

Исключающее ИЛИ — XOR (⊕, сложение по модулю 2)

Исключающее ИЛИ A ⊕ B истинно, когда значения операндов различны. Это полная противоположность эквиваленции. Обозначения: A ⊕ B, A xor B, A ≠ B.

A	B	A ⊕ B
0	0	0
0	1	1
1	0	1
1	1	0

Полезно: A ⊕ B = ¬(A ↔ B), а также A ⊕ A = 0 и A ⊕ 0 = A.

Сводная таблица всех операций

Все бинарные операции на одной картинке — удобно для повторения перед экзаменом.

A	B	A ∧ B	A ∨ B	A → B	A ↔ B	A ⊕ B
0	0	0	0	1	1	0
0	1	0	1	1	0	1
1	0	0	1	0	0	1
1	1	1	1	1	1	0

Приоритет логических операций

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

¬ — отрицание (самый высокий приоритет)
∧ — конъюнкция (И)
∨ — дизъюнкция (ИЛИ)
→ — импликация
↔ — эквиваленция (самый низкий приоритет)

Скобки меняют порядок и выполняются первыми. Исключающее ИЛИ обычно приравнивают по приоритету к дизъюнкции (но в заданиях ЕГЭ XOR почти всегда в скобках).

Пример разбора ¬A ∨ B ∧ C: сначала ¬A, затем B ∧ C, затем (¬A) ∨ (B ∧ C).

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

Законы позволяют упрощать выражения и решать задание №15 без полного перебора. Главное оружие — законы де Моргана.

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

Отрицание «переносится внутрь скобок», при этом ∧ меняется на ∨ и наоборот:

¬(A ∧ B) = ¬A ∨ ¬B
¬(A ∨ B) = ¬A ∧ ¬B

Переместительный и сочетательный

A ∧ B = B ∧ A          A ∨ B = B ∨ A
(A ∧ B) ∧ C = A ∧ (B ∧ C)
(A ∨ B) ∨ C = A ∨ (B ∨ C)

Распределительный (раскрытие скобок)

A ∧ (B ∨ C) = (A ∧ B) ∨ (A ∧ C)
A ∨ (B ∧ C) = (A ∨ B) ∧ (A ∨ C)

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

A ∨ (A ∧ B) = A
A ∧ (A ∨ B) = A

Закон склеивания

(A ∧ B) ∨ (A ∧ ¬B) = A
(A ∨ B) ∧ (A ∨ ¬B) = A

Операции с константами и идемпотентность

A ∧ 1 = A      A ∧ 0 = 0      A ∧ A = A      A ∧ ¬A = 0
A ∨ 1 = 1      A ∨ 0 = A      A ∨ A = A      A ∨ ¬A = 1
¬¬A = A

Замена импликации и эквиваленции

A → B = ¬A ∨ B
A ↔ B = (¬A ∨ B) ∧ (A ∨ ¬B)
A ⊕ B = (A ∧ ¬B) ∨ (¬A ∧ B)

Построение таблицы истинности сложного выражения

Алгоритм для выражения с n переменными:

Определить число переменных n — строк будет 2ⁿ (для 3 переменных — 8 строк).
Выписать наборы значений переменных по порядку (как двоичные числа от 0 до 2ⁿ−1).
Расставить промежуточные столбцы по приоритету операций.
Заполнять столбцы слева направо, опираясь на таблицы базовых операций.

Пример: построим таблицу для F = (A ∨ B) → ¬C.

A	B	C	A ∨ B	¬C	F = (A∨B) → ¬C
0	0	0	0	1	1
0	0	1	0	0	1
0	1	0	1	1	1
0	1	1	1	0	0
1	0	0	1	1	1
1	0	1	1	0	0
1	1	0	1	1	1
1	1	1	1	0	0

Задание ЕГЭ №2: восстановление по фрагменту таблицы

В задании №2 дан фрагмент таблицы истинности логической функции и сама функция (или несколько), нужно сопоставить столбцы таблицы с переменными x1, x2, x3…

Приём: найдите строку, где функция = 0 (для дизъюнкции/импликации) или = 1 (для конъюнкции) — таких строк обычно мало, и они однозначно задают значения переменных. Затем подберите соответствие столбцов.

Пример. Функция F = (x ∧ ¬y) ∨ (¬z). Найдём, когда F = 0: нужно x ∧ ¬y = 0 и ¬z = 0, то есть z = 1 и (x = 0 или y = 1). Это резко сужает перебор и помогает «привязать» столбцы фрагмента к переменным.

Задание ЕГЭ №15: логические уравнения и системы

В задании №15 чаще всего нужно найти количество различных наборов переменных, при которых выражение истинно (или ложно), либо подобрать наибольшее число A для тождественно истинной формулы с делимостью/отрезками.

Тип 1. Подсчёт числа решений уравнения

Дано логическое выражение от n переменных, нужно посчитать, на скольких из 2ⁿ наборов оно равно 1.

Стратегия: заменить импликации по формуле A → B = ¬A ∨ B, упростить законами, а затем либо построить дерево решений, либо рассуждать «от конца цепочки».

Пример: сколько решений у уравнения (A → B) ∧ (B → C) = 1 при трёх переменных? Условие требует: если A=1, то B=1; если B=1, то C=1. Перебираем 8 наборов:

A	B	C	A→B	B→C	F
0	0	0	1	1	1
0	0	1	1	1	1
0	1	0	1	0	0
0	1	1	1	1	1
1	0	0	0	1	0
1	0	1	0	1	0
1	1	0	1	0	0
1	1	1	1	1	1

Истинных строк — 4. Это решения: 000, 001, 011, 111. Заметьте закономерность: цепочка импликаций x1 → x2 → … → xn имеет ровно n+1 решение.

Тип 2. Системы уравнений с цепочками

Часто дают систему вида:

(x1 → x2) = 1
(x2 → x3) = 1
...
(x(n−1) → xn) = 1

Каждое уравнение независимо, но переменные общие. Считают число наборов комбинаторно или методом «динамики»: ведут таблицу, в которой для каждого значения последней переменной хранят число способов. Для одной цепочки импликаций ответ — n+1; при добавлении эквиваленций и второй цепочки числа перемножают/складывают по правилам.

Метод подсчёта по «дереву»

Удобный приём для систем: идти от первой переменной к последней. На каждом шаге для значений 0 и 1 текущей переменной записывать, сколько наборов приводит к этому значению с учётом всех уже учтённых уравнений. Итоговое число решений — сумма по последнему столбцу.

Диаграммы Эйлера-Венна (поисковые запросы)

Задание про поисковые запросы: запрос «&» (логическое И) — это пересечение множеств, запрос «|» (логическое ИЛИ) — объединение. Число найденных страниц равно мощности соответствующего множества.

Обозначим количество страниц по запросам через площади областей на диаграмме. Базовая формула для двух множеств:

|A ∨ B| = |A| + |B| − |A ∧ B|

Отсюда пересечение: |A ∧ B| = |A| + |B| − |A ∨ B|.

Типовая задача. Известно число страниц по запросам:

Запрос	Найдено страниц
Тигр \| Лев	200
Тигр	120
Лев	140
Тигр & Лев	?

Решение: |Тигр & Лев| = 120 + 140 − 200 = 60 страниц.

Для трёх множеств используют формулу включений-исключений:

|A ∨ B ∨ C| = |A| + |B| + |C|
            − |A ∧ B| − |A ∧ C| − |B ∧ C|
            + |A ∧ B ∧ C|

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

Частые ошибки на экзамене

Путают строку импликации 1 → 0 = 0 — это единственный ложный случай, проверяйте отдельно.
Забывают приоритет: ¬ сильнее ∧, а ∧ сильнее ∨.
При применении де Моргана не меняют ∧ на ∨ (и наоборот).
В запросах путают «&» (пересечение, меньше страниц) и «|» (объединение, больше страниц).
При подсчёте решений забывают, что всего наборов 2ⁿ, и теряют строки.