New answers tagged boolean-algebra
1
If $f,g$ are two $\pm1$-valued functions and $f \lor g$ is their maximum (this is the standard notation for maximum; $\land$ stands for minimum), then
$$
f \lor g = \frac{1 + f + g - fg}{2}.
$$
Since $\chi_S \chi_T = \chi_{S \Delta T}$, this shows that
$$
\chi_S \lor \chi_T = \frac{1}{2} + \frac{\chi_S}{2} + \frac{\chi_T}{2} - \frac{\chi_{S\Delta T}}{2}.
$$
...
Top 50 recent answers are included
Related Tags
boolean-algebra × 221logic × 51
complexity-theory × 28
circuits × 22
satisfiability × 20
algorithms × 19
digital-circuits × 18
propositional-logic × 13
karnaugh-map × 12
arithmetic × 9
optimization × 7
machine-learning × 6
3-sat × 6
computer-architecture × 5
discrete-mathematics × 5
turing-machines × 4
np-complete × 4
polynomials × 4
learning-theory × 4
xor × 4
graphs × 3
np-hard × 3
proof-techniques × 3
combinatorics × 3
neural-networks × 3