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

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

На числовой прямой даны отрезки P = [43; 65] и Q = [57; 83]. Укажите наименьшую возможную длину отрезка A, при котором… Тождественно истинная формула — ЕГЭ по информатике, тема «Логические выражения». Ответ проверяется на странице, разбор — сразу.

Пример 1

На числовой прямой даны отрезки P = [43; 65] и Q = [57; 83]. Укажите наименьшую возможную длину отрезка A, при котором формула

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

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

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

Ответ: 8

Обозначим P, Q, A высказывания «x ∈ P», «x ∈ Q», «x ∈ A».
Формула ¬(P ∧ Q) ∨ A — это импликация (P ∧ Q) → A (X → Y = ¬X ∨ Y).
Она тождественно истинна ⇔ каждая точка пересечения P и Q лежит в A. Пересечение: [57; 65].
Наименьший отрезок A — само пересечение, его длина 65 − 57 = 8.

Ответ: 8.

Нашли ошибку? Напишите нам, код задания: ege-informatics-tozhdestvennaya-istinnost-1as6opw

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

Номер сетевого порта в TCP и UDP занимает 16 бит: возможны значения от 0 до 65 535. Порт помогает направить данные нужной службе на одном устройстве. Поэтому один компьютер с одним адресом может обслуживать несколько разных сетевых приложений.

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

Обозначим через ДЕЛ(n, m) утверждение «натуральное число n делится без остатка на натуральное число m». Для какого наименьшего натурального числа A формула

(ДЕЛ(x, A) ∧ ДЕЛ(x, 49)) → ДЕЛ(x, 28)

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

Решение

Ответ: 4

Обозначим D = ДЕЛ(x, A), P = ДЕЛ(x, 49), Q = ДЕЛ(x, 28).
Формула (D ∧ P) → Q читается прямо: «если x делится на A и на 49, то x делится на 28».
x делится и на 49, и на A ⇔ x делится на НОК(49, A). Формула тождественно истинна ⇔ НОК(49, A) делится на 28.
Разложим: 28 = 2² · 7, 49 = 7². Чтобы НОК делился на 28, не хватает 2² (в 49 его нет) — это и должно дать A, остальное даёт 49.
Наименьшее A = 2² = 4.

Ответ: 4.

Нашли ошибку? Напишите нам, код задания: ege-informatics-tozhdestvennaya-istinnost-1og5imq

Формулы и приём

Импликация

Почему «если 2·2 = 5, то Луна из сыра» — истинное высказывание?

A → B = ¬A ∨ B

A
посылка — высказывание до стрелки
B
следствие — высказывание после стрелки

Импликация A → B ложна в единственном случае: A истинно, а B ложно. Из ложной посылки следует что угодно, поэтому «если 2·2 = 5, то Луна из сыра» — истина. Для преобразований заменяй стрелку по формуле: (x > 5) → (x > 3) = (x ≤ 5) ИЛИ (x > 3), а это истинно при любом x.

Импликация не симметрична: A → B и B → A — разные выражения. При ложном A результат — истина при любом B.

Побитовые операции

Что на самом деле делает операция & с двумя числами?

&: единица там, где 1 у обоих · |: единица там, где 1 хотя бы у одного · считай столбиком в двоичной

Поразрядные операции сравнивают числа бит за битом в двоичной записи. Для 12 & 10 запиши 1100 и 1010 столбиком: единица остаётся там, где она у обоих чисел, — выйдет 1000, то есть 8. А 12 | 10 = 1110 = 14, потому что ИЛИ зажигает бит, когда единица есть хотя бы в одном из чисел.

Проверка бита: x & 2ᵏ ≠ 0 означает, что бит номер k (нумерация с нуля, справа) равен единице. Записывай оба числа с одинаковым числом разрядов, дописывая нули слева.

Логические операции

Когда «И» истинно, а когда «ИЛИ»?

A ∧ B; A ∨ B; ¬A

A
первое высказывание (истина или ложь), 0 или 1
B
второе высказывание, 0 или 1

Конъюнкция ∧ («И») истинна только когда истинны оба. Дизъюнкция ∨ («ИЛИ») ложна только когда ложны оба. Отрицание ¬ переворачивает значение.

Импликация A → B ложна ровно в одном случае: A истинно, B ложно. Это самое частое место ошибок в таблицах истинности.

Ещё примеры

Пример 2

Обозначим через ДЕЛ(n, m) утверждение «натуральное число n делится без остатка на натуральное число m». Для какого наибольшего натурального числа A формула

ДЕЛ(x, 30) → (ДЕЛ(x, 9) → ДЕЛ(x, A))

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

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

Ответ: 90

Обозначим D = ДЕЛ(x, A), P = ДЕЛ(x, 30), Q = ДЕЛ(x, 9).
Формула P → (Q → D) равносильна ¬P ∨ ¬Q ∨ D (импликация X → Y — это ¬X ∨ Y), то есть (P ∧ Q) → D.
P ∧ Q — «x делится и на 30, и на 9», то есть на НОК(30, 9) = 90 (30 = 2 · 3 · 5, 9 = 3²).
Формула тождественно истинна, если каждое число, кратное 90, делится на A, — то есть если 90 делится на A. Наибольшее такое A — само 90.

Ответ: 90.

Нашли ошибку? Напишите нам, код задания: ege-informatics-tozhdestvennaya-istinnost-ai72gr

Пример 3

Обозначим через m & n поразрядную конъюнкцию неотрицательных целых чисел m и n. Для какого наименьшего неотрицательного целого числа A формула

(x & 119 ≠ 0) → ((x & 50 = 0) → (x & A ≠ 0))

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

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

Ответ: 69

Решение

Формула P → (Q → R) равносильна (P ∧ Q) → R: ((x & 119 ≠ 0) ∧ (x & 50 = 0)) → (x & A ≠ 0).
119 = 1110111₂, 50 = 0110010₂. Посылка: у x есть единица в разрядах числа 119 и нет единиц в разрядах числа 50. Разряды 119, которых нет в 50: 1000101₂ = 1 + 4 + 64.
Если x — одна такая единица (x = 1, x = 4, x = 64), посылка истинна, значит x & A ≠ 0: каждый из этих разрядов обязан быть в A. И этого хватает: при истинной посылке у x есть единица в одном из них.
Наименьшее A = 69.

Ответ: 69.

Нашли ошибку? Напишите нам, код задания: ege-informatics-tozhdestvennaya-istinnost-ucbp6j

Пример 4

Обозначим через ДЕЛ(n, m) утверждение «натуральное число n делится без остатка на натуральное число m». Для какого наибольшего натурального числа A формула

¬ДЕЛ(x, A) → (ДЕЛ(x, 12) → ¬ДЕЛ(x, 37))

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

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

Ответ: 444

Обозначим D = ДЕЛ(x, A), P = ДЕЛ(x, 12), Q = ДЕЛ(x, 37).
Формула ¬D → (P → ¬Q) равносильна D ∨ ¬P ∨ ¬Q (импликация X → Y — это ¬X ∨ Y), то есть (P ∧ Q) → D.
P ∧ Q — «x делится и на 12, и на 37», то есть на НОК(12, 37) = 444 (12 = 2² · 3, 37 = 37).
Формула тождественно истинна, если каждое число, кратное 444, делится на A, — то есть если 444 делится на A. Наибольшее такое A — само 444.

Ответ: 444.

Нашли ошибку? Напишите нам, код задания: ege-informatics-tozhdestvennaya-istinnost-1vblo4r

Рядом

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

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

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

Родителю

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