вернуться
Информатика

Вопрос 18

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

Для какого наименьшего неотрицательного целого числа A формула тождественно истинна (то есть, принимает значение 1 при любом неотрицательном целом значении переменной x): \(\mathrm{x}\&25\neq 0 \Rightarrow (\mathrm{x}\&17=0\Rightarrow \mathrm{x}\&\mathrm{A}\neq 0)\).

Решение №1

Для решения этой задачи нам потребуется сделать несколько логических умозаключений, поэтому "следите за руками".

  1. От нас хотят, чтобы мы нашли минимальное целое неотрицательное А, при котором выражение всегда истинно.
  2. Что из себя представляет выражение в целом? Что-то там импликация что-то там в скобках. 
  3. Давайте вспомним таблицу истинности для импликации:
    1 => 1 = 1
    1 => 0 = 0
    0 => 1 = 1
    0 => 0 = 1
  4. Значит, возможно три варианта, когда это будет истинно. Рассматривать все эти три варианта — это убиться и не жить. Давайте подумаем, можем ли мы пойти "от противного".
  5. Давайте вместо того, чтобы искать А, попробуем найти x, при котором это выражение ложно.
  6. То есть, возьмём некоторое число А (пока не знаем какое, просто какое-то).  Если вдруг мы найдём такое x, при котором всё высказывание ложно, значит, выбранное А — плохое (потому что в условии требуется, чтобы всегда выражение было истинным)! 
  7. Таким образом мы сможем получить какие-то ограничение на число А.
  8. Итак, давайте пойдём от противного и вспомним, когда импликация бывает ложной? Когда первая часть истинна, а вторая — ложна.
  9. Значит
    \((\mathrm{x}\&25\neq 0 )= 1 \\ (\mathrm{x}\&17=0\Rightarrow \mathrm{x}\&\mathrm{A}\neq 0) = 0\)
  10. Что означает, что \((x\&25\neq 0) = 1\)? Это означает, что действительно \(\mathrm{x}\&25\neq 0\).
  11. Давайте переведём 25 в двоичную. Получим: 110012.
  12. Какие ограничения это накладывает на x? Раз не равно нулю, значит, при поразрядной конъюнкции должна где-то получиться единица. Но где она может быть? Только там, где в 25 уже есть единица!
  13. Значит, в числе x хотя бы в одном кресте должна быть единица: XX**X.
  14. Отлично, теперь рассмотрим второй множитель: \((\mathrm{x}\&17=0\Rightarrow \mathrm{x}\&\mathrm{A}\neq 0) = 0\)
  15. Это выражение из себя также представляет импликацию. При этом оно так же ложно.
  16. Значит, его первая часть обязана быть истинной, а вторая — ложной.
  17. Значит
     \((\mathrm{x}\&17=0) = 1 \\ ((\mathrm{x}\&\mathrm{A}\neq 0) = 0) = 0\)
  18. Что означает, что \(\mathrm{x}\&17=0\)? То, что на всех местах, где в 17 стоят единицы, в x должны стоять нули (иначе в результате не получится 0). 
  19. Переведём 17 в двоичную: 100012. Значит, в x на последнем с конца и на 5 с конца месте должны стоять нули.
  20. Но стоп, мы же в пункте 13 получили, что на последнем ИЛИ на 4 с конца ИЛИ на 5 с конца должна быть единица. 
  21. Раз согласно строке 19 на последнем или 5 с конца местах единицы быть не может, значит, она обязана быть на 4 с конца месте.
  22. То есть, если мы хотим, что при нашем x всё выражение было ложным, на 4 с конца месте обязана стоять единица: XX...XX1XXX2
  23. Отлично, рассмотрим теперь последнее условие: \((\mathrm{x}\&\mathrm{A}\neq 0) = 0\). Что это означает?
  24. Это означает, что неверно, что \(\mathrm{x}\&\mathrm{A}\neq 0\).
  25. То есть, на самом деле, \(\mathrm{x}\&\mathrm{A}=0\).
  26. Что мы знаем про x? Что на 4 с конца месте там единица. Во всём остальном x может быть практически любым.
  27. Если мы хотим, чтобы исходное выражение в условии задачи было всегда истинным, то мы не должны найти х, который бы удовлетворял всем условиям. Ведь, действительно, если бы мы нашли такой x, получилось бы, что исходное выражение не всегда истинно, что противоречит условию задачи.
  28. Значит, вот это самое последнее условие просто обязано не выполняться.
  29. А как оно может не выполняться? Если только мы будем уверены на 100%, что при поразрядной конъюнкции где-то останется единица.
  30. И это возможно: если в А тоже на 4 месте с конца будет единица, то в результате поразрядной конъюнкции на 4 с конца месте останется единица.
  31. Какое минимально возможное двоичное число имеет единицу на 4 с конца месте? Очевидно, что 10002. Значит, это число и будет ответом.
  32. Осталось только перевести его в десятичную: \(1000_2=0\times 2^0 + 0\times 2^1 + 0\times 2^2 + 1\times 2^3=8\)

Ответ: минимально возможное A, удовлетворяющее условиям, равно 8.

Евгений Смирнов
Эксперт в IT, учитель информатики

Решение №2

Можно предложить несколько более короткий подход. Обозначим наше высказывание как F = (A->(B->C)), где А - это высказывание "Х&25 не равно 0", В= "Х&17=0" и C="X&A не равно 0".

Раскроем импликации, пользуясь известным законом X->Y = не(Х) ИЛИ Y, получим F = A -> (не(В) ИЛИ C) = не(А) ИЛИ не(B) ИЛИ С. Распишем также двоичные значения констант 25 и 17:

25 = 11001

17 = 10001

Наше выражение - логическое ИЛИ от трёх высказываний:

1) не(А) - это значит, X&25 = 0 (биты 0,3,4 числа Х все равны 0)

2) не(B) - значит, X&17 не равно 0 (биты 0 и 4 числа Х хотя бы один равен 1)

3) C - знаит, X&A не равно 0 (биты, задаваемые маской A, хотя бы 1 равен 1)

Х  - произвольное число. Все его биты независимы. Поэтому требовать выполнения какого-то условия на биты произвольного числа можно только в одном единственном случае - когда речь идёт об одной и той же маске (наборе битов). Мы можем заметить, что двоичная маска 17 - почти то же самое, что и 25, только не хватает бита номер 3. Вот если бы дополнить 17 битом номер 3, то выражение (не(В) ИЛИ С) превратилось бы в не(неА), т.е. в А = (X&25 не равно 0). По-другому: допустим, А=8 (бит 3=1). Тогда требование (не(В) B или С) равносильно требованию: (Хотя бы один из битов 4,0 равен 1) ИЛИ (бит 3 равен 1) = (хотя бы один из битов 0,3,4 не равен 1) - т.е. инверсия не(А) = А = (Х&25 не равно 0).

В итоге мы заметили, что если А=8, то наше выражение принимает вид F = не(А) ИЛИ А, что, по закону исключённого третьего, всегда тождественно истинно. При других, меньших, значениях А независимость от значения Х получить не удаётся, т.к. маски выходят разные. Ну, а при наличии в старших битах А единиц в битах выше 4 ничего не меняется, т.к. в остальных масках у нас нули. Получается, что только при А=8 формула превращается в тавтологию для произвольного Х.

 

Дмитрий Лисин