Are || and ! operators sufficient to make every possible logical expression?

Question

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

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. — azurefrog, Oct 15 '15 at 17:58
Don't confuse the capability to write a statement this way with the desirability to do so. Syntactic sugar is a **good** thing. — azurefrog, Oct 15 '15 at 17:59
See also "How to make logical OR with AND,and NOT?" at http://stackoverflow.com/questions/8374895/how-to-make-logical-or-with-and-and-not — Andy Thomas, Oct 15 '15 at 18:01
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 — Basic, Oct 15 '15 at 22:52
Yes, using ! and || operators is even more options than NOR - the fact that NOR gates are sufficient means you can build all logic exclusively with expressions of the form !(A || B). — Random832, Oct 16 '15 at 04:23
you can build a working computer and RAM just using NAND. that also means you can build stackoverflow site with only NAND gate :) — Gorkem, Oct 16 '15 at 09:26
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. — Lightness Races in Orbit, Oct 16 '15 at 13:11
In fact, you only need _one_ logical expression to express all logical operators: The Sheffer stroke, or "not both": https://en.wikipedia.org/wiki/Sheffer_stroke — user151841, Oct 16 '15 at 15:54
People seeing this question might like this [TED talk](https://www.ted.com/talks/shimon_schocken_the_self_organizing_computer_course?language=en). It's about building a computer using only NAND gates. — displayName, Oct 16 '15 at 16:33
Please don't go writing code using nothing but `||` and `!` - it will be very unreadable and future devs may not easily grasp the code intention. Not to mention the compiler and/or hardware will ultimately do what it believes is best, ie. hardware modules will already only have NAND gates and all your code will be thrown through it, so no need to try to use only NAND (or NOR) in your code. — SnakeDoc, Oct 16 '15 at 17:02
@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. — ryuu9187, Oct 16 '15 at 19:00
Also relevant [One Instruction Set Ccomputer](https://en.wikipedia.org/wiki/One_instruction_set_computer). In the usual implementation the instruction is "subtract branch if negativel", but it isn't abbreviated `sbn` because there is no need to write it. Assembly code consists of ordered triples. — dmckee --- ex-moderator kitten, Oct 19 '15 at 01:18
You can create all logical expressions using "or" || and "not" ! operators, but it doesn't mean that you should. Introducing "not" operator usually makes code more complicated to read, can be source of mistakes and misunderstandings. You should avoid "not" operator when you can. You can even replace || with + (addition) and && with * (multiplication), so you can skip more logical operators! Addition and multiplication are identical with "or" and "and" for primitive boolean data types. You can do all of that stuff, but do you really want to make your code less readable and harder to maintain? — Piotr Wittchen, Oct 20 '15 at 17:38
@piotr.wittchen Do you have any links or references to best practices stating that you should avoid the not operator? I think it's completely circumstantial when the not operator makes code more or less readable. While I agree that you should generally have the minimum operators while making the code still readable, I don't agree that you should generally avoid any specific operator. And to my knowledge, you cannot replace || with addition or && with star. — ryuu9187, Oct 20 '15 at 18:37
@jason9187 You're right. I don't have any reference to practice of avoiding operator, but in my opinion, if you can use less amount of operators, you should do it, as you said. Generally, you shouldn't replace || with addition and && with star, but when you have two boolean values you can do that in conditional statement and it will work. Maybe it won't work in every language, but in C++ it works. — Piotr Wittchen, Oct 20 '15 at 19:13

Peter Olson · Accepted Answer · 2015-10-16T05:51:57.033

429

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]

edited Oct 16 '15 at 05:51

answered Oct 16 '15 at 01:40

Peter Olson

139,199
49
202
242

21

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). – David Richerby Oct 18 '15 at 10:13
5

The circles containing circles and the transitions form a Hasse Diagram (https://en.wikipedia.org/wiki/Hasse_diagram). (Yay, I learned something new today!) – Kasper van den Berg Oct 18 '15 at 18:59
5

@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. – Peter Olson Oct 19 '15 at 01:22
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. – Paul R Oct 20 '15 at 17:15
It might be useful to note that you are also using brackets (i.e. precedence), but this is not fundamental, since the same operations can be expressed chronologically (via polish notation). – Sklivvz Oct 20 '15 at 17:27
1

Just wanted to add [another visualization as a table](https://upload.wikimedia.org/wikipedia/commons/9/91/Logical_connectives_table.svg) for people's reference. Same source as above. – aug Oct 20 '15 at 18:34

rgettman · Answer 2 · 2015-10-20T18:57:40.063

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 2⁴, 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.

+1 for the edit. Despite the difference in vote counts, I think your answer is actually more detailed than mine now. — Peter Olson, Oct 21 '15 at 00:56
Truth Tables i thought i had left them behind after first year in university — Barkermn01, Nov 25 '15 at 12:57

score 80 · Answer 3 · answered Oct 15 '15 at 18:01

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.

answered Oct 15 '15 at 18:01

Paul Boddington

37,127
10
65
116

64

@PaulDraper ***or*** NAND gates – slebetman Oct 16 '15 at 09:17
25

It took 4100 NOR gates to land two people on the moon. – Hans Passant Oct 16 '15 at 14:54
4

@HansPassant And some string. Lots of string. (Core rope memory, not the tin can variety.) – user Oct 16 '15 at 21:24
3

@HansPassant Sometimes I wish Stack Exchange was Wikipedia, then I would insert a `[citation-needed]` mark right there. – Simon Forsberg Oct 17 '15 at 22:32
11

Yes, sorry, [Apollo guidance computer](https://en.wikipedia.org/wiki/Apollo_Guidance_Computer#Design). – Hans Passant Oct 18 '15 at 07:27
to make your answer more complete, it would be nice to show how a NOR gate can be made from a NOT and OR. – rogerdpack Nov 13 '15 at 12:34

ryuu9187 · Answer 4 · 2015-10-20T17:20:23.160

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    |
_______________________________________________________

edited Oct 20 '15 at 17:20

answered Oct 15 '15 at 18:00

ryuu9187

1,162
7
15

19

Some people have to down vote as part of their "functional completeness" – Jesse Oct 16 '15 at 13:16
3

At +27/-2, I wouldn't worry much about a stray downvote. – user Oct 16 '15 at 21:25
2

@MichaelKjörling I'm just curious why some people thought my answer was not helpful / was harmful. – ryuu9187 Oct 16 '15 at 21:47
3

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 Oct 17 '15 at 04:10
@user2813274 Thanks for the explanation. Hopefully, my edits will help bridge the gap between personal research and getting to the answer. – ryuu9187 Oct 20 '15 at 17:21

score 11 · Answer 5 · answered Oct 21 '15 at 04:45

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.

score 10 · Answer 6 · answered Oct 20 '15 at 16:41

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

Are || and ! operators sufficient to make every possible logical expression?

6 Answers6