Ещё пример задания:

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

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

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

Решение:

1. введём обозначения A = ДЕЛ(x, А), D₂₁ = ДЕЛ(x, 21) , D₃₅ = ДЕЛ(x, 35) и D_N = ДЕЛ(x, N)

2. введём множества:

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

D₂₁ –множество натуральных чисел, для которых выполняется условие D₂₁

D₃₅ –множество натуральных чисел, для которых выполняется условие D₃₅

…

3. Запишем формулу из условия в наших обозначениях

4. Раскроем импликацию по правилу :

5. Чтобы формула была тождественно истинной необходимо, чтобы А = 1, когда . Тогда множество А определяется так:

6. Множество , точно соответствующее выражению с помощью функции ДЕЛ получить невозможно.

7. Выполним анализ исходной формулы с помощью кругов Эйлера.

в множество А должны входить все числа, попавшие в объединение . Нужно найти множество, в которое входят оба эти множества. Для этого рассмотрим делители чисел 21 и 35.

8. Число 35 делится на 5 и 7, поэтому: , 21 делится на 3 и 7, поэтому:

9. Перепишем и упростим формулу для А:

10. Таким образом, каждое из множеств D₃₅ и D₂₁ входит в множество D₇ . Объединение D₃₅ + D₂₁ тоже входит в D₇. Поскольку 7 – наибольший общий делитель чисел 21 и 35, то найдено максимальное значение соответствующее условию задачи.

11. Ответ: 7.

Ещё пример задания:

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

¬(x A)  (¬(x P)  (x Q))

Решение:

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

A: x  А, P: x  P, Q: x  Q

1. перейдем к более простым обозначениям

2. раскрываем импликацию по формуле :

3. для выполнения условия при любом x необходимо, чтобы для всех x, для которых , то есть

4. множество – это все 8-битовые цепочки, которые начинаются с 1 и оканчиваются НЕ на 000

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

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

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

8. Ответ: 112.

Решение (А.Н. Носкин):

1. упростим исходное выражение и получим: А  ¬Р  Q = 1

2. всё множество всех 8-битовых цепочек расположено на отрезке от 0 до 255

3. минимальное число множества Р начинающегося с 10000000₂ = 128, следовательно, все множество Р занимает часть отрезка от 128 до 255; длина этой части отрезка равна 255 – 128 + 1 = 128.

4. Q – множество всех 8-битовых цепочек, оканчивающихся на 000, которые имеют вид ****000, где * обозначает любой из двух символов (0 или 1); количество таких чисел в множестве равно 2⁴ = 16, где 4 – число звездочек в числе Q

5. из выражения видно, что множество ¬Р закрывает интервал от 0 до 127, следовательно, множество A должно перекрыть все числа во множестве Р (таких чисел 128), которые не перекрывают числа из множества Q

6. минимальное множество A содержит 128 – 16 = 112 элементов.

7. Ответ: 112.