Можно ли написать вентиль AND, используя ворота XOR?

21

Как я могу выразить И-ворота, используя только ворота XOR?

user2991856
источник
1
почему вы хотите выразить и ворота с помощью xor и в чем?
ABD
1
Я читаю кое-что о гомоморфном шифровании, а именно этот документ eprint.iacr.org/2013/094.pdf, также известный как схема LTV. Там указано, что умножение означает AND, сложение между двумя битами означает XOR. Поэтому я спрашиваю, можно ли переписать схему, используя только XOR? Может быть, мне следует перенести вопрос в бета-версию Cryptography?
user2991856
4
Связанный: функциональная полнота
CodesInChaos
2
Связанный: stackoverflow.com/questions/6106934/…
rackandboneman

Ответы:

36

Вы не можете.

Поскольку является ассоциативным, т. Е. ( X 1x 2 ) x 3 = x 1( x 2x 3 ) , вы можете реализовать только функции вида x i 1. , , х я K , где х я J{ х 1 , х 2 }ИксОр(Икс1Икс2)Икс3знак равноИкс1(Икс2Икс3)Икся1,,,ИксяКИксяJ{Икс1,Икс2}, Это эквивалентно (в зависимости от четности числа экземпляров и x 2 ) либо 0, x 1 , x 2 или x 1x 2 , которые не эквивалентны AND.Икс1Икс2Икс1Икс2Икс1Икс2

Ariel
источник
5
Вы также можете использовать 0 и 1 в качестве входных данных. Вы все равно не получите И, хотя вы также получите отрицание и выше.
Taemyr
19

Хммм. Это не может быть сделано с булевой алгеброй, это точно, но я мог бы связать ее физически. Хитрость заключается в подключении одного из входов к выводу питания затвора XOR.

                     I2
                     |
      0  I1          |
      |   |          |
     \|   |/         |
     |\   / |        |
.|---| \ /  |--------/
     \  V  /  
      \   /  
       \ /  
        V 
        |            
     AND OUTPUT

Вентиль XOR подключен как неинвертирующий буфер. Уловка заключается в том, что если вы подключаете VCC к GND (или, если расширять, логическое заземление), выходной сигнал будет слабым GND.

Отказ от ответственности: это работает на кремнии у меня есть, но может не работать на всех кремния.

Джошуа
источник
8
Некоторое объяснение того, как это работает, сделало бы это намного лучшим ответом.
Дэвид Ричерби
Разве первые ворота не избыточны в этом случае?
Nit
1
Что это .|, |>?
Wojowu
1
@ Wojowu Ground и Vcc, я полагаю.
Джон Дворак
4
«может не работать на всех кремния». ... да, и может даже повредить некоторые из них - применение входа к физическому вентилю с выключенным питанием или, что еще хуже, последующее включение питания, для многих деталей нецелесообразно (re: CMOS latchup effect !). Кроме того, «истинное» выходное напряжение первого вентиля ниже вашего напряжения питания, и в зависимости от того, насколько оно ниже, значительно изменит интерпретацию входных уровней во втором вентиле. И весьма вероятно (защитные диоды, дополнительный выход ...), что I2 будет эффективным коротким замыканием на землю, когда нижний затвор отключен.
rackandboneman