Задание №18 ЕГЭ по информатике

Мнемоническое правило

Соционика – это информационная психология

Один из ее главных принципов – дополнение до целого (дополнение противоположностью)

А  ¬А = 1

Решающая формула

В алгебре логики есть формула

дополнения до целого:

В некоторых задачах мы будем использовать вместо этой формулы умножение противоположностей:

А  ¬А = 0

Типы задания 18

• Задания на отрезки
• Задания на множества
• Задания на поразрядную конъюнкцию
• Задания на условие делимости

Задания на отрезки

(№ 376) На числовой прямой даны два отрезка: P=[4,15] и Q=[12,20]. Укажите наименьшую возможную длину такого отрезка A, что формула

((x  P)  (x  Q)) → (x  A)

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

Источник - сайт Полякова К.Ю.

Решающая формула

А  ¬А = 1

Для выбора решающей формулы важно внимательно прочитать требование задачи. В нашей задаче в требовании сказано: принимает значение 1 при любом значении переменной х.

Выбор решающей формулы очевиден:

Решение задачи на отрезки

Разделим решение задачи на этапы:

• Легенда
• Формализация условия
• Решение логического уравнения
• Интерпретация полученного результата

Решение задачи на отрезки

1) Легенда – это удобные нам условные обозначения, которые мы будем использовать при решении.

Введем следующие обозначения:

P = x  P

Q = x  Q A = x  A

Решение задачи на отрезки

2) Формализация условия – перепишем формулу из условия задачи в соответствие с легендой.

Было:

((x  P)  (x  Q)) → (x  A) = 1

Стало:

(P  Q) → A = 1

Решение задачи на отрезки

3) Решение логического уравнения – вначале это, возможно, самый сложный этап в решении задачи. Но позже, при накоплении опыта, он уже не будет казаться таким уж сложным ☺

Рассмотрим решение логического уравнения по шагам.

Решение задачи на отрезки

3.1. Представим логическое следование в базовых логических операциях по формуле: А → В = ¬А  В:

(P  Q) → A = 1

¬(P  Q)  A = 1

Решение задачи на отрезки

3.2. Сведем получившееся выражение к решающей формуле: А  ¬А = 1 (в алгебре логики справедлив закон коммутативности, т.е. А  ¬А = ¬А  А) :

¬(P  Q)  A = 1, отсюда

¬А = ¬(P  Q)

Ответом в логическом уравнении будет:

А = P  Q.

Решение задачи на отрезки

4) Интерпретация полученного результата.

Наш ответ: А = P  Q.

В алгебре логики это выражение означает пересечение объемов двух логических объектов. По условию нашей задачи – это пересечение отрезков P и Q.

Решение задачи на отрезки

Пересечение отрезков P и Q можно визуализировать: P=[4,15] и Q=[12,20].

4 12 15 20

По условию нашей задачи, нам нужна минимальная длина отрезка А. Находим ее: 15 – 12 = 3.

Ответ: 3.

Ответ на сайте Полякова К.Ю.: 3

Задания на отрезки

(№ 360) На числовой прямой даны три отрезка: P=[10,25], Q=[15,30] и

R=[25,40]. Какова максимальная длина отрезка A, при котором формула

((x  Q) → (x  R) )  (x  A)  (x  P)

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

Источник - сайт Полякова К.Ю.

Решающая формула

А  ¬А = 0

Для выбора решающей формулы важно внимательно прочитать требование задачи. В нашей задаче в требовании сказано: принимает значение 0 при любом значении переменной х.

Выбор решающей формулы очевиден:

Решение задачи на отрезки

• Легенда
• Формализация условия
• Решение логического уравнения
• Интерпретация полученного результата

Решение задачи на отрезки

1) Легенда

R = x  R Q = x  Q A = x  A P = x  P

Решение задачи на отрезки

2) Формализация условия

Было:

((x  Q) → (x  R) )  (x  A)  (x  P) = 0

Стало:

( Q → ¬R )  A  ¬ P = 0

Решение задачи на отрезки

3) Решение логического уравнения

