Logical Operator

For example, considering the Assertion s "It's raining", and "I'm inside", we can form the compound assertions "it's raining, ''and'' I'm inside" or "it's ''not'' raining" or "''if'' it's raining, ''then'' I'm inside."

A new statement or proposition combining two statements is called a compound statement or '''compound proposition'''.

The basic operators are " Not " (¬ or ~), " And " (∧,

\land

, or &), " Or " (∨), " Conditional " (→ or ⊃), and " Biconditional " ( Iff ) (↔). "Not" is a Unary Operator —it takes a single term (¬ P). The rest are Binary Operators , taking two terms to make a compound statement (P ∧ Q, P ∨ Q, P → Q, P ↔ Q).

Note the similarity between the symbols for "and" (

\land

) and Set-theoretic Intersection (∩); likewise for "or" (∨) and Set-theoretic Union (∪). This is not a coincidence: the definition of the intersection uses "and" and the definition of union uses "or".

Truth Tables for these connectives:

In order to reduce the number of necessary parentheses, one introduces precedence rules: ¬ has higher precedence than ∧, ∧ higher than ∨, and ∨ higher than →. So for example, P ∨ Q ∧ ¬ R → S is short for (P ∨ (Q ∧ (¬ R))) → S.

Not all of these operators are necessary for a full-blooded logical calculus.
Certain compound statements are Logically Equivalent .
For example, ¬ P ∨ Q is logically equivalent to P → Q;.
So the conditional operator "→" is not necessary if you have "¬" (not) and "∨" (or).

For the sake of convenience (and brevity), only the five most-commonly used operators (in math) are listed above.
One can also consider other connectives, such as NAND ("not-and"), XOR ("not-biconditional"), and NOR ("not-or").

Logical operators are implemented as Logic Gate s in Digital Circuit s. Practically all digital circuits (the major exception is DRAM ) are built up from NAND , NOR , NOT , and Transmission Gate s. NAND and NOR gates with 3 or more inputs rather than the usual 2 inputs are fairly common, although they are logically equivalent to a cascade of 2-input gates. All other operators are implemented by breaking them down into a logically equivalent combination of 2 or more of the above logic gates.

If you throw away all the operators that are not necessary, what operators are you left with?
Which conditionals are the crucial must-have ones?
Surprisingly, there is more than one answer to that question.

All connectives can be expressed with NAND alone.

All connectives can be expressed with NOR alone, as demonstrated by the Apollo Guidance Computer .

Since NAND can be built from NOT and AND, and we know that all connectives can be built from NAND alone, clearly all connectives can be built from combinations of NOT and AND.

... and several other answers.

The "logical equivalence" of "NAND alone", "NOR alone", and "NOT and AND" is similar to Turing Equivalence .

Is some new technology (such as Reversible Computing , Clockless Logic , Quantum Dots computing, or Tinker Toys) "logically complete", in that it can be used to build computers that can do all the sorts of computation that CMOS -based computers can do?
If it can implement the NAND operator, only then is it logically complete.

REFERENCES

Article on logical constants at the Stanford Encyclopedia Of Philosophy .

Information About

Logical Operator