Для какого наименьшего неотрицательного целого числа а формула

Разбор 18 задания ЕГЭ 2017 по информатике из демоверсии

Разбор 18 задания ЕГЭ 2017 года по информатике из проекта демоверсии. Это задание повышенного уровня сложности. Примерное время выполнения задания 3 минуты.

Проверяемые элементы содержания:
— знание основных понятий и законов математической логики.

Элементы содержания, проверяемые на ЕГЭ:
— высказывания, логические операции, кванторы, истинность высказывания.

Задание 18

Обозначим через m&n поразрядную конъюнкцию неотрицательных целых чисел m и n. Так, например, 14&5 = 1110₂&0101₂ = 0100₂ = 4.

Для какого наименьшего неотрицательного целого числа А формула

тождественно истинна (т.е. принимает значение 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 в двоичную систему счисления

3) Определяем те значения X, при которых истинно выражение x&51 = 0:
51₁₀ 110011
Х 111111
=0 110011

Если в числе Х на месте 1-го, 2-го, 5-го и 6-го разряда окажутся единицы, то после поразрядной конъюнкции на этих местах также будут стоять единицы, т.е. мы не получим «0» и выражение (x&51 = 0) будет ЛОЖНО.
Все остальные цифры в числе X могут быть любыми, так как после поразрядной конъюнкции на этих местах все равно будет «0».
Значит первое слагаемое учитывает все числа х, в которых нет на 1-м, 2-м, 5-м и 6-м местах единиц.

4) Рассмотрим второе выражение (x&41 ≠ 0): только для тех чисел Х, у которых на 1-м, 2-м, 5-м и 6-м местах стоят единицы.
Переведём число 41 в двоичную систему счисления

5) Определяем те значения X, при которых истинно выражение x&41 ≠ 0:
41₁₀ 101001
Х 11 11
≠0 10 01

Если в числе Х на месте 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₂ = 18₁₀

Е15.7 фор­му­ла x&25 ≠ 0 → (x&17 = 0 → x&А ≠ 0) тож­де­ствен­но ис­тин­на

Обо­зна­чим через m&n по­раз­ряд­ную конъ­юнк­цию не­от­ри­ца­тель­ных целых чисел m и n. Так, на­при­мер, 14&5 = 1110₂&0101₂ = 0100₂ = 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.

Задание 18

Для решения этого задания необходимы знания алгебры логики. Вам сюда.

Первый тип задания — числовые отрезки.

Пример задания.

На числовой прямой даны два отрезка: P=[8,50] и Q=[27,76]. Определите наименьшую возможную длину отрезка А, при котором выражение

¬(x ϵ A) → ¬(¬(x ϵ P) → (x ϵ Q))

тождественно истинно, то есть принимает значение 1 при любом значении переменной х.

Первое, что необходимо сделать — преобразовать выражение — избавиться от импликации, а также заменить выражение (x ϵ A) на А, (x ϵ P) на Р, (x ϵ Q) на Q:

¬A→ ¬(¬ P → Q)=A v¬(¬ P → Q)=A v¬(P v Q)=A v ¬P & ¬ Q

Итак, мы получили более понятное выражение. Так как выражение должно быть истинным на протяжении всей числовой прямой, необходимо посмотреть какие участки не закрыты P и Q, и именно они должны быть закрыты отрезком А.

На рисунке 1 отображены отрезки Р и Q.

На рисунке 2 отображен результат выражения ¬P & ¬ Q. Обратите внимание, что точки "выколоты", так как в отрезки они входят, а под отрицанием получаем "все кроме" данного отрезка. Кроме того, так как в выражении конъюнкция нужная нам область — пересечение двух областей — показано штриховкой.

Анализируя рисунок заметно, что остался не закрыт отрезок [8,76], таким образом получаем, что А=[8,76] и наименьшая возможная длина отрезка А=76-8=68

Второй тип задания — функция делимость.

Пример задания.

Обозначим через ДЕЛ(n, m) утверждение "натуральное число n делится без остатка на натуральное число m". Для какого наибольшего натурального числа А формула

¬ДЕЛ(x, A) → (ДЕЛ(x, 4) → ¬ДЕЛ(x, 10))

