17
$\begingroup$

I am a Software Developer but I came from a non-CS background so maybe it is a wrong question to ask, but I do not get why logic gates/boolean logic behave the way they do.

Why for example:

1 AND 1 = 1  // true AND true
1 OR 0 = 1   // true OR False
0 AND 1 = 0  // false AND true

And so on..
Is it a conditional definition for example, like it is like that by definition?
Or there is a logical/intuitive explanation for these results?

I have searched google, also looked at the Wiki page of logic gates for an explanation of 'why' but I can only find 'how'.
I would appreciate any answer or resources.

$\endgroup$
  • 33
    $\begingroup$ That's the definition of an OR gate. If it doesn't do that, it's not an OR gate. If it does that, it's an OR gate. Why does soap clean hands? Well there are plenty of things that don't clean hands but we don't call them soap. $\endgroup$ – user253751 May 1 at 1:39
  • 6
    $\begingroup$ There is no "why" in math. We define terms & assume things & then there are consequences. However some terms, assumptions & consequences are useful for getting certain things done. If we use something the "why" is, it is useful. The utility is specific to the terms, assumptions (with consequent consequences) & things to get done. $\endgroup$ – philipxy May 1 at 7:55
  • 14
    $\begingroup$ @user253751 Well, soap might not be the best example; there are soaps that don't clean hands, and there are things that clean hands that aren't soap, and it is in fact possible to give a detailed and interesting explanation of why soap cleans hands. Perhaps a good question would be "Why don't empty boxes have anything in them?" $\endgroup$ – Tanner Swett May 1 at 11:02
  • 3
    $\begingroup$ @OP: On the other hand, if you're a software developer, you must have used boolean operators in your code, so I'd assume you know the meaning of those - and this is the same thing. Can you clarify the nature of your lack of understanding? What exactly are you asking for us to help you with? Please give us some more detail and try to more narrowly articulate the focus of the question. $\endgroup$ – Filip Milovanović May 1 at 16:18
  • 3
    $\begingroup$ Glad you found a satisfactory answer, then! OP stands for "Original Poster" (a term used in traditional forums for the person who posted the first message or started a thread). $\endgroup$ – Filip Milovanović May 1 at 16:38

11 Answers 11

77
$\begingroup$

As stated by user120366, 16 possible 2-input logic gates exist, I've tabulated them for you here:

A|B||0|1|2|3|4|5|6|7|8|9|a|b|c|d|e|f
-+-++-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-
0|0||0|0|0|0|0|0|0|0|1|1|1|1|1|1|1|1
0|1||0|0|0|0|1|1|1|1|0|0|0|0|1|1|1|1
1|0||0|0|1|1|0|0|1|1|0|0|1|1|0|0|1|1
1|1||0|1|0|1|0|1|0|1|0|1|0|1|0|1|0|1

A and B are the inputs, 0 through f are the possible permutations of outputs.

These gates have been named:

0 = FALSE 
1 = AND
2 = A NIMPLY B (A AND NOT B)
3 = A
4 = B NIMPLY A (B AND NOT A)
5 = B
6 = XOR
7 = OR
8 = NOR
9 = XNOR
a = NOT B
b = B IMPLY A (A OR NOT B)
c = NOT A
d = A IMPLY B (B OR NOT A)
e = NAND
f = TRUE

6 of these (0,3,5,a,c,f) discard one or both inputs. The IMPLY and NIMPLY gates are rare, though they are certainly used in formal logic. AND, OR and XOR are easiest for humans to reason with, but for physical hardware, NOR and NAND are also used heavily, because they can be simpler to implement and make smaller circuits. The same probably holds for XNOR.

So, as stated earlier, it's not so much that we decided that the gates should behave this way, but that 16 possible gates can be defined, and we came up with descriptive names for them.

