Задание 18 (презентация по типам задач к ЕГЭ)

повышенный уровень, время – 3 мин

ege 18

Тема: Основные понятия математической логики

Что нужно знать?

Множества и логика

Множество можно задать перечислением его элементов или с помощью логического выражения ( условия ), которое истинно для каждого элемента множества и ложно для всех элементов, не входящих во множество.

Универсальное множество ( I ) - это множество, содержащее все возможные элементы заданного типа (например, все целые числа)

Универсальное множество играет роль логической единицы :

для любого множества целых чисел X справедливы равенства

X + I = I и X · I = X (здесь используем знаки сложения и умножения вместо знаков пересечения  и объединения  множеств)

Основные операции над множествами — это дополнение (до выбранного универсального множества), пересечение и объединение .

Если A — это множество точек , принадлежащих отрезку , то A — это множество точек, не принадлежащих этому отрезку (здесь универсальное множество — это множество всех точек числовой оси)

• пусть требуется выбрать множество A так, чтобы выполнялось равенство A + X = I ; в этом случае множество A должно включать дополнение т.е. или проще,

то есть

• пусть требуется выбрать множество A так, чтобы выполнялось равенство

, в этом случае множество

должно включать дополнение , то есть

, отсюда

, то есть

Дополнение А до универсального множества

A

Пересечение множеств A и B

Объединение множеств A и B

A  B

A  B

A ·B

A+B

A

B

свойства импликации

формулы де Моргана:

для упрощения выражений

Задача 1 . Каким должно быть множество A для того, чтобы множество A + B совпадало с универсальным множеством ?

Очевидно, что можно выбрать в качестве решения дополнение множества B до универсального множества:

Множество A min = — это минимальное множество, которое является решением задачи.

Кроме того, решением будет и любое множество, включающее , то есть любое A , такое, что (или, используя обозначения теории множеств, )

Заметим, что множество A + B , которое должно по условию задачи совпадать с универсальным множеством , определяется логическим выражением A+B .

Это выражение может быть преобразовано, с учетом свойств импликации, к форме .

Переход от условия A + B =1 к условию в некоторых случаях упрощает решение задач.

Задача 2 . Каким должно быть множество A для того, чтобы множество совпадало с универсальным множеством ?

В этом случае получаем , откуда сразу следует, что A ≤ B , то есть множество A должно быть подмножеством множества B ( A ⊆ B ). Тогда максимальное множество A , которое является решением, совпадает с B : A max = B.

В некоторых случаях задача упрощается, если заменить условие , определяющее множество , на эквивалентное условие A → B =1 или

Таким образом, конкретную задачу на множества и математическую логику нужно попытаться привести к форме Задачи 1 или Задачи 2 , а затем использовать готовое решение.

Отрезки

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

(x ∈ P)→ (((x ∈ Q) ∧ ¬(x ∈ A)) → ¬(x ∈ P)) истинно при любом значении переменной х.

Решение

Введем обозначения: P = ( x ∈ P ), Q = ( x ∈ Q ), A = ( x ∈ A ).

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

Используя свойство импликации и закон де Моргана , получаем

В результате задачу свели к базовой Задаче 1 , где B=P +Q . Ее решение A min = P +Q =P ⋅Q — это пересечение множеств P и Q , то есть общая часть двух отрезков.

В нашей задаче это отрезок [40; 60] (он обозначен желтым цветом на рисунке), его длина — 20 .

Ответ: 20

Задача 4 . На числовой прямой даны два отрезка:

P = [10; 20] и Q = [25; 55]. Укажите наибольшую возможную длину такого отрезка A , что выражение (x ∈ A)→ ((x ∈ P) ∈ (x ∈ Q))

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

Решение

Введем обозначения: P = ( x ∈ P ), Q = ( x ∈ Q ), A = ( x ∈ A ).

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

Используя свойство импликации , получаем

В результате задачу свели к базовой Задаче 2 , где B=P +Q . Ее решение A max = P +Q — это объединение множеств P и Q , включающее оба отрезка:

Наибольший из 2 - х отрезков: Q, его длина - 30

Ответ: 30

Множества чисел

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

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

(x ∈ P)→ (((x ∈ Q) ∧ ¬(x ∈ A)) → ¬(x ∈ P))

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

Решение

Введем обозначения: P = ( x ∈ P ), Q = ( x ∈ Q ), A = ( x ∈ A ).

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

P → ( Q ⋅ A → P )

Преобразуем и получим:

В результате задачу свели к базовой Задаче 1 , где B= P +Q . Ее решение A min = P +Q =P ⋅Q — это пересечение множеств P и Q , т.е. множество общих элементов P и Q .

Ответ: 24

Поэтому A min = { 4, 8, 12}. Сумма элементов равна 24 .

Задача 6. Элементами множеств А, 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))

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

