Поразрядную конъюнкцию неотрицательных целых чисел

Часть 1

Задание 18

Решение примера 2

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

Для какого наименьшего неотрицательного целого числа А формула

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

Решение.

1) Для начала упростим нашу формулу x&51 = 0 ∨ (x&41 = 0 → x&А ≠ 0), заменив импликацию простыми логическими операциями используя формулу: A→B = ¬A + B

x&51 = 0 ∨ x&41 ≠ 0 ∨ x&А ≠ 0

2) Рассмотрим первое выражение (x&51 = 0) и узнаем для каких чисел X это выражение будет истинно:
Переведём число 51 в двоичную систему счисления

3) Определяем те значения X, при которых истинно выражение x&51 = 0:
51₁₀ 110011
Х 111111
=0 110011

Если в числе Х на месте 1-го, 2-го, 5-го и 6-го разряда окажутся единицы, то после поразрядной конъюнкции на этих местах также будут стоять единицы, т.е. мы не получим «0» и выражение (x&51 = 0) будет ЛОЖНО.
Все остальные цифры в числе X могут быть любыми, так как после поразрядной конъюнкции на этих местах все равно будет «0».
Значит первое слагаемое учитывает все числа х, в которых нет на 1-м, 2-м, 5-м и 6-м местах единиц.

4) Рассмотрим второе выражение (x&41 ≠ 0): только для тех чисел Х, у которых на 1-м, 2-м, 5-м и 6-м местах стоят единицы.
Переведём число 41 в двоичную систему счисления

5) Определяем те значения X, при которых истинно выражение x&41 ≠ 0:
41₁₀ 101001
Х 11 11
≠0 1 1

Если в числе Х на месте 2-го и 5-го разряда стоят единицы, то после поразрядной конъюнкции на этих местах будут стоять нули, т.е. мы не получим «1» и выражение (x&41 ≠ 0) будет ложно.
Единицы на 1-м и 6-м месте в числе Х после поразрядной конъюнкции дадут «1» и выражение (x&41 ≠ 0) будет истинно.
Значит второе слагаемое учитывает числа Х, в которых на 1-м и 6-м местах стоят «1» и не учитывает числа Х, в которых на 2-м и 5-м местах стоят «1».

6) Рассмотрим третье выражение (x&A≠0):
У нас остались неучтенными лишь те числа Х, у которых на 5-м и 2-м месте стоят «1», следовательно, их нужно учесть в числе А.
Минимально возможное такое число это 10010₂ = 18₁₀

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

Для ка­ко­го наи­мень­ше­го не­от­ри­ца­тель­но­го це­ло­го числа А фор­му­ла

x&25 ≠ 0 → (x&17 = 0 → x&А ≠ 0)

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

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

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

Далее применяем обозначения и реализуем способ решения, изложенный К. Ю. Поляковым в теоретических материалах (см., например, раздел «Теория» на нашем сайте) без дополнительных пояснений.

Имеем импликацию Z₁₇Z_A → Z₂₅ или Z_{(17 or A)} → Z₂₅. Запишем число 25 в двоичной системе счисления: 25₁₀ = 11001₂. Единичные биты, стоящие в правой части, должны являться единичными битами левой. Поскольку 17₁₀ = 10001₂, двоичная запись искомого числа А должна содержать единичный бит в третьем разряде (как обычно, считая справа налево, начиная с нуля).

Тем самым, наименьшее А = 1000₂ = 8₁₀.

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

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

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

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

Далее применяем обозначения и реализуем способ решения, изложенный К. Ю. Поляковым в теоретических материалах (см., например, раздел «Теория» на нашем сайте), без дополнительных пояснений.

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

Тем самым, наименьшее А = 10001₂ = 17₁₀.

Обо­зна­чим через m&n по­раз­ряд­ную конъ­юнк­цию не­от­ри­ца­тель­ных целых чисел m и n.

Для ка­ко­го наи­мень­ше­го не­от­ри­ца­тель­но­го це­ло­го числа А фор­му­ла

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

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

(¬Х + ¬Y) → (W → ¬Z) = ¬(¬Х + ¬Y) + (¬W + ¬Z) = ХY + ¬(WZ) = WZ → XY.

Далее применяем обозначения и реализуем способ решения, изложенный К. Ю. Поляковым в теоретических материалах (см., например, раздел «Теория» на нашем сайте), без дополнительных пояснений.

Имеем импликацию Z₁₇Z_A → Z₂₈Z₄₅ или Z_{(17 or А)} → Z_{(28 or 45)}. Поскольку 28₁₀ = 11100₂, 45₁₀ = 101101₂, для побитовой дизъюнкции имеем: 28or45 = 111101. Тогда Z_{(17 or А)} = Z₆₁.

Импликация принимает вид Z_{(17 or A)} → Z₆₁. Единичные биты двоичной записи числа 61, должны являться единичными битами левой части. Поэтому в побитовой дизъюнкции 17orA единицы должны стоять на нулевой, второй, третьей, четвертой и пятой позициях (как обычно, считая справа налево, начиная с нуля). Запишем числа 17, А и 61 в двоичной системе счисления, и выясним, что наименьшее число, дающее при поразрядной дизъюнкции единицы на указанных позициях:

В записи наименьшего числа, дающего при поразрядной дизъюнкции с числом 17 единицы в необходимых разрядах, на месте знаков ? должны стоять нули. Тем самым, искомым числом является А = 101100₂ = 44₁₀.

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

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