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

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

Разбор 18 задания ЕГЭ 2016 года по информатике из демоверсии. Это задание на знание основных понятий и законов математической логики (уметь вычислять логическое значение сложного высказывания по известным значениям элементарных высказываний). Это задание повышенного уровня сложности. Примерное время выполнения задания 3 минуты.

Задание 18:

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

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

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

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

Ответ: ________

Разбор 18 задания ЕГЭ 2016:

Преобразуем исходное выражение

x&25 ≠ 0 → (x&17 = 0 → x&А ≠ 0)
¬(x&25 ≠ 0) ∨ (¬(x&17 = 0) ∨ x&А ≠ 0)

x&25 = 0 ∨ x&17 ≠ 0 ∨ x&А ≠ 0

Переведем числа из выражения в двоичную систему счисления

2510 = 110012
1710 = 100012

Определяем те значения Х, при которых истинно выражение x&25 = 0

2510 11001
  Х    00??0
  0    00000

Х — 00??0

Определяем те значения Х, при которых истинно выражение x&17 ≠ 0

1710 10001
  Х    ?????
  0    ?000?

Х — 1????, ????1, 1???1

Следовательно

Х — 01??0

Определим наименьшее А, при котором истинно выражение x&А ≠ 0
Х — 01??0

А10 ?????
 Х   01??0
≠ 0  0???0

Очевидно, что А ≠ 0

Пусть А = 12

А10 ????1
 Х   01??0
≠ 0  00000

не подходит, так как не выполняется условие А ≠ 0

Пусть А = 10002

А10 01000
 Х   01??0
≠ 0  01000

подходит, 10002 = 810

Ответ: 8

infedu.ru

Разбор 18 задания ЕГЭ 2018 по информатике: задание 2

Продолжаю разбор с решением задач задания №18 ЕГЕ по информатике:

Задача №1

Обозначим через m & n по­раз­ряд­ную конъ­юнк­цию не­от­ри­ца­тель­ных целых чисел m и n. Так, например, 14 & 5 = 11102 & 01012 = 01002 = 4. Для ка­ко­го наи­мень­ше­го не­от­ри­ца­тель­но­го це­ло­го числа А фор­му­ла

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

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

х)?

 

Решение:

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

Согласно закона сокращения A → B = ¬ A ∨ B — упрощаем выражение:

x & 29 = 0 ∨ (x & 12 ≠ 0 ∨  x & А ≠ 0)

Переводим числа в степень двойки:

2910 = 16 + 8 + 4 + 1   получаем: X ∈ [16, 8, 4, 1]  = 111012

1210 = 8 + 4  получаем X ∉ [8, 4] = 11002

т.к. выражение должно притять истиное выражение, берем диапазон X ∈ [16, 8, 4, 1] т.к. [ 8, 4 ] ∉ X из этого у нас остается только  [16, 1]  складывам 16+1 = 17

Получаем наименьшее возможное число А

Ответ: 17

 


 

Задача №2

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

Так, например, 14&5 = 1110

2&01012 = 01002 = 4.

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

((x & 28 ≠ 0) ∨ (x & 45 ≠ 0)) → ((x & 17 = 0) → (x & A  ≠ 0))

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

Решение:

((x & 28 ≠ 0) ∨ (x & 45 ≠ 0)) → ((x & 17 = 0) → (x & A  ≠ 0))

Согласно закона сокращения A → B = ¬ A ∨ B — упрощаем выражение:

((x & 28 = 0) ∨ (x & 45 = 0)) ∨ ((x & 17 ≠ 0) → (x & A  ≠ 0))

Переводим числа в степень двойки:

2810 = 16 + 8 + 4   получаем: X ∈ [16, 8, 4]  = 111002

4510 = 32 + 8 + 4 + 1  получаем X ∈  [32, 8, 4, 1] = 1

011012

1710 = 16 + 1  получаем X ∉ [16, 1] = 100012

т.к. выражение должно притять истиное выражение, берем диапазоны X ∈ [16, 8, 4]  и [32, 8, 4, 1] т.к. [ 16, 1 ] ∉ X из этого у нас остается только  [32, 8, 4]  складывам 32 + 8 + 4 = 44

Получаем наименьшее возможное число А

Ответ: 44

 

Редактировалось Дата:

www.fordus.org.ua

поразрядную конъюнкцию неотрицательных целых чисел

Обозначим через 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

Ответ: 18


Демонстрационный вариант Единый государственный экзамен ЕГЭ 2016 г. – задание №18

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

2&01012 = 01002 = 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.

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

Ответ: 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

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

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

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



vuz-24.ru

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

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

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

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

Задание 18

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

5110 = 1100112

3) Определяем те значения X, при которых истинно выражение x&51 = 0:
5110 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 в двоичную систему счисления

4110 = 1010012

5) Определяем те значения X, при которых истинно выражение x&41 ≠ 0:
4110 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», следовательно, их нужно учесть в числе А.
Минимально возможное такое число это 100102 = 1810

Ответ: 18

infedu.ru

Author: alexxlab

Добавить комментарий

Ваш адрес email не будет опубликован.