18. Преобразование логических выражений
Обозначим через 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.
51 + ¬41 + ¬A = 1
Так как ¬A, то для А берем множество, которое входит в 51, но не входит в 41.
51 и 41 представим в виде суммы степеней 2.
51 = 32 + 16 + 2 + 1
41 = 32 + 8 + 1
A=16 + 2 = 18
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 |
Ответ: 18
Демонстрационный вариант Единый государственный экзамен ЕГЭ 2016 г. – задание №18
Обозначим через m&n поразрядную конъюнкцию неотрицательных целых чисел m и n. Так, например, 14&5 = 11102&01012 = 01002 = 4.
Для какого наименьшего неотрицательного целого числа А формула
Решение:
1-й способ:
Упростим выражение x&25 = 0 \/ (x&17 = 0 → x&А ≠ 0) :
x&25 = 0 ∨ x&17 ≠ 0 ∨ x&А ≠ 0.
25 + ¬17 + ¬A = 1
Так как ¬A, то для А берем множество, которое входит в 25, но не входит в 17.
25 и 17 представим в виде суммы степеней 2.
25 = 16 + 8 + 1
17 = 16 + 1
A=8
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 |
Ответ: 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)
A + ¬56 + ¬20 = 1
Наибольшее, это объединение 56 и 20.
56 = 32 + 16 + 8
20 = 16 + + 4
А = 32 + 16 + 8 + 4
А = 60
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 |
A=0 + 56=0 + 20=0
| 56 | 111000 | 20 | 10100 | |
| 000xxx | 0x0xx |
000xxx
0x0xx
0000xx
A=0 => x=0
наибольшее натуральное число 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))
A + ¬P + ¬Q
50-30 = 20
Ответ: 20
Демонстрационный вариант Единый государственный экзамен ЕГЭ 2015 г. (досрочный период) – задание №18
Обозначим через ДЕЛ(n, m) утверждение «натуральное число n делится без остатка на натуральное число m».
Для какого наибольшего натурального числа А формула
¬ДЕЛ(x, А) → (ДЕЛ(x, 6) → ¬ДЕЛ(x, 4))
тождественно истинна (то есть принимает значение 1 при любом натуральном значении переменной х)?
Решение:
Упростим выражение ¬ДЕЛ(x, А) → (ДЕЛ(x, 6) → ¬ДЕЛ(x, 4))
A + ¬6 + ¬4 = 1
| A | ¬6 | ¬4 |
| 1 | 0 | 0 |
A + 6 + 4
X делится на 6 и 4. Это 12, 24, 36 ..
X делится на A.
Делители 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))
¬18 + A + ¬12 = 1
| A | ¬18 | ¬12 |
| 1 | 0 | 0 |
A + 18 + 12
X делится на 18 и 12. Это 36, 72, 108 ..
X делится на A.
Делители X=36 => 1,2,3,4,… 36
Для какого наибольшего натурального числа А = 36
Ответ: 36
Сколько существует целых значений числа A, при которых формула
((x < 5) → (x2 < A)) /\ ((y2 ≤ A) → (y ≤ 5))
тождественно истинна при любых целых неотрицательных x и y?
Ответ:
Источник: СтатГрад 2017−2018
Решение:
( x ≥ 5 + x2 < A ) . (y2 > A + y ≤ 5)
Если x ≥ 5 = 0, тогда x2 < A = 1
x ≥ 5 = 0, когда x=4; x2 < A = 1 => 42 < A => 16<A
Если y ≤ 5 = 0, тогда y2 > A= 1
y ≤ 5 = 0, когда y=6; y2 > A = 1 => 62 > A => 36 > A
16<A<36
Ответ: 19