Презентация ЕГЭ - 2019 "Множества и логика"

Информатика. ЕГЭ - 2019 Множества и логика Метод решения задачи В18. Множества делимости В18

• задания повышенного уровня сложности,
• время выполнения – примерно 5 минут
• 1 балл

Примеры заданий В18

На числовой прямой даны два отрезка: P = [37; 60] и Q = [40; 77]. Укажите наименьшую возможную длину такого отрезка A, что выражение

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

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

Элементами множеств А, P и Q являются натуральные числа, причём

P = {2, 4, 6, 8, 10, 12} и Q = {4, 8, 12, 116}.

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

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

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

Примеры заданий В18

Для какого наибольшего натурального числа А выражение

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

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

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

(x & 53  0)  ((x & 41 = 0)  (x & A  0))

тождественно истинно?

Преобразование логических операций

• Импликация
• Эквивалентность
• XOR (сложение по модулю 2, исключающее ИЛИ)

•  

Законы алгебры логики

• Законы де Моргана:
• Закон поглощения:
• Распределительный закон:

•  

Подход к решению А  F (P, Q) F (P, Q)  А A является подмножеством F  А  F (P, Q) A max = F (P, Q) F является подмножеством A  F  A A min = F (P, Q)

• Записать в более удобном виде, введя утверждения

P = (x  P), Q = (x  Q), A = (x  A)

• С помощью преобразования приводим к одному из видов

Отношения между множествами F (P, Q)

• P+Q
• PQ

•  

• Q
• P +

•  

P

Q

P

Q

P

Q

P

P

Q

Уравнения с множествами делимости Общая формулировка

• Обозначим через ДЕЛ (n, m) утверждение «натуральное число n делится без остатка на натуральное число m». Для какого наименьшего(наибольшего) натурального числа А формула
F(ДЕЛ(x, А), ДЕЛ(x, P), ДЕЛ(x, Q)) тождественно истинна (то есть принимает значение 1 при любом натуральном значении переменной х и заданных значениях P и Q)? Заметим, что необходимо найти нетривиальное, т.е., неединичное решение.
• Введём более компактные обозначения для множеств
ДA = ДЕЛ(x, А) ДP = ДЕЛ(x, P) ДQ= ДЕЛ(x, Q)
• Тогда решение задачи сводится к преобразованию исходного выражения к одной из импликативных форм.
• ДA  F(ДP , ДQ) или F(ДP , ДQ)  ДA

Отобразить отношения множеств Дел(х, 2), Дел(х, 4), Дел (х, 8) с помощью кругов Эйлера-Венна

Д2, Д4, Д8

Д4

Д2

Д8

Если множество ДA является подмножеством множества ДВ

ДA  ДВ

то А = k*В, где k- произвольное натуральное число.

Amin  amax

Почему максимальное число a дает минимальное множество A?

12

x

36

24

0

6

18

30

a=6

12

x

36

24

0

a=12

x

24

0

a=24

12

36

№	Форма	Аmin	Amax
1	ДAДPДQ
2	ДAДP +ДQ

Случай 1.

• Для какого наименьшего натурального числа А формула (ДЕЛ(x, 4) → (¬ДЕЛ(x, 6)) → ¬ДЕЛ(x, А) тождественно истинна (то есть принимает значение 1 при любом натуральном значении переменной х)?

ДА→Д4Д6

А  F (P, Q)

Д4

Д6

НОК(4, 6)=12

А = k 12

(Д4  ¬Д6)  ¬ДA = ¬ (¬Д4 + ¬Д6) +¬ ДA =Д4 Д6 + ¬ДA = ¬ (¬ДA )  Д4 Д6 = ДA  Д4Д6

Наименьшее А=12

Случай 2. Для какого наименьшего натурального числа А формула ДЕЛ(x, A) → (ДЕЛ(x, 21) +ДЕЛ(x, 35)) тождественно истинна (то есть принимает значение 1 при любом натуральном значении переменной х)? ДА→(Д21+ Д35)

А  F (P, Q)

НОК(21, 35)=105

Д21

Д35

 

Наименьшее А=21

 

№	Форма	Аmin	Amax
1	ДAДPДQ	НОК (P, Q)	не существует
2	ДAДP +ДQ	min(P, Q)	не существует

Случай 3. Для какого наибольшего натурального числа А формула ¬ДЕЛ(x, A) → ¬ (ДЕЛ(x, 21) & ¬ДЕЛ(x, 35)) тождественно истинна (то есть принимает значение 1 при любом натуральном значении переменной х)? Д21+ Д35→ДА

F (P, Q)  А

Д21

Д35

НбОД (21, 35) = 7

 

¬DA ( ¬ D21 & ¬ D35 ) = DA + ¬D21 & ¬ D35 = D21 + D35  DA

ДА

Д21 А

Д35 А

Наибольшее А=7

Случай 4. Для какого наименьшего натурального числа А формула ¬ДЕЛ(x, А) (ДЕЛ(x, 4)  ¬ДЕЛ(x, 6)) тождественно истинна (то есть принимает значение 1 при любом натуральном значении переменной х)? Д4Д6→ДА

F (P, Q)  А

12 = k*A

A может быть = 2, 4, 6, 12.

Д12→ДА

¬DA  (D4  ¬D6) = DA + ¬D4+ ¬D6= ¬(¬D4 + ¬D6) + DA= D4D6  DA

Аmin =2

Д6

Д4

Случай 5. Для какого наименьшего натурального числа А формула ДЕЛ(x, А)  (¬ДЕЛ(x, 21) + ДЕЛ(x, 35)) тождественно истинна ? ДA→ (¬ Д21+Д35)

35=5*7

Нельзя 3, 7 (21=3*7)

Аmin =5

ДА ¬ Д21

ДА Д35

Д35

Д21

№	Форма	Аmin	Amax
1	ДAДPДQ	НОК (P, Q)	не существует
2	ДAДP +ДQ	min(P, Q)	не существует
3	ДP + ДQДA	НМОД (P ,Q)	НБОД(P,Q)
4	ДPДQ ДA	НМД (P, Q)	НОК(P, Q)
5	ДAДP + ДQ	А=min (А: (А ≠ k1P и P ≠ k2А или А=k3Q) и АP =k4Q)	не существует
6	ДPДQДA	НМД(Q)	Q

Источники

• https://cyberleninka.ru/article/n/logicheskie-uravneniya-s-mnozhestvami
• http://kpolyakov.spb.ru/