задачка, компьютерное

[avva]

Убил на нее немало времени сегодня, но очень понравилась:

Придумайте схему, у которой есть три входа A, B, C и три выхода not-A, not-B, not-C. Можно пользоваться элементами AND, OR и NOT, но AND и OR сколько угодно, а NOT не более двух штук.

Я на время постараюсь скрывать правильные ответы. Но у меня есть предложение: если вы уже знаете решение, или нашли его компьютерным перебором, не пишите его в комментах - напишите просто, что нашли, например. Нет ничего плохого в компьютерном переборе, но не всем интересно. Мне хотелось именно найти решение самому аналитическим путем.

Comments

[unsignedlong.livejournal.com]

сделать новый "my_not"

1)x xor 1 = not x

2)z or (not z ) = 1 (это для единички в xor)
3)xor = not(z) * y + not(y)+z

not(z) можно использовать из единички, которую получили в формуле 2

[avva.livejournal.com]

с третьим пунктом что-то не так, вам же надо вычислять не y xor z, а x xor 1, т.е. по формуле третьего пункта нужно будет еще отдельно not x.

[sleeping-death.livejournal.com]

xor=not(ZY)(Y+Z)

[(Anonymous)]

неинтересно, слишком много условий.

[unsignedlong.livejournal.com]

это не условия

[burrru.livejournal.com]

На ум сразу приходят фамилии: Карацуба и Штрассен...

[avva.livejournal.com]

Я их кстати так и не изучил, все эти быстрые умножения :(

[adp.myopenid.com (from livejournal.com)]

Кстати говоря, к решению этой задачи вышеупомянутые алгоритмы отношения, по-моему, не имеют. Карацуба осуществляет метод вычисление-умножение-интерполяция, Штрассен - вообще непонятно какой (трактовок много, но ни одна не обобщается на большие размерности, задача сложности умножения матриц до сих пор не решена), здесь же - чистый анализ множеств на гиперкубе.

[alexeybobkov]

О, я её лет десять назад решил аналитически.
Что интересно, вначале я доказал, что это невозможно :). Потом понял, что не учёл, что выход с одного инвертора можно завести на другой (через промежуточную логику, разумеется). Когда понял, задача сразу решилась.
Одно время схема у меня даже висела на стенке.
Могу восстановить, если надо.

В общем, в мире есть всего два инвертора. Не дай Бог один сгорит.

[avva.livejournal.com]

В общем, в мире есть всего два инвертора. Не дай Бог один сгорит.

О!

[alexeybobkov]

P.S. Слышал, что задача легко решается на Прологе. Было бы полезное упражнение, наверное. Сам я, однако, не настолько хороший знаток Пролога, чтобы её решить.

[renivid.livejournal.com]

Заводим A, B, C на AND, результ - на NOT, получаем !A+!B+!C дальше можно отделить A, B и С с помощью ИЛИ и пар B+C, A+C и A+B. Или я неправльно понял условия :).

[avva.livejournal.com]

попробуйте выписать точнее, и увидите, что это не так просто :)

[(Anonymous)]

похоже что из not(A) or not(B) or not(C) трудно получить отдельно not(A) и остальные

[(Anonymous)]

Любую логическую схему можно реализовать на двух NOT.

[(Anonymous)]

Ну то есть да, конечно. Если три инвертора можно построить из двух, то и больше тоже можно. Duh.

[adp.myopenid.com (from livejournal.com)]

Не буду портить удовольствия решения :-) Замечу только, что это - частный случай более общей задачи: как реализовать при неограниченном количестве AND и OR n отрицаний NOT x_1, ..., NOT x_n. Можно доказать, что для этого достаточно целой части сверху log_2 (n+1). Справедлива аналогичная нижняя оценка.

[spamsink.livejournal.com]

not_A = (A+B+C) == 0 || (A+B+C) == 1 && (B || C) || (A+B+C) == 2 && B && C

Дальше подсказывать не буду.

У вас ошибка

[adp.myopenid.com (from livejournal.com)]

Если приоритет операций классический, то правая часть равна 1 при A = 1, B = 1, C = 0, а левая - нет.

[g00d.livejournal.com]

X1 = not (A * C)
X2 = not (B + C)

not C = (X1 * X2)

X3 = X1 * (not C)
X4 = X2 + (not C)

not A = (X1 * X3)
not B = (X2 * X4)

Неверно

[adp.myopenid.com (from livejournal.com)]

A = 1, B = 1, C = 0 => X1 = 1, X2 = 0, X1 * X2 = 0 = C.

[ao-terekhov.livejournal.com]

А как эта задача решается компьютерным перебором?

[avva.livejournal.com]

Думаю об этом отдельную запись написать.

[1benrinnes.livejournal.com]

http://domino.research.ibm.com/Comm/wwwr_ponder.nsf/Challenges/August2009.html

[avva.livejournal.com]

nice.

[burivykh.livejournal.com]

