Содержание:
15 задание ЕГЭ «Основные законы алгебры логики»
Уровень сложности — повышенный,
Требуется использование специализированного программного обеспечения — нет,
Максимальный балл — 1,
Примерное время выполнения — 5 минут.
Проверяемые элементы содержания: Знание основных понятий и законов математической логики
Плейлист видеоразборов задания на YouTube:
Задание демонстрационного варианта 2022 года ФИПИ
Задания с множествами
Элементами множества А
являются натуральные числа. Известно, что выражение
((x ∈ {1, 3, 5, 7, 9, 11}) → ¬(x ∈ {3, 6, 9, 12})) ∨ (x ∈ A)
истинно (т. е. принимает значение 1) при любом значении переменной х
.
Определите наименьшее возможное значение суммы элементов множества A
.
Ответ: 12
- Введем обозначения:
P ≡ (x ∈ {1, 3, 5, 7, 9, 11}) ; Q ≡ (x ∈ {3, 6, 9, 12}) ; A ≡ (x ∈ A).
(P → ¬Q) ∨ A = 1 Избавимся от импликации: ¬P ∨ ¬Q ∨ A = 1
А
) была непременно истинной, необходимо, чтобы известная часть была ложна:¬P ∨ ¬Q ∨ А = 1 0 1
¬P ∨ ¬Q = 0, или ¬P = 0 отсюда P = 1 ¬Q = 0 отсюда Q = 1
Q
и P
. То есть необходимо выбрать элементы, которые встречаются в обоих множествах одновременно:A = {3,9}
3 + 9 = 12
📹 Видео (аналитическое решение)
📹 Видеорешение на RuTube здесь
Элементами множества А
являются натуральные числа. Известно, что выражение
(x ∈ {2, 4, 6, 8, 10, 12}) → (((x ∈ {3, 6, 9, 12, 15}) ∧ ¬(x ∈ A)) → → ¬(x ∈ {2, 4, 6, 8, 10, 12}))
истинно (т. е. принимает значение 1) при любом значении переменной х
.
Определите наименьшее возможное значение суммы элементов множества A
.
Ответ: 18
- Введем обозначения:
P≡(x ∈ {2, 4, 6, 8, 10, 12}) ; Q ≡ (x ∈ {3, 6, 9, 12, 15}) ; A ≡ (x ∈ A).
P → ((Q ∧ ¬A) → ¬P) = P → (¬(Q ∧ ¬А) ∨ ¬P) = ¬P ∨ (¬(Q ∧ ¬А) ∨ ¬P) = ¬P ∨ ¬Q ∨ А.
А
) была непременно истинной, необходимо, чтобы известная часть была ложна:¬P ∨ ¬Q ∨ А = 1 0 1
¬P ∨ ¬Q = 0, или ¬P = 0 отсюда P = 1 ¬Q = 0 отсюда Q = 1
Q
и P
. То есть необходимо выбрать элементы, которые встречаются в обоих множествах одновременно:A = {6,12}
6 + 12 = 18
Элементами множеств А
, P
, Q
являются натуральные числа, причём P = {2, 4, 6, 8, 10, 12, 14, 16, 18, 20}
, Q = {3, 6, 9, 12, 15, 18, 21, 24, 27, 30}
. Известно, что выражение
( (x ∈ A) → (x ∈ P) ) ∧ ( (x ∈ Q) → ¬(x ∈ A) )
истинно (т. е. принимает значение 1) при любом значении переменной х
.
Определите наибольшее возможное количество элементов в множестве A
.
Ответ: 7
- Введем обозначения:
P ≡ (x ∈ P); Q ≡ (x ∈ Q); A ≡ (x ∈ A).
Избавимся от импликации: (¬A ∨ P) ∧ (¬Q ∨ ¬A) = 1 Применим распределительный закон (но можно вывести самостоятельно): ¬A ∨ (P ∧ ¬Q) = 1
А
) была непременно истинной, необходимо, чтобы известная часть была ложна:¬A ∨ (P ∧ ¬Q) = 1 0 1
P ∧ ¬Q = 1, или P = 1 и ¬Q = 1 отсюда Q = 0
Q
и P
. То есть это новое множество, элементы которого принадлежат P
, но не принадлежат Q
:A = {2, 4, 8, 10, 14, 16, 20}
Элементами множества А являются натуральные числа. Известно, что выражение
¬(x ∈ A) →¬(x ∈ {1, 3, 7}) ∨ (¬(x ∈ {1, 2, 4, 5, 6}) ∧ (x ∈ {1, 3, 7}))
истинно (т. е. принимает значение 1) при любом значении переменной х
.
Определите наименьшее возможное количество элементов множества A.
Ответ: 1
- Введем обозначения:
P ≡ (x ∈ {1, 3, 7}); Q ≡ (x ∈ {1, 2, 4, 5, 6}); A ≡ (x ∈ A).
Избавимся от импликации: A ∨ ¬P ∨ (¬Q ∧ P) = 1 Применим закон поглощения (но можно вывести самостоятельно): A ∨ ¬P ∨ ¬Q = 1
А
) была непременно истинной, необходимо, чтобы известная часть была ложна:A ∨ ¬P ∨ ¬Q = 1 1 0
¬P ∨ ¬Q = 0, или P = 1 и Q = 1
Q
и P
:A = {1}
Задания с отрезками на числовой прямой
Отрезки на числовой прямой:
На числовой прямой даны два отрезка: P=[44,48] и Q=[23,35].
Укажите наибольшую возможную длину отрезка А, для которого формула
((x ϵ P) → (x ϵ Q)) ∧ (x ϵ A)
тождественно ложна, то есть принимает значение 0 при любом значении переменной x.
Ответ: 4
- Упростим формулу, избавившись от ‘x ϵ‘:
(P → Q) ∧ A
(¬P ∨ Q) ∧ A
(¬P ∨ Q) ∧ A = 0
(¬P ∨ Q) ∧ A 0 ∧ 0 = 0 0 ∧ 1 = 0 1 ∧ 0 = 0 1 ∧ 1 = 1
1. (¬P ∨ Q) = 1 ∨ 0 = 1 - на данном отрезке А должно равняться 0
2. (¬P ∨ Q) = 1 ∨ 1 = 1 - на данном отрезке А должно равняться 0
3. (¬P ∨ Q) = 1 ∨ 0 = 1 - на данном отрезке А должно равняться 0
4. (¬P ∨ Q) = 0 ∨ 0 = 0 - на данном отрезке А может! равняться 1
5. (¬P ∨ Q) = 1 ∨ 0 = 1 - на данном отрезке А должно равняться 0
48 - 44 = 4
✎ Решение 2 (программирование):
Внимание! этот способ подходит НЕ для всех заданий с отрезками!
Python:
1 2 3 4 5 6 7 8 9 | def f(a1,a2,x): return((44<=x<=48)<=(23<=x<=35))and(a1<=x<=a2) maxim = 0 for a1 in range (1,200): for a2 in range (a1+1,200): if all(f(a1,a2,x)==0 for x in range (1,200)):# если все ложны if a2-a1>maxim: maxim=a2-a1 print(a1,a2, a2-a1) # сами точки отрезка и длина |
Вывод:
44 45 1
44 46 2
44 47 3
44 48 4
PascalABC.net:
1 |
Вывод:
📹 Видео (аналитическое решение)
📹 Видеорешение на RuTube здесь
Отрезки на числовой прямой:
На числовой прямой даны два отрезка: P = [10,20] и Q = [30,40].
Укажите наибольшую возможную длину отрезка A, для которого формула
((x ∈ P) → (x ∈ Q)) → ¬(x ∈ A)
тождественно истинна, то есть принимает значение 1 при любом значении переменной x.
Ответ: 10
- Упростим выражение, введя обозначения:
A: x ∈ A P: x ∈ P Q: x ∈ Q
(P → Q) → ¬A = 1
(P → Q) → ¬A = 1 => ¬(P → Q) ∨ ¬A = 1 => ¬(¬P ∨ Q) ∨ ¬A = 1
¬(¬P ∨ Q) ∨ ¬A = 1 =>
P ∧ ¬Q ∨ ¬A = 1
А = 1 P = 1 ¬Q = 1 или Q = 0
Отрезки на числовой прямой:
На числовой прямой даны два отрезка: P = [3, 20] и Q = [6, 12].
Укажите наибольшую возможную длину отрезка A, для которого формула
((x ∈ P) ~ (x ∈ Q)) → ¬(x ∈ A)
тождественно истинна, то есть принимает значение 1 при любом значении переменной x.
Ответ: 8
- Упростим выражение, введя обозначения:
A: x ∈ A P: x ∈ P Q: x ∈ Q
(P ~ Q) → ¬A = 1
(P ~ Q) → ¬A = 1 => ¬(P ~ Q) ∨ ¬A = 1
Далее возможно 2 способа решения.
✎ 1 способ:
¬(P ~ Q) = ¬((P ∧ Q) ∨ (¬P ∧ ¬Q)) = = ¬(P ∧ Q) ∧ ¬(¬P ∧ ¬Q)
¬(P ∧ Q) ∧ ¬(¬P ∧ ¬Q) = = ¬(P ∧ Q) ∧ (P ∨ Q)
¬(P ∧ Q) ∧ (P ∨ Q) ∨ ¬A = 1
¬(P ∧ Q) ∧ (P ∨ Q) = 1 А = 1
✎ 2 способ:
После того, как мы избавились от импликации, имеем:
¬(P ~ Q) ∨ ¬A = 1
📹 Видео (аналитическое решение)
📹 Видеорешение на RuTube здесь
Отрезки на числовой прямой:
На числовой прямой даны два отрезка: P = [11, 21] и Q = [15, 40].
Укажите наибольшую возможную длину отрезка A, для которого формула
(x ∈ A) → ¬((x ∈ P) ~ (x ∈ Q))
тождественно истинна, то есть принимает значение 1 при любом значении переменной x.
Ответ: 19
- Упростим выражение, введя обозначения:
A: x ∈ A P: x ∈ P Q: x ∈ Q
A → ¬(P ~ Q) = 1
A → ¬(P ~ Q) = 1 =>
¬A ∨ ¬(P ~ Q) = 1
Задания с ДЕЛ
Поиск наибольшего А, известная часть Дел ∨ Дел = 1
Для какого наибольшего натурального числа А формула
(ДЕЛ(x, 40) ∨ ДЕЛ(x, 64)) → ДЕЛ(x, A)
тождественно истинна (то есть принимает значение 1 при любом натуральном значении переменной х)?
Ответ: 8
- Введем обозначения:
A = ДЕЛ(x,A); D40 = ДЕЛ(x, 40); D64 = ДЕЛ(x, 64)
(D40 ∨ D64) → A = 1
¬(D40 ∨ D64) ∨ A = 1 или (¬D40 ∧ ¬D64) ∨ A = 1
(¬D40 ∧ ¬D64) ∨ A = 1 1 2
Т.е. (¬D40 ∧ ¬D64) должно быть = 0. Это нам ничего не дает, т.к. конъюнкция ложна в трех случаях (1*0, 0*1 и 0*0), т.е. D40 и D64 могут быть равны как 0, так и 1 (исключение составляет лишь вариант, когда оба D истинны, тогда логическое умножение 1 * 1 ≠ 0).
¬D40 ∧ ¬D64 = 0 или ¬(¬D40 ∧ ¬D64) = 1 Преобразуем по закону Де Моргана и получим: D40 ∨ D64 = 1
Далее можно решать задание либо с помощью кругов Эйлера, либо с помощью логических рассуждений.
Решение с помощью логических рассуждений:
x
, которые делятся на А
и при этом делятся на 40 ИЛИ делятся на 64:x
/A :x
/40 ∨x
/64
x = 40, 64, 80, 120, 128, 160, 192, 200, ...
A
, начиная с самого наименьшего (единицы), на которые делятся все x
без исключения:А = 1, 2, 4, 8
А
равно 8.
НОД (40,64) = 8
40,64 (64 - 40 = 24)
40,24 (40 - 24 = 16)
24,16 (24 - 16 = 8)
16,8 (16 - 8 = 8)
8,8
Решение с помощью кругов Эйлера:
64 / 40 = 1 (24 остаток) 40 / 24 = 1 (16 остаток) 24 / 16 = 1 (8 остаток) 16 / 8 = 2 (0 остаток) - НОД = 8 +++ 40 / 8 = 5 64 / 8 = 8
Результат: 8
✎ Решение 2 (программирование):
Python:
1 2 3 4 5 6 | for A in range(1,500): OK = 1 for x in range(1,1000): OK *= ((x % 40 == 0) or (x % 64 == 0))<=(x % A== 0) if OK: print( A ) |
Вывод:
1
2
4
8
PascalABC.net:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 | begin for var A := 1 to 500 do begin var ok := 1; for var x := 1 to 1000 do begin if (((x mod 40 = 0) or (x mod 64 = 0)) <= (x mod A = 0)) = false then begin ok := 0; break; end; end; if (ok = 1) then print(A) end; end. |
Вывод:
1
2
4
8
Результат: 8
Поиск наименьшего А, известная часть Дел ∧ ¬Дел = 1
Для какого наименьшего натурального числа А формула
ДЕЛ(x, A) → (¬ДЕЛ(x, 28) ∨ ДЕЛ(x, 42))
тождественно истинна (то есть принимает значение 1 при любом натуральном значении переменной х)?
Ответ: 3
Имеем:
ДЕЛ(x, A) → (¬ДЕЛ(x, 28) ∨ ДЕЛ(x, 42)) = 1
A = ДЕЛ(x,A); D28 = ДЕЛ(x, 28); D42 = ДЕЛ(x, 42)
A → (¬D28 ∨ D42) = 1
Избавимся от импликации:
¬A ∨ (¬D28 ∨ D42) = 1
¬A ∨ (¬D28 ∨ D42) = 1 1 2
(¬D28 ∨ D42) = 0 один случай: когда ¬D28 = 0 и D42 = 0
x
/¬A :x
/28 ∧x
/¬42
x
, которые НЕ делятся на А
и при этом делятся на 28 И НЕ делятся на 42:x = 28, 56,84, 112, 140,168, 196, 224, ...
A
, начиная с самого наименьшего (единицы), на которые НЕ делятся все x
без исключения:А = 1, 2, 3
А
равно 3.
✎ Решение 2 (программирование). Язык Python, Pascal:
-
Из общего выражения:
ДЕЛ(x, A) → (¬ДЕЛ(x, 28) ∨ ДЕЛ(x, 42)) = 1
А
, необходимо рассмотреть диапазон натуральных значений x
. Если выражение будет истинным для диапазона всех рассматриваемых х
, то такое А
необходимо вывести на экран.А
(ограничим их числом 50, т.к. необходимо найти наименьшее А
), будем запускать внутренний цикл, перебирающий значения х
(х
ограничим числом 1000, будем рассматривать данный диапазон, как «любое натуральное значение переменной х»).Python:
for A in range(1,50): OK = 1 for x in range(1,1000): OK *= (x % A == 0) <= ((x % 28 != 0) or (x % 42== 0)) if OK: print( A ) break |
PascalABC.net:
begin for var A := 1 to 50 do begin var ok := 1; for var x := 1 to 1000 do begin if (x mod A = 0) <= ((x mod 28 <> 0)or (x mod 42 = 0)) = false then begin ok := 0; break; end; end; if (ok = 1) then begin print(A); break; end end; end. |
OK
— переменная-индикатор: если находится такое А
при котором, диапазон всех значений x
, подставленных в выражение, возвращает истинное значение выражения, то ОК
остается равным 1, т.к. используется операция умножения (до цикла ОК
необходимо присвоить единице).Следует иметь в виду, что в программировании вместо операции импликация (
->
) можно использовать нестрогое неравенство: <=
. Т.к. таблица истинности для операции импликация соответствует операции <=
:
a b F(a<=b) 0 0 1 0 1 1 1 0 0 1 1 1
А
, т.к. используется оператор break
для выхода из цикла после первого найденного значения:
3
Результат: 3
Задание с ДЕЛ:
Для какого наименьшего натурального числа А формула
(¬ДЕЛ(x, 19) ∨ ¬ДЕЛ(x, 15)) → ¬ДЕЛ(x, A)
тождественно истинна (то есть принимает значение 1 при любом натуральном значении переменной х)?
Ответ: 285
- Введем обозначения:
A = ДЕЛ(x,A); D19 = ДЕЛ(x, 19); D15 = ДЕЛ(x, 15)
(¬D19 ∨ ¬D15) → ¬A = 1
D19 ∧ D15 ∨ ¬A = 1
¬A ∨ D19 ∧ D15 = 1 1 2
¬A ∨ D19 ∧ D15 = 1 0 ∨ 1 = 1
¬A = 0 при D19 ∧ D15 = 1 или A = 1 при D19 = 1 и D15 = 1
A = 1 D19 = 1 D15 = 1
19 * 2 = 38 (38 не делится на 15) 19 * 3 = 57 (57 не делится на 15) 19 * 4 = 76 (76 не делится на 15) 19 * 5 = 95 (95 не делится на 15) ... 19 * 10 = 190 (190 не делится на 15) 19 * 15 = 285 (285 делится на 15)
✎ Решение 2 (программирование):
Python:
Из общего выражения:
(¬ДЕЛ(x, 19) ∨ ¬ДЕЛ(x, 15)) → ¬ДЕЛ(x, A) = 1
А
, необходимо рассмотреть диапазон натуральных значений x
. Если выражение будет истинным для диапазона всех рассматриваемых х
, то такое А
необходимо вывести на экран.А
(ограничим их числом 500, т.к. необходимо найти наименьшее А
), будем запускать внутренний цикл, перебирающий значения х
(х
ограничим числом 1000, будем рассматривать данный диапазон, как "любое натуральное значение переменной х").for A in range(1,500): OK = 1 for x in range(1,1000): OK *= ((x % 19 != 0) or (x % 15 != 0))<= (x % A!= 0) if OK: print( A ) |
OK
- переменная-индикатор: если находится такое А
при котором, диапазон всех значений x
, подставленных в выражение, возвращает истинное значение выражения, то ОК
остается равным 1, т.к. используется операция умножения (до цикла ОК
необходимо присвоить единице).Следует иметь в виду, что в программировании вместо операции импликация (
->
) можно использовать нестрогое неравенство: <=
. Т.к. таблица истинности для операции импликация соответствует операции <=
:
a b F(a<=b) 0 0 1 0 1 1 1 0 0 1 1 1
А
:285
Задание с ДЕЛ:
Задания с поразрядной конъюнкцией
Поразрядная конъюнкция:
Для какого наименьшего неотрицательного целого числа A формула
(X & A = 0) ∧ ¬(X & 35 ≠ 0 → X & 52 ≠ 0)
тождественно ложна (то есть принимает значение 0 при любом неотрицательном значении переменной X)?
Ответ: 3
Рассмотрим один из вариантов решения:
- Удалим из формулы X&, чтобы сократить ее запись:
(A = 0) ∧ ¬(35 ≠ 0 → 52 ≠ 0)
(A = 0) ∧ ¬(35 ≠ 0 → 52 ≠ 0)
(A = 0) ∧ ¬(35 ≠ 0 → 52 ≠ 0) 1 2
(A = 0) ∧ ¬(35 = 0 ∨ 52 ≠ 0)
т.к. в результате получается отрицание того, что 35 ≠ 0,
то убираем знак "не равно": было 35 ≠ 0, стало 35 = 0
A = 0 ∧ 35 ≠ 0 ∧ 52 = 0 = 0
0 ∧ 0 = 0 0 ∧ 1 = 0 1 ∧ 0 = 0 1 ∧ 1 = 1
(A = 0) ∧ 35 ≠ 0 ∧ 52 = 0 = 0 0 ∧ 1 = 0
35 ≠ 0 ∧ 52 = истинно (=1) если: 35 ≠ 0 = истинно (=1) и 52 = 0 = истинно (=1) так как стоит логическое умножение ∧ - смотрим выше таблицу истинности для конъюнкции
35 ≠ 0 = 1 (истина) и 52 = 0 = 1 (истина) и A = 0 = 0 (ложь)
35: 100011 (≠ 0) 52: 110100 (= 0)
52 | 1 | 1 | 0 | 1 | 0 | 0 |
---|---|---|---|---|---|---|
X | 0 | 0 | ? | 0 | ? | ? |
35 | 1 | 0 | 0 | 0 | 1 | 1 |
---|---|---|---|---|---|---|
X | 1 | ? | ? | ? | 1 | 1 |
0 0 ? 0 ? ?& 1 ? ? ? 1 1 0 0 ? 0 1 1
X | 0 | 0 | ? | 0 | 1 | 1 |
---|---|---|---|---|---|---|
A | 0 | 0 | 0 | 0 | 1 | 1 |
0000112 = 310
📹 Видео (аналитическое решение)
📹 Видеорешение на RuTube здесь
Поразрядная конъюнкция:
Для какого наибольшего неотрицательного целого числа A формула
X & A ≠ 0 → (X & 36 = 0 → X & 6 ≠ 0)
тождественно истинна (то есть принимает значение 1 при любом неотрицательном значении переменной X)?
Ответ: 38
-
✎ Способ 1:
- Произведем замену:
z36 = (x&36 = 0), z6 = (x&6 = 0), A = (x&A = 0)
¬A → (z36 → ¬ z6)
¬A → (z36 → ¬ z6) = A + ¬z36 + ¬z6
A + ¬z36 + ¬z6 = A + ¬(z36 * z6)
A + ¬(z36 * z6) = ¬(z36 * z6) + A = (z36 * z6) → A
z36 * z6 = z36 or 6
1001002 -> 36 1102 -> 6 100100 + 110 1001102 -> 36 or 6 = 3810
z38 → A
A = 1001102 = 3810
✎ Способ 2:
x&A ≠ 0 → (x&36 = 0 → x&6 ≠ 0) = 1
A = (x&A = 0); P = (x&36 = 0); Q = (x&6 = 0);
¬A → (P → ¬Q) = 1
A ∨ (¬P ∨ ¬Q) = 1
¬P ∨ ¬Q
нам необходимо подобрать такой вариант (равный 0 или 1), при котором единственно возможным значением A была бы единица (1).
A ∨ (¬P ∨ ¬Q) = 1;
или
1 ∨ (0) = 1
¬P ∨ ¬Q = 0 Отсюда имеем: ¬P = 0 и ¬Q = 0 (дизъюнкция равна 0 в единственном случае, когда все операнды равны 0)
Q = 1 и P = 1
100100 : 36 000110 : 6 0**0** : маска P (x&36 = 0) ***00* : маска Q (x&6 = 0)
0**0** : маска P (x&36 = 0) ***00* : маска Q (x&6 = 0) 0**00* : общая маска x *00**0 : маска для A (x&A = 0) т.е. в тех битах А, где может получиться единица (звездочки в обеих масках),
мы поставили нули.
100110 = 3810
Результат: 38
📹 Видео 1
📹 Видеорешение на RuTube здесь
📹 Видео 2
📹 Видеорешение на RuTube здесь
Поразрядная конъюнкция:
Определите наименьшее натуральное число А из интервала [43, 55], такое, что выражение
((x & 17 ≠ 0) → ((x & A ≠ 0) → (x & 58 ≠ 0))) → → ((x & 8 = 0) ∧ (x & A ≠ 0) ∧ (x & 58 = 0))
тождественно ложно (то есть принимает значение 0 при любом натуральном значении переменной х)?
Ответ: 48
-
Кратко изложенное решение *:
- Введем обозначения:
(¬Z17 → (¬A → ¬Z58)) → (z8 ∧ ¬A ∧ Z58) = 0
¬(((¬Z17 → (¬A → ¬Z58)) → (z8 ∧ ¬A ∧ Z58)) = 1
Z8 ∧ Z58 = Z8 or 58 : 8 = 1000 or 58 = 111010 111010 = 58
Z8 ∧ Z58 = Z58
¬(¬(Z17 ∨ A ∨ ¬Z58) ∨ (¬A ∧ Z58)) = 1
(Z17 ∨ A ∨ ¬Z58) ∧ ¬(¬A ∧ Z58)) = 1
(Z17 ∨ A ∨ ¬Z58) ∧ (A ∨ ¬Z58) = 1
A ∨ ¬Z58 = 1
¬Z58 ∨ A => Z58 → A = 1
43 = 101011 - не подходит! 58 = 111010 44 = 101100 - не подходит! 58 = 111010 45 = 101101 - не подходит! 58 = 111010 46 = 101110 - не подходит! 58 = 111010 47 = 101111 - не подходит! 58 = 111010 48 = 110000 - подходит! 58 = 111010
Результат: 48
Поразрядная конъюнкция:
Определите набольшее натуральное число A, такое что выражение
((x & 26 = 0) ∨ (x & 13 = 0)) → ((x & 78 ≠ 0) → (x & A = 0))
тождественно истинно (то есть принимает значение 1 при любом натуральном значении переменной х)?
Ответ: 8
- Для упрощения восприятия введем обозначения:
z26 = (x & 26 = 0) z13 = (x & 13 = 0) z78 = (x & 78 = 0) A = (x & A = 0)
(z26 ∨ z13) → (¬z78 → A) = 1
(z26 ∨ z13) → (z78 ∨ A) = 1
26 : 11010 единичные биты: 4, 3, 1 13 : 1101 единичные биты: 3, 2, 0 ∧ =------------------------ 01000 = 810
z8 → (z78 ∨ A) z78: не влияет на решение, так как операция дизъюнкция истинна тогда, когда хотя бы один операнд истинен z8 → A : ????
Наибольшее А = 1000 = 810
Результат: 8
Задания на поиск наибольшего или наименьшего числа А
Поиск наибольшего или наименьшего числа А:
Для какого наибольшего целого числа А формула
тождественно истинна, то есть принимает значение 1 при любых целых неотрицательных x и y?
Ответ: 99
Pascalabc.net:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 | begin for var A := 200 downto -100 do begin var OK := 1; for var x := 0 to 100 do for var y := 0 to 100 do if ((x <= 9) <= (x * x <= A)) and ((y * y <= A) <= (y <= 9)) = false then begin OK := 0; break; end; if OK = 1 then begin print(A); break end; end; end. |
Бейсик:
|
Python:
|
||
С++:
|
✎ Способ 2 (теоретическое решение):
- Условно разделим исходное выражение на части:
- Главное действие (внешняя операция) в исходном выражении - это конъюнкция. Конъюнкция истинна, когда все операнды истинны. Т.е. в задаче обе части
1
и2
должны быть истинными (т.к. по условию общая формула должна быть истинной).
-
Рассмотрим часть
- если в
1.1
имеем x > 9, то часть1
будет истинна независимо от А. Значит, значение числа А влияет на решение только при выполнении условия: - теперь, для того чтобы в части
1
, выражение было истинным, надо чтобы часть1.2
была истинной: - таким образом, получаем:
1
:
(импликация 0 → 0 = 1, 0 → 1 = 1)
(импликация 1 → 1 = 1)
x <= 9 x2 <= A при любых x
возьмем наибольшее натуральное: x=9, тогда A>=81
Рассмотрим часть 2
:
2.2
истинно (т.е. y <= 9), то часть 2
будет истинна независимо от А. Значит, значение числа А влияет на решение только при выполнении условия:2
выражение было истинным, надо чтобы часть 2.1
была ложной:(импликация 0 → 0 = 1)
y > 9 y2 > A при любых y
возьмем наименьшее возможное по условию натуральное: y = 10, тогда A < 100
📹 Видео (аналитическое решение)
📹 Видеорешение на RuTube здесь
Поиск наибольшего или наименьшего числа А:
Укажите наименьшее значение А, при котором выражение
(y + 3x < A) ∨ (x > 20) ∨ (y > 40)
истинно для любых целых положительных значений x и y.
Типовые задания для тренировки: разбор досрочного егэ по информатике 2019
Ответ: 101
Pascalabc.net:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 | begin for var A := -100 to 200 do begin var OK := 1; for var x := 1 to 100 do for var y := 1 to 100 do if ((y+3*x<A) or (x >20)or(y>40)) = false then begin OK := 0; break; end; if OK = 1 then begin print(A); break end; end; end. |
Бейсик:
|
Python:
|
||
С++:
|
✎ Способ 2 (теоретическое решение):
- Определим основные части выражения, выделив отдельно неизвестную часть - с А, и, так сказать, известную часть, то есть остальную.
1 2 (y+3x < A) ∨ (x > 20) ∨ (y > 40)
(y+3x < A) ∨ (x > 20) ∨ (y > 40) 1 или 0? 1 = 1 Не подходит!
1. (y+3x < A) = 1 2. (x > 20) ∨ (y > 40) = 0
x <= 20 y <= 40
А > 3x + y A > 3*20 + 40 A > 100
📹 Видео (аналитическое решение)
📹 Видеорешение на RuTube здесь
Поиск наибольшего и наименьшего числа A:
Для какого наибольшего целого неотрицательного числа А выражение
(48 ≠ y + 2x) ∨ (A < x) ∨ (A < y)
тождественно истинно, т.е. принимает значение 1 при любых целых неотрицательных x и y?
Ответ: 15
- Разделим общее выражение на две части. Выделим неизвестную часть красным:
(48 ≠ y + 2x) ∨ (A < x) ∨ (A < y)
(48 ≠ y + 2x) ∨ (A < x) ∨ (A < y) = 1
0 1
y + 2x = 48 : при x = 0, y = 48 при y = 0, 2x = 48 => x = 24
x + 2x = 48 => 3x = 48 x = 16
✎ Решение 2 (программное):
Python:
1 2 3 4 5 6 7 8 | for A in range(200,0,-1): OK = 1 for x in range(0,100): for y in range(0,100): OK *= (48!=y+2*x) or(A<x)or (A<y) if OK: print(A) break |
📹 Видео (аналитическое решение)
📹 Видеорешение на RuTube здесь
Поиск наибольшего и наименьшего числа A:
Для какого наименьшего целого числа А формула
(y + 5x <= 34) → ((y - x > 4) ∨ (y <= A))
тождественно истинна, т.е. принимает значение 1 при любых целых неотрицательных x и y?
Ответ: 9
- Общая идея такова:
необходимо упростить формулу так, чтобы последняя операция (внешняя) выполнялась со скобкой, в которой находится искомое A. После чего разделить формулу на две части, в одной из которых находится искомое. - Избавимся от импликации, это даст нам возможность опустить общие скобки во второй части формулы:
¬(y + 5x <= 34) ∨ (y - x > 4) ∨ (y <= A)
¬(y + 5x <= 34) ∨ (y - x > 4) ∨ (y <= A) = 1 1 часть 2 часть
¬(y + 5x <= 34) ∨ (y - x > 4) ∨ (y <= A) = 1 1 часть = 0 2 часть = 1
y + 5x > 34 = 0, значит: 1. y + 5x <= 34 y - x > 4 = 0, значит: 2. y - x <= 4
y <= A или A >= y
34 - 5x = 4 + x 30 = 6x x = 5 Найдем y: y = 4 + 5 = 9
y = 9:
A >= 9 => наименьшее A = 9
✎ Решение 2 (программное):
Python:
1 2 3 4 5 6 7 8 | for A in range(-100,100): OK = 1 for x in range(0,100): for y in range(0,100): OK *= (y+5*x<=34)<=((y-x >4)or(y<=A)) if OK: print( A ) break |
PascalABC.NET:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 | begin for var A := -100 to 100 do begin var OK := true; for var x := 0 to 100 do begin for var y := 0 to 100 do begin OK := (y + 5 * x <= 34) <= ((y - x > 4) or (y <= A)); if OK = false then break; end; if OK = false then break; end; if OK then begin print(A); break; end; end; end. |
Поиск наибольшего и наименьшего числа A:
Укажите наименьшее целое значение А при котором выражение
(2y + 5x < A) ∨ (2x + 4y > 100) ∨ (3x – 2y > 70)
истинно для любых целых положительных значений x и y.
Ответ: 171
-
✎ Решение (программное):
Python:
1 2 3 4 5 6 7 8 | for A in range(-200,200): OK = 1 for x in range(1,100): for y in range(1,100): OK *= (2*y + 5*x < A) or (2*x + 4*y > 100) or (3*x - 2*y > 70) if OK: print( A ) break |
PascalABC.NET:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 | begin for var A := -200 to 200 do begin var OK := true; for var x := 1 to 100 do begin for var y := 1 to 100 do begin OK := (2*y + 5*x < A) or (2*x + 4*y > 100) or (3*x - 2*y > 70); if OK = false then break; end; if OK = false then break; end; if OK then begin print(A); break; end; end; end. |
📹 Видео (аналитическое решение)
📹 Видеорешение на RuTube здесь
Поиск наибольшего и наименьшего числа A:
Укажите наибольшее целое значение А при котором выражение
(3y – x > A) ∨ (2x + 3y < 30) ∨ (2y – x < –31)
истинно для любых целых положительных значений x и y.
Ответ: -31
-
✎ Решение 1 (теоретическое):
- Разделим выражение на две части: часть с неизвестным = 1, часть известная = 0:
(3y – x > A) ∨ (2x + 3y < 30) ∨ (2y – x < –31) = 1
(1) (2x + 3y) >= 30, y >= (30 - 2x) / 3 x = (30 - 3y) /2
(2) (2y – x >=–31) y >= (x - 31) / 2 x = 2y + 31
(1) x | y 0 | 10 15| 0
(2) x | y 0 | -15 ( целые) 30|0
A<3y-x
:A < 3y – x
, то будем перемещать А
снизу вверх. Наибольшее значение А
будет достигнуто в указанной точке пересечения с прямой (2)
.если y = 1, то x = 2*1 + 31 = 33
А < 3y - x A < 3-33, A < -30, A=-31
✎ Решение 2 (программное):
Python:
1 2 3 4 5 6 7 8 | for A in range(200,-200,-1): OK = 1 for x in range(1,100): for y in range(1,100): OK *= (3*y-x>A) or (2*x+3*y<30) or (2*y-x<-31) if OK: print(A) break |
Елена
Здравствуйте! Понравилось Ваше объяснение задач. Всё очень просто и доступно. Вопрос по подобной задаче (у Вас 18_4). Объяснение оттуда не очень меня удовлетворяет. Помогите, пожалуйста! Вот задача:
На числовой прямой даны два отрезка: P = [8, 39] и Q = [23, 58].
Выберите из предложенных отрезков такой отрезок A, что логическое выражение
((x ∈ P) ∨ (x ∈ А)) → ((x ∈ Q) ∨ (x ∈ А))
тождественно истинно, то есть принимает значение 1 при любом значении переменной х.
1) [5, 30]
2) [15, 40]
3) [25, 50]
4) [35, 60]
В отличие от 19_4 вместо умножения стоит плюс
Alex
Решение к 18_8 как можно увидеть? У Вас только ответ
admin
скоро будет, спасибо
Вилена Снегирева
Здравствуйте, как можно решить задачу
Определите наименьшее натуральное число A, при котором выражение
( x & 25 1) or ((x & 34 = 2) -> (x & A = 0))
тождественно истинно (то есть принимает значение 1 при любом натуральном значении переменной x)?
Екатерина
Спасибо за простой и понятный разбор сложных заданий.
admin
Пожалуйста:)
Евгений
Здравствуйте, объясните пожалуйста на видео, задания с ДЕЛ. Я не могу его понять
Сергей
Здравствуйте. А будут ли напечатаны разборы 18.10-18.14?
Сергей
Господа! К наиболее проблематичной задаче из задания 18_14 у вас нет решения. А в прилагаемом видео решается другая задача.
Сергей
Прошу прощения. Оказывается там в одном видео рассматриваются два задания.
Спасибо за помощь.
Николай
Очень интересно. Задача не имеет никакого практического применения и не тренирует никаких навыков, кроме изучения как раз-таки этого метода.
Анастасия
Здравствуйте. Опубликованный ответ к заданию 15_14 не совпадает с ответом в решении к этому же номеру. Странно…
admin
Ответ -31
Наталья
Уточните пожалуйста, может я не совсем понимаю Задание 15_3. Там в 4 части указан интервал от 44 до 48 включительно. Не означает ли это, что в результате должны получиться числа 44, 45, 46, 47, 48, т. е. 5 чисел, а не 4. Или я не совсем понимаю решение? Заранее благодарна за ответ.
Олег
Почему в 15.14 ответ один, а видео другой