如何相互转换 xor, and, not operators

Question

我正在阅读一篇关于加密哈希函数的论文。它显示了一个我很难理解的公式转换。

Ch(x,y,z) = (x & y) ^ (~x & z)

在上面，&是按位与，^是按位异或，~是按位非。可以简化为：

Ch(x,y,z) = ((y^z)&x)^z

不知道怎么算的

Answer 1

向后工作，从：

开始

((y ^ z) & x) ^ z

分配“&x”：

((y & x) ^ (z & x)) ^ z

删除多余的括号：

(y & x) ^ (z & x) ^ z

通勤操作数：

(x & y) ^ (x & z) ^ z

添加括号：

(x & y) ^ ((x & z) ^ z)

将"A ^ B = (~A & B) | (A & ~B)"应用于右侧：

(x & y) ^ ((~(x & z) & z) | ((x & z) & ~z))

删除多余的括号：

(x & y) ^ ((~(x & z) & z) | (x & z & ~z))

应用"A & ~A = 0":

(x & y) ^ ((~(x & z) & z) | (x & 0))

应用"A & 0 = 0":

(x & y) ^ ((~(x & z) & z) | (0))

应用"A | 0 = A":

(x & y) ^ ((~(x & z) & z))

删除多余的括号：

(x & y) ^ (~(x & z) & z)

应用德摩根定律“~(A & B) = (~A | ~B)”：

(x & y) ^ ((~x | ~z) & z)

分发“&z”：

(x & y) ^ ((~x & z) | (~z & z))

应用"A & ~A = 0":

(x & y) ^ ((~x & z) | (0))

应用"A | 0 = A":

(x & y) ^ (~x & z)

因此，(x & y) ^ (~x & z)等同于((y ^ z) & x) ^ z。

Answer 2

a truth table should convince you it is correct

尝试在 ASCII 艺术中绘制真值表非常乏味，因此对于以下...

z=0      x      z=1      x 
     |  0 1          |  0 1
   --+-------      --+-------      ===     a b   e f
 y 0 |  a b      y 0 |  e f                c d   g h
   1 |  c d        1 |  g h

所以...

x & y  =  0 0   0 0     ~x & z  =  0 0   1 0 
          0 1   0 1                0 0   1 0

因此：

(x&y) ^ (~x&z)  =  0 0   1 0
                   0 1   1 1

现在解决部分问题：

        y ^ z  =  0 0   1 1
                  1 1   0 0

    (y^z) & x  =  0 0   0 1
                  0 1   0 0

((y^z)&x) ^ z  =  0 0   1 0
                  0 1   1 1

令人高兴的是，这与我们对原始表达式的看法相同。

如何相互转换 xor, and, not operators

How to convert xor, and, not operators mutually

c

xor