( Q → ¬R )  A  ¬ P = 0

3.1. Представим логическое следование в базовых логических операциях по формуле: А → В = ¬А  В, и переставим множители согласно закону коммутативности умножения:

A  (¬ Q  ¬R )  ¬ P = 0

Решение задачи на отрезки

3) Решение логического уравнения

A  (¬ Q  ¬R )  ¬ P = 0

3.2. Сведем получившееся выражение к решающей формуле: А  ¬А = 0 и найдем, чему равно ¬А :

¬А = (¬ Q  ¬R )  ¬ P

Решение задачи на отрезки

3) Решение логического уравнения

¬А = (¬ Q  ¬R )  ¬ P

3.3. Упростим выражение для ¬А по закону де Моргана ¬А¬В=¬(АВ):

¬А = ¬ (Q  R )  ¬ P,

и по другому закону де Моргана

¬А¬В=¬(АВ):

¬А = ¬ (Q  R  P)

Решение задачи на отрезки

3) Решение логического уравнения

¬А = ¬ (Q  R  P)

3.4. Очевидно, что

А = Q  R  P

Решение задачи на отрезки

4) Интерпретация полученного результата

А = Q  R  P

Отрезок А – это пересечение отрезков Q и R и его объединение с отрезком Р.

Решение задачи на отрезки

Пересечение отрезков R и Q можно визуализировать: Q=[15,30] и R=[25,40].

15 25 30 40

Отрезок P=[10,25] нанесем на наш чертеж и объединим с пересечением:

25 30

40

10 15

Решение задачи на отрезки

А = Q  R  P

10 15 25 30 40

По условию нашей задачи, нам нужна

максимальная длина отрезка А. Находим ее: 30 – 10 = 20.

Ответ: 20.

Ответ на сайте Полякова К.Ю.: 20

2. Задания на множества

(№ 386) Элементами множеств А, P, Q являются натуральные числа, причём P={1,2,3,4,5,6}, Q={3,5,15}. Известно,

что выражение

(x  A) → ((x  P)  (x  Q))  (x  Q)

истинно (т.е. принимает значение 1 при любом значении переменной х.

Определите наименьшее возможное количество элементов в множестве A.

Источник - сайт Полякова К.Ю.

Решение задачи на множества

• Легенда
• Формализация условия
• Решение логического уравнения
• Интерпретация полученного результата

Решение задачи на множества

1) Легенда

A = x  A P = x  P Q = x  Q

Решение задачи на множества

2) Формализация условия

Было:

(x  A) → ((x  P)  (x  Q))  (x  Q) = 1

Стало:

¬ A → (¬P  Q)  ¬ Q = 1

Решение задачи на множества

• Решение логического уравнения

¬ A → (¬P  Q)  ¬ Q = 1

• Представим логическое следование в базовых логических операциях и сгруппируем:

A  ((¬P  Q)  ¬ Q) = 1

Решение задачи на множества

A  ((¬P  Q)  ¬Q) = 1

3.2. Сведем получившееся выражение к решающей формуле:

А  ¬А = 1

и найдем, чему равно ¬А :

¬А = (¬P  Q)  ¬Q

Решение задачи на множества

¬А = (¬P  Q)  ¬Q

3.3. Упростим выражение для ¬А, раскрыв скобки по закону дистрибутивности сложения:

¬А = (¬P  ¬Q)  (Q  ¬Q)

Q  ¬Q = 1

¬А = (¬P  ¬Q)

Решение задачи на множества

¬А = (¬P  ¬Q)

По закону де Моргана:

¬А = ¬(P  Q)

3.4. Очевидно, что

А = P  Q

Решение задачи на множества

А = P  Q

4) Интерпретация полученного результата

Искомое множество А представляет собой пересечение множеств P и Q.

Решение задачи на множества

Искомое множество А есть пересечение множеств

P = 1, 2, 3, 4, 5, 6 и Q ={3, 5,15},

таким образом A ={3, 5}

и содержит только 2 элемента. Ответ: 2

Ответ на сайте Полякова: 2

2. Задания на множества

