Для решения этой задачи нам потребуется сделать несколько логических умозаключений, поэтому "следите за руками".
- От нас хотят, чтобы мы нашли минимальное целое неотрицательное А, при котором выражение всегда истинно.
- Что из себя представляет выражение в целом? Что-то там импликация что-то там в скобках.
- Давайте вспомним таблицу истинности для импликации:
1 => 1 = 1
1 => 0 = 0
0 => 1 = 1
0 => 0 = 1 - Значит, возможно три варианта, когда это будет истинно. Рассматривать все эти три варианта — это убиться и не жить. Давайте подумаем, можем ли мы пойти "от противного ".
- Давайте вместо того, чтобы искать А, попробуем найти x, при котором это выражение ложно.
- То есть, возьмём некоторое число А (пока не знаем какое, просто какое-то). Если вдруг мы найдём такое x, при котором всё высказывание ложно, значит, выбранное А — плохое (потому что в условии требуется, чтобы всегда выражение было истинным)!
- Таким образом мы сможем получить какие-то ограничение на число А.
- Итак, давайте пойдём от противного и вспомним, когда импликация бывает ложной? Когда первая часть истинна, а вторая — ложна.
- Значит
\((\mathrm{x}\&25\neq 0)= 1 \\ (\mathrm{x}\&17=0\Rightarrow \mathrm{x}\&\mathrm{A}\neq 0) = 0\) - Что означает, что \((x\&25\neq 0) = 1\) ? Это означает, что действительно \(\mathrm{x}\&25\neq 0\) .
- Давайте переведём 25 в двоичную. Получим: 11001 2 .
- Какие ограничения это накладывает на x? Раз не равно нулю, значит, при поразрядной конъюнкции должна где-то получиться единица. Но где она может быть? Только там, где в 25 уже есть единица!
- Значит, в числе x хотя бы в одном кресте должна быть единица: XX**X.
- Отлично, теперь рассмотрим второй множитель: \((\mathrm{x}\&17=0\Rightarrow \mathrm{x}\&\mathrm{A}\neq 0) = 0\)
- Это выражение из себя также представляет импликацию. При этом оно так же ложно.
- Значит, его первая часть обязана быть истинной, а вторая — ложной.
- Значит
\((\mathrm{x}\&17=0) = 1 \\ ((\mathrm{x}\&\mathrm{A}\neq 0) = 0) = 0\) - Что означает, что \(\mathrm{x}\&17=0\) ? То, что на всех местах, где в 17 стоят единицы, в x должны стоять нули (иначе в результате не получится 0).
- Переведём 17 в двоичную: 10001 2 . Значит, в x на последнем с конца и на 5 с конца месте должны стоять нули.
- Но стоп, мы же в пункте 13 получили, что на последнем ИЛИ на 4 с конца ИЛИ на 5 с конца должна быть единица.
- Раз согласно строке 19 на последнем или 5 с конца местах единицы быть не может, значит, она обязана быть на 4 с конца месте.
- То есть, если мы хотим, что при нашем x всё выражение было ложным, на 4 с конца месте обязана стоять единица: XX...XX1XXX 2 .
- Отлично, рассмотрим теперь последнее условие: \((\mathrm{x}\&\mathrm{A}\neq 0) = 0\) . Что это означает?
- Это означает, что неверно, что \(\mathrm{x}\&\mathrm{A}\neq 0\) .
- То есть, на самом деле, \(\mathrm{x}\&\mathrm{A}=0\) .
- Что мы знаем про x? Что на 4 с конца месте там единица. Во всём остальном x может быть практически любым.
- Если мы хотим, чтобы исходное выражение в условии задачи было всегда истинным, то мы не должны найти х, который бы удовлетворял всем условиям. Ведь, действительно, если бы мы нашли такой x, получилось бы, что исходное выражение не всегда истинно, что противоречит условию задачи.
- Значит, вот это самое последнее условие просто обязано не выполняться.
- А как оно может не выполняться? Если только мы будем уверены на 100%, что при поразрядной конъюнкции где-то останется единица.
- И это возможно: если в А тоже на 4 месте с конца будет единица, то в результате поразрядной конъюнкции на 4 с конца месте останется единица.
- Какое минимально возможное двоичное число имеет единицу на 4 с конца месте? Очевидно, что 1000 2 . Значит, это число и будет ответом.
- Осталось только перевести его в десятичную: \(1000_2=0\times 2^0 + 0\times 2^1 + 0\times 2^2 + 1\times 2^3=8\)
Ответ: минимально возможное A, удовлетворяющее условиям, равно 8 .
Евгений Смирнов
Эксперт в IT, учитель информатики
Решение №2
Можно предложить несколько более короткий подход. Обозначим наше высказывание как F = (A->(B->C)), где А - это высказывание "Х&25 не равно 0", В= "Х&17=0" и C="X&A не равно 0".
Раскроем импликации, пользуясь известным законом X->Y = не(Х) ИЛИ Y, получим F = A -> (не(В) ИЛИ C) = не(А) ИЛИ не(B) ИЛИ С. Распишем также двоичные значения констант 25 и 17:
Наше выражение - логическое ИЛИ от трёх высказываний:
1) не(А) - это значит, X&25 = 0 (биты 0,3,4 числа Х все равны 0)
2) не(B) - значит, X&17 не равно 0 (биты 0 и 4 числа Х хотя бы один равен 1)
3) C - знаит, X&A не равно 0 (биты, задаваемые маской A, хотя бы 1 равен 1)
Х - произвольное число. Все его биты независимы. Поэтому требовать выполнения какого-то условия на биты произвольного числа можно только в одном единственном случае - когда речь идёт об одной и той же маске (наборе битов). Мы можем заметить, что двоичная маска 17 - почти то же самое, что и 25, только не хватает бита номер 3. Вот если бы дополнить 17 битом номер 3, то выражение (не(В) ИЛИ С) превратилось бы в не(неА), т.е. в А = (X&25 не равно 0). По-другому: допустим, А=8 (бит 3=1). Тогда требование (не(В) B или С) равносильно требованию: (Хотя бы один из битов 4,0 равен 1) ИЛИ (бит 3 равен 1) = (хотя бы один из битов 0,3,4 не равен 1) - т.е. инверсия не(А) = А = (Х&25 не равно 0).
В итоге мы заметили, что если А=8, то наше выражение принимает вид F = не(А) ИЛИ А, что, по закону исключённого третьего, всегда тождественно истинно. При других, меньших, значениях А независимость от значения Х получить не удаётся, т.к. маски выходят разные. Ну, а при наличии в старших битах А единиц в битах выше 4 ничего не меняется, т.к. в остальных масках у нас нули. Получается, что только при А=8 формула превращается в тавтологию для произвольного Х.
Дмитрий Лисин
Разбор 18 задания ЕГЭ 2017 года по информатике из проекта демоверсии. Это задание повышенного уровня сложности. Примерное время выполнения задания 3 минуты.
Проверяемые элементы содержания:
— знание основных понятий и законов математической логики.
Задание 18
Обозначим через m&n поразрядную конъюнкцию неотрицательных целых чисел m и n . Так, например, 14&5 = 1110 2 &0101 2 = 0100 2 = 4.
Для какого наименьшего неотрицательного целого числа А формула
x &51 = 0 ∨ (x &41 = 0 → x &А ≠ 0)
тождественно истинна (т.е. принимает значение 1 при любом неотрицательном целом значении переменной х )?
Ответ: ________
Разбор 18 задания ЕГЭ 2017
1) Для начала упростим нашу формулу x&51 = 0 ∨ (x&41 = 0 → x&А ≠ 0) , заменив импликацию простыми логическими операциями используя формулу: A→B = ¬A + B
x&51 = 0 ∨ x&41 ≠ 0 ∨ x&А ≠ 0
2) Рассмотрим первое выражение (x&51 = 0)
и узнаем для каких чисел X
это выражение будет истинно
:
Переведём число 51 в двоичную систему счисления
51 10 = 110011 2
3) Определяем те значения X
x&51 = 0
:
51 10 110011
Х 111111
=0 11
0011
Если в числе Х
на месте 1-го, 2-го, 5-го и 6-го разряда окажутся единицы, то после поразрядной конъюнкции на этих местах также будут стоять единицы, т.е. мы не получим «0» и выражение (x&51 = 0)
будет ЛОЖНО
.
Все остальные цифры в числе X
могут быть любыми, так как после поразрядной конъюнкции на этих местах все равно будет «0».
Значит первое слагаемое учитывает все числа х, в которых нет на 1-м, 2-м, 5-м и 6-м местах единиц.
4) Рассмотрим второе выражение (x&41 ≠ 0)
: только для тех чисел Х
, у которых на 1-м, 2-м, 5-м и 6-м местах стоят единицы.
Переведём число 41 в двоичную систему счисления
41 10 = 101001 2
5) Определяем те значения X
, при которых истинно выражение x&41 ≠ 0
:
41 10 101001
Х 11 11
≠0 10
0
1
Если в числе Х
на месте 2-го и 5-го разряда стоят единицы, то после поразрядной конъюнкции на этих местах будут стоять нули, т.е. мы не получим «1» и выражение (x&41 ≠ 0) будет ложно
.
Единицы на 1-м и 6-м месте в числе Х
после поразрядной конъюнкции дадут «1» и выражение (x&41 ≠ 0)
будет истинно
.
Значит второе слагаемое учитывает числа Х
, в которых на 1-м и 6-м местах стоят «1» и не учитывает числа Х
, в которых на 2-м и 5-м местах стоят «1».
6) Рассмотрим третье выражение (x&A≠0)
:
У нас остались неучтенными лишь те числа Х
, у которых на 5-м и 2-м месте стоят «1», следовательно, их нужно учесть в числе А
.
Минимально возможное такое число это 10010 2 = 18 10
Каталог заданий.
Множества
Пройти тестирование по этим заданиям
Вернуться к каталогу заданий
Версия для печати и копирования в MS Word
Элементами множеств А, 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.
Решение.
Введем обозначения:
(x ∈ P) ≡ P; (x ∈ Q) ≡ Q; (x ∈ A) ≡ A; ∧ ≡ · ; ∨ ≡ +.
Тогда, применив преобразование импликации, получаем:
(¬A + P) · (¬Q + ¬A) ⇔ ¬A · ¬Q + ¬Q · P + ¬A + ¬A · P ⇔
⇔ ¬A · (¬Q + P + 1) + ¬Q · P ⇔ ¬A + ¬Q · P.
Требуется чтобы ¬A + ¬Q · P = 1. Выражение ¬Q · P истинно когда x ∈ {2, 4, 8, 10, 14, 16, 20}. Тогда ¬A должно быть истинным когда x ∈ {1, 3, 5, 6, 7, 9, 11, 12, 13, 15, 17, 18, 19, 21, 22, 23,...}.
Следовательно, максимальное количество элементов в множестве A будет, если A включает в себя все элементы множества ¬Q · P, таких элементов семь.
Ответ: 7.
Ответ: 7
Элементами множества А являются натуральные числа. Известно, что выражение
(x ∈ {2, 4, 6, 8, 10, 12}) → (((x ∈ {3, 6, 9, 12, 15}) ∧ ¬(x ∈ A)) → ¬(x ∈ {2, 4, 6, 8, 10, 12}))
истинно (т. е. принимает значение 1) при любом значении переменной х. Определите наименьшее возможное значение суммы элементов множества A.
Решение.
Введем обозначения:
(x ∈ {2, 4, 6, 8, 10, 12}) ≡ P; (x ∈ {3, 6, 9, 12, 15}) ≡ Q; (x ∈ A) ≡ A.
Преобразовав, получаем:
P → ((Q ∧ ¬A) → ¬P) = P → (¬(Q ∧ ¬А) ∨ ¬P) = ¬P ∨ (¬(Q ∧ ¬А) ∨ ¬P) = ¬P ∨ ¬Q ∨ А.
Логическое ИЛИ истинно, если истинно хотя бы одно утверждение. Выражение ¬P ∨ ¬Q истинно при всех значениях x, кроме значений 6 и 12. Следовательно, множество А должно содержать точки 6 и 12. То есть минимальный набор точек в множестве А ≡ {6, 12}. Сумма элементов множества А равна 18.
Ответ: 18.
Ответ: 18
Из-вест-но, что вы-ра-же-ние
((x ∈ P) → (x ∈ A)) ∨ (¬(x ∈ A) → ¬(x ∈ Q))
ис-тин-но (т. е. при-ни-ма-ет зна-че-ние 1) при любом зна-че-нии пе-ре-мен-ной х. Опре-де-ли-те наи-мень-шее воз-мож-ное зна-че-ние суммы эле-мен-тов мно-же-ства A.
Решение.
Раскроем две импликации. Получим:
(¬(x ∈ P) ∨ (x ∈ A)) ∨ ((x ∈ A) ∨ ¬(x ∈ Q))
Упростим:
(¬(x ∈ P) ∨ (x ∈ A) ∨ ¬(x ∈ Q))
¬(x ∈ P) ∨ ¬(x ∈ Q) дают 0 только, когда число лежит в обоих множествах. Значит, чтобы все выражение было истинно нам нужно все числа лежащие в P и Q занести в А. Такие числа 6, 12, 18. Их сумма 36.
Ответ: 36.
Ответ: 36
Источник: Тренировочная работа по ИНФОРМАТИКЕ 11 класс 18 января 2017 года Вариант ИН10304
Эле-мен-та-ми мно-жеств А, 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.
Ре-ше-ние.
Пре-об-ра-зу-ем дан-ное вы-ра-же-ние:
((x A) → (x P)) ∨ ((x Q) → (x A))
((x A) ∨ (x P)) ∨ ((x Q) ∨ (x A))