Ну, поскольку "и" и "или" позволяют делать монотонные функции, то первый инвертор вешается на "A+B+C >= 2"; после этого выясняется, что XOR всех трёх A,B,C от них и от первого инвертора монотонна, и второй инвертор вешаем на неё. А теперь на каждом "возрастающем" ребре хоть один из инверторов, да убывает, поэтому все отрицания можно собрать.

Формально:
X=NOT (AB OR AC OR BC)
Y=NOT (((A OR B OR C) X) OR ABC).

NOT A = (X (Y OR B OR C)) OR (YBC)

Вроде, так...

[oxfv.livejournal.com]

Поленился решать головой и написал программу. Работает 15 секунд, наверняка можно улучшить.

a = 0x0f
b = 0x33
c = 0x55

# three stages of list proliferation: before the first ~, after the first ~, after the second ~
# the stage counts picked empirically
stages = [3,2,2]

# adds to the list l all values that could be computed out of its elements with & and |
def proliferate_list(l, stage, d = None):

    for i in range(stages[stage]):
        lset = frozenset(l)
        for v1 in lset:
            for v2 in lset:
                if v1 < v2:     # for all unique pairs in l
                    if not (v1 & v2) in l:     l.append( v1 & v2 )
                    if not (v1 | v2) in l:     l.append( v1 | v2 )

                    if d:
                        # wraps operand in round brackets only when needed
                        def wrap_operand( s, operation ):
                            balance = 0
                            for c in s:
                                if c in ['&','|'] and balance==0:
                                    return (c==operation) and s or '(%s)'%s
                                elif c=='(':    balance += 1
                                elif c==')':    balance -= 1
                            return s

                        # keep the most concise expression for each value
                        s = wrap_operand(d[v1],'&') + '&' + wrap_operand(d[v2],'&')
                        if not d.has_key(v1&v2) or len(d[v1&v2])>len(s):  d[v1&v2] = s

                        s = wrap_operand(d[v1],'|') + '|' + wrap_operand(d[v2],'|')
                        if not d.has_key(v1|v2) or len(d[v1|v2])>len(s):  d[v1|v2] = s
    if d:
        return l, d
    else:
        return l


try:
    l = proliferate_list([a,b,c],0)
    for v1 in l:
        x = 0xff & ~v1
        l1 = proliferate_list(l+[x], 1)
        for v2 in l1:
            y = 0xff & ~v2
            if not y in l1:
                l2 = proliferate_list(l1+[y], 2)

                if len(set([0xf0, 0xcc, 0xaa]) & set(l2)) == 3:   # all three of ~a,~b,~c are found
                    # repeat the proliferation steps, this time keeping the dictionary of expressions
                    d = { a:'a', b:'b', c:'c', x:'x', y:'y' }
                    l3,d = proliferate_list([a,b,c],0,d)
                    print '  x = ~(%s)' % d[v1]   # have to print x here lest the more concise but y-dependent expression replaces it
                    l3,d = proliferate_list(l3+[x],1,d)
                    print '  y = ~(%s)' % d[v2]
                    l3,d = proliferate_list(l3+[y],2,d)

                    for v in [a, b, c]:
                        print '  ~%s: %s' % (d[v], d[0xff&~v])
                    raise Exception
except:
    pass

Вот её результат:

  x = ~((a&b)|((a|b)&c))
  y = ~((a&b&c)|((a|b|c)&x))
  ~a: ((b|c)&x)|(y&((b&c)|x))
  ~b: ((a|c)&x)|(y&((a&c)|x))
  ~c: ((a|b)&x)|(y&((a&b)|x))

7 минут

[gurka-ju.livejournal.com]

муж случайно нашел эту задачку

если А Б С принять за 0 1 2 ...
тогда
А&(Б||C)= ^B || ^C
B&C = ^A....

на этом, кажется, все...

Re: 7 минут

[adp.myopenid.com (from livejournal.com)]

Что такое А&(Б||С), когда A Б С = 0 1 2?

[ijon-ru.livejournal.com]

x4 = B and C
x6 = A and C
x7 = A and B
n1 = not (x4 or x6 or x7)
z2 = n1 and C
z3 = n1 and B
z5 = n1 and A
n2 = not (z2 or z3 or z5 or (A and B and C))
z1 = n1 and n2
z4 = x4 and n2
z6 = x6 and n2
z7 = x7 and n2
notA = z1 or z2 or z3 or z4
notB = z1 or z2 or z5 or z6
notC = z1 or z3 or z5 or z7

По совместительству код на Питоне:
c = 2
s = ''
for A in range(c):
for B in range(c):
for C in range(c):
...
s += '%i %i %i | %i %i %i | %i %i %i\n' % \
(A, B, C, not A, not B, not C, notA, notB, notC)
print s

[bronyuk.ru (from livejournal.com)]

http://bronyuk.ru/s_pomoshcyu_dvuh_otritsaniy_sdelat_tri.html

[(Anonymous)]

X = NOT(A AND B)
NOT(A) = B OR X
NOT(B) = A OR X
NOT(C) = NOT(C)
Как то уж очень просто.

[(Anonymous)]

даже так:
X=NOT(A AND B AND C)
NOT(A) = X OR B OR C
NOT(B) = X OR A OR C
NOT(C) = X OR A OR B