(№ 368) Элементами множеств А, P, Q являются натуральные числа, причём P={2,4,6,8,10,12} и Q={4,8,12,116}.

Известно, что выражение

(x  P) → (((x  Q)  (x  A)) → (x  P))

истинно (т. е. принимает значение 1) при любом значении переменной х.

Определите наименьшее возможное значение суммы элементов множества A.

Источник - сайт Полякова К.Ю.

Решение задачи на множества

• Легенда
• Формализация условия
• Решение логического уравнения
• Интерпретация полученного результата

Решение задачи на множества

1) Легенда

A = x  A P = x  P Q = x  Q

Решение задачи на множества

2) Формализация условия

Было:

(x  P)→(((x  Q)  (x  A))→(x  P)) = 1

Стало:

P → ((Q  ¬A) → ¬P) = 1

Решение задачи на множества

• Решение логического уравнения

P → ((Q  ¬A) → ¬P) = 1

• Представим первое логическое следование (в скобках) в базовых логических операциях :

P → (¬(Q  ¬A)  ¬P) = 1

Решение задачи на множества

P → (¬(Q  ¬A)  ¬P) = 1

Представим второе логическое следование в базовых логических операциях, применим закон де Моргана и перегруппируем:

¬P (¬(Q  ¬A)  ¬P) = 1

¬P ¬Q  A  ¬P = 1

Решение задачи на множества

A  (¬P ¬Q  ¬P) = 1

3.2. Сведем получившееся выражение к решающей формуле:

А  ¬А = 1

и найдем, чему равно ¬А :

¬А = (¬P ¬Q  ¬P)

Решение задачи на множества

¬А = ¬P ¬Q  ¬P

3.3. Упростим выражение для ¬А

по формуле А  А = А:

¬А = ¬P ¬Q

Далее, по закону де Моргана получаем:

¬А = ¬(P Q)

Решение задачи на множества

¬А = ¬(P Q)

3.4. Очевидно, что

А = P Q

4) Интерпретация полученного результата

Искомое множество А представляет собой пересечение множеств P и Q.

Решение задачи на множества

Искомое множество А есть пересечение множеств

P = 2, 4, 6, 8, 10, 12 и

Q ={4, 8, 12, 16}, таким образом

A ={4, 8, 12}

и содержит только 3 элемента, сумма которых 4+8+12=24 .

Ответ: 24

Ответ на сайте Полякова: 24

3. Задания на поразрядную конъюнкцию

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

14 & 5 = 11102 & 01012 = 01002 = 4. Для

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

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

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

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

• Легенда
• Формализация условия
• Решение логического уравнения
• Интерпретация полученного результата

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

1. Легенда

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

B = (x & 29 ≠ 0) C = (x & 12 ≠ 0) A = (x & А ≠ 0)

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

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

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

2) Формализация условия Было:

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

Стало:

В → (¬С → А) = 1

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

3) Решение логического уравнения

В → (¬С → А) = 1

В → (С А) = 1 (¬В  С) А = 1

¬А = ¬В  С

¬А = ¬(В ¬ С)

Очевидно, что

А = В ¬ С

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

4) Интерпретация полученного результата

Искомое двоичное значение поразрядной конъюнкции А – это двоичное значение поразрядной конъюнкции значения В и инверсии двоичного значения С.

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

B = (x & 29 ≠ 0)

В или 29 = 111012

C = (x & 12 ≠ 0) 12 = 11002

¬С или инверсия 12 = 00112

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

В или 29 = 111012

¬С или инверсия 12 = 00112

А = В ¬ С

х111012

0011

2

100012

А = 10001 = 17

Ответ на

сайте Полякова: 17

3. Задания на поразрядную конъюнкцию

(№ 375) Введём выражение M & K, обозначающее поразрядную конъюнкцию M и K (логическое «И» между соответ- ствующими битами двоичной записи).

Определите наименьшее натуральное число A, такое что выражение

(X & 49 ≠ 0) → ((X & 33 = 0) → (X & A ≠ 0))

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

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

