15.04 Побитовая конъюнкция

for a in range(1000):
    flag = 0
    for x in range(1000):
        if ((x & 51 == 0) or ((x & 42 == 0) <= (x & a != 0))) == False:
            flag = 1
    if flag == 0:
        print(a)
        break

for a in range(1000):
    flag = 0
    for x in range(1000):
        if ((x & 39 == 0) or ((x & 41 == 0) <= (x & a != 0))) == False:
            flag = 1
    if flag == 0:
        print(a)
        break

Введем обозначение: Тогда данное выражение перепишется в виде

Воспользуемся тем, что Тогда наше выражение имеет вид

Теперь воспользуемся тем же, только в обратную сторону. Запишем выражение так:

Помним, что Значит, нам нужно найти наибольшее неотрицательное целое такое, что

мы можем сразу вычислить. Так как можем выполнить поразрядное сложение:

Чтобы импликация была истинна, нам нужно, чтобы на тех местах, где справа стоит единица (в двоичной записи числа), слева она стояла тоже.

Таким образом, единица может стоять на тех местах, где она стоит в двоичной записи числа слева — необязательно, но если где-то и стоит, то только там. Но вспомним, что мы ищем максимальное : значит, мы хотим, чтобы в было как можно больше единиц. А так как единицы могут быть только на тех местах, где стоят единицы в наибольшее возможное — это и есть

Введем обозначение: Тогда наше выражение имеет вид:

Так как получаем Так как

Тогда посчитаем

Тогда наше выражение имеет вид Это то же самое, что

Мы сразу можем определить, истинна ли

Нет, не истинна, т.к. на первом месте, например, в двоичной записи 17 стоит 0, а на первом в двоичной записи 58 — 1. Значит, нужно, чтобы истинна была импликация

Мы ищем наибольшее Чтобы импликация истинна, на тех местах, где в двоичной записи A стоят единицы, стоят единицы и в двоичной записи 17. То есть больше единиц, чем есть в 17, в записи быть не может. Тогда наибольшее — это и есть само 17.

Программное решение

for a in range(1,1000):
    flag = True
    for x in range(10000):
        if (((x & 23 == 0) or (x & 17 == 0)) <= ((x & 58 != 0) <= (x & a == 0))) == False:
            flag = False
            break
    if flag == True:
        print(a)

def f(a):
    for x in range(1000):
        if not((x & 17 == 0) <= ((x & 33 != 0) <= (x & a != 0))):
            return False
    return True

for a in range(1000):
    if f(a):
        print(a)
        break

def f(a):
    #если отрцание формулы возвращает истину,
    # то сама формула возвращает ложь
    for x in range(1000):
        if not((x & 15 == 0) <= ((x & 29 != 0) <= (x & a != 0))):
            return False
    return True

for a in range(1000):
    if f(a):
        print(a)
        break

def f(a):
    # если отрцание формулы возвращает истину,
    # то сама формула возвращает ложь
    for x in range(1000):
        if not((x & a != 0) <= ((x & 10 == 0) <= (x & 5 != 0))):
            return False
    return True

for a in range(1000):
    if f(a):
        print(a)

Решение руками

Для начала упростим данное выражение:

Раскроем импликации:

Разделим известную часть и выражения с :

Сделаем отрицание известной части, чтобы найти те значения , которые будут давать истину для отрицания.

Тогда они будут обязаны выполняться для условия с :

Выпишем поразрядную конъюнкцию :

Значит для истинности отрицания числа должны в двоичном виде принимать вид , где x – любая цифра

Теперь выпишем поразрядные конъюнкции с учётом известных цифр в числах :

Условие не выполнится, так как для уже известных цифр чисел результат поразрядной конъюнкции будет равен 0.

Условие выполнится, если хотя бы одна цифра на месте x будет равна 1. Выпишем числа , которые дают истину для отрицания известной части:

Для этих чисел должно быть истинным условие . Значит, в числе обязательно должны быть единицы в двоичном виде на разрядах 1 и 5 при нумерации с 0 справа налево. Значит наименьшее число имеет значение . Ответ 34.

Программное решение

for a in range(1000):
    flag = True
    for x in range(10000):
        if (((x & 47 != 0) or (x & 24 != 0)) <= ((x & 29 == 0) <= (x & a != 0))) == False:
            flag = False
            break
    if flag == True:
        print(a)
        break

for a in range(0, 1000):
    flag = True
    for x in range(0, 1000):
        if ((x & a != 0) <= (((x & 17 == 0) and (x & 5 == 0)) <= (x & 3 != 0))) == False:
            flag = False
            break
    if flag:
        print(a)