| cite | improve this answer | |
$\endgroup$
  • 1
    $\begingroup$ Obviously two binary inputs produce four possible input states, which means 16 unique output states, but these are not fundamental boolean operators - they are simply combinations of the two binary boolean operators and the negation operator. This table and explanation doesn't do anything to explain why the result is what it is it just gives names to various combinations of these basic operators. $\endgroup$ – Trevor May 2 at 1:45
  • $\begingroup$ It may be worth adding that some of these form a basis, i.e., with a hand full of them all others can be formulated. For human readability, the choice of AND, OR and NOT is the easiest subset, sometimes also A IMPLY B additionally (but not so in informatics). $\endgroup$ – rexkogitans May 2 at 7:55
  • 4
    $\begingroup$ @Trevor "it just gives names to various combinations of these basic operators" - That's the power of the answer, it doesn't make it any more complicated than it has to be. $\endgroup$ – Paul May 2 at 11:29
  • $\begingroup$ NAND and NOR are known as universal gates as any boolean function may be realised using just those functions (all NAND or all NOR). Some time ago, the AND-OR-INVERT gate was popular (and used heavily in PAL/GAL/PLA devices) as this structure permitted any boolean function to be available. $\endgroup$ – Peter Smith May 2 at 13:07
  • 1
    $\begingroup$ @PeterSmith my point was not that in computer science we should prefer AND or OR over NAND or NOR. My point was that talking about these is just providing more names and thereby complicating the issue without answering the why question. I think the use of permutations of inputs/outputs might be a useful way of explaining the why question but the emphasis on all these names distracts from the true answer, which is that we just agree on a name for particular permutations of input/output, which we call OR, AND etc. The effect of AND/OR is what it is BY DEFINITION. $\endgroup$ – Trevor May 3 at 13:30
25
$\begingroup$

It's easiest to think of $1$ representing a true statement and $0$ representing a false statement. The logic gates then act as truth functions.

Say you put two statements, $p,q$, together to form a new statement, $r$.

In the case of and (logical conjunction), both $p$ and $q$ must be true for $r$ to be true. In the case of or (logical disjunction), $r$ is true if at least one of $p$ or $q$ are true.

| cite | improve this answer | |
$\endgroup$
  • 2
    $\begingroup$ 1 & 0 represent the truth values of the statements, not the statements. $\endgroup$ – philipxy May 1 at 7:57
  • 3
    $\begingroup$ Good way to think about it, since it closely (but not exactly) mirrors the common semantic usage of AND and OR. Both things must be true for an AND statement to be true - "The sun is hot and the earth is flat" is false, because one of those things is false. Semantic "or" is typically the exclusive OR (XOR) function, however - in the statement "today I'm going to the park or the mall", you wouldn't expect me to go to both, but with logical OR, the statement is true if I go to one, the other, or both. $\endgroup$ – Nuclear Hoagie May 1 at 15:09
23
$\begingroup$

I think the questioner has it backwards. If we have a logical function such that

    A | B | result  
   ---+---+-------  
    0 | 0 | 0  
    0 | 1 | 0  
    1 | 0 | 0  
    1 | 1 | 1  

then we decide to call that function and because it is obvious that the result is 1 only when A and B are both 1.

Similarly for or, exclusive-or, etc.

There are 16 possible logical functions of 2 operands --it's easy to list them all, it's just the permutations of the 'result' column above. Some have obvious names.. The field probably dates from George Boole. As far as circuits are concerned, any of the 16 could in principle be built, but some are more useful than others.

| cite | improve this answer | |
$\endgroup$
  • 19
    $\begingroup$ No, of course not. There are 16 possible logical functions of 2 openands --it's easy to list them all, it's just the permutations of the 'result' column above. Some have obvious names.. The field probably dates from George Boole. As far as circuits are concerned, any of the 16 could in principle be built, but some are more useful than others. $\endgroup$ – user120366 May 1 at 0:57
  • 4
    $\begingroup$ There's nothing obvious or intuitive about this. Especially not with OR. Most people new to logic (e.g. programming) struggle with the difference between OR and XOR both of which correspond to English language usages of the word 'or'. These are definitions, that's all. And luckily these definitions are pretty much universal across the world. $\endgroup$ – Joooeey May 1 at 10:22
