The logical expression ( a && b ) (both a and b have boolean values) can be written like !(!a || !b), for example. Doesn't this mean that && is "unneccesary"? Does this mean that all logical expressions can be made only using || and !?
294
votes
6 Answers
428
votes
Yes, as the other answers pointed out, the set of operators comprising of || and ! is functionally 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)
Note that both NAND and NOR are by themselves functionally complete (which can be proved using the same method above), so if you want to verify that a set of operators is functionally complete, it's enough to show that you can express either NAND or NOR with it.
Here's a graph showing the Venn diagrams for each of the connectives listed above:
[source]
126
votes
What you are describing is functional completeness.
This describes a set of logical operators that is sufficient to "express all possible truth tables". Your Java operator set, {||, !}, is sufficient; it corresponds to the set {∨, ¬}, which is listed under the section "Minimal functionally complete operator sets".
The set of all truth tables means all possible sets of 4 boolean values that can be the result of an operation between 2 boolean values. Because there are 2 possible values for a boolean, there are 24, or 16, possible truth tables.
A B | 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
----+------------------------------------------------
T T | T T T T T T T T F F F F F F F F
T F | T T T T F F F F T T T T F F F F
F T | T T F F T T F F T T F F T T F F
F F | T F T F T F T F T F T F T F T F
Here is a table of the truth table numbers (0-15), the || and ! combinations that yield it, and a description.
Table | Operation(s) | Description
-------+----------------------------------+-------------
0 | A || !A | TRUE
1 | A || B | OR
2 | A || !B | B IMPLIES A
3 | A | A
4 | !A || B | A IMPLIES B
5 | B | B
6 | !(!A || !B) || !(A || B) | XNOR (equals)
7 | !(!A || !B) | AND
8 | !A || !B | NAND
9 | !(A || !B) || !(!A || B) | XOR
10 | !B | NOT B
11 | !(!A || B) | NOT A IMPLIES B
12 | !A | NOT A
13 | !(A || !B) | NOT B IMPLIES A
14 | !(A || B) | NOR
15 | !(A || !A) | FALSE
There are plenty of other such functionally complete sets, including the one element sets {NAND} and {NOR}, which don't have corresponding single operators in Java.
80
votes
Yes.
All logic gates can be made from NOR gates.
Since a NOR gate can be made from a NOT and an OR, the result follows.
64
votes
Take the time to read up on DeMorgan's Laws if you can.
You will find the answer in the reading there, as well as references to the logical proofs.
But essentially, the answer is yes.
EDIT: For explicitness, my point is that one can logically infer an OR expression from an AND expression, and vice-versa. There are more laws as well for logical equivalence and inference, but I think this one most apropos.
EDIT 2: Here's a proof via truth-table showing the logical equivalence of the following expression.
DeMorgan's Law: !(!A || !B) -> A && B
_____________________________________________________ | A | B | !A | !B | !A || !B | !(!A || !B) | A && B | ------------------------------------------------------- | 0 | 0 | 1 | 1 | 1 | 0 | 0 | ------------------------------------------------------- | 0 | 1 | 1 | 0 | 1 | 0 | 0 | ------------------------------------------------------- | 1 | 0 | 0 | 1 | 1 | 0 | 0 | ------------------------------------------------------- | 1 | 1 | 0 | 0 | 0 | 1 | 1 | _______________________________________________________
11
votes
NAND and NOR are universal they can be used to build up any logical operation you want anywhere; other operator are available in programming languages to make it easy to write and make readable codes.
Also all the logical operations which are needed to be hardwired in circuit are also developed using either NAND or NOR only ICs.
A and B == !A nor !B == !(!A or !B). LikewiseA or B == !A nand !B == !(!A and !B). Obviously passing the same value to both inputs of a NAND or NOR will give the same result as a simple NOT. XOR and XNOR are also possible but more complex. See De Morgan's theorem – Basic