ЕГЭ–2026, информатика: задания, ответы, решения

Построение и анализ таблиц истинности логических выражений

Условные обозначения логических операций:

¬A, $\barA$ — не A (отрицание, инверсия);

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

A ∨ B, A + B— A или B (логическое сложение, дизъюнкция);

A → B— импликация (следование);

A ≡ B— эквивалентность (равносильность).

Операцию «импликация» можно выразить через «ИЛИ» и «НЕ»:

A → B = ¬A ∨ B — A → B = $\barA плюс B.$

Иногда для упрощения выражений полезны формулы де Моргана:

¬(A ∧ B) = ¬A ∨ ¬B — $\overlineA умножить на B=\barA плюс \barB;$

¬(A ∨ B) = ¬A ∧ ¬B — $\overlineA плюс B=\barA умножить на \barB.$

Если в выражении нет скобок, сначала выполняются все операции «НЕ», затем — «И», затем — «ИЛИ», «импликация», и самая последняя — «эквивалентность».

Таблица истинности выражения определяет его значения при всех возможных комбинациях исходных данных.

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

Количество разных логических выражений, удовлетворяющих неполной таблице истинности, равно $2 в степени левая круглая скобка k правая круглая скобка ,$ где k – число отсутствующих строк; например, полная таблица истинности выражения с тремя переменными содержит 23 = 8 строчек, если заданы только 6 из них, то можно найти 2⁸⁻⁶ = 2² = 4 разных логических выражения, удовлетворяющие этим 6 строчкам (но отличающиеся в двух оставшихся).

Логическая сумма A + B + C + … равна 0 (выражение ложно) тогда и только тогда, когда все слагаемые одновременно равны нулю, а в остальных случаях равна 1 (выражение истинно).

Логическое произведение A · B · C · … равно 1 (выражение истинно) тогда и только тогда, когда все сомножители одновременно равны единице, а в остальных случаях равно 0 (выражение ложно).

Логическое следование (импликация) А → В равна 0 тогда и только тогда, когда A (посылка) истинна, а B (следствие) ложно.

Эквивалентность А ≡ B равна 1 тогда и только тогда, когда оба значения одновременно равны 0 или одновременно равны 1.

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

В поисковых запросах операция «НЕ» обозначается знаком ~, операция «И» обозначается знаком &, а операция «ИЛИ» — знаком |.

Пусть A — множество страниц, на которых встречается слово A, а B — множество страниц, на которых встречается слово B; тогда:

а) запрос A & B соответствует пересечению множеств A ∩ B;

б) запрос A | B соответствует объединению множеств A ∪ B.

Будем обозначать через N_X количество страниц, которые выдаёт поисковая система по запросу X.

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

N_{A | B} = N_A + N_B − N_{A & B}

Эту формулу можно переписать в разных формах в зависимости от того, что требуется найти, например,

N_{A & B} = N_A + N_B − N_{A | B};

N_A = N_{A | B} + N_{A & B} − N_B;

N_A + N_B = N_{A | B} + N_{A & B}

Равенство сохраняется, если каждая из 4-х областей заменяется на её пересечение с третьей областью C:

N_{(A | B) & C} = N_{A & C} + N_{B & C} – N_{A & B & C}

Таким образом, если все 4 запроса имеют вид X & C, область C при вычислениях можно игнорировать (это равносильно переходу от областей A и B к областям A’ = A & C и B’ = B & C, что не изменяет результата).

Формула включений и исключений для трёх областей выглядит так:

N_{A | B | C} = N_A + N_B + N_C – N_{A & B} – N_{A & C} – N_{B & C} +

+ N_{A & B & C}.

Основные понятия математической логики

Для упрощения выражений можно использовать формулы:

$A плюс A умножить на B=A$ (т. к. $A плюс A умножить на B=$

$=A умножить на 1 плюс A умножить на B=A умножить на левая круглая скобка 1 плюс B правая круглая скобка =A умножить на 1=A$ );

$A плюс \barA умножить на B=A плюс B$ (т.к. $A плюс \barA умножить на B=$

$= левая круглая скобка A плюс \barA правая круглая скобка умножить на левая круглая скобка A плюс B правая круглая скобка =1 умножить на левая круглая скобка A плюс B правая круглая скобка =A плюс B$ ).

Некоторые свойства импликации:

$A\to левая круглая скобка B умножить на C правая круглая скобка = левая круглая скобка A\to B правая круглая скобка умножить на левая круглая скобка A\to C правая круглая скобка ;$

$A\to левая круглая скобка B плюс C правая круглая скобка = левая круглая скобка A\to B правая круглая скобка плюс левая круглая скобка A\to C правая круглая скобка .$

Связь логики и теории множеств:

— пересечение множеств соответствует умножению логических величин, а объединение — логическому сложению;

— пустое множество $\varnothing$ — это множество, не содержащее ни одного элемента, оно играет роль нуля в теории множеств;

— универсальное множество U — это множество, содержащее все возможные элементы заданного типа (например, все целые числа), оно играет роль логической единицы: для любого множества целых чисел X справедливы равенства $X плюс U = U$ и $X умножить на U = X$ (для простоты мы используем знаки сложения и умножения вместо знаков пересечения ∩ и объединения ∪ множеств);

— дополнение $\barX$ множества X — это разность между универсальным множеством U и множеством X (например, для целых чисел $\barX$ — все целые числа, не входящие в X);

— пусть требуется выбрать множество A так, чтобы выполнялось равенство $A плюс X = U;$ в этом случае множество A должно включать дополнение $\barX,$ то есть $A\supseteq \barX$ (или «по-простому» можно записать $A больше или равно \barX правая круглая скобка ,$ то есть $A_\min =\barX.$

— пусть требуется выбрать множество A так, чтобы выполнялось равенство $\barA плюс X=U,$ в этом случае множество $\barA$ должно включать дополнение $\barX,$ то есть $\barA\supseteq \barX;$ отсюда $A\subseteq X,$ то есть $A_\max =X.$

Преобразование логических выражений

Операцию «эквиваленция» также можно выразить через «ИЛИ» и «НЕ»:

A ≡ B = ¬A ∧ ¬B ∨ A ∧ B

или в других обозначениях

A ≡ B = $\barA умножить на \barB плюс A умножить на B.$

Правила преобразования логических выражений (законы алгебры логики):

Закон	Для И	Для ИЛИ
Двойного отрицания	$\overline\overlineA=A$
Исключения третьего	$A \!\! умножить на \!\! \overlineA=0$	$A плюс \overlineA=1$
Исключения констант	$A умножить на 1=A;A умножить на 0=0$	$A плюс 0=A;A плюс 1=1$
Повторения	$A умножить на A=A$	$A плюс A=A$
Поглощения	$A умножить на левая круглая скобка A плюс B правая круглая скобка =A$	$A плюс A умножить на B=A$
Переместительный	$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$
Де Моргана	$\overlineA \!\! умножить на \!\! B=\overlineA плюс \overlineB$	$\overlineA плюс B=\overlineA \!\! умножить на \!\! \overlineB$