desktop/inf.jpg mobile/inf.jpg

Задание 15. Графы. Количество путей. ЕГЭ 2021 по информатике

За это задание ты можешь получить 1 балл. На решение дается около 3 минут. Уровень сложности: повышенный.
Средний процент выполнения: 68.7%
Ответом к заданию 15 по информатике может быть цифра (число) или слово.

Задачи для практики

Задача 1

Даны множества P = {5, 8, 19, 24, 42, 124}, Q = {3, 8, 12, 24, 64, 127, 211} и A. Элементами множества являются натуральные числа. Известно, что выражение

((x ∈ A) → ¬((x ∈ P) ∨ (x ∈ A))) ∨ ¬((x ∈ Q) → ¬(x ∈ P)).

истинно (т. е. принимает значение 1) при любом значении переменной x. Определите наибольшее возможное значение суммы элементов множества A.

Решение

Обозначим $P↖{∼}$: (x ∈ P); $Q↖{∼}$: (x ∈ Q); $A↖{∼}$: (x ∈ A).

Перепишем исходное выражение: ($A↖{∼}$ → ¬($P↖{∼}$ ∨ $A↖{∼}$)) ∨ ¬($Q↖{∼}$ → ¬ $P↖{∼}$).

На основании законов алгебры логики преобразуем это выражение.

($A↖{∼}$ → ¬($P↖{∼}$ ∨ $A↖{∼}$)) ∨ ¬($Q↖{∼}$ → ¬ $P↖{∼}$) ≡

≡ (¬ $A↖{∼}$ ∨ ¬($P↖{∼}$ ∨ $A↖{∼}$)) ∨ ¬(¬$Q↖{∼}$ ∨ ¬ $P↖{∼}$) ≡

≡ ¬ $A↖{∼}$ ∨ (¬ $P↖{∼}$ ∧ ¬ $A↖{∼}$) ∨ ($Q↖{∼}$ ∧ $P↖{∼}$) ≡

≡ ¬ $A↖{∼}$ ∨ ($Q↖{∼}$ ∧ $P↖{∼}$)

Возвращаясь к исходным выражениям, получим: ((x ∉ A) ∨ ((x ∈ Q)) ∧ (x ∈ P)).

Логическое выражение (x ∈ Q)) ∧ (x ∈ P) истинно на промежутке на множестве Q ∩ P = {8, 24}. Согласно условию, нужно выбрать такое множество A, что для любого целого x будет истинным выражение (x ∉ A) ∨ x ∈ {8, 24}. При этом множество A должно содержать наибольшее число элементов.

Таким множеством A является {8, 24}.Сумма элементов этого множества равна 32.

Ответ: 32
Показать решение
Полный курс

Задача 2

На числовой прямой даны два отрезка: P = [18, 63] и Q = [2, 29]. Укажите наименьшую возможную длину такого отрезка A, что логическое выражение

$ (¬(x ∈ A) → ((x ∈ P) ∧ (x ∈ A))) ∨ ((x ∈ Q) → (x ∈ P))$

тождественно истинно, то есть принимает значение 1 при любом значении переменной x.

Решение
Ответ: 16
Показать решение
Полный курс

Задача 3

На числовой прямой даны два отрезка: P = [2, 35] и Q = [12, 54]. Укажите наибольшую возможную длину такого отрезка A, что логическое выражение

$ ((x ∈ P) → ((x ∈ Q) ∧ (x ∈ P))) → ¬(x ∈ A)$

тождественно истинно, то есть принимает значение 1 при любом значении переменной x.

Решение
Ответ: 10
Показать решение
Полный курс

Задача 4

Для какого наименьшего целого числа A выражение

$((x^4 < A) → (x ≤ 2)) ∧ ((y < 7) → (y^2 < A))$

тождественно истинно (то есть принимает значение 1 при любых целых неотрицательных значениях переменных x и y)?

Решение
Ответ: 37
Показать решение
Полный курс

Задача 5

Для какого наибольшего целого числа A выражение

$((x ≤ 6) → (x^2 ≤ A)) ∧ ((y^3 ≤ A) → (y ≤ 3))$

тождественно истинно (то есть принимает значение 1 при любых целых неотрицательных значениях переменных x и y)?

Решение
Ответ: 63
Показать решение
Полный курс

Задача 6

Для какого наименьшего целого числа A выражение

$((x · x < A) ∨ (x ≥ 8)) ∧ ((y · y < A) → (y < 8))$

тождественно истинно (то есть принимает значение 1 при любых целых неотрицательных значениях переменных x и y)?

Решение
Ответ: 50
Показать решение
Полный курс

Задача 7

Для какого наибольшего целого неотрицательно числа A выражение

$(4 · x + 8 · y ≠ 124) ∨ (x > 3 · A − 1) ∨ (2 · y > A)$

тождественно истинно (то есть принимает значение 1 при любых целых неотрицательных значениях переменных x и y)?

Решение
Ответ: 7
Показать решение
Полный курс

Задача 8

Для какого наибольшего целого неотрицательно числа A выражение

(5 · x + 2 · y ≠ 32) ∨ (x > A − 8) ∨ (y > A + 1)

тождественно истинно (то есть принимает значение 1 при любых целых неотрицательных значениях переменных x и y)?

Решение
Ответ: 9
Показать решение
Полный курс

Задача 9

Для какого наименьшего целого неотрицательно числа A выражение

$(x + 2 · y ≤ A) ∨ (x > 25) ∨ (y > 12)$

тождественно истинно (то есть принимает значение 1 при любых целых неотрицательных значениях переменных x и y)?

Решение
Ответ: 49
Показать решение
Полный курс

Задача 10

Для какого наименьшего целого неотрицательно числа A выражение

$(3 · x + y < A) ∨ (x > 15) ∨ (y > 20)$

тождественно истинно (то есть принимает значение 1 при любых целых неотрицательных значениях переменных x и y)?

Решение
Ответ: 66
Показать решение
Полный курс

Задача 11

На числовой прямой даны два отрезка: P = [1, 70] и Q = [25, 96]. Укажите наибольшую возможную длину такого отрезка A, что логическое выражение

((x ∈ P) → ((x ∈ Q) ∧ (x ∈ P))) → ¬(x ∈ A)

тождественно истинно, то есть принимает значение 1 при любом значении переменной x.

Решение
Ответ: 24
Показать решение
Полный курс
Показать еще

Готовим к ЕГЭ на 85+ баллов и побеждаем лень

Каждый месяц 12 онлайн-занятий в дружелюбной атмосфере + 16 домашних работ с жесткими сроками.
Не готовишься — вылетаешь.

Подробнее о курсе