Обозначим Перепишем: для любых

Воспользуемся тем, что Тогда Теперь воспользуемся тем же в обратную сторону: соберем импликацию. Получим

Помним, что Тогда

Переведем в двоичную систему счисления известные числа: 17 = 10001, 25 = 11001.

\(\)

r _& 10001;
;

\(\)

Известно, что, чтобы данная импликация была равна 1, на тех местах, где в двоичной записи 25 стоят единички, в двоичной записи должны тоже стоять единички.

Мы ищем наименьшее неотрицательное целое число Значит, где вместо звездочек можно ставить нули, — будем ставить. Двигаемся справа налево. На место первой звездочки можно поставить 0 — единичка уже есть в записи числа 17. На втором месте все равно, что ставить, — в записи 25 на этом месте 0. Ставим 0. Аналогично ставим на третье место. Теперь посмотрим на четвертое: в записи 25 — стоит 1, а вот в записи 17 — 0. Значит, на четвертом месте в числе должна быть единичка. Аналогично заканчиваем ставить знаки. Никаких лишних разрядов впереди числа добавлять не будем — мы ищем наименьшее.

Итак, получили 1000. Это число в двоичной системе счисления. В десятичной — 8.

for a in range(0, 100):
    flag = True
    for x in range(0, 10000):
        if (((x & 47 != 0) or (x & 24 != 0)) <= ((x & 29 == 0) <= (x & a != 0))) == False:
            flag = False
    if flag:
        print(a)
        break

def f(a):
    # если отрцание формулы возвращает истину,
    # то сама формула возвращает ложь
    for x in range(1000):
        if not((x & a != 0) <= ((x & 14 == 0) <= (x & 3 != 0))):
            return False
    return True

for a in range(1000):
    if f(a):
        print(a)

Преобразуем выражение к виду с помощью законов де Моргана:

Для того, чтобы выражение вида являлось истинным, единичные биты, стоящие в правой части, должны являться единичными битами левой.

Запишем числа 10 и 5 в двоичной системе счисления:

Значит, обязательно должно содержать в себе единицу во всех разрядах. Так как ищем наибольшее , наш ответ .

Преобразуем выражение к виду с помощью законов де Моргана:

Заметим, что если , то последнее выражение всегда , а следовательно последняя скобка всегда , то есть выражение имеет вид:

, а это всегда истинно.

Нам нужно минимальное неотрицательное целое число , значит наш ответ .

 

Решение программой:

for a in range(1000):
    fl = 0
    for x in range(1000):
        if ((x & a != 0) <= ((x & 10 == 0) <= (x & 5 != 0))) == 0:
            fl = 1
            break
    if not fl:
        print(a)
        break

Враги хотят подобрать такой, что . Тогда на всех разрядах где у 38 единички будут нули и в одном из разрядов или в двух одновременно (где у 38 в двоичной записи нули, а у 55 единички) будут единички. Во всех остальных разрядах будут нули чтобы была больше вероятность истинности .

Тогда друзья чтобы поставят единички где они гарантированно могут появится в . Это будет число .

Враги хотят подобрать такой, что . Тогда на всех разрядах где у 65 единички будут нули и в одном из разрядов или в двух одновременно (где у 65 в двоичной записи нули, а у 91 единички) будут единички. Во всех остальных разрядах будут нули чтобы была больше вероятность истинности .

Тогда друзья чтобы поставят единички где они гарантированно могут появится в . Это будет число .

Враги хотят чтобы одновременно , , .

Для выполнения первого условия должен иметь вид _ _ _ 0 _ 0 _ _ 0. На месте _ может стоять либо 0, либо 1.

Для выполнения и второго условия должен иметь вид _ _ * 0 * 0 * * 0. На месте хотя бы одной звездочки должна стоять единичка.

Для выполнения третьего условия единиц должно быть как можно меньше, значит должен иметь вид 0 0 * 0 * 0 * * 0. На месте только одной звездочки должна стоять единица.

Тогда друзья подберут такое минимальное чтобы . Друзьям достаточно подставить единички в тех местах где они могут появиться в . Итоговое .

Враги хотят чтобы одновременно , , .

Для выполнения первого условия должен иметь вид _ _ _ _ 0 0 _ 0. На месте _ может стоять 1 или 0.

Для выполнения и второго условия должен иметь вид _ _ 0 _ 0 0 0 0.

Для выполнения третьего условия единиц в должно быть как можно больше. Тогда он имеет вид ...1 1 0 1 0 0 0 0.

Друзья хотят такое максимальное чтобы . Тогда на местах с единицами в будут нули, а на местах нулей будут единицы. Значит .