9
$\begingroup$

The why of it actually comes from the development of logic, which is a philosophical study of what is true and what is not true. Logic was originally a study of human language with the assumption that if you can reason about how human language works you can maybe reason about how reason works.

Since the language I'm answering you in English let's use English as an example even though the original study of logic was probably on the Greek language. First let's differentiate the study of logic (or what is true and what is not true) from the other study of language: grammar. Grammar involves interpreting the meaning of words put together involving elements of syntax, morphology, semantics etc., that is not what we are studying. We assume that grammar is a given and you and I understand it. What we are studying is if a statement is true.

So let's take a look at AND in English.

Example 1:

My nickname is slebetman AND I am a stackexchange user

Ok, so is my nickname slebetman? Yes, so the first part of the sentence before AND is true.

Am I a stackexchange user? Yes because I'm writing this answer, so the second part of the sentence after AND is true.

In the English language, is the above sentence truthful? Yes. So we can see the first behavior of AND:

true sentence = something true AND something true

Or we can simplify:

true = true AND true

So let's look at another sentence:

My nickname is slebetman AND I don't understand English

In this case the first part is unchanged so it is still true but the second part is obviously false because this entire answer is in English. So we have true AND false. Is the entire sentence true? Would you say I'm not lying if I said the sentence above? Of course not, the entire sentence is false. So here we see the second behavior of AND:

false = true AND false

Since we can rearrange the sentence and still keep it false: I don't understand English AND my nickname is slebetman we can say that AND is commutative. Which gives us:

true  = true  AND true
false = true  AND false
false = false AND true

Finally it shouldn't be hard to convince you that if I said two false things and joined them by AND the entire sentence would still be a lie. Which defines what AND does:

true  = true  AND true
false = true  AND false
false = false AND true
false = false AND false

The same reasoning can be applied to OR and NOT.

In a sense, this definition is just giving an operator a name. What the operator really does is make sure all conditions are true. We could have named AND something different, maybe ALL (short for all must be true) and we could have named OR something different like ANY (short for if any of the following is true) and the logic would still work:

XANY(a,b) = ANY( ALL(a, NOT(b)), ALL(NOT(a), b))

But we have decided to call the operators AND and OR so instead we write:

a XOR b = (a AND (NOT b)) OR ((NOT a) AND b)

It's a bit arbitrary what we call the operators but if you need to know where they come from they come from our language (originally probably Greek not English) and over time and the application of formality gets adopted into mathematics and engineering.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ I was going to write a similar answer. One important thing about the development of classical logic is the realization of the utility of the law of the excluded middle, which is that any given statement can be strictly judged to be either true or false (and not neither). A consequence of this is that we have to accept that implication, for example, must be the material implication, where only the truth is considered, rather than how it is used in common language, which tends to be that somehow the consequence follows in a clear way from the hypothesis. Thus, we have an algebra of truth values. $\endgroup$ – Kyle Miller May 1 at 20:40
  • $\begingroup$ @KyleMiller Well, when we got rid of the excluded middle and start treating truthiness as a probability we ended up with the development of game theory in mathematics and fuzzy logic in engineering (which is now forgotten in favor of machine learning). Funny you mentioned algebra from which we developed digital electronics, it was not the first offshoot of logic even though it is now the most popularly known. The first offshoot of logic was set theory which indeed used different words for the operators: AND is called INTERSECTION and OR is called UNION $\endgroup$ – slebetman May 2 at 5:25
  • $\begingroup$ ... we got full-circle with the development of SQL which is based on set theory but uses the keyword AND for INTERSECTION operation and OR for UNION. But my answer was long enough as it is and I decided not to go off on a tangent $\endgroup$ – slebetman May 2 at 5:26
  • $\begingroup$ What I had in mind is constructive logic, where truth values are sets of proofs for a statement; implications are no longer material (the incompleteness theorem says there's a statement this neither provable nor disprovable, so it's not crazy to not accept the LEM. Also, constructive logic seems to be more compatible with thinking about computation). Boole's algebra originally was him realizing he could encode propositional logic using arithmetic expressions (xy for AND, x+y-xy for OR, 1-x for NOT, etc.), and I heard Shannon was the one who introduced it into digital electronics design. $\endgroup$ – Kyle Miller May 2 at 6:44
