Задания на отрезки на числовой прямой
Впервые данного типа задание появилось в демонстрационном варианте 2013
На числовой прямой даны два отрезка: P = [2; 10] и Q = [6; 14]. Укажите наименьшую возможную длину такого
отрезка A, для которого логическое выражение
((x∈A) → (x∈P)) ∨ (x∈Q)
истинно (т.е. принимает значение 1) при любом значении переменной х.
1) [0, 3] 2) [3, 11] 3) [11, 15] 4) [15, 17]
Также, как и в предыдущей задаче сделаем замену для удобства: x ∈ A = A, x ∈ P = P, x ∈ Q = Q и перепишем данное логическое выражение:
(A→P)∨Q
После чего упростим, используя формулу раскрытия импликации и законы де Моргана:
(A → P) ∨ Q = ¬A ∨ P ∨ Q
Так как Amin = ¬B, a B=P∨QB=P∨Q, тогда ¬B = ¬P ∧ ¬Q
Нарисуем область истинности на числовом луче:
Получим интервал (−∞;2)∪(14;+∞). Таким образом, нужный нам интервал A, при котором наше исходное выражение при котором исходное выражение будет всегда истина - это [2, 14]. Тогда из приведенных вариантов ответом нам подходит только второй [3,11].
Рассмотрим еще одну задачу из демонстрационного варианта 2025 года.
На числовой прямой даны два отрезка: P = [15; 40] и Q = [21; 63]. Укажите наименьшую возможную длину такого отрезка A, что формула
(x ∈ P) → (((x ∈ Q)∧¬(x ∈ A)) → ¬(x ∈ P))
истинна при любом значении переменной х, т.е. принимает значение 1 при любом значении переменной х.
Решение. Сделаем замены и выполним преобразования логического выражения:
P → (( Q∧¬A) → ¬ P)=¬ P∨(( Q∧¬A) → ¬ P)=¬ P∨(¬( Q∧¬A)∧¬ P)=¬ P∨¬Q∨A
Так как Amin=¬BAmin=¬B, a B=¬ P∨¬QB=¬ P∨¬Q, тогда ¬B=P∧Q.
Нарисуем область истинности на числовом луче:
Таким образом: минимальная длина отрезка A [40,60] равна 40−21=19.
Задания на делимость
В первые данный прототип задания на алгебру логики появился в 2015 году на досрочном экзамене.
Рассмотрим для начала аналитическое решение данной задачи.
Открытый банк заданий ФИПИ. Обозначим через ДЕЛ(n, m) утверждение «натуральное число n делится без остатка на натуральное число m». Для какого наибольшего натурального числа А логическое выражение
¬ДЕЛ(x,A) → (ДЕЛ(x,36) → ¬ДЕЛ(x,54))
тождественно истинно (т.е. принимает значение 1 при любом неотрицательном целом значении переменной х)?
Для того, чтобы было легче выполнять преобразования, сделаем замены:
- ДЕЛ(x,A)=A;
- ДЕЛ(x,36)=D36;
- ДЕЛ(x,54)=D54.
Перепишем выражение из условия задачи, выполнив замену, и для замены импликации будем использовать формулу:
X → Y = ¬X ∨ Y
Таким образом, наше выражение примет вид:
¬A → (D36 → ¬D54) = ¬¬A ∨ (D36 → ¬D54) = A ∨ ¬D36 ∨ ¬¬D54 = A ∨ ¬D36 ∨D54
В учебнике К.Ю. Полякова предложено построить логическое выражение A такое, что логическое выражение A+BA+B истинно для всех элементов универсального множества.
Задача сводится к равенству A ∨ B = 1, а так как в алгебре логики нет операции вычитания, то A = ¬B
Таким образом, вернемся к нашей задаче. В данном случае множеством BB будет являться ¬D36∨D54, тогда
¬B = ¬(¬D36 ∨ D54)=D36 ∧ ¬D54
Таким образом, x одновременно должен делиться на 36 и не делиться на 54:
Мы видим, что это число 108.
Рассмотрим еще один вариант задач - их обычно называют "смешанными", где формула содержит как утверждение делимости, так и уравнение прямой в координатной плоскости.
Апробация 01.2023. Обозначим через ДЕЛ(n, m) утверждение «натуральное число n делится без остатка на натуральное число m»; и пусть на числовой прямой дан отрезок В = [50; 70].
Для какого наибольшего натурального числа А формула
ДЕЛ(x,А)∨(ДЕЛ(x,23)→¬(x∈В))
тождественно истинна (т.е. принимает значение 1) при любом натуральном значении переменной х?
Решим задачу аналитически, для этого выполним замены и преобразования, аналогично предыдущим шагам:
ДЕЛ(x,A)∨(ДЕЛ(x,23)→¬(x∈В))=A∨(D23→¬B)=A∨¬D23∨¬B
Чтобы наше выражение было истинным, тогда ¬D23∨¬B=0, (опираясь на материал учебника К.Ю. Полякова):
¬(¬D23 ∨ ¬B) = D23 ∧ B.
Таким образом, число должно делиться на 23, а также принадлежать отрезку [50;70] - это число 69:
Задания с координатной плоскостью
Рассмотрим задачу № 18 демонстрационного варианта 2019 ЕГЭ по информатике.
Для какого наибольшего целого неотрицательного числа А выражение
(48 ≠ y +2x)∨(A < x)∨(A < y)
тождественно истинно, т.е. принимает значение 1 при любых целых неотрицательных x и y?
Для того, чтобы решить данную задачу, необходимо уметь строить графики функций, чаще всего - это уравнение прямой:
y=kx+b
Так как в задаче между условиями стоит логическая операция ИЛИ, то достаточно, чтобы было истина хотя бы одно из условий:
48 ≠ y +2x,
y ≠−2x+4848
A < x,
A < y.
Для начала изобразим на координатной плоскости выражения, в которых нет параметра - это y ≠−2x+48:
Чтобы исходное выражение было тождественно истинно для любых целых и неотрицательных x и y, все три прямые, указанные в условии задачи должны пересекаться в одной точке, для этого необходимо составить и решить систему уравнений
Подставим значения x = A,y = A в уравнение y=−2x+48:
A=−2A+48,
A+2A=48,
3A=48,
A=48/3=16.
Так как у нас строгие неравенства, то необходимо взять значения A на единицу меньше. Тогда A=15. Таким образом, наши прямые будут пересекаться в точке с координатами (15, 15).
В ответе напишем число 15.
Демонстрационный вариант ЕГЭ по информатике 2020 г.
Для какого наименьшего целого неотрицательного числа А выражение
(x +2y < A)∨(y > x)∨(x >30)
тождественно истинно, т.е. принимает значение 1 при любых целых неотрицательных x и y?
Тут также достаточно, чтобы было истинно хотя бы одно из трех условий:
x +2y < A,,
y > x,
x >30.
Далее также изобразим на координатной плоскости области для выражений, не имеющий параметра A:
Закрашенные области соответствуют истине и без параметра AA. Для того, чтобы полное выражение принимало значение истины, необходимо, чтобы вся координатная плоскость была перекрыта.
2y < -x + A,
y < -x/2+A/2
Построим вспомогательную область y < -x/2
Нам необходимо "закрасить" оставшуюся область на координатной плоскости. Поэтому необходимо "поднять" область y < -x/2 до точки пересечения первых двух областей, которая имеет координаты (30,30).
Подставим данную точку в уравнение прямой y < -x/2 + A/2.
30 < -30/2+A/2,
30 < -15 + A/2,
60 < −30+A,
90 < A.
A>90.
Так как неравенства строгие, то берем значение на единицу больше - это 91.
Основная волна 2021. Для какого наибольшего целого неотрицательного числа А выражение
(2x+y≠70)∨(x < y)∨(A < x)
тождественно истинно, т.е. принимает значение 1 при любых целых неотрицательных x и y?
Изобразим на координатной плоскости выражения, в которых нет параметра - это y ≠ −2x + 70 и y > x
Также аналитический найдем точку пересечения двух прямых:
{y=−2x+70,
{y=x.
Подставим значение y=x в первое уравнение:
3x = 70, x = 23,(3)
Подставим значения x=23,(3) в x > A:
A<23,(3)
A=23.
В ответе напишем число 23.
Рассмотрим "смешанные" задачи, где формула содержит как утверждение делимости, так и уравнение прямой в координатной плоскости.
Рассмотрим на примере задания из варианта основной волны 2022 I.
Обозначим через ДЕЛ(n, m) утверждение «натуральное число n делится без остатка на натуральное число n». Для какого наименьшего натурального числа А формула
(ДЕЛ(х,2)→¬ДЕЛ(x,3))∨(x+A≥80)
тождественно истинна (т.е. принимает значение 1) при любом натуральном значении переменной х?
Решим задачу аналитически. Для начала выполним замену и преобразования, аналогично предыдущим задачам:
(D2 → ¬D3) ∨ (x + A ≥ 80) = ¬D2 ∨ ¬D3 ∨ (x + A ≥ 80)
Выбор натурального числа А должен обеспечить истинность формулы условия задачи, поэтому Amin=¬B, то B = ¬D2 ∨ ¬D3, тогда ¬B = ¬(¬D2 ∨ ¬D3) = D2 ∧ D3.
Таким образом, нам необходимо, чтобы число делилось на 2 и на 3 одновременно, очевидно, x=6. Подстивим данное значение в неравенство x + A ≥ 80, и найдем А:
6 + A ≥ 80,
A ≥ 80 − 6,
A ≥ 80 − 6, А ≥ 74.
Так как неравенство не строгое, то A=74.
Задания с поразрядной конъюнкцией
Перейдем к самому сложному типу задач - это поразрядная конъюнкция. Для начала рассмотрим аналитическое решение задачи из демонстрационного варианта ЕГЭ по информатике 2016.
Обозначим через m&n поразрядную коньюнкцию неотрицательных целых чисел m и n. Так, например, 14 & 5 = 11102 & 01012 = 01002 = 4. Для какого наименьшего неотрицательного целого числа А формула
(x&25 ≠ 0) → ((x&17=0) → (x&А ≠ 0))
тождественно истинна (т.е. принимает неотрицательном целом значении переменной х)?
Введем обозначения: ¬K25 = (x & 25 ≠ 0), K17 = (x & 17 = 0), ¬A = (x & A ≠ 0)
После перепишем выражение и выполним преобразования:
¬K25 → (K17 → ¬A) = ¬¬K25 ∨ (K17 → ¬A) = K25 ∨ ¬K17 ∨ ¬A
Перейдем к импликации, используя законы де Моргана:
¬K17 ∨ ¬A ∨ K25 = (K17 ∧ A) → K25.
Тут мы будем использовать следующее свойство:
K_N ∧ K_M=K_N or M
Условие K_N→K_M истино для любых натуральных значений x тогда и только тогда, когда все единичные биты двоичной записи числа M входят в множество единичных битов двоичной записи числа N.
Таким образом, K17 ∧ A = K17 ∧ K_M = K17 or M
Для того, чтобы выражение было истинно для всех x, нужно, чтобы двоичная запись числа 17 or A17 содержала все единичные биты числа 25, т.е. с помощью числа нужно добавить те единичные биты числа 25, которых нехватке в числе 17.
В данном случае мы имеем дело с поразрядной дизъюнкцией, например 14 & 5 = 11102 & 01012 = 11112 = 15.
Сначала определим те разряды, где точно стоит единица. Например, это тот случай, когда из нуля при дизъюнкции (операции ИЛИ) получается единица:
Затем проставим те разряды, где точно будет ноль. Такой случай возможен только тогда, когда из нуля получается ноль при применении дизъюнкции:
Мы видим, что на первый и последний разряд может быть как ноль, так и единица, так как при применении дизъюнкции из единицы мы получаем единицу
Таким образом, мы получим следующие значения x:
- 10002
- 10012
- 110012
- 110002
Но так как нам необходимо минимальное значение x, то возьмем 10002 = 8.