Разбор 18 задания ЕГЭ 2018 по информатике и ИКТ из демонстрационного варианта
Разбор 18 задания ЕГЭ 2018 по информатике и ИКТ из демоверсии. Это задание повышенного уровня сложности. Примерное время выполнения задания 3 минуты.
Проверяемые элементы содержания:
— Знание основных понятий и законов математической логики.
Элементы содержания, проверяемые на ЕГЭ:
— высказывания,
— логические операции,
— кванторы,
— истинность высказывания.
Задание 18
Для какого наибольшего целого числа А формула
тождественно истинна, то есть принимает значение 1 при любых целых неотрицательных x и y?
Разбор 18 задания ЕГЭ 2018 по информатике
Разделим наше выражение на 2 части:
B ⋀ C
Главное действие в исходном выражении — это коньюнкция. Конъюнкция истинна, когда все операнды истинны. Т.е. в задаче обе части B и C должны быть истинными.
Рассмотрим часть B:
если в выражении (x ≤ 9), х > 9, то часть В будет истинна независимо от А. Значит значение числа А влияет на решение только при выполнении условия:
x ≤ 9
теперь для того чтобы в части В, выражение было истинным, надо чтобы (x⋅x ≤ A) было истинным:
(импликация 1 → 1 = 1)
таким образом получаем:
x ≤ 9
x 2 ≤ A
Но нам нам необходимо найти наибольшее возможное А, поэтому надо ограничить его значения сверху, а данная часть выражения ограничивает только снизу:
возьмем наименьшее натуральное: x = 1, тогда A ≥ 1
Рассмотрим часть С:
если выражение (y ≤ 9) действительно истинно (т.е. y ≤ 9), то часть С будет истинна независимо от А. Значит значение числа А влияет на решение только при выполнении условия:
y > 9
теперь для того чтобы в части C, выражение было истинным, надо чтобы (y⋅y ≤ A) было ложным:
(импликация 0 → 0 = 1)
таким образом получаем:
y > 9
y 2 > A
данная часть выражения ограничивает значения А сверху:
возьмем наименьшее возможное по условию натуральное: y = 10, тогда A
ЕГЭ по информатике 2022 — Задание 15 (Простым языком)
Сегодняшний урок посвящён 15 заданию из ЕГЭ по информатике 2022.
Темой этого урока связана с преобразованием логических выражений.
Теорию для преобразования логических выражений Вы можете посмотреть в этой статье. Как можно работать с логическими выражениями на питоне, можно прочитать в этой статье.
Перейдём к практике решения задач 15 задания из ЕГЭ по информатике 2022.
Задача (Неравенство, одна переменная)
Какое количество натуральных чисел удовлетворяет логическому условию:
Первый способ (с помощью питона).
Здесь перебираем с помощью цикла for натуральные числа от 1 до 1000.
Если логическое выражение выдаёт истину, то мы подсчитываем такой вариант.
Программа напечатает число 5.
Второй способ (с помощью рассуждений).
Натуральные числа — это целые, положительные числа. Например: 1, 2, 3, 4, и т. д.
Преобразуем первое выражение ¬(X 2 ≥ 9) = (X 2 Важно: Если было строгое неравенство, то оно станет нестрогим, и наоборот, если было неравенство нестрогим, то оно станет строгим.
Получается, что выражение (X 2 Формула де Моргана:
Преобразуем выражение по формуле де Моргана и внесём отрицание в скобки:
Получилось выражение (X ≥ 7) ∧ (X (x ≥ A) ∨ (y ≥ A) ∨ (x * y ≤ 205)
тождественно истинно, т.е. принимает значение 1 при любых целых положительных x и y ?
Первый способ (с помощью питона).
В первом цикле перебираем значения для A. Здесь мы пытаемся подобрать ответ в диапазоне от 0 до 300. Этот диапазон меньше, чем в прошлой задаче. Потому что здесь три вложенных цикла, и если перебирать числа от 0 до 1000, то программа может работать очень долго. При необходимости можно указать другой диапазон.
Для каждого A устанавливаем счётчик k в ноль.
Затем перебираем все числа в диапазоне от 1 до 300 (включительно) для переменных x и y, тем самым имитируем фразу «для любых x и y».
Если логическое выражение сработает при каждом значении x и y, то считается, что значение A нам подходит, и в счётчике по окончанию вложенных циклов будет значение 90000 (300 * 300 = 90000).
Наибольшее число, которое напечатает программа равно 15.
Второй способ (с помощью рассуждений).
Здесь есть три выражения в скобках, которые соединены логическим сложением. При логическом сложении достаточно хотя бы одного выражения, где будет истина, чтобы всё общее выражение было истинно.
Если мы сделаем A слишком большим, к примеру A = 250, то найдутся такие x = 16, y = 16, при которых все три условия в скобках не будут выполняться, и, значит, всё общее выражение будет ложным.
Следовательно, нам нужно выбрать таким A, чтобы не было возможности подобрать x, y, при которых все три выражения ложны.
Сделаем так: пока x и y меньше A, должно «работать» третье выражение в скобках. Как только x или y сравняются с A — начинают «работать» первое или второе выражение.
До какого же максимального значения могут дойти x и y, чтобы перемножение этих двух чисел было меньше или равно 205 (x * y ¬ДЕЛ(x, А) → (ДЕЛ(x, 6) → ¬ДЕЛ(x, 9))
тождественно истинна (то есть принимает значение 1 при любом натуральном значении переменной x)?
Первый способ (с помощью питона).
Здесь мы формируем функцию ДЕЛ (функцию D). Если n делится на m, то функция возвращает Истину, в противном случае функция возвращает Ложь.
Далее решаем примерно так же, как и в прошлых задачах: для каждого числа A перебираем все значения x. Следование расписываем по формуле A ⟶ B = ¬A ∨ B.
Наибольшее число здесь получается равно 18.
Второй способ (с помощью рассуждений).
Рассмотрим случай, когда в левой части логического выражения будет 1, а в правой 0. В остальных случаях беспокоится не за что, потому что вся формула будет выдавать истину.
Посмотрим, когда в правой части получается ноль. Функция ДЕЛ(x, 6) должна выдавать истину. Т.е. x должен делится на 6. А функция ¬ДЕЛ(x, 9) должна выдавать ноль. Т.е. без отрицания ДЕЛ(x, 9) должна выдавать истину. Значит, x так же делится на 9.
x делится на 6 => x = 2*3*n, n ∈ N
x делится на 9 => x = 3*3*n, n ∈ N
Чтобы выполнялся случай, когда в правой части получается ноль, икс должен быть равен x = 3*3*2*n (n ∈ N). Т.е. получается, что икс должен быть кратен 18.
Т.е. получается, что когда x делится на 18, в правой части логического выражения будет получатся ноль. Чтобы спасти ситуацию, мы должны в левой части логического выражения не получать 1. Следовательно, ¬ДЕЛ(x, А) должно выдавать ноль. Значит, ДЕЛ(x, А) должно выдавать 1. Таким образом, приходим к выводу, что A должно равняться 18.
Если получится опасная ситуация, когда x кратен 18, то она будет нейтрализована, ведь в левой части будет получатся ноль.
Ещё один важный тип задач 15 задания ЕГЭ по информатике 2022
Задача (Поразрядная конъюнкция)
Обозначим через m&n поразрядную конъюнкцию неотрицательных целых чисел m и n. Так, например, 14&5 = 11102 & 01012 = 4
Для какого наименьшего неотрицательного целого числа A формула
x&51 ≠ 0 → (x&A = 0 → x&25 ≠ 0)
тождественно истинна (то есть принимает значение 1 при любом неотрицательном целом значении переменной x)?
Первый способ (с помощью питона).
Здесь следование преобразовываем по формуле: A ⟶ B = ¬A ∨ B. Так же и A, и x неотрицательные числа. Поэтому мы перебираем их диапазон, начиная с нуля. Из-за этого в цикле, который перебирает переменную x, мы устанавливаем верхнюю границы равной 1000, а не 1001. Тогда тоже будет 1000 повторений в этом цикле.
Наименьшее число равно 34.
Второй способ (с помощью рассуждений).
Переведём числа 51 и 25 в двоичную систему.
Формула будет тождественно ложна, когда
Этого допустить нельзя!
При каком x получается в левой выражении формулы истина ? Если у икса в двоичном представлении в тех разрядах, где у числа 51 стоят 1, будет хотя бы в одном месте 1.
Рассмотрим правое выражение формулы. Ноль получается в единственном случае:
Рассмотрим выражение x&25 ≠ 0. Чтобы в этом логическом выражении получился ноль, нужно x&25 = 0. Посмотрим на двоичное представление числа 25. В тех разрядах, где стоят единицы, у икс должны быть нули (для x&25 = 0).
Сформулируем окончательное условие для x, при котором возникает опасность превращение общей формулы в ложь.
Нам нужно «поломать эту песенку» с помощью x&A = 0. Т.е. нельзя допускать, чтобы это выражение было истинно.
Получается, что A = 1000102. Это наименьшее из возможных число, при котором мы точно себя обезопасим от того, что вся формула будет ложна.
A = 1000102 в десятичной системе будет 34.
Ещё один тип задач 15 задания ЕГЭ по информатике
На числовой прямой даны отрезки P=[5, 13] и Q=[8, 19]. Укажите наименьшую возможную длину такого отрезка A, что формула (¬(x ∈ P) → (x ∈ Q)) → (x ∈ A ) верна при любых значениях x.
Первый способ (с помощью питона).
Получается ответ 14. Более подробно, как решать задачи на ОТРЕЗКИ из 15 задания ЕГЭ по информатике на Python, можете посмотреть в этой статье.
Второй способ (с помощью рассуждений).
Если будут такие варианты:
То нам беспокоится не о чём. Потому что формула всегда будет истинна! (см. таблицу истинности для следования →)
Нас же будет интересовать этот случай.
При таком раскладе вся формула будет ложна! Нам нужно этого не допустить при любом значении x!
Единица получается в первом подвыражении в трёх случаях:
1) Случай
Выражение ¬(x ∈ P) получается ложно, когда (x ∈ P) будет истинно! Получается при x ∈ [5, 13] выражение ¬(x ∈ P) — ложно!
Выражение (x ∈ Q) ложно, когда x ∉ [8, 19]
Какой же минимальной длины должен быть отрезок A, чтобы этот случай не проходил при любом x ? При этом случае отрезок A должен быть равен [5, 8). Тогда левое выражение пусть и может стать единицей при x ∈ [5, 8), но выражение (x ∈ A) будет также равно 1 при x ∈ [5, 8)! И схема 1 → 0 не пройдёт. Будет 1 → 1.
Для 1 случая A=[5, 8).
2) Случай
При каких x выражение ¬(x ∈ P) обращается в ноль, мы уже рассматривали: x ∈ [5, 13].
Второе выражение «выдаёт» 1 при x ∈ [8, 19].
Получается, что при при x ∈ [8; 13] первое выражение в скобках в главной формуле будет тождественно истинно!
С помощью отрезка A нужно это нейтрализовать путём превращения второго выражения в скобках в главной формуле в 1, пока x ∈ [8; 13]. Значит, для этого случая A = [8; 13]
3) Случай
В выражении ¬(x ∈ P) единица получается, когда в выражении (x ∈ P) получается ноль. Тогда x ∉ [5, 13]!
Чтобы во втором выражении (x ∈ Q) была единица, нужно, чтобы x ∈ [8, 19].
Получается, что 3 случай выполняется, если x ∈ (13, 19].
С помощью отрезка A нужно этому противодействовать! Нужно чтобы выражение (x ∈ A) было всегда 1 при x ∈ (13, 19]. Тогда A должно быть (13, 19].
Следовательно, для третьего случая A=(13, 19].
Нам нельзя допустить ни одного случая! Поэтому, объединив все случаи, получаем, что A=[5, 19].
Длина отрезка равна 14.
Ещё одна задача про числовую прямую из банка тренировочных заданий ЕГЭ по информатике 2021.
Задача (Числовая прямая, закрепление)
На числовой прямой даны отрезки P=[5, 13] и Q=[8, 19]. Укажите наименьшую возможную длину такого отрезка A, что формула ((x ∈ P) ∧ ¬(x ∈ A)) → ((x ∈ Q) ∧ ¬(x ∈ A)) верна при любых значениях x.
Первый способ (с помощью питона).
Второй способ (с помощью рассуждений).
Формула может быть ложна, когда
Во всех остальных случаях, формула всегда верна.
Чтобы выражение ((x ∈ P) ∧ ¬(x ∈ A)) было тождественно 1, выражение (x ∈ P) обязательно должно быть тождественно 1. А, значит, x ∈ [5, 13] — это опасная зона , при которой появляется возможность обратить всю формулу в ноль!
Мы можем сразу пресечь эту опасность с помощью отрезка A. Выбрать такой отрезок, чтобы он всегда «выдавал» ложь при x ∈ [5, 13]. Для этого достаточно выбрать A=[5, 13]! Но вдруг его можно сделать ещё более маленьким за счёт правой части формулы ?
Предположим, что отрезок A сделали ещё меньшим. Тогда при каком-то x (x ∈ [5, 13]) выражение ¬(x ∈ A) будет «выдавать» 1! Причём такое же выражение стоит и в правой части формулы! Там тоже будет 1 для выражения ¬(x ∈ A).
Нас же в этом случае должно выручить выражение (x ∈ Q). Если оно «выдаст» 1 в этот «сложный» момент, то мы спасены! Ведь тогда получается, что правая часть всей формулы будет «выдавать» не 0, а 1. Посмотрим при каких x из отрезка [5, 13] приходит это спасение.
Видим, что в интервале x ∈ [8, 13] нас спасает выражение (x ∈ Q).
Значит, отрезок A можно сократить до A=[5, 8).
Длина отрезка будет равна 3!
Задачи для закрепления
Задача (Неравенство, две переменные, закрепление)
Для какого наибольшего целого неотрицательного числа A выражение
тождественно ложно, т.е. принимает значение 0 при любых целых положительных x и y ?
Первый способ (с помощью питона).
Т.к. выражение должно быть ЛОЖНО, то обернём логическое выражение в функцию not(). Видим, что программа не сильно отличается от прошлой задачи. Данный шаблон подходит для большинства задач подобного типа.
Наибольшее число получается равно 25.
Второй способ (с помощью рассуждений).
В этой задаче нужно, чтобы общее выражение было ложно!
Если мы поставим отрицание над всем выражением, то можно искать такое максимальное A, при котором всё выражение тождественно истинно, а не ложно!
Здесь применили формулу де Моргана! Т.е. каждое подвыражение получило отрицание + соединительная логическая операция (логическое умножение) сменилась на противоположную операцию (логическое сложение).
Внесём отрицание в скобки. Получается:
(x ≥ A) ∨ (y ≥ A) ∨ (x * y ≤ 603)
Получили ситуацию, как в прошлой задаче! Напомню, что теперь нужно, чтобы общее выражение было истинно.
Найдём максимальное число, до которого могут «подняться» x и y, чтобы ещё работало третье выражение!
Обратите внимание, что x и y — симметричны. Значит, что верхняя планка для x и y будет одно и тоже число.
Поэтому вспоминаем таблицу квадратов.
25 * 25 = 625
24 * 24 = 576
Получается, что максимальное число до которого могут «дойти» x и y, чтобы «работало» третье выражение, равно 24.
Тогда, начиная с 25 для x и y, должны работать первое и второе выражение.
Получается, что максимальное число для A равно 25.
Ещё одна задачка подобного типа из тренировочных упражнений 15 задания ЕГЭ по информатике.
Задача (Неравенство, две переменные, закрепление)
Для какого наименьшего целого числа A формула
тождественно истинна, т.е. принимает значение 1 при любых целых неотрицательных x и y ?
Первый способ (с помощью питона).
Наименьшее число равно 61. Здесь не сказали, что A принимает неотрицательные значения, поэтому мы включили в диапазон для A числа, которые меньше нуля. Из-за этого увеличилось время выполнения программы, но ответ получим за приемлемое время.
Второй способ (с помощью рассуждений).
Чтобы вся формула была тождественно истинна, нужно, чтобы хотя бы одно выражение «выдавало» истину, т.к. выражения в формуле соединяются с помощью логического сложения!
Взглянем на третье выражение. Пока x ≥ 16, всё идёт как надо. Третье выражение будет истинно, и, значит, вся формула будет истинна.
Но если x ≤ 15, то нужно, чтобы нас «спасало» первое или второе выражение.
Рассмотрим второе выражение. Пока y > x (x ≤ 15) => y > 15, у нас всё нормально, второе выражение будет истинно, и вся формула будет истинна.
Теперь обратим внимание на первое выражение. Оно должно нас «спасать», когда третье и второе выражение «не спасло»! Это возможно, если x ≤ 15 (иначе «спасло» бы третье выражение), а так же y ≤ 15 (иначе «спасало» бы второе выражение).
Но, чтобы первое выражение было всегда истинно при x ≤ 15 и y ≤ 15, мы должны подобрать число A при максимальных x и y (x=15, y=15)! Ведь для более маленьких значений выражение (3 * x + y 3 * 15 + 15
Нужно найти наименьшее число для A, при котором A > 60. Тогда там, где не «спасли» третье и второе выражение, точно «спасёт» первое выражение. Получается A = 61.
Задача (ЕГЭ по информатике, Москва, 2020)
Для какого наибольшего целого неотрицательного числа A выражение
(x > A) ∨ (y > x) ∨ (2 * y + x
тождественно истинно, то есть принимает значение 1 при любых целых неотрицательных x и y ?
Первый способ (с помощью питона).
Максимальное число получается равно 36.
Второй способ (с помощью рассуждений).
Пока y > x, второе подвыражение всегда истинно, значит, и всё выражение истинно.
Теперь будем рассматривать случай y ≤ x.
Рассмотрим третье подвыражение. Найдём максимальные значения для x и для y, которые они одновременно могут принимать, и при которых ещё выполняется третье условие.
Т.к. мы рассматриваем случай y ≤ x, то максимальное число для y будет xmax т.е. ymax = xmax.
Если x «перевалит» за 36, и при этом y ≤ x (иначе «спасает» второе подвыражение), то должно «спасать» первое выражение.
Получается, что наибольшее значение A будет равно 36.
Следующий тип задач часто можно встретить в тренировочных вариантах ЕГЭ по информатике 2022.
Задача (С функцией ДЕЛ, закрепление)
Обозначим через ДЕЛ(n, m) утверждение «натуральное число n делится без остатка на натуральное число m». Для какого наибольшего натурального числа A формула
ДЕЛ(120, A) ∧ ((ДЕЛ(x, 70) ∧ ДЕЛ(x, 30)) → ДЕЛ(x, A))
тождественно истинна (то есть принимает значение 1 при любом натуральном значении переменной х)?
Первый способ (с помощью питона).
Наибольшее число получается равно 30.
Второй способ (с помощью рассуждений).
Рассмотрим левую часть логического выражения. Мы видим, что число 120 должно делится на A. Значит, для A уже есть некоторое ограничение (A
Т.е. x должен делится на 70 и одновременно x должен делится на 30.
x = 70*n = 2*5*7*n (n ∈ N)
x = 30*n = 2*5*3*n (n ∈ N)
Чтобы одновременно выполнялись два условия, икс должен быть равен x = 2*5*7*3*n (n ∈ N).
Для того, чтобы правое выражение не превращалось в ноль, x как раз должен делится на число 2*5*7*3. Тогда будет 1->1. Т.е. число A должно равняться 2*5*7*3. Но мы сказали, что A 1. Но это значение не подходит для левой части, ведь тогда A не является делителем числа 120.
Приходится брать число 2*5*3 (без семёрки). Здесь ситуация аналогично предыдущему случаю, только теперь это число является делителем числа 120.
В ответе напишем 30.
Задача (Поразрядная конъюнкция, закрепление)
Введём выражение M & K, обозначающее поразрядную конъюнкцию M и K (логическое «И» между соответствующими битами двоичной записи). Определите наименьшее натуральное число A, такое что выражение
(X & 49 ≠ 0) → ((X & 33 = 0) → (X & A ≠ 0))
тождественно истинно (то есть принимает значение 1 при любом натуральном значении переменной X)?
Первый способ (с помощью питона).
Наименьшее число равно 16.
Второй способ (с помощью рассуждений).
Переведём числа 49 и 33 в двоичную систему.
Рассмотрим случай, когда функция стремится превратится в ноль.
Чтобы левое выражение выдавало истину, икс должен иметь 1 (единицу) в первом разряде или во второй разряде, или в последнем разряде (в 6-ти битном числе).
Рассмотрим правое выражение. Посмотрим, когда выражение (X & 33 = 0) выдаёт истину. Первый бит и последний бит должен быть равен нулю. Т.е получается, что в 6-ти битном числе нас интересует второй бит. Если он будет равен 1 и при этом первый бит и последний будут равны 0, то возникает опасная ситуация, которую нужно спасть.
При выше описанных условиях выражение (X & A ≠ 0) должно выдавать истину. Тогда наименьшее A равно 100002 = 162.
Задача (числовая прямая, закрепление 2)
На числовой прямой даны два отрезка: P = [20, 30] и Q = [35, 60]. Найдите наименьшую возможную длину отрезка A, при котором формула
тождественно ложна, то есть принимает значение 0 при любых x.
Первый способ (с помощью питона).
Второй способ (с помощью рассуждений).
Рассмотрим наоборот, когда логическое выражение выдаёт истину.
В правой части получается 1, когда x ∈ P или x ∈ Q. Именно в эти моменты выражение ¬(x ∈ A) должно спасать ситуацию и выдавать 0. Тогда без отрицания (x ∈ A) должно выдавать 1. Чтобы покрыть два отрезка, берём A=[20; 60].
Минимальная длина получается 60-20=40.
На этом всё! Увидимся в новых уроках по подготовке к ЕГЭ по информатике!
Решу ЕГЭ и Незнайка объединились,
чтобы запустить свои курсы ЕГЭ в Тик-Ток формате. Никаких скучных вебинаров, только залипательный контент!
Готовься к ЕГЭ в Тик-Ток формате
«Незнайка» и «Решу ЕГЭ» запускают свои курсы подготовки. Короткие видео, много практики и нереальная польза!
Задание № 6889
Обозначим через m&n поразрядную конъюнкцию неотрицательных целых чисел тип. Так, например, 12&6 = 11002&01102 = 01002 = 4.
Для какого наибольшего неотрицательного целого числа А формула
х&А ≠ 0 → (х&10 = 0 → х& 3 ≠ 0)
тождественно истинна (т.е. принимает значение 1 при любом неотрицательном целом значении переменной х)?
Для какого наибольшего целого числа а формула
Для какого наибольшего целого числа А формула ((x ≤ 9) →(x⋅x ≤ A)) ⋀ ((y⋅y ≤ A) → (y ≤ 9)) тождественно истинна, то есть принимает значение 1 при любых целых неотрицательных x и y?
Решение:
В формуле имеется операция ^ — конъюнкция (логическое умножение), при нём в результате получится истинна если только все выражения будут истинными.
Рассмотрим скобки раздельно, избавимся от → — импликации (логическое следование).
A→B = A vB => (x > 9) v (x 2 ≤ A) между скобками получилась операция дизъюнкция (логическая сумма), при данной операции истинна будет, если хотя бы одно из выражений истинно. При x>9 [(x > 9) v (x 2 ≤ A)] – уже будет истинным, но при x [0; 9] (диапазон от 0 потому что в условии сказано: при любых целых неотрицательных x и y) выражение в первой скобки станет ложным и возникает необходимость проверки выражения во второй (x 2 ≤ A). В этой ситуации от ложного результата и должна спасти переменная А.
Значит чтобы (x 2 ≤ A)=1 => А>= x 2 (x ≤ 9) => A>=81.
Аналогично рассмотрим вторую часть выражения ((y⋅y ≤ A) → (y ≤ 9)) = 1
(y 2 >=A) v (y ≤ 9)=1
y [10;+ ∞ ) = > y 2 > A => A<100
т. е. 81 ≤ A < 100
По условию задачи надо найти максимальное А => A = 99
Ответ: 99
Решение попробую объяснить на следующем примере:
(x^53≠0)=>((x^41=0)=>(x^A≠0)). Как обычно надо найти наименьшее значение А для истинности данного выражения.
Избавляемся от импликации (хоть с помощью переменных или без них):
Из полученного выражения становится ясно, что для истинности выражения достаточно истинности всего лишь одной из скобок, т.е. если будет такой х что, хотя бы первая или вторая скобка (скобки с конъюнкцией х на числа) истинна, то не важно каким будет число А.
Но, т.к. нам надо найти именного его, предположим, что скобки без А ложны, а скобка с А обязательно истинна, тогда получаем:
(x^53=0) v (x^41≠0) = 0; (x^A≠0) = 1
Для ложности первых двух скобок надо чтобы они обе были ложными т.е.:
Представим число 53 в двоичной системе счисления и найдем значение x при котором скобка будет истинной:
X10 — 11x1x12 , т.е после поразрядной конъюнкции скобка будет истинной.
Представим число 41 в двоичной системе счисления и найдем значение x при котором скобка будет ложной:
X10 — 0х0хx02 , т.е после поразрядной конъюнкции скобка будет ложной0.
Сопоставим полученные числа:
0 и 1 или 0 и х даст – 0; х и х – даст х; 1 и х – даст 1.
Соответственно получим следующее число: 0101х0, т.е. таковым и должно быть число А, но т.к. нам надо найти наименьшее, вместо х проставляем 0 и переводим полученное число в десятичную систему счисления: 010100 = 20
Задание 15. Преобразование логических выражений
За правильное выполненное задание получишь 1 балл. На решение отводится примерно 5 минуты.
Задачи для тренировки
Для какого наибольшего целого числа А формула ((x ≤ 9) →(x ⋅ x ≤ A)) ⋀ ((y ⋅ y ≤ A) → (y ≤ 9)) тождественно истинна, то есть принимает значение 1 при любых целых неотрицательных x и y?
На числовой прямой даны два отрезка: Р = [30, 50] и Q = [21, 41].
Укажите наибольшую возможную длину промежутка А, для которого формула ((x ∈ P) → (x ∈ Q)) ∧ (x ∈ A) тождественно ложна, то есть принимает значение 0 при любом значении переменной х.
Обозначим через ДЕЛ(n, m) утверждение «натуральное число n делится без остатка на натуральное число m ». Для какого наименьшего натурального числа А формула
тождественно истинна (то есть принимает значение 1 при любом натуральном значении переменной х )?
15. Преобразование логических выражений
тождественно истинно, т.е. принимает значение 1 при любых целых неотрицательных x и y?
Решение:
Если 48≠y+2x = 0 , тогда A<x = 1 или A<y = 1
при x=0, y=48; при y=0, x=24
Ответ: 15
Демонстрационный вариант ЕГЭ 2018 г. – задание №18
Для какого наибольшего целого числа А формула
((x ≤ 9) →(x⋅x ≤ A)) ⋀ ((y⋅y ≤ A) → (y ≤ 9))
тождественно истинна, то есть принимает значение 1 при любых целых неотрицательных x и y?
Решение:
y.y>A + y≤9 => при y=10, 100>A => A=99
Ответ: 99
Обозначим через m&n поразрядную конъюнкцию неотрицательных целых чисел m и n. Так, например, 14&5 = 11102&01012 = 01002 = 4. Для какого наименьшего неотрицательного целого числа А формула
x&51 = 0 ∨ (x&41 = 0 → x&А ≠ 0)
тождественно истинна (т.е. принимает значение 1 при юбом неотрицательном целом значении переменной х)?
Демонстрационный вариант ЕГЭ 2017 г. – задание №18
Решение:
1-й способ:
Упростим выражение x&51 = 0 \/ (x&41 = 0 → x&А ≠ 0) :
x&51 = 0 ∨ x&41 ≠ 0 ∨ x&А ≠ 0.
Так как ¬A, то для А берем множество, которое входит в 51, но не входит в 41.
51 и 41 представим в виде суммы степеней 2.
51 = 32 + 16 + 2 + 1
2-й способ:
Упростим выражение x&51 = 0 \/ (x&41 = 0 → x&А ≠ 0) :
x&51 = 0 ∨ x&41 ≠ 0 ∨ x&А ≠ 0
51=0 + 41≠0 + A≠0 = 1
| 51=0 | 41≠0 | A≠0 |
| 0 | 0 | 1 |
| 51 | 110011 | 41 | 101001 |
| 11xx11 | 0x0xx0 |
11xx11
0x0xx0
010×10=010010=18 (x=0 Для какого наименьшего)
единицы в числе X могут быть
000010
010000
010010
таким образом, А&x≠0, это 010010, т.к. это число учитывает все 3 случая.
Ответ: 18
Демонстрационный вариант ЕГЭ 2016 г. – задание №18
Обозначим через m&n поразрядную конъюнкцию неотрицательных целых чисел m и n. Так, например, 14&5 = 11102&01012 = 01002 = 4.
Для какого наименьшего неотрицательного целого числа А формула
x&25 ≠ 0 → (x&17 = 0 → x&А ≠ 0) тождественно истинна (т.е. принимает значение 1 при любом неотрицательном целом значении переменной х)?
Решение:
1-й способ:
Упростим выражение x&25 = 0 \/ (x&17 = 0 → x&А ≠ 0) :
x&25 = 0 ∨ x&17 ≠ 0 ∨ x&А ≠ 0.
Так как ¬A, то для А берем множество, которое входит в 25, но не входит в 17.
25 и 17 представим в виде суммы степеней 2.
2-й способ:
Упростим выражение x&25 = 0 \/ (x&17 = 0 → x&А ≠ 0) :
x&25 = 0 ∨ x&17 ≠ 0 ∨ x&А ≠ 0.
25=0 + 17≠0 + A≠0 = 1
| 25=0 | 17≠0 | A≠0 |
| 0 | 0 | 1 |
| 25 | 11001 | 17 | 10001 |
| 11xx1 | 0xxx0 |
11xx1
0xxx0
01xx0=01000=8 (x=0 Для какого наименьшего)
единицы в числе X могут быть
01000
таким образом, А&x≠0, это 01000=8.
Ответ: 8
Определите наибольшее натуральное число A
Введём выражение M & K, обозначающее поразрядную конъюнкцию M и K (логическое «И» между соответствующими битами двоичной записи). Определите наибольшее натуральное число A, такое что выражение
(X & A ≠ 0) → ((X & 56 = 0) → (X & 20 ≠ 0))
тождественно истинно (то есть принимает значение 1 при любом натуральном значении переменной X)?
Решение:
1-й способ:
Упростим выражение (X & A ≠ 0) → ((X & 56 = 0) → (X & 20 ≠ 0)) :
(X & A = 0) ∨ (X & 56 ≠ 0) ∨ (X & 20 ≠ 0)
Наибольшее, это объединение 56 и 20.
А = 32 + 16 + 8 + 4
2-й способ:
Упростим выражение (X & A ≠ 0) → ((X & 56 = 0) → (X & 20 ≠ 0)) :
(X & A = 0) ∨ (X & 56 ≠ 0) ∨ (X & 20 ≠ 0)
A=0 + 56≠0 + 20≠0 = 1
| A=0 | 56≠0 | 20≠0 |
| 1 | 0 | 0 |
| 56 | 111000 | 20 | 10100 |
| 000xxx | 0x0xx |
000xxx
0x0xx
0000xx
наибольшее натуральное число A
таким образом, А&x=0, это 111100=60.
Ответ: 60
Демонстрационный вариант ЕГЭ 2016 г. (досрочный период ) – задание №18
На числовой прямой даны два отрезка: P = [20, 50] и Q = [30,65]. Отрезок A таков, что формула
¬(x ∈ A) → ((x ∈ P) →¬ (x ∈ Q))
истинна при любом значении переменной x. Какова наименьшая возможная длина отрезка A?
Решение:
Упростим выражение ¬(x ∈ A) → ((x ∈ P) →¬ (x ∈ Q))
Ответ: 20
Демонстрационный вариант ЕГЭ 2015 г. (досрочный период ) – задание №18
Обозначим через ДЕЛ(n, m) утверждение «натуральное число n делится без остатка на натуральное число m».
Для какого наибольшего натурального числа А формула
¬ДЕЛ(x, А) → (ДЕЛ(x, 6) → ¬ДЕЛ(x, 4))
тождественно истинна (то есть принимает значение 1 при любом натуральном значении переменной х)?
Решение:
Упростим выражение ¬ДЕЛ(x, А) → (ДЕЛ(x, 6) → ¬ДЕЛ(x, 4))
| A | ¬6 | ¬4 |
| 1 | 0 | 0 |
X делится на 6 и 4. Это 12, 24, 36 ..
Делители X=12 => 1,2,3,4,6,12
Для какого наибольшего натурального числа А = 12
Ответ: 12
Демонстрационный вариант ЕГЭ 2015 г. (досрочный период ) – задание №18
Обозначим через ДЕЛ(n, m) утверждение «натуральное число n делится без остатка на натуральное число m».
Для какого наибольшего натурального числа А формула
ДЕЛ(x, 18) → (¬ДЕЛ(x, A) → ¬ДЕЛ(x, 12))
тождественно истинна (то есть принимает значение 1 при любом натуральном значении переменной х)?
Решение:
Упростим выражение ДЕЛ(x, 18) → (¬ДЕЛ(x, A) → ¬ДЕЛ(x, 12))
| A | ¬18 | ¬12 |
| 1 | 0 | 0 |
X делится на 18 и 12. Это 36, 72, 108 ..
Делители X=36 => 1,2,3,4,… 36
Для какого наибольшего натурального числа А = 36
Ответ: 36
Сколько существует целых значений числа A, при которых формула
((x < 5) → (x 2 < A)) /\ ((y 2 ≤ A) → (y ≤ 5))
тождественно истинна при любых целых неотрицательных x и y?
Источник: СтатГрад 2017−2018
Решение:
( x ≥ 5 + x 2 < A ) . (y 2 > A + y ≤ 5)
Если x ≥ 5 = 0, тогда x 2 < A = 1
x ≥ 5 = 0, когда x=4; x 2 < A = 1 => 4 2 < A => 16<A
Если y ≤ 5 = 0, тогда y 2 > A= 1
y ≤ 5 = 0, когда y=6; y 2 > A = 1 => 6 2 > A => 36 > A
16<A<36
Ответ: 19
Введём выражение M & K, обозначающее поразрядную конъюнкцию M и K (логическое «И» между соответствующими битами двоичной записи). Определите наименьшее натуральное число a, такое что выражение
( (x & 28 ≠ 0) ∨ (x & 45 ≠ 0)) → ((x & 48 = 0) → (x & a ≠ 0))
тождественно истинно (то есть принимает значение 1 при любом натуральном значении переменной x)?
Решение:
(¬28 + ¬45) → (48 → ¬a) = 1
¬ (¬28 + ¬45) + (¬48 + ¬a) = 1
(28 ⋅ 45) + ¬48 + ¬a = 1
| (28 ⋅ 45) | ¬48 | ¬a |
| 0 | 0 | 1 |
| 28 | 0 | 1 | 1 | 1 | 0 | 0 |
| 45 | 1 | 0 | 1 | 1 | 0 | 1 |
| 28 or 45 | 1 | 1 | 1 | 1 | 0 | 1 |
| 48 | 1 | 1 | 0 | 0 | 0 | 0 |
| x | 0 | 0 | ||||
| x&48=0 | 0 | 0 | 0 | 0 | 0 | 0 |
| 28 or 45 | 1 | 1 | 1 | 1 | 0 | 1 |
| x | 0 | 0 | ||||
| 1 | 1 | 0 | 1 | = 13 |
Ответ: 13
На числовой прямой даны два отрезка: P = [10, 35] и Q = [17, 48].
Укажите наименьшую возможную длину отрезка A, для которого формула
((x ∈ A) → ¬(x ∈ P)) → ((x ∈ A) → (x ∈ Q))
тождественно истинна, то есть принимает значение 1 при любом значении переменной х.
Решение:
((x ∈ A) → ¬(x ∈ P)) → ((x ∈ A) → (x ∈ Q))
Ответ: 7
На числовой прямой задан отрезок A. Известно, что формула
((x ∈ A) → (x 2 ≤ 121)) /\ ((x 2 ≤ 81) → (x ∈ A))
тождественно истинна при любом вещественном x. Какую наименьшую длину может иметь отрезок A?
Решение:
((x ∉ A) + (x 2 ≤ 121)) · ((x 2 > 81) + (x ∈ A)) = 1
| 1 | · | 1 | =1 |
| ((x ∉ A) + (x 2 ≤ 121)) | · | ((x 2 > 81) + (x ∈ A)) | =1 |
((x ∉ A) + (x 2 ≤ 121))
Если x 2 ≤ 121=0, тогда (x ∉ A)=1 => x 2 > 121 и (x ∉ A)
-11>x и x>11 => 11 ≤ A ≤ 11, 11+11=22
((x 2 > 81) + (x ∈ A))
Если x 2 > 81=0, тогда (x ∈ A)=1 => x 2 ≤ 81 и (x ∈ A)
-9 ≤ x ≤ 9 => -9 ≤ A ≤ 9, 9+9=18
наименьшую длину => 18
Ответ: 18
На числовой прямой задан отрезок A. Известно, что формула
((x ∈ A) → (x 2 ≤ 64)) /\ ((y 2 ≤ 49) → (y ∈ A))
тождественно истинна при любых вещественных x и y. Какую наименьшую длину может иметь отрезок A?
Для какого наибольшего целого числа а формула
Упростим выражение
29 = 0 / 17 ≠ 0 / A ≠ 0
Найдем иксы, для которых известная часть (29 = 0 / 17 ≠ 0) будет ложна. То есть такие числа, при которых (29 ≠ 0 / 17 = 0)
29 = 11101
17 = 10001
Числа, которые при умножении на 29 не дают 0 и при умножении на 17 дают 0:
00100
00110
01000
01010
01110
Чтобы выражение было истинно, все они при умножении на А не должны давать 0. Соответственно наименьшее А = 1100 = 12