Are || and ! operators sufficient to make every possible logical expression?
"
[...] the set of operators comprising of
||
and !
isfunctionally complete. Here's a constructive proof of that, showing how to use them to express all sixteen possible logical connectives between the boolean variables A
and B
:- True:
A || !A
- A NAND B:
!A || !B
- B implies A:
!B || A
- A implies B:
!A || B
- A OR B:
A || B
- Not B:
!B
- Not A:
!A
- A XOR B:
!(!A || B) || !(A || !B)
- A XNOR B:
!(!A || !B) || !(A || B)
- A:
A
- B:
B
- A NOR B:
!(A || B)
- A does not imply B:
!(!A || B)
- B does not imply A:
!(!B || A)
- A AND B:
!(!A || !B)
- False:
!(A || !A)
See the fill answer here
No comments:
Post a Comment