3
$\begingroup$

The boolean operators (and, or) are functions that map two inputs to an output, just like any other binary operator (i.e. +). Their exact behavior (the why question) is an axiom of boolean logic, just as the behavior of addition is an axiom of mathematics, which is to say that we agree that these operators do what they do. It is therefore the bedrock of the system and it is meaningless to try explain why they work in this way, just as it is meaningless to explain why a rose is a rose: it is because we agree it is.

How the operators are implemented in a computer (the how question) is a matter of engineering and there are may other ways of implementing these operators other than using logic gates built from transistors (there is a video floating around of an adder built from dominoes for example).

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ I believe the referred video is using logic gates as well, which inspired me to ask this question. I kind of predicted this answer but @A. Bollans has another opinion, what do you think of their answer? $\endgroup$ – aldokkani May 1 at 0:54
  • 1
    $\begingroup$ @HossamAldokkani - the two answers don't contradict each other, but they are answering a slightly different question (they have different interpretations of what exactly you're asking). Bollans' answer explains what these functions mean, which is, I think, what you really asked about. Trevor is addressing the deeper "why" question (e.g., not the meaning, but literally why is "true and true == true" and not something else) - to which the answer is that we've taken it as an axiom (taken it for granted) and managed to build a useful, working, self-consistent system with that. $\endgroup$ – Filip Milovanović May 1 at 15:58
  • $\begingroup$ @HossamAldokkani - And by "taken it for granted" I don't mean that that's how they've been historically developed (how the ideas came to be), but that in their mathematical formalism they are taken as "basic facts" considered valid without proof, the underlying building blocks upon which the rest of the formalism is built (see: axiom). $\endgroup$ – Filip Milovanović May 1 at 16:02
  • $\begingroup$ @FilipMilovanović is correct. A. Bollins in my view is reforming the question in a more linguistic form i.e. he is replacing 1 and 0 with true and false and expressing the operations using natural language (and adding some technical terms) but he is not really saying why the result is produced. You appeared to be asking the why question. $\endgroup$ – Trevor May 2 at 1:23
1
$\begingroup$

To answer this, I think it is best to go back to those early 'Truth Tables' you probably saw in algebra. The first ones you see are 'and' & 'or'. We have two statements #1 & #2 (usually called p & q) which can either be true or false. Then, when we test them we have a result (usually called r).

For example,

#1 p = I like red

#2 q = I like dogs

NOW let's test the affirmative and negative statements using 'and'.

If #1 is True AND #2 is True then the result(r) is True.

  • I like red AND I like dogs. This is True. [1 and 1 then r = T]

If #1 is False AND #2 is True then r = F

  • I don't like red AND I like dogs. This is false. [0 and 1 then r = F]

If #1 is True AND #2 is False then r = F

  • I like red AND I don't like dogs. This is false. [1 and 0 then r = F]

If #1 is False AND #2 is False then r = F

  • I don't like red AND I don't like dogs. This is false. [0 and 0 then r = F]

NOW look at 'OR'

If #1 is True OR #2 is True then the result(r) is True.

  • I like red OR I like dogs this is True. [1 or 1 then r = T]

If #1 is False OR #2 is True then the result(r) is True. [0 or 1 then r = T]

If #1 is True OR #2 is False then the result(r) is True. [1 or 0 then r = T]

If #1 is False OR #2 is False then the result(r) is False. [0 or 0 then r = F]


NOW Your questions

1 and 1 = 1, I like red and dogs. True
1 or 0 = 1, I like red or I don't like dogs. True
0 and 1 = 0, I don't like red and I like dogs, False ... Voila

| cite | improve this answer | |
$\endgroup$
1
$\begingroup$

You can look at it as two stages.

