Таблицы истинности и логические уравнения: задания с разбором — ЕГЭ по информатике

ЕГЭ Информатика

ЕГЭ по информатике, тема «Таблицы истинности и логические уравнения»: Система логических уравнений. Ответ проверяется на странице, разбор открывается сразу.

Пример 1

Для логической функции, заданной выражением x ∨ y (других переменных у функции нет), составляют полную таблицу истинности: в неё выписывают все возможные наборы значений переменных, по одному набору в строке. Сколько строк с наборами будет в таблице? Строку заголовка с именами переменных не считайте.

Ответ и разбор

Ответ: 4

Строк в полной таблице истинности ровно столько, сколько существует различных наборов значений переменных: каждый набор занимает одну строку.
Разных переменных в выражении x ∨ y — 2: x и y.
Каждая из них принимает два значения, 0 или 1, поэтому наборов 2 · 2 = 2² = 4.
Какие именно операции стоят в выражении, на число строк не влияет: от них зависит только столбец со значениями функции, а наборы слева от него всегда одни и те же.

Частая ошибка — решить, что строк столько же, сколько переменных, и ответить 2. Переменных две, а наборов четыре — на двух переменных их легко выписать целиком: 00, 01, 10 и 11.

Вторая ошибка — посчитать заодно и строку заголовка с именами переменных: тогда вышло бы 5. Заголовок — подпись столбцов, а не набор значений.

Нашли ошибку? Напишите нам, код задания: ege-informatics-stroki-tablicy-istinnosti-6npf7y

Ещё задания — ниже. Открыть тренажёр

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

Все карточки предмета — в разделе «Формулы»

Ещё задания

Пример 2

Дана система из трёх логических уравнений с переменными x₁, x₂, …, x₆ и y₁, y₂, …, y₆:

(x₁ → x₂) ∧ (x₂ → x₃) ∧ (x₃ → x₄) ∧ (x₄ → x₅) ∧ (x₅ → x₆) = 1
(y₁ → y₂) ∧ (y₂ → y₃) ∧ (y₃ → y₄) ∧ (y₄ → y₅) ∧ (y₅ → y₆) = 1
(x₁ → y₁) ∧ (x₂ → y₂) ∧ (x₃ → y₃) ∧ (x₄ → y₄) ∧ (x₅ → y₅) ∧ (x₆ → y₆) = 1

Сколько различных наборов значений всех этих переменных удовлетворяют одновременно всем трём уравнениям? В ответе укажите только количество таких наборов.

Ответ и разбор

Ответ: 28

1) Первое уравнение (цепочка по x): если какая-то переменная равна 1, то и все следующие равны 1 — решения вида 0…01…1. Таких наборов 7 (число единиц kx от 0 до 6).

2) Второе уравнение (цепочка по y): если какая-то переменная равна 1, то и все следующие равны 1 — решения вида 0…01…1. Таких наборов 7 (число единиц ky от 0 до 6).

Цепочки по x и по y независимы: без третьего уравнения наборов было бы 7 · 7 = 49.

3) Третье уравнение: где xᵢ = 1, там и yᵢ = 1. У обеих цепочек единицы стоят в конце, поэтому условие выполняется, когда единиц в y не меньше, чем в x (ky ≥ kx). Таких пар: 7 + 6 + 5 + 4 + 3 + 2 + 1 = 28.

Ответ: 28.

Нашли ошибку? Напишите нам, код задания: ege-informatics-sistema-logicheskih-uravneniy-pqd3m5

Пример 3

Сколько различных пар значений логических переменных (x, y) являются решениями уравнения (x ∨ y) ∧ ¬(x ∧ y) = 1?

Ответ и разбор

Ответ: 2

Уравнение требует, чтобы хотя бы одна переменная была истинна, но не обе сразу — это исключающее ИЛИ. Перебираем четыре пары: (0,0) даёт 0, (0,1) и (1,0) дают 1, (1,1) даёт 1 ∧ ¬1 = 0. Решений два.

Нашли ошибку? Напишите нам, код задания: bank2-ege-informatics-logic-27

Пример 4

Сколько существует различных наборов значений логических переменных a, b, c, d, при которых выражение (a ∨ b) → (c ∧ d) истинно?

Ответ и разбор

Ответ: 7

Удобнее посчитать ложные наборы: импликация ложна, когда a ∨ b = 1 (3 варианта пары a, b) и одновременно c ∧ d = 0 (3 варианта пары c, d), то есть на 3 × 3 = 9 наборах. Всего наборов 2⁴ = 16, значит, истинных 16 − 9 = 7.

Нашли ошибку? Напишите нам, код задания: bank2-ege-informatics-logic-33

Пример 5

