ГДЗ по информатике, 10 класс, Босова, номер 20.9: Преобразование логических выражений

Дана формула: (x&25≠0)→((x&17=0)→(x&A≠0)). Вспомним правило импликации: P→Q ложно только тогда, когда P истинно, а Q ложно. Чтобы вся формула была тождественно истинной, не должно существовать такого x, при котором:

• Левая часть первой импликации истинна: x&25≠0;
• Правая часть первой импликации ложна. Правая часть — это тоже импликация: (x&17=0)→(x&A≠0). Она ложна, если её посылка истинна (x&17=0), а следствие ложно (x&A=0).

Таким образом, условие «формула не тождественно истинна» эквивалентно существованию числа x, удовлетворяющего системе: {nx&25≠0x&17=0x&A=0 Нам нужно выбрать такое минимальное A, чтобы такая система не имела решений. То есть, для любого x, если выполняются первые два условия, то третье (x&A=0) должно быть ложным (то есть x&A≠0).

Запишем числа 25 и 17 в двоичном виде. Обычно в таких задачах рассматриваются младшие разряды (например, до 8-го или 16-го). Посмотрим на биты чисел:

Разберём условия на x:

1. x&25≠0 : Это означает, что хотя бы один из разрядов, где у числа 25 стоит единица, должен быть равен 1 у числа x. У числа 25 единицы стоят в разрядах с номерами 0, 3 и 4 (считая от нуля справа налево). Значит, x должен иметь хотя бы одну единицу в позициях 0, 3 или 4.
2. x&17=0 : Это означает, что во всех разрядах, где у числа 17 стоит единица, у числа x должны стоять нули. У числа 17 единицы стоят в разрядах 0 и 4. Значит, x₀=0 и x₄=0.

Подставим ограничения из второго пункта в первый. Из условия x&17=0 мы знаем, что x₀=0 и x₄=0. Тогда условие x&25≠0 сводится к тому, что оставшийся разряд, где у 25 есть единица (это разряд 3), должен быть равен 1. Иначе все единицы маски 25 будут обнулены маской 17. Итак, необходимые условия для x: x₃=1, x₀=0, x₄=0. Остальные разряды могут быть любыми.

Теперь посмотрим на третье условие системы, которое мы хотим сделать невозможным: x&A=0. Мы выяснили, что любое x, попадающее под первые два условия, обязательно имеет x₃=1. Чтобы гарантировать, что x&A≠0 для всех таких x, нам нужно, чтобы конъюнкция x и A давала ненулевой результат. Поскольку мы точно знаем, что x₃=1, самым надежным способом обеспечить это является наличие единицы в том же разряде у числа A. Если A₃=1, то произойдет совпадение единиц в третьем разряде, и x&A будет содержать эту единицу, то есть не будет равно нулю. Если мы поставим A₃=1, то для любого x, удовлетворяющего условиям x&25≠0 и x&17=0, будет выполняться x&A≠0. Следовательно, система не имеет решений, и исходная формула тождественно истинна. Нам нужно наименьшее неотрицательное целое A. Мы установили, что третий разряд должен быть равен 1. Все остальные разряды можно оставить равными 0, чтобы число было минимальным. Значит, двоичная запись числа A должна быть: ...001000₂. Переведем это в десятичную систему: A=2³=8. Проверим, может ли A быть меньше? Если A<8, то его двоичная запись не содержит единицы в третьем разряде (так как 2³=8). Например, если A=7 (111₂), то возьмем x, у которого x₃=1, но x₀=x₁=x₂=0 (например, x=8). Проверим условия: 1. x&25=8&25. 8=1000₂, 25=11001₂. Конъюнкция: 01000₂&11001₂=01000₂=8≠0. (Истина) 2. x&17=8&17. 17=10001₂. Конъюнкция: 01000₂&10001₂=00000₂=0. (Истина) 3. x&A=8&7. 7=00111₂. Конъюнкция: 01000₂&00111₂=00000₂=0. (Ложь для неравенства, то есть условие x&A≠0 не выполнено). При A=7 существует контрпример x=8, при котором формула ложна. Значит, A должно иметь бит в позиции 3. Минимальное такое число — 8.