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

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

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

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

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

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

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

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

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

 

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

for a in range(1000, 1, -1):
    flag = True
    for x in range(10000):
        if ((x & a != 0) <= ((x & 11 == 0) <= (x & 17 != 0))) == False:
            flag = False
            break
    if flag == True:
        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)

Решение аналитически

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

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

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

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

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

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

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

Для всех таких чисел должно быть истинным условие . Значит, двоичная запись числа обязательно должна иметь вид , чтобы при поразрядной конъюнкции с любым числом получался в результате хотя бы один разряд 1. Значит наименьшее число имеет значение . Ответ .

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

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

Решение аналитически

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

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

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

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

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

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

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

Для всех таких чисел должно быть истинным условие . Значит, двоичная запись числа обязательно должна иметь вид , чтобы при поразрядной конъюнкции с любым числом получался в результате хотя бы один разряд 1. Значит наименьшее число имеет значение . Ответ .

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

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, 1, -1):
    if f(a):
        print(a)
        break

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

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

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

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

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

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

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

Значит для истинности отрицания числа должны в двоичном виде принимать вид , где 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(1000, 1, -1):
    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)
        break

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

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

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

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

Переведем в двоичную систему счисления известные числа: 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 & 25 != 0) <= ((x & 17 == 0) <= (x & a != 0))) == False:
            flag = False
    if flag:
        print(a)
        break

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, 1, -1):
    if f(a):
        print(a)
        break

Решение аналитикой

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

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

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

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

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

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

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

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

 

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

for a in range(1000, 1, -1):
    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

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

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

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

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

 

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

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

Решение аналитикой

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

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

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

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

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

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

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

Для всех таких чисел должно быть истинным условие . Значит, двоичная запись числа обязательно должна иметь вид , чтобы при поразрядной конъюнкции с любым числом получался в результате хотя бы один разряд 1. Значит наименьшее число имеет значение . Ответ .

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

def f(a):
    for x in range(1, 1000):
        if ((x & 38 == 0) <= ((x & 55 != 0) <= (x & a != 0))) == 0:
            return False
    return True

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

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

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

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

 

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

def f(a):
    for x in range(1, 1000):
        if ((x & 65 == 0) <= ((x & 91 != 0) <= (x & a != 0))) == 0:
            return False
    return True

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

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

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

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

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

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

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

 

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

def f(a):
    for x in range(1, 1000):
        if ((x & 41 == 0) <= ((x & 119 != 0) <= (x & a != 0))) == 0:
            return False
    return True

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

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

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

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

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

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

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

 

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

def f(a):
    for x in range(1, 1000):
        if ((((x & 13 != 0) or (x & 39 == 0)) <= (x & 13 != 0)) or ((x & a == 0) and (x & 13 == 0))) == 0:
            return False
    return True

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