Система логических уравнений: как решать — ЕГЭ по информатике

ЕГЭ Информатика сложность в тренажёре: продвинутая

Дана система из трёх логических уравнений с переменными x₁, x₂, …, x₄ и y₁, y₂, …, y₄: (x₂ → x₁) ∧ (x₃ → x₂) ∧ (x₄ → x₃… Система логических уравнений — ЕГЭ по информатике, тема «Таблицы истинности и логические уравнения». Ответ проверяется на странице, разбор — сразу.

Пример 1

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

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

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

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

Ответ: 24

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

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

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

3) Третье уравнение x₄ → y₄ = 1 запрещает одновременно x₄ = 1 и y₄ = 0. x₄ = 1 только в наборе из одних единиц цепочки x — это 1 набор; y₄ = 0 — только в наборе из одних нулей цепочки y, это 1 набор. Запрещено 1 · 1 = 1 пара.

Всего: 25 − 1 = 24.

Ответ: 24.

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

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

Две программы могут застрять, если каждая удерживает ресурс, нужный другой, и ждёт его освобождения. Такое взаимное ожидание называется тупиком, или deadlock. Быстрый процессор сам по себе его не устраняет: нужно изменить порядок захвата или освободить ресурс.

Разобранный пример

Дана система из трёх логических уравнений с переменными 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₅) ∧ (y₇ → y₆) ∧ (y₈ → y₇) = 1
x₆ → y₈ = 1

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

Решение

Ответ: 15

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

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

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

3) Третье уравнение x₆ → y₈ = 1 запрещает одновременно x₆ = 1 и y₈ = 0. x₆ = 1 во всех наборах, кроме набора из одних нулей цепочки x — это 6 наборов; y₈ = 0 — во всех наборах, кроме набора из одних единиц цепочки y, это 8 наборов. Запрещено 6 · 8 = 48 пар.

Всего: 63 − 48 = 15.

Ответ: 15.

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

Ещё примеры

Пример 2

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

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

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

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

Ответ: 15

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

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

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

3) Третье уравнение: где xᵢ = 1, там и yᵢ = 1. Единицы x стоят в конце, а единицы y — в начале. При kx = 0 подходит любой набор y (8); при kx ≥ 1 единица x₇ требует y₇ = 1, а это только набор y из одних единиц — ещё 7 пар. Всего 8 + 7 = 15.

Ответ: 15.

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

Пример 3

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

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

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

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

Ответ: 41

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

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

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

3) Третье уравнение x₁ ∨ y₁ = 1 запрещает одновременно x₁ = 0 и y₁ = 0. x₁ = 0 во всех наборах, кроме набора из одних единиц цепочки x — это 7 наборов; y₁ = 0 — только в наборе из одних нулей цепочки y, это 1 набор. Запрещено 7 · 1 = 7 пар.

Всего: 48 − 7 = 41.

Ответ: 41.

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

Пример 4

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

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

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

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

Ответ: 31

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

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

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

3) Третье уравнение x₅ → y₅ = 1 запрещает одновременно x₅ = 1 и y₅ = 0. x₅ = 1 только в наборе из одних единиц цепочки x — это 1 набор; y₅ = 0 — во всех наборах, кроме набора из одних единиц цепочки y, это 5 наборов. Запрещено 1 · 5 = 5 пар.

Всего: 36 − 5 = 31.

Ответ: 31.

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

Рядом

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

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

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

Родителю

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