Введем обозначения P = ( x ∈ P ), Q = ( x ∈ Q ), A = ( x ∈ A ).

Решение

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

Используя свойство импликации и закон поглощения A + A⋅B= A , получаем

В результате задача сводится к базовой Задаче 2 , где . Ее решение A max = — это пересечение множеств P и Q , то есть все элементы, которые входят в Q и не входят в P :

A max = {3, 9, 15, 21, 24, 27, 30}.

Ответ: 7

Количество элементов этого множества равно 7.

Делимость

ДЕЛ(n, m) обозначает утверждение “ натуральное число n делится без остатка на натуральное число m ”.

D N - множество натуральных чисел, делящихся на N.

D N = (x ∈ D N ), A = (x ∈ D A )

Задача 7 . Для какого наибольшего натурального

числа А выражение ￢ ДЕЛ(x, А)→ (ДЕЛ(x, 6)→ ￢ ДЕЛ(x, 4))

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

Решение

Истинным для всех x должно быть выражение

Упростим это выражение:

Задачу свели к базовой Задаче 1 , где

Ее решение

— это множество всех чисел, которые делятся одновременно на 4 и 6

НОК(4,6)=12

Поэтому 12 — это и есть наибольшее возможное значение A .

Ответ: 12

Задача 8 . Для какого наибольшего натурального

числа А выражение ￢ ДЕЛ(x, А) → ( ￢ ДЕЛ(x, 21) ∧ ￢ ДЕЛ(x, 35))

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

Решение

Истинным для всех x должно быть выражение

Раскроем импликацию

Т.е. задача сведена к базовой Задаче 1 , где

Ее решение:

— это множество чисел, которые делятся на 21 или на 35 .

Получить множество D A min с помощью одной операции ДЕЛ невозможно. Заметим, что любое множество D A , где A — какой-нибудь общий делитель чисел 21 и 35 , содержит D A min (все числа, делящиеся на 21 или на 35 ) . Так как 7 — это наибольший общий делитель этих чисел, множество D 7 — это минимальное множество, которое включает D A min (нужно учитывать, что чем больше A, тем меньше множество D A ).

Поэтому наибольшее значение A равно 7 .

Ответ: 7

Задача 9 . Для какого наименьшего натурального числа А выражение ДЕЛ(x, А)→ (ДЕЛ(x, 21) ∨ ДЕЛ(x, 35)) тождественно истинно?

Решение

Истинным для всех x должно быть выражение

Раскроем импликацию

Т.е. задача сведена к базовой Задаче 2 , где

Ее решение:

— это множество чисел, которые делятся на 21 или на 35 .

Получить такое множество в точности с помощью операции ДЕЛ не удается; нужное множество должно входить во множество

Можно выбрать в качестве A число 21 или число 35 , так как D 21 ≤ D 21 + D 35 и D 35 ≤ D 21 + D 35 .

А вот числа, меньшие, чем 21 , выбирать нельзя: при этом

множество D A не будет подмножеством D 21 +D 35 .

Например, при выборе A = 7 множество D 7 содержит числа 7 , 14 , 28 и др., которые не делятся ни на 21 , ни на 35 .

Ответ: 21

Задача 10 . Для какого наименьшего натурального числа А выражение ДЕЛ(x, А) → ( ￢ ДЕЛ(x, 21) ∧ ДЕЛ(x, 35))

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

Решение

Истинным для всех x должно быть выражение

Раскроем импликацию

Т.е. задача сведена к базовой Задаче 2 , где

— это множество чисел, которые не делятся на 21 , но делятся на 35 .

Ее решение:

Если натуральное число x делится на A , то его можно записать в виде x = A*k для некоторого натурального k .

Т.е., если x делится на 21 , то x = 21⋅m для некоторого натурального m , а если x делится на 35 , то x = 35⋅q для некоторого натурального q .

Представим числа 21 и 35 в виде произведения простых сомножителей: 21 = 3⋅7 , 35 = 5⋅7 .

Таким образом, при любом значении k число x = A⋅k = 3⋅7⋅ m должно делиться на 35 = 5⋅7 .

Для этого нужно с помощью сомножителя A добавить в произведение A⋅k = 3⋅7⋅m недостающий сомножитель 5 , который есть среди простых сомножителей числа 35 , но отсутствует среди простых сомножителей числа 21 .

Этого будет достаточно, чтобы обеспечить делимость числа A⋅k = 3⋅7⋅m на 35 , поскольку сомножитель 7 там уже и так есть.

Заметим, что в качестве A можно взять любое число, кратное 5 , но минимальное возможное значение — это 5 .

Ответ: 5

Задача 11 . Для какого наименьшего натурального числа А выражение (ДЕЛ(x, А)  ДЕЛ(x, 21))  ДЕЛ(x, 18)

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

Решение

Истинным для всех x должно быть выражение