The first stage is that we want some particular outcome, such as wanting a 1 if either of the (2) inputs is a 1. We call this an “OR” gate. Another outcome that people want is to get a 1 only if both inputs are a 1. We call this an AND gate.

The final stage is that we want a particular gate for every possible combination (of two inputs and one output). Now, the only problem is having meaningful names for them all.

This gives us confusing things such as IOR (Inclusive OR) — two 1’s gives a 1 — and XOR (exclusive OR) — two 1’s gives a 0. It gives us amusing things such as NAND — the opposite of AND. …But in the end we have every possible gate, and a more or less intuitive name for each and every one.

| cite | improve this answer | |
$\endgroup$
1
$\begingroup$

I interpret question 'why' as asking for the purpose.

So imagine OR, AND and NOT as the simplest building blocks from which you can build almost anything else. (Just remember it as some kind of simplification: NAND gate seems to be more universal and simpler from electronic engineering point of view but is less intuitive for learning purposes)

As an example, let think of building a device for adding numbers (a sumator).

01010b + 00110b = 10000b
10d + 6d = 16d

Notice that we can build it from simpler blocks. Each one computes single binary digit at each position and 'carry out'.

In order to compute digit at each position we need:

(A XOR B) XOR C_in

Where C_in is a carry remaining from computing previous digit. To build XOR gate from simpler gates, we can:

A XOR B = (A AND NOT B) OR (NOT A OR B)

Another possibility:

A XOR B = (A OR B) AND NOT (A AND B)

I will stop explaining sumator here. For more information please visit: Full adder circuit or Adder and subtractor. My objective here was to only describe an idea of logic gates as building blocks.

There is a class of electronic circuits called 'combinational circuits'. It simply takes some N bits of input and computes M bits of output. We can prove that every possible combinational circuit can be made of only NOT, AND and OR gates. Let see an example:

ABC | XY
000 | 00
001 | 11
010 | 00
011 | 00
100 | 10
101 | 00
110 | 01
111 | 10

To compute X output, we can simply take each row, where X is 1, construct condition that must be fulfilled by NOTs and ANDs and connect each conditions with ORs.

X = (NOT A AND NOT B AND C) OR (A AND NOT B AND NOT C) OR (A AND B AND C)

Similarly for Y:

Y = (NOT A AND NOT B AND C) OR (A AND B AND NOT C)

For more information: Disjunctive Normal Form

Please note that it is only for proof purpose, to show that it is possible. It is obviously not optimal. Finding circuits for minimum number of logic gates is NP computing problem. Please also see: Logic Optimization

But combinational circuits are not only things we can build using AND, OR and NOT gates. If we add some kind of feedback loops we can gain an ability to generate clock signals (Multivibrators) or to remember things (Latches).

| cite | improve this answer | |
$\endgroup$
1
$\begingroup$

AND
I like red AND ripe apples.
If the apple is red and the apple is ripe, then the result is true
1 and 1 makes 1 (true)
The apple is green, so I don't like it
0 and 1 makes 0 (false)
The apple is red but not ripe
1 and 0 makes 0 (false)

OR
I'll eat an apple if it's ripe OR if it's red
The apple is red, but not ripe so I'll eat it
1 or 0 makes 1 (true)
The apple is green but it's ripe - I eat it
0 or 1 makes 1 (true)
The apple is not ripe and it's purple - no thanks
0 or 0 makes 0 (false)

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ I'll eat an apple if it's ripe OR if it's red $\endgroup$ – JeremiahBarrar May 3 at 20:50
  • $\begingroup$ Good catch, that was a typo $\endgroup$ – JeremiahBarrar May 4 at 22:55
0
$\begingroup$

Is it a conditional definition for example?

Yeah, that's a good way to look at it.

One way of writing the definition of the AND operator is:

The AND operator is that operator that takes two bits as input and gives one bit as output, such that

  • 0 AND 0 = 0;
  • 0 AND 1 = 0;
  • 1 AND 0 = 0;
  • 1 AND 1 = 1.

Likewise, one way of writing the definition of the OR operator is:

