295

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 !?

Improve this question
16
  • 84
    This is more of a basic symbolic logic question than a Java issue, but yes. OR and NOT in combination can be used to construct everything else. The same with AND and NOT. For instance, when I was in school we were taught to build everything using only NAND gates because they took fewer transistors. Commented Oct 15, 2015 at 17:58
  • 80
    Don't confuse the capability to write a statement this way with the desirability to do so. Syntactic sugar is a good thing. Commented Oct 15, 2015 at 17:59
  • 20
    Many logic gate chips only provide NAND or NOR gates as it's possible to implement all operations with them and it makes them cheap to produce - A and B == !A nor !B == !(!A or !B). Likewise A 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 Commented Oct 15, 2015 at 22:52
  • 17
    Isn't this a computer science question? I see no code here. In particular, whether this is true in practice will vary by implementation, e.g. in C++ with operating overloading it's not in general. Commented Oct 16, 2015 at 13:11
  • 6
    @SnakeDoc I don't think anyone here is advocating to do such a thing. I believe this question was more of theoretical logic question, than a programming one, really. Commented Oct 16, 2015 at 19:00

6 Answers 6

Reset to default
430

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:

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:

enter image description here

[source]

Improve this answer
Sign up to request clarification or add additional context in comments.

6 Comments

It's hard to tell whether the question intends this, but this answer doesn't address short-circuit behaviour (relevant, since the question asks about || rather than |) or side-effects (relevant because the expansion of true, false, XOR and XNOR evaluate their arguments more times than the original constant or operator did).
The circles containing circles and the transitions form a Hasse Diagram (en.wikipedia.org/wiki/Hasse_diagram). (Yay, I learned something new today!)
@DavidRicherby That's true. Other than the XOR, XNOR, true, and false, as far as I can tell, the side effects and number of evaluations should be the same as built-in equivalents (e.g. !(!A || !B) has the same short-circuiting and evaluation count as A && B). I don't think you can do this for XOR and XNOR without additional constructs (e.g. a ? !b : b), and true or false isn't a problem if you can save values, since you could start your program by defining true and false using some dummy boolean variable.
It's interesting to note that the list above comprises 16 operations. This is consistent with the fact that there are 16 possible truth tables for the case where you have 2 inputs and 1 output.
Just wanted to add another visualization as a table for people's reference. Same source as above.
|
126

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.

Improve this answer

2 Comments

+1 for the edit. Despite the difference in vote counts, I think your answer is actually more detailed than mine now.
Truth Tables i thought i had left them behind after first year in university
80

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.

Improve this answer

6 Comments

@PaulDraper or NAND gates
It took 4100 NOR gates to land two people on the moon.
@HansPassant And some string. Lots of string. (Core rope memory, not the tin can variety.)
@HansPassant Sometimes I wish Stack Exchange was Wikipedia, then I would insert a [citation-needed] mark right there.
Yes, sorry, Apollo guidance computer.
|
64

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    |
_______________________________________________________
Improve this answer

5 Comments

Some people have to down vote as part of their "functional completeness"
At +27/-2, I wouldn't worry much about a stray downvote.
@MichaelKjörling I'm just curious why some people thought my answer was not helpful / was harmful.
Generally answers that rely on links aren't liked too much (as links die), but in this case any there are so many alternative explanations of DeMorgan's Laws, that I don't see an issue - still, that's my guess as to the DV's
@user2813274 Thanks for the explanation. Hopefully, my edits will help bridge the gap between personal research and getting to the answer.
11

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.

Improve this answer

Comments

10

Yes, according to Boolean algebra, any Boolean function can be expressed as a sum of minterms or a product of maxterms, which is called canonical normal form. There is no reason why such logic couldn't be applied to the same operators used in computer science.

https://en.wikipedia.org/wiki/Canonical_normal_form

Improve this answer

Comments

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.