Это означает, что нужно выбрать такое A , что если число делится на A и делится на 21 , то оно должно делиться на 18 .

Находим, что при любом значении k число x = A⋅k = 3⋅7⋅m должно делиться на 18 = 2⋅3⋅3 .

Для этого нужно с помощью сомножителя A добавить в произведение A⋅k = 3⋅7⋅m недостающие сомножители 2 и 3 . Этого будет достаточно, чтобы обеспечить делимость числа A⋅k = 3⋅7⋅ m на 18 , поскольку один сомножитель 3 там уже и так есть.

Кажется, что можно принять A = 2⋅3 , но это не так: при таком выборе A получаем x = 2⋅3⋅k = 3⋅7⋅m , что гарантирует делимость числа на 2 и 3 , но не гарантирует его делимость на 9 , поскольку одна тройка в правой части уже была.

Поэтому среди сомножителей A тройка должна встречаться дважды, то есть A = 2⋅3⋅3 = 1 8.

Ответ: 18

Побитовые операции

Задача 12 . Определите наименьшее натуральное число A , такое, что выражение (x & 53 ≠ 0) → ((x & 41 = 0)→ (x & A ≠ 0)) тождественно истинно?

Решение

Обозначим через D N множество натуральных чисел, для которых побитовая конъюнкция с числом N дает не нулевое значение: D N = {x: x & N ≠ 0} .

Введем условия: D N = (x ∈ D N ), A = (x ∈ D A ).

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

Т.е. задача сведена к базовой Задаче 1 , где

Ее решение:

Минимальное множество D A min определяется одновременным выполнением двух условий: x & 53 ≠ 0 и x & 41 = 0.

Побитовая конъюнкция (операция “И”) применяется к соответствующим битам чисел x и 53 , где 53 выполняет роль маски.

Запишем число 53 в двоичной системе счисления:

53 = 32 + 16 + 4 + 1 = 2 5 + 2 4 + 2 2 + 2 0 = 110101 2

После выполнения побитовой операции “И” сохраняются только те биты числа x , для которых соответствующие биты маски равны 1 , остальные (соответствующие нулевым битам маски) обнуляются:

Условие D 53 обозначает, что среди битов {5, 4, 2, 0} числа x есть не нулевые.

номер бита 5 4 3 2 1 0

53 =1 1 0 1 0 1

x = a b c d e f

x & 53 =a b 0 d 0 f

Запишем в двоичном коде число 41 = 32 + 8 + 1 = 2 5 + 2 3 + 2 0 = 101001 2 .

Выполнение условия означает, что биты { 5, 3, 0 } числа x — нулевые.

Если выполняется условие , определяющее нужное нам множество, то среди битов {4, 2} числа x есть не нулевые. Для всех таких чисел x & A ≠ 0 , где A может быть любым числом, у которого биты 4 и 2 равны 1.

Минимальное из таких чисел равно 2 4 + 2 2 = 20 .

Ответ: 20

Побитовые операции

Задача 13 . Определите наибольшее натуральное число A , такое, что выражение (x & A ≠ 0) → ((x & 20 = 0)→ (x & 5≠ 0)) тождественно истинно?

Решение

Используя обозначения, введенные в предыдущей задаче, преобразуем выражение

Т.е. задача сведена к базовой Задаче 2 , где

Ее решение:

Максимальное множество D A max определяется выполнением одного из двух условий: x & 20 ≠ 0 или x & 5 ≠ 0.

Представим числа 20 и 5 в двоичной системе счисления:

20 = 16 + 4 = 2 4 + 2 2 = 10100 2

5 = 4+1= 2 2 + 2 0 =101 2

Объединение этих множеств — это множество чисел, в двоичной записи которых среди битов {4, 2, 0} есть ненулевые .

Это (максимальное) множество определяется условием x & A ≠ 0 , где A = 2 4 + 2 2 + 2 0 = 21.

Ответ: 21

Битовые цепочки

Задача 14 . Пусть P — множество всех 8 -битовых цепочек, начинающихся с 1 , Q — множество всех 8 -битовых цепочек, оканчивающихся на 000 , а A - некоторое множество произвольных 8 -битовых цепочек. Сколько элементов содержит минимальное множество A , при котором для любой 8 -битовой

цепочки x истинно выражение ¬(x ∈ A)→ (¬(x ∈ P) ∨ (x ∈ Q)) ?

Решение

Введем обозначения P = (x ∈ P), Q = (x ∈ Q), A = (x ∈ A).

Запишем условие в виде

Раскроем импликацию:

Получили базовую Задачу 1 , где

Ее решение:

Это множество, состоящее из всех элементов множества P , не входящих во множество Q , то есть все 8 -битовые цепочки, которые начинаются с 1 и оканчиваются не на 000 .

