1

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

Так, например, 14 & 5 = 1110 & 0101 = 0100 = 4. Для какого наименьшего неотрицательного целого числа А формула

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

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


Написал функцию этой самой конъюнкции и импликации, затем функцию перебора всех x до 100 при каком либо A, которая вернет False, если хоть одно значение x не прошло.

def conc(n, k):
    n = bin(n)[2:]
    k = bin(k)[2:]
    s = ''
    if len(n) != len(k):
        if len(n) > len(k):
            k = '0' * (len(n) - len(k)) + k
        else:
            n = '0' * (len(k) - len(n)) + n
    for i in range(len(n)):
        if n[i] == k[i]:
            s += '1'
        else:
            s += '0'
    return int(s,2)

def impl(x, y): return not x or y

def F(A):
    for x in range(10000):
        if not impl(conc(x, 29) != 0, impl(conc(x, 17) == 0,conc(x, A) != 0)):
            return False
    return A


for i in range(100):
    if F(i)!=False: print(i)

Функции конъюнкции и импликации вроде правильные, но при выполнении программы выдает все значения от 2 до 100. В ответе к задаче число 12. Где я ошибся, уже часа 2 бьюсь над задачей, но не могу понять??

2
  • А что означает ? 26 апр 2021 в 12:22
  • 1
    Это импликация вроде как, т.е. x»y==not x or y.
    – StupNum
    26 апр 2021 в 12:25

1 ответ 1

3
    if n[i] == k[i]:
        s += '1'
    else:
        s += '0'

Это не побитовое И (конъюнкция), надо чтобы оба разряда не только были равны между собой, но и равны 1 при этом, так что правильно будет так:

    if n[i] == k[i] == '1':
        s += '1'
    else:
        s += '0'

После этого исправления вывод кода такой:

12
13
14
15
28
29
30
31
44
45
46
47
60
61
62
63
76
77
78
79
92
93
94
95

Ваш ответ

By clicking “Отправить ответ”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.