This file contains Unicode characters that might be confused with other characters. If you think that this is intentional, you can safely ignore this warning. Use the Escape button to reveal them.
定义
FF2(X, Y, Z) = (X \land Y) \lor (X \land Z) \lor (Y \land Z)
GG2(X, Y, Z) = (X \land Y) \lor (\lnot X \land Z)
等价公式
FF2(X, Y, Z) = (X \land Y) \bigoplus (X \land Z) \bigoplus (Y \land Z)
GG2(X, Y, Z) = (X \land Y) \bigoplus (\lnot X \land Z) = (X \land Y) \bigoplus ((1 \bigoplus X) \land Z) = (X \land Y) \bigoplus (X \land Z) \bigoplus Z = (Y \bigoplus Z) \land X \bigoplus Z
GG2等价公式初次见于Intel® Integrated Performance Primitives Cryptography
应用
特别是GG2，其等价公式相比原来的公式，因其简单，具有一点点性能优势（不明显），也可以省一个寄存器，还有就是ANDN指令属于BMI1，有些老机器不支持。
原公式：
MOVL f, y3; \
ANDL e, y3; \ // y3 = e AND f
ANDNL g, e, y1; \ // y1 = NOT(e) AND g
ORL y3, y1; \ // y1 = (e AND f) OR (NOT(e) AND g)
等价公式：
MOVL f, y1; \
XORL g, y1; \
ANDL e, y1; \
XORL g, y1; \ // y1 = GG2(e, f, g)
验证
| X | Y | Z | (X \land Y) \lor (X \land Z) \lor (Y \land Z) |
(X \land Y) \bigoplus (X \land Z) \bigoplus (Y \land Z) |
(X \land Y) \lor (\lnot X \land Z) |
(Y \bigoplus Z) \land X \bigoplus Z |
|---|---|---|---|---|---|---|
| 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| 0 | 0 | 1 | 0 | 0 | 1 | 1 |
| 0 | 1 | 0 | 0 | 0 | 0 | 0 |
| 0 | 1 | 1 | 1 | 1 | 1 | 1 |
| 1 | 0 | 0 | 0 | 0 | 0 | 0 |
| 1 | 0 | 1 | 1 | 1 | 0 | 0 |
| 1 | 1 | 0 | 1 | 1 | 1 | 1 |
| 1 | 1 | 1 | 1 | 1 | 1 | 1 |
证明
Ask help https://math.stackexchange.com/questions/4775054/how-to-prove-below-two-logic-formulas
GG2(X,Y,Z)
= (X \land Y) \bigoplus (\lnot X \land Z)
= (\lnot (X \land Y) \land (\lnot X \land Z)) \lor ((X \land Y) \land (\lnot (\lnot X \land Z)))
= ((\lnot X \lor \lnot Y) \land (\lnot X \land Z)) \lor ((X \land Y) \land (X \lor \lnot Z))
= (\lnot X \land Z) \lor (\lnot X \land \lnot Y \land Z) \lor (X \land Y) \lor (X \land Y \land \lnot Z)
= ((\lnot X \land Z) \lor (\lnot X \land Z \land \lnot Y)) \lor ((X \land Y) \lor (X \land Y \land \lnot Z))
= ((X \land Y) \land (1 \lor \lnot Z)) \lor ((\lnot X \land Z) \land (1 \lor \lnot Y))
= (X \land Y) \lor (\lnot X \land Z)
FF2(X, Y, Z) = (X \land Y) \bigoplus (X \land Z) \bigoplus (Y \land Z)
(X \land Y) \bigoplus (X \land Z)
= X \land (Y \bigoplus Z)
= X \land ((Y \land \lnot Z) \lor (\lnot Y \land Z))
= (X \land Y \land \lnot Z) \lor (X \land Z \land \lnot Y)
(X \land Y) \bigoplus (X \land Z) \bigoplus (Y \land Z)
= (\lnot((X \land Y \land \lnot Z) \lor (X \land Z \land \lnot Y)) \land (Y \land Z)) \lor (((X \land Y \land \lnot Z) \lor (X \land Z \land \lnot Y)) \land (\lnot Y \lor \lnot Z))
\lnot((X \land Y \land \lnot Z) \lor (X \land Z \land \lnot Y)) \land (Y \land Z)
= \lnot(X \land Y \land \lnot Z) \land \lnot(X \land Z \land \lnot Y) \land (Y \land Z)
= (\lnot X \lor \lnot Y \lor Z) \land (\lnot X \lor \lnot Z \lor Y) \land (Y \land Z)
= (\lnot X \lor (\lnot X \land \lnot Z) \lor (\lnot X \land Y) \lor (\lnot X \land \lnot Y) \lor (\lnot Z \land \lnot Y) \lor (Z \land \lnot X) \lor (Z \land Y)) \land (Y \land Z)
= $(\lnot X \lor (\lnot X \land \lnot Z) \lor (Z \land \lnot X) \lor (\lnot X \land Y) \lor (\lnot X \land \lnot Y) \lor (\lnot Z \land \lnot Y) \lor (Z \land Y)) \land
(Y \land Z) $
= (\lnot X \lor ((\lnot X \land \lnot Z) \lor (Z \land \lnot X)) \lor ((\lnot X \land Y) \lor (\lnot X \land \lnot Y)) \lor (\lnot Z \land \lnot Y) \lor (Z \land Y)) \land (Y \land Z)
= (\lnot X \lor (\lnot Z \land \lnot Y) \lor (Z \land Y)) \land (Y \land Z)
= (Y \land Z)
((X \land Y \land \lnot Z) \lor (X \land Z \land \lnot Y)) \land (\lnot Y \lor \lnot Z)
= (X \land Y \land \lnot Z) \lor (X \land Z \land \lnot Y)
(X \land Y \land \lnot Z) \lor (X \land Z \land \lnot Y) \lor (Y \land Z)
= (X \land Y \land \lnot Z) \lor (X \land Z \land \lnot Y) \lor (Y \land Z) \lor (X \land Y \land Z) \lor (X \land Y \land Z)
= (X \land Y \land \lnot Z) \lor (X \land Y \land Z) \lor (X \land Z \land \lnot Y) \lor (X \land Y \land Z) \lor (Y \land Z)
= (X \land Y) \lor (X \land Z) \lor (Y \land Z)
相关知识：
A \bigoplus B = (\lnot A \land B) \lor (A \land \lnot B)- Boolean algebra
- 布尔代数运算律