Поскольку рассматриваются 8 -битные цепочки, структура всех таких цепочек имеет вид 1****??? , где * обозначает любой из двух символов (0 или 1), а ??? — трехбитное окончание, не совпадающее с 000 .

Всего может быть 2 3 = 8 комбинаций из трех битов , одно из них, 000 , запрещено для окончания, поэтому остается еще 7 разрешенных вариантов.

Общее количество подходящих цепочек находим по правилам комбинаторики, перемножив количество вариантов для каждой части цепочки ( 1 для первого бита, по 2 для следующих четырех и 7 для трехбитного окончания):

1·2·2·2·2·7 = 112

Ответ: 112

Еще один метод решения задач с битовыми операциями

Введём обозначения

сокращ.

, то это равносильно тому, что истинно

если истинно

Пусть в двоичной записи числа K бит с номером i , обозначаемый как k i , равен 1.

Если при этом для некоторого x выполнено условие , то соответствующий i- й бит в двоичной записи числа x равен 0, так как должно выполняться условие

Для преобразования выражений полезно следующее свойство:

где « or » означает поразрядную дизъюнкцию между двумя натуральными числами.

Самый важный результат можно сформулировать так:

Условие истинно для любых натуральных значений x тогда и только тогда, когда все единичные биты двоичной записи числа M входят во множество единичных битов двоичной записи числа K.

Для упрощения выражений полезен следующий результат:

Условие при любых натуральных K, M и N ложно для некоторых натуральных значений x .

Итак, метод заключается в следующем:

• упростить заданное выражение, сведя его к импликации, в которой нет инверсий

• применить полученные выше результаты для нахождения всех подходящих значений неизвестного числа a , включая минимальное и максимальное значения.

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

( (x & 28  0)  (x & 45  0))  ((x & 48 = 0)  (x & a  0))

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

Решение:

Z 28 = ( x & 28 = 0)

1. Введём обозначения:

Z 45 = ( x & 45 = 0)

Z 48 = ( x & 48 = 0)

A = ( x & a = 0)

2. Перепишем исходное выражение и преобразуем его, используя свойство импликации:

3. Перейдем к импликации, используя закон де Моргана:

4. Преобразуем выражение в правой части по формуле

выполнив поразрядную дизъюнкцию (операцию ИЛИ):

28 = 011100

45 = 101101

получаем

= 61

28 or 45 = 111101

5. Для того, чтобы это выражение было истинно для всех x, нужно, чтобы двоичная запись числа 48 or a содержала все единичные биты числа 61 .

Таким образом, с помощью числа a нужно добавить те единичные биты числа 61 , которых « не хватает» в числе 48 :

48 = 110000

a = **11*1

61= 111101

биты, обозначенные звездочками, могут быть любыми.

6. поскольку в задании интересует минимальное значение a , все биты, обозначенные звездочкой, можно принять равными нулю .

7. Получается a = 2 3 + 2 2 + 2 0 = 13

Ответ: 13

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

( ( (x&a  0)  (x&12=0) )  ( (x&a=0)  (x&21  0) ) )  ( (x&21=0)  ((x&12= 0) ) тождественно истинно (то есть принимает значение 1 при любом натуральном значении переменной x )?

Решение:

Z 12 = ( x & 1 2 = 0)

1. Введём обозначения:

Z 21 = ( x & 21 = 0)

A = ( x & a = 0)

2. Перепишем исходное выражение и преобразуем его, используя свойство импликации:

Выражение в первой скобке упрощаем, используя следствие из распределительного закона

Полученное выражение также можно упростить, используя ещё одно следствие из распределительного закона

3. Перейдем к импликации, избавившись от инверсии:

4. Поскольку множество единичных битов числа 21 = 10101­ 2 не входит во множество единичных битов числа 12 = 1100­ 2 , импликация ложна для некоторых x ;

поэтому нужно обеспечить истинность выражения

Это выражение истинно при условии, что множество единичных битов числа a входит во множество единичных битов числа 12 , поэтому в двоичной записи числа a ненулевыми могут быть только биты в разрядах 2 и 3

поэтому a max = 2 3 + 2 2 = 12

Ответ: 12

Демо - 2017

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

Для какого наименьшего неотрицательного целого числа А формула x&51 = 0  (x&41 = 0 → x&А ≠ 0) тождественно истинна (т.е. принимает значение 1 при любом неотрицательном целом значении переменной х)?

Решение

D 51 =x&51  0

Введем обозначения:

D 41 =x&41  0

A=x&A  0

Запишем исходное выражение

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

где

Тогда

51=32+16+2+1=110011

x&51  0

x

=abcdef

x&41 = 0

x&51

=ab00ef

Тренировочные задания из ege18 :

Делимость: № 120 - № 133 ; № 135 - № 146

Битовые цепочки : №147 - №149

Побитовые операции : № 150 - № 166