истинна при любом натуральном значении x?

Также, как и в предыдущем задании сначала преобразуем выражение:

¬ДЕЛ(x, A) → (ДЕЛ(x, 4) → ¬ДЕЛ(x, 10))= ДЕЛ(x, A) v (ДЕЛ(x, 4) → ¬ДЕЛ(x, 10))=

ДЕЛ(x, A) v (¬ДЕЛ(x, 4) v ¬ДЕЛ(x, 10))=ДЕЛ(x, A) v ¬(ДЕЛ(x, 4) & ДЕЛ(x, 10))

Проанализируем выражение под отрицанием:

То есть число х должно одновременно делиться и на 4 и на 10, поэтому нам необходимо найти НОК 4 и 10. НОК (4,10)=20.

Получаем: (ДЕЛ(x, 4) & ДЕЛ(x, 10)) = (ДЕЛ(x, 20)

Полное выражение теперь примет вид:

ДЕЛ(x, A) v ¬ (ДЕЛ(x, 20)

Выражением ¬ (ДЕЛ(x, 20) выбраны все такие х, которые не делятся на 20, а чтобы выражение стало истинным при любом х, то нам необходимо захватить оставшиеся значения — которые делятся на 20, получаем, что А=20

Примечание. По сути задание сводится к тому, чтобы найти НОК двух чисел.

Третий тип задания — поразрядная конъюнкция.

Теория.

При поразрядной конъюнкции важно помнить, что выражение будет истинным, только в том случае, когда при умножении единицы получается там же, где и они стоят в первом числе:

Ложь, так как в последнем разряде получился ноль.

А вот это выражение будет истинным:

Пример задания

Обозначим через m & n поразрядную конъюнкцию неотрицательных целых чисел m и n. Так, например, 12&6 = 1100₂&0110₂ = 0100₂ = 4

Для какого наименьшего неотрицательного целого числа A формула

(X & A = 0) & ¬(X & 35 ≠ 0 → X & 52 ≠ 0)

тождественно ложна (то есть принимает значение 0 при любом неотрицательном значении переменной X)?

И снова преобразование:

(X & A = 0) & ¬(X & 35 ≠ 0 → X & 52 ≠ 0) =(X & A = 0) & ¬(X & 35 = 0 v X & 52 ≠ 0)=

(X & A = 0) & (X & 35 ≠ 0 & X & 52 = 0)

Чтобы найти А, сначала найдем все х, которые охвачены известными числами. Для этого переведем все числа в двоичную систему:

для того, чтобы X & 35 ≠ 0 было истинным, необходимо, чтобы там, где стоят в числе 35 единицы и в числе, а следовательно и нашей маске стояли единицы:

для того, чтобы X & 52 = 0 было истинным, необходимо, чтобы там, где стоят в числе 52 единицы и числе х, а следовательно и нашей маске стояли нули:

А теперь небольшая хитрость при наложении масок — там где мы видим в масках 1->x или наоборот, x->1 должны стоять единицы.

1 х х х 1 1

0 0 х 0 x x

Так как нам необходимо найти наименьшее неотрицательное целое число A, то в остальных разрядах поставим нули:

Внимание!

если X & A = 0, там, где мы видим 1->x или наоборот, x->1 должны стоять единицы

если X & A ≠ 0, там, где мы видим 0->x или наоборот, x->0 должны стоять нули

Как решить задачу на поразрядную конъюнкцию

Обозначим через m & n поразрядную конъюнкцию неотрицательных целых чисел m и n.

Так, например, 14 & 5 = 1110 & 0101 = 0100 = 4. Для какого наименьшего неотрицательного целого числа А формула

x & 29 ≠ 0 → (x & 17 = 0 → x & А ≠ 0)

тождественно истинна (т. е. принимает значение 1 при любом неотрицательном целом значении переменной x)?

Написал функцию этой самой конъюнкции и импликации, затем функцию перебора всех x до 100 при каком либо A, которая вернет False, если хоть одно значение x не прошло.

Функции конъюнкции и импликации вроде правильные, но при выполнении программы выдает все значения от 2 до 100. В ответе к задаче число 12. Где я ошибся, уже часа 2 бьюсь над задачей, но не могу понять??