The OR operator is that operator that takes two bits as input and gives one bit as output, such that

  • 0 OR 0 = 0;
  • 0 OR 1 = 1;
  • 1 OR 0 = 1;
  • 1 OR 1 = 1.

So, the reason that 1 AND 1 = 1 is that the definition says so. Likewise, the reason that 1 OR 0 = 1 is that the definition says so. And likewise for the other 6 equations; they're true because the definition says so.

| cite | improve this answer | |
$\endgroup$
0
$\begingroup$

$\def\N#1{{\left[\text{#1}\right]}}$tl;dr There're only 3 possible gates that satisfy these properties:

  1. depend on both of 2 binary inputs to produce 1 binary output;

  2. don't discriminate between the inputs;

  3. aren't just another gate $\texttt{NOT}\text{'d} .$

These 3 gates are usually described as $\texttt{AND} ,$ $\texttt{OR} ,$ and $\texttt{XOR}$ as the $3$ possible gates, along with their $\texttt{NOT}\text{'d} .$ variants, $\texttt{NAND} ,$ $\texttt{NOR} ,$ and $\texttt{NXOR} .$


For each possible input, there's $1$ possible function for each possible output. This means $$ \N{functions} ~=~ {\N{possible outputs}} ^ {\N{possible inputs}} \,. $$

Here, there're two possible outputs, $\left\{0,\,1\right\} ,$ and there're four possible inputs, $\left\{\left\{0,\,0\right\}.\, \left\{0,\,1\right\}, \,\left\{1,\,0\right\}, \, \left\{1,\,1\right\} \right\} ,$ so $$ \N{functions} ~=~ {2} ^ {4} ~=~ 16 \,, $$ meaning that there're 16 possible gates. as shown @AI0867's answer.

If we exclude both of the inputs, that'd have been $2^1=2$ possible gates. These are the $\texttt{true}$ and $\texttt{false}$ gates, which always return $1$ or $0 ,$ respectively, without regard for their inputs.

If we exclude one of the inputs, that'd have been $2^2 = 4$ possible gates. These would be the identity-gate (return the input), the NOT-gate (invert the input), plus the {true, false}-gates again. So, that's $2$ gates that depend only on one of the inputs.

Since there're 2 inputs, there're:

  • 2 gates that don't care about either input;

  • 2 gates that don't care about the first input; and

  • 2 gates that don't care about the second input;

for a total of 6 gates that don't care about both inputs, reducing the 16 possibilities down to 10 gates which can be meaningfully described as having 2 inputs.

Then, we can note that of these 10 gates, half of them just return the inverted input $(\text{e.g.},$ $\texttt{AND}$ vs. $\texttt{NAND}).$ So we can say that it's just 5 gates, plus their inversions. @AI0867's answer covered this, too.

The point I'd add is that this analysis assumes that inputs are ordered; for example, $\left\{0,1\right\}$ is distinct from $\left\{1,0\right\} .$ However, in practice, we don't tend to discuss gates which discriminate between the inputs.

So, instead of having $4$ distinguishable inputs, we have $3 .$ Then, that's $2^3 = 8$ possible gates. We again remove the $2$ that don't depend either gate; we don't remove the other $2+2=4$ that didn't depend on just one gate because we no longer distinguish between the two gates, so those cases already don't exist. This leaves $2^3-2=6$ possible gates that:

  • depend on both inputs; and

  • don't discriminate between the inputs.

Then, again, we can note the inversion of the outputs, so instead of saying $6$ different gates, we can say that there're $3$ gates with their inversions.

This leaves $\texttt{AND} ,$ $\texttt{OR} ,$ and $\texttt{XOR}$ as the $3$ possible gates, plus their inversions, $\texttt{NAND} ,$ $\texttt{NOR} ,$ and $\texttt{NXOR} .$

In short, when we talk about gates as though only 3 binary-gates exist (plus the unary $\texttt{NOT}$ gate), that's because there're only 3 that:

  1. depend on both inputs;

  2. don't discriminate between the inputs;

  3. aren't just another gate with the output inverted.

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.