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

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

(x & a  0 )  ((x & 20 = 0)  (x & 5  0))

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

Решение:

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

Z₂₀ = (x & 20 = 0), Z₅ = (x & 5 = 0), A = (x & a = 0)

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

3. преобразуем это выражение в импликацию, избавившись от инверсии:

4. заменим на :

20 = 10100

5 = 00101

20 or 5 = 10101 = 21

5. таким образом, нужно обеспечить истинность выражения при всех x

6. это возможно только тогда, когда множество единичных битов числа a входит во множество единичных битов числа 21

7. поэтому максимальное a_max = 10101₂ = 21

8. Ответ: 21.

Решение (2 способ, Н.Г. Неуймина, г. Екатеринбург):

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

P = (X & 20 = 0), Q = (X & 5 = 0), A = (X & A = 0)

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

3. чтобы формула была тождественно истинной для любых Х необходимо, чтобы при было А=1

4. имеем тогда и только тогда, когда ;

5. посмотрим, какими свойствами должен обладать X для того, чтобы было

6. если , то есть, (X & 5 = 0), имеем

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

X = ab0d0

5 = 00101

X & 5 = 00000

это значит, что биты {2, 0} – нулевые

7. если одновременно , то есть, (X & 20 = 0), имеем

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

X = 0b0d0

20 = 10100

X & 20 = 00000

это значит, что бит 4 в X – обязательно нулевой

8. так как биты {3,1} числа X могут быть ненулевыми, в этих разрядах числа A должны стоять нули, а вот биты {4,2,0} в X – нулевые, поэтому в числе A эти биты могут быть равны 1

9. поскольку нужно найти наибольшее подходящее A, получаем ответ 2⁴ + 2² + 2⁰ = 21

10. Ответ: 21.

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

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

ДЕЛ(x, А)  (ДЕЛ(x, 21) + ДЕЛ(x, 35))

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

Решение:

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

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

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

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

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

…

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

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

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

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

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

Чтобы в множество входили все числа, не попавшие в объединение , достаточно, чтобы множество А находилось внутри этого объединения, например, совпадая с одним из множеств D₃₅ или D₂₁, или располагаясь внутри любого из них, что возможно, если использовать делители, кратные 21 или 35.

8. В задании требуется найти НАИМЕНЬШЕЕ значение, этому условию соответствует 21.

9. Ответ: 21