Send
Close Add comments:
(status displays here)
Got it! This site "creationpie.com" uses cookies. You consent to this by clicking on "Got it!" or by continuing to use this website. Note: This appears on each machine/browser from which this site is accessed.
Binary logical operations
1. Binary logical operations
Some people new to logical operations, or who have not studied them in detail, may think that the operations are arbitrary. That is, someone could "invent" a "new" operation such as "conjunction".
However, there are only 2*2*2*2 = 16 possible binary logical operations and these can be enumerated.
Once can assign new names or symbols to those operations, but for all the useful operations, this was done long ago, many by Peano.
Here we look at this enumeration. The first known use of this idea is from Wittgenstein (Tractatus Logico-Philosophicus, 5.101).
2. Views
Some people unfamiliar with the foundations of logic as studied, for example, in the theory of programming language theory, logic, syntax, semantics, etc., might think that logical operations are arbitrary and waiting to be "
invented". Here we take systematic view at all binary logical operations, which are finite in number.
First a little background.
3. Sets and Venn diagram
Logical conjunction (i.e., "
And", "
&", etc.) is related to the intersection operation of sets.
Here is a mathematical definition of set intersection.
Note how the set intersection operator "
∩" and the logical conjunction symbol "
∧" are related. They are wide at the bottom and narrow/close at the top. This did not just happen. They are related.
4. Peano: symbols
The "
there exists" symbol "
∃", and many others, were created by the Italian mathematician Giuseppe Peano (1858-1932), many by reversing letters or turning them upside down.
Peano created the "
or" symbol as "
∨" from the letter "
v" starting the Latin word
"vel" ≈ "or". The "
and" symbol "
∧" is an upside down "
or" symbol.
Other mathematicians then followed this convention in creating more symbols over time. One such symbol was the "
for all" symbol "
∀" first used in 1935 by logician Gerhard Gentzen (1909-1945) and called it, in German, "
All-Zeichen", the "
all character"
5. Conjunction
The
conjunction or
intersection of
A & B or
A and B is
true=
1 if both of
A and
B are
true=
1, else the result is
false=
0.
|
Venn diagram
|
Expression tree
|
Extended truth table
|
|
 |
A B | A & B
-----------
0 0 | 0 0 0
0 1 | 0 0 1
1 0 | 1 0 0
1 1 | 1 1 1
|
6. And
The word "
and" is a conjunction in that both parts (on either side) are needed.
Example: You need to buy milk
and cookies at the store.
Distribute as follows.
You need to buy milk at the store and
you need to buy cookies at the store.
You need to do both.
7. Conjunction
Let us rewrite the truth table for logical conjunction in an expanded form. Note that the result is under the "
&" symbol.
A B | A & B
-----------
0 0 | 0 0 0
0 1 | 0 0 1
1 0 | 1 0 0
1 1 | 1 1 1
| Conjunction |
| # |
A=0
B=0 |
A=0
B=1 |
A=1
B=0 |
A=1
B=1 |
Operation |
Usage |
| 1 |
0 |
0 |
0 |
1 |
AND |
Conjunction |
The result can be viewed as a binary number/sequence that defines all
2*2*2*2 =
16 possible (and only) binary logical operations. Let us fill in the complete table.
8. All binary logical operations
| # |
A=0
B=0 |
A=0
B=1 |
A=1
B=0 |
A=1
B=1 |
Operation |
Usage |
| 0 |
0 |
0 |
0 |
0 |
Always 0 |
False, Contradiction |
| 1 |
0 |
0 |
0 |
1 |
AND |
Conjunction |
| 2 |
0 |
0 |
1 |
0 |
NOT (A IMP B)=NOT B AND A |
Resolution, Inhibition |
| 3 |
0 |
0 |
1 |
1 |
A |
Identity |
| 4 |
0 |
1 |
0 |
0 |
NOT (B IMP A)=NOT A AND B |
Resolution, Inhibition |
| 5 |
0 |
1 |
0 |
1 |
B |
Identity |
| 6 |
0 |
1 |
0 |
1 |
XOR=NOT EQV |
Security |
| 7 |
0 |
1 |
1 |
1 |
OR |
Disjunction |
| 8 |
1 |
0 |
0 |
0 |
NOR |
Not Disjunction |
| 9 |
1 |
0 |
0 |
1 |
EQV=NOT XOR |
Equivalence |
| 10 |
1 |
0 |
1 |
0 |
not B |
Complement, Negation |
| 11 |
1 |
0 |
1 |
1 |
B IMP A=NOT B OR A |
Implication |
| 12 |
1 |
1 |
0 |
0 |
not A |
Complement, Negation |
| 13 |
1 |
1 |
0 |
1 |
A IMP B=NOT A OR B |
Implication |
| 14 |
1 |
1 |
0 |
1 |
NAND |
Build a computer |
| 15 |
1 |
1 |
1 |
1 |
Always 1 |
True, Tautology |
My preference is to number the operations according to binary number order where zero is false and one is true.
9. Wittgenstein and logical operations
Here is the table from Wittgenstein's
Tractatus Logico-Philosophicus, 5.101. This is often cited as
TLP (Tractatus Logico-Philosophicus). He completed it in 1918 (as a soldier in World War I) and published it in 1921. An English translation and Latin title was published in 1922.
The German word "Falsch" ≈ "false" abbreviated as "F".
The German word "Wahr" ≈ "true" abbreviated as "W".
The German word "Nicht" ≈ "not".
I created my own table of these operations in graduate school. It was many years until I found out that it had been done long before.
10. Summary
As one can see, one does not just make up logical binary operations since there are only
16 possible.
Each of these has some use. Some are used more than others in any given (problem solving) situation.
Some of the more important operations are now covered.
11. The XOR operation and one-time pads
A
OTP (One Time Pad) cipher system that uses the cipher key one time only, and for short messages (key is longer than the message).
The most secure keys are one-time pads of random, but agreed-on keys. It is impossible to break a one-time pad. If the key is ever reused, then it becomes almost trivial to break that one-time pad.
That is why it is called a one-time pad. It can only (securely) be used one time.
The one-time pad was first described in 1882 and re-discovered in 1917 by Gilbert Vernam.
Today, most cryptography systems are based on the
XOR (Exclusive Or) logical bit operation. The complexity arises in negotiating secure distributed keys and distributed difficult-to-guess pseudo random number sequences.
12. NAND operator
The logical NAND operation is the "
NOT AND" operation.
Every logical operation can be formed using NAND operations.
Claude Shannon showed that a computer can be built of logic gates. Thus, a computer can be built from NAND gates.
In programming language theory, this process is called a structural induction. It is (initially) much easier to build hardware that has only one physical part, suitably connected. In proving properties and in implementing program languages, it is easier to do the proof for just a small selected subset of possible constructs. Any combined construct is thus already handled.
13. Claude Shannon
Claude Shannon (Information scientist)
Claude Shannon's masters thesis was a detailed description of how to build (the first) programmable digital electronic computer. He later founded the modern field of information and communication theory. He worked on encryption technologies during World War II.
Claude Shannon, in the 1950's, used the term "
information" to describe the statistical properties of data transmitted from one place to another. He was working for the telephone company AT&T at Bell Labs in order to improve the quality of phone calls. He founded the modern field of (statistical) information - he was not overly concerned with the meaning of the "
data" that he called "
information".
14. End of page
