Преобразование (Конъюнкция, импликация, дизъюнкция)

Здравствуйте не могу разобраться в задачах подобной этой:

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

x & 29 ≠ 0 → (x & 12 = 0 → x & А ≠ 0)

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

Я произвёл замену
D = (x & 29 = 0)
B = (x & 12 = 0)
C = (x & А = 0)

Получил выражение: ¬D → (B → ¬C)
После всех преобразований пришёл к выражению: B /\ C → D

Что делать дальше?

P.S. Я смотрел в объяснение и там говориться что единичные биты правой части, должны соответствовать единичным битам левой части и ответ в итоге получается 10001, но я не могу понять почему. Объясните на пальцах пожалуйста

0

Будем нумеровать биты справа, начиная с нуля. Тогда x & 29 ≠ 0 <=> в x отличен от нуля хотя бы один из битов с номерами 0, 2, 3, 4. Далее, x & 12 = 0 <=> в x равны нулю биты с номерами 2, 3. Значит, (x & 29 ≠ 0 /\ x & 12 = 0) <=> в x отличны от нуля хотя бы один из битов с номерами 0, 4 (здесь /\ обозначает конъюнкцию). Заметим, что x & 29 ≠ 0 → (x & 12 = 0 → x & А ≠ 0) эквивалентна (x & 29 ≠ 0 /\ x & 12 = 0) → x & А ≠ 0. Чтобы эта формула была тождественно истинной, оба бита 0, 4 должны равняться 1 в A.

0

3D Homer, вообщем я так понимаю сначала надо разделить уравнение на две части, чтобы с одной было всё известно, а в другой осталась искомая переменная. Из-за того что импликация нам надо выяснить какие биты справа равны 1, чтобы слева тоже сделать 1( т.к. если будет 1 -> 0, то будет 0 ). Но у меня вопрос: Почем просто не взять скажем A = 00001 , ведь тогда выражение вроде как не стане равным 0. Или я чего-то не понимаю ?

p.s. я в этой теме вообще 0, знаю только основные операции и Законы де Моргана

0

Сообщение от Drouro сначала надо разделить уравнение на две части

Уравнение — это формула вида A = B. Соответственно, формула x & 29 ≠ 0 → (x & 12 = 0 → x & А ≠ 0) не является уравнением. У меня нет алгоритма, как решать эту задачу, наподобие алгоритма решения линейного уравнения (переносим все члены с x в левую часть, приводим подобные члены, ...). Мое решение основано просто на здравом смысле.

Во-первых нужно заметить, что это задача не на пропозициональную, а на предикатную логику. Здесь есть не только битовые операции (которые можно выразить в пропозициональной логике), но и импликация и конъюнкция (если преобразовать формулу, как я предлагал), а также предметная переменная x. Она пробегает по всем целым неотрицательным числам, а не только по множеству {0, 1}. Поэтому эту формулу нужно воспринимать как "если..., то" в обычной речи: если x & 29 ≠ 0 и x & 12 = 0, то x & А ≠ 0. Это высказывание зависит от x и A: для каждых натуральных x и A оно или истинно, или ложно. От нас фактически требуется доказать следующее:

∃A ∀x (x & 29 ≠ 0 /\ x & 12 = 0 → x & А ≠ 0).

Это можно прочитать так: существует A, такое что для любого x, если x имеет единицу в битах 0, 2, 3, или 4 и ноль в битах 2 и 3, то x и A имеют единицу в одном и том же бите. Кроме того, нужно найти наименьшее A, которое делает эту формулу истинной. Посылка эквивалентна тому, что x имеет единицу в битах 0 или 4. Но единица может быть только в 0 или только в 4. Значит, у A должны быть единицы в обоих этих битах. Если взять A = 00001, то x = 16, то есть 10000, делает формулу ложной.

1

3D Homer, после вашего объяснения я наконец понял, спасибо.

P.S. Если интересно, то автор данного примера приводит следующее решение:

Преобразуем выражение по законам алгебры логики:

¬Х → (Y → ¬Z) = Х + (Y → ¬Z) = Х + ¬Y + ¬Z = X + ¬(YZ) = YZ → X.

Имеем импликацию Z(12) Z(A) → Z(29) или Z(12 or A) → Z(29). Запишем число 29 в двоичной системе счисления: 29 = 11101. Единичные биты, стоящие в правой части, должны являться единичными битами левой. Поскольку 12 = 01100, двоичная запись искомого числа А должна содержать единичные биты в нулевом и четвертом разрядах.

Тем самым, наименьшее А = 10001 = 17

0