• Легенда
• Формализация условия
• Решение логического уравнения
• Интерпретация полученного результата

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

1) Легенда

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

B = (x & 49 ≠ 0) C = (x & 33 ≠ 0) A = (x & А ≠ 0)

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

2) Формализация условия

Было:

(X & 49 ≠ 0) → ((X & 33 = 0) → (X & A ≠ 0))=1

Стало:

В → (¬С → А) = 1

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

3) Решение логического уравнения

В → (¬С → А) = 1

В → (С  А) = 1 (¬В  С)  А = 1

¬А = (¬В  С)

Очевидно:

А = В ¬С

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

4) Интерпретация полученного результата

Искомое двоичное значение поразрядной конъюнкции А – это двоичное значение поразрядной конъюнкции значения В и инверсии двоичного значения С.

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

B = (x & 49 ≠ 0)

В или 49 = 1100012

C = (x & 33 ≠ 0) 33 = 1000012

¬С или инверсия 33 = 0111102

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

В или 49 = 1100012

¬С или инверсия 33 = 0111102

А = В ¬ С

х1100012

0111102 0100002

А = 10000 = 16

Ответ на

сайте Полякова: 16

4. Задания на условие делимости

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

¬ДЕЛ(x,А) → (¬ДЕЛ(x,21)  ¬ДЕЛ(x,35))

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

Источник - сайт Полякова К.Ю.

Решение задачи на условие делимости

• Легенда
• Формализация условия
• Решение логического уравнения
• Интерпретация полученного результата

Решение задачи на условие делимости

1) Легенда

Легенда простая:

А = ДЕЛ(x,А) 21 = ДЕЛ(х,21)

35 = ДЕЛ(x,35)

Решение задачи на условие делимости

2) Формализация условия

Было:

¬ДЕЛ(x,А) → (¬ДЕЛ(x,21)  ¬ДЕЛ(x,35))

тождественно истинна (то есть принимает значение 1)

Стало:

¬А → (¬21  ¬35) = 1

Решение задачи на условие делимости

3) Решение логического уравнения

¬А → (¬21  ¬35) = 1

А (¬21  ¬35) = 1

¬А = ¬21  ¬35 Очевидно, что А = 21  35

Решение задачи на условие делимости

4) Интерпретация полученного результата

А = 21  35

В данной задаче это самый сложный этап решения. Нужно понять, что же представляет из себя число А – НОК или НОД или …

Решение задачи на условие делимости

4) Интерпретация полученного результата

А = 21  35

Итак, наше число А таково, что Х делится на него без остатка, тогда и только тогда, когда Х делится без остатка на 21 или на 35. В этом случае ищем

А = НОД (21, 35) = 7

Ответ на сайте Полякова: 7

4. Задания на условие делимости

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

¬ДЕЛ(x,А) → ((ДЕЛ(x,6) → ¬ДЕЛ(x,4))

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

Источник - сайт Полякова К.Ю.

Решение задачи на условие делимости

• Легенда
• Формализация условия
• Решение логического уравнения
• Интерпретация полученного результата

Решение задачи на условие делимости

1) Легенда

А = ДЕЛ(x,А) 6 = ДЕЛ(x,6)

4 = ДЕЛ(x,4)

Решение задачи на условие делимости

2) Формализация условия

Было:

¬ДЕЛ(x,А) → ((ДЕЛ(x,6) → ¬ДЕЛ(x,4))

тождественно истинна (то есть принимает

значение 1

Стало:

¬А → (6 → ¬4) = 1

Решение задачи на условие делимости

3) Решение логического уравнения

¬А → (6 → ¬4) = 1

¬А → (¬ 6  ¬4) = 1

А  (¬ 6  ¬4) = 1

¬А = ¬ 6  ¬4

Очевидно:

А = 64

Решение задачи на условие делимости

4) Интерпретация полученного результата

А = 64

Итак, А таково, что Х делится на него без остатка тогда и только тогда, когда Х делится без остатка и на 6, и на 4. Т.е. А = НОК(6, 4) = 12

Ответ на сайте Полякова: 12