Пример задания:

Р-26 (демо-2018). Для какого наибольшего целого числа А формула

( (x  9)  (xx  A) )  ( (yy  A)  (y  9) )

Тождественно истинна (то есть принимает значение 1 при любых целых неотрицательных значениях переменных X и y)?

Решение:

1. заметим, что здесь два условия, которые объёдиняются с помощью логической операции «И»:

(x  9)  (xx  A)

(yy  A)  (y  9)

2. необходимо, чтобы оба условия были выполнены одновременно; к счастью, первое зависит только от переменной x, а второе – только от переменной y, поэтому их можно рассматривать отдельно: каждое из них задает некоторое ограничение на значение A

3. рассмотрим первое условие: (x  9)  (xx  A). Для того чтобы импликация была истинной, нужно не допустить варианта 1  0, то есть при истинной левой части правая часть тоже должна быть истинной.

4. это значит, что для всех 0 < x  9 мы должны обеспечить xx  A, то есть выбрать A  xx для все допустимых значений x. Очевидно, что для этого необходимо и достаточно выбрать A  99 = 81. Таким образом, мы определили минимальное допустимое значение A = 81.

5. теперь рассмотрим второе условие: (yy  A)  (y  9). Чтобы оно было истинно, нужно не допустить варианта 1  0. Выбором A мы можем влиять на левую часть, но не на правую. «Угрозу» представляет вариант, когда правая часть ложна, то есть y > 9. В этом случае нам нужно сделать левую часть ложной, то есть обеспечить выполнение условия yy > A.

6. для выбора максимального A возьмем минимальное значение y, для которого y > 9. Это даёт условие 1010 > A, откуда следует A < 100

7. таким образом, максимально допустимое значение A равно 99.

8. Ответ: 99.

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

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

( x & 125  1)  ((x & 34  2)  (x & a =0))

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

Решение:

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

где Z₁₂₄ = (x & 124 = 0), Z₁ = (x & 1 = 0), Z₂ = (x & 2 = 0), A = (x & a = 0)

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

3. применим закон де Моргана :

4. перейдём к импликации, в которой нет выражений с инверсиями (операциями «НЕ»):

5. преобразуем левую часть выражения:

так что

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

7. представим числа в двоичной системе счисления:

124 = 1111100₂, 1 =1₂, 2 =10₂

8. поскольку двоичная запись чисел 1 и 2 содержит единичные биты, которых нет в наборе единичных битов числа 124, имеем

в том смысле, что найдутся такие значения x, при которых эти выражения ложны.

9. тогда для истинности заданного выражения остаётся обеспечить истинность при всех x, а это условие будет выполняться тогда и только тогда, когда все единичные биты двоичной записи числа a входят во множество единичных битов числа 124 = 1111100₂; таким образом, минимальное подходящее положительное значение a – 2² = 4, а максимальное – 124.

10. Ответ: 4.