Сколько существует различных наборов значений логических переменных x₁, x₂, x₃, x₄, x₅, при которых выражение x₁ → (x₂ ∧ x₃ ∧ x₄ ∧ x₅) ложно?

Ответ и разбор

Ответ: 15

Импликация ложна только при истинной посылке и ложном заключении: x₁ = 1, а конъюнкция x₂ ∧ x₃ ∧ x₄ ∧ x₅ = 0. Конъюнкция четырёх переменных ложна на всех наборах, кроме единственного 1111, то есть на 2⁴ − 1 = 15 наборах. Итого 1 × 15 = 15 наборов.

Нашли ошибку? Напишите нам, код задания: bank2-ege-informatics-logic-32

Пример 6

Обозначим через ДЕЛ(x, n) высказывание «x делится на n без остатка». Сколько существует натуральных чисел x, не превышающих 30, для которых истинно выражение ДЕЛ(x, 3) ∧ ¬ДЕЛ(x, 6)?

Ответ и разбор

Ответ: 5

Нужны числа, кратные 3, но не кратные 6 — то есть нечётные кратные тройки. Кратных 3 от 1 до 30 всего 10, из них кратных 6 ровно 5 (6, 12, 18, 24, 30). Остаются 10 − 5 = 5 чисел: 3, 9, 15, 21, 27.

Нашли ошибку? Напишите нам, код задания: bank2-ege-informatics-logic-30

Пример 7

Сколько различных наборов значений логических переменных (x, y, z) удовлетворяют уравнению (x → y) ∧ (y → z) = 1?

Ответ и разбор

Ответ: 4

Обе импликации истинны, когда нет ситуации «1 → 0», то есть запрещены наборы с x = 1, y = 0 и с y = 1, z = 0. Перебор восьми наборов оставляет (0,0,0), (0,0,1), (0,1,1) и (1,1,1) — в них значения не убывают в цепочке x, y, z. Итого 4 решения.

Нашли ошибку? Напишите нам, код задания: bank2-ege-informatics-logic-28

Пример 8

Логическая функция F задана выражением (x → y) ∧ z. Дан фрагмент таблицы истинности с тремя различными строками, порядок столбцов переменных неизвестен:

???F
1001
1100
0110

Определите, какая переменная соответствует каждому столбцу, и запишите в ответе три буквы подряд без разделителей в порядке следования столбцов (например, xyz).

Ответ и разбор

Ответ: zxy

Почему так

В первой строке F = 1, значит, z = 1 — единица стоит только в первом столбце, поэтому первый столбец это z (в строках 2 и 3 такое размещение не противоречит F = 0).

Проверяем порядок z, x, y: первая строка (0 → 0) ∧ 1 = 1, вторая (1 → 0) ∧ 1 = 0, третья — z = 0, значит F = 0 — всё сходится.

Вариант zyx отпадает по второй строке: (0 → 1) ∧ 1 = 1 ≠ 0, поэтому ответ zxy единственный.

Нашли ошибку? Напишите нам, код задания: bank2-ege-informatics-logic-26

Пример 9

Сколько существует различных наборов значений логических переменных x₁, x₂, x₃, x₄, x₅, x₆, при которых выражение (x₁ ∨ x₂) ∧ (x₃ ∨ x₄) ∧ (x₅ ∨ x₆) истинно?

Ответ и разбор

Ответ: 27

Выражение истинно, когда истинна каждая из трёх скобок. Дизъюнкция пары переменных истинна на 3 из 4 наборов этой пары (ложна только на 0,0). Пары независимы, поэтому по правилу произведения получаем 3 × 3 × 3 = 27 наборов.

Нашли ошибку? Напишите нам, код задания: bank2-ege-informatics-logic-31

Пример 10

На числовой прямой даны отрезки P = [15; 30] и Q = [25; 42]. Известно, что формула ((x ∈ P) ∨ (x ∈ Q)) → (x ∈ A), где A — некоторый отрезок, истинна при любом значении вещественной переменной x. Какова наименьшая возможная длина отрезка A?

Ответ и разбор

Ответ: 27

Импликация тождественно истинна, только если всякий x из P или из Q попадает и в A, то есть A должен содержать объединение P ∪ Q. Отрезки пересекаются (25 ≤ 30), поэтому объединение — отрезок [15; 42]. Наименьший подходящий A совпадает с ним, его длина 42 − 15 = 27.

Нашли ошибку? Напишите нам, код задания: bank2-ege-informatics-logic-34

Виды заданий темы

Разборы отдельных заданий

Рядом

Продолжить тренировку

Откройте тренажёр, чтобы решать похожие задания и отслеживать прогресс по темам. Для тренажёра нужен вход; на этой странице вход не нужен.

Задание в формате экзамена с разбором

Родителю

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