In
Boolean functionIn mathematics, a Boolean function is a function of the form f : Bk → B, where B = {0, 1} is a Boolean domain and k is a nonnegative integer called the arity of the function...
s and
propositional calculusIn logic and mathematics, a propositional calculus or logic is a formal system in which formulae representing propositions can be formed by combining atomic propositions using logical connectives, and a system of formal proof rules allows certain formulae to be established as theorems.-...
, the
Sheffer stroke, named after
Henry M. ShefferHenry Maurice Sheffer was an American logician.Sheffer was a Polish Jew born in Ukraine, who immigrated to the USA with his parents. He was educated at Harvard University, learning logic from Josiah Royce. Sheffer spent most of his career teaching in Harvard's philosophy department...
, written "|" (see
vertical barThe vertical bar has various names including the pipe , verti-bar, vbar, stick, vertical line, vertical slash, think colon, or divider line by others...
) or "↑", denotes a logical operation that is equivalent to the negation of the
conjunctionIn logic and mathematics, logical conjunction or and is a two-place logical connective that has the value true if both of its operands are true, otherwise a value of false.-Notation:...
operation, expressed in ordinary language as "not both". It is also called the
alternative denial, since it says in effect that at least one of its operands is false. In Boolean algebra and digital electronics it is known as the
NAND operation ("not and").
Like its
dualIn mathematics, duality has numerous meanings, and although it is “a very pervasive and important concept in mathematics” and “an important general theme that has manifestations in almost every area of mathematics”, there is no single definition that unifies all concepts of duality.Generally...
, the
NOR operatorIn boolean logic, logical nor or joint denial is a truth-functional operator which produces a result that is the negation of logical or. That is, a sentence of the form is true precisely when neither p nor q is true—i.e. when both of p and q are false...
(a.k.a.
| INPUT |
OUTPUT |
| A |
B |
A NAND B |
| 0 |
0 |
1 |
| 0 |
1 |
1 |
| 1 |
0 |
1 |
| 1 |
1 |
0 |
In
Boolean functionIn mathematics, a Boolean function is a function of the form f : Bk → B, where B = {0, 1} is a Boolean domain and k is a nonnegative integer called the arity of the function...
s and
propositional calculusIn logic and mathematics, a propositional calculus or logic is a formal system in which formulae representing propositions can be formed by combining atomic propositions using logical connectives, and a system of formal proof rules allows certain formulae to be established as theorems.-...
, the
Sheffer stroke, named after
Henry M. ShefferHenry Maurice Sheffer was an American logician.Sheffer was a Polish Jew born in Ukraine, who immigrated to the USA with his parents. He was educated at Harvard University, learning logic from Josiah Royce. Sheffer spent most of his career teaching in Harvard's philosophy department...
, written "|" (see
vertical barThe vertical bar has various names including the pipe , verti-bar, vbar, stick, vertical line, vertical slash, think colon, or divider line by others...
) or "↑", denotes a logical operation that is equivalent to the negation of the
conjunctionIn logic and mathematics, logical conjunction or and is a two-place logical connective that has the value true if both of its operands are true, otherwise a value of false.-Notation:...
operation, expressed in ordinary language as "not both". It is also called the
alternative denial, since it says in effect that at least one of its operands is false. In Boolean algebra and digital electronics it is known as the
NAND operation ("not and").
Like its
dualIn mathematics, duality has numerous meanings, and although it is “a very pervasive and important concept in mathematics” and “an important general theme that has manifestations in almost every area of mathematics”, there is no single definition that unifies all concepts of duality.Generally...
, the
NOR operatorIn boolean logic, logical nor or joint denial is a truth-functional operator which produces a result that is the negation of logical or. That is, a sentence of the form is true precisely when neither p nor q is true—i.e. when both of p and q are false...
(a.k.a. the Peirce arrow or
QuineWillard Van Orman Quine was an American philosopher and logician in the analytic tradition...
dagger), NAND can be used by itself, without any other logical operator, to constitute a logical
formal systemIn logic, a formal system consists of a formal language together with a deductive system which consists of...
(making NAND
functionally completeIn logic, a complete set of logical connectives or Boolean operators is one which can be used to express all possible truth tables by combining members of the set into a Boolean expression. A well known complete set of connectives is { AND, OR, NOT }, consisting of binary...
). This property makes the NAND gate crucial to modern digital electronics, including its use in NAND flash memory and computer processor design.
Definition
The
NAND operation is a logical operation on two
logical valueIn logic and mathematics, a logical value, also called a truth value, is a value indicating the relation of a proposition to truth.In classical logic, the truth values are true and false...
s, typically the values of two
propositionA proposition is a sentence expressing something true or false. In philosophy, particularly in logic, a proposition is identified ontologically as an idea, concept, or abstraction whose token instances are patterns of symbols, marks, sounds, or strings of words...
s, that produces a value of
false if and only if both of its operands are true. In other words, it produces a value of
true if and only if at least one of its operands is false.
Truth table
The
truth tableA truth table is a mathematical table used in logic—specifically in connection with Boolean algebra, boolean functions, and propositional calculus—to compute the functional values of logical expressions on each of their functional arguments, that is, on each combination of values taken by their...
of
p NAND q (also written as
p | q or
p ↑ q) is as follows:
| p |
q |
↑ |
| T |
T |
F |
| T |
F |
T |
| F |
T |
T |
| F |
F |
T |
History
The stroke is named after
Henry M. ShefferHenry Maurice Sheffer was an American logician.Sheffer was a Polish Jew born in Ukraine, who immigrated to the USA with his parents. He was educated at Harvard University, learning logic from Josiah Royce. Sheffer spent most of his career teaching in Harvard's philosophy department...
, who proved (Sheffer 1913) that all the usual operators of propositional logic (
notIn logic and mathematics, negation is an operation on propositions. For example, in classical logic negation is normally interpreted by the truth function that takes truth to falsity and vice versa...
,
andIn logic and mathematics, logical conjunction or and is a two-place logical connective that has the value true if both of its operands are true, otherwise a value of false.-Notation:...
,
orIn logic and mathematics, or, also known as logical disjunction or inclusive disjunction, is a logical operator that results in true whenever one or more of its operands are true. E.g. in this context, "A or B" is true if A is true, or if B is true, or if both A and B are true. In grammar, or is a...
, implies, and so on), could be expressed in terms of it. Charles Sanders Peirce (1880) had discovered this fact more than 30 years earlier, but never published his finding. Peirce also observed that all boolean operators could be defined in terms of the
NORIn boolean logic, logical nor or joint denial is a truth-functional operator which produces a result that is the negation of logical or. That is, a sentence of the form is true precisely when neither p nor q is true—i.e. when both of p and q are false...
operator, the dual of NAND.
Properties
Nand does not possess any of the following five properties, each of which is required to be absent from at least one member of a set of
functionally completeIn logic, a complete set of logical connectives or Boolean operators is one which can be used to express all possible truth tables by combining members of the set into a Boolean expression. A well known complete set of connectives is { AND, OR, NOT }, consisting of binary...
operators: truth-preservation, falsity-preservation,
linearThe word linear comes from the Latin word linearis, which means created by lines.In mathematics, a linear map or function f is a function which satisfies the following two properties......
ity, monotonicity,
self-dualityIn mathematics, duality has numerous meanings, and although it is “a very pervasive and important concept in mathematics” and “an important general theme that has manifestations in almost every area of mathematics”, there is no single definition that unifies all concepts of duality.Generally...
. An operator is truth- (falsity-) preserving if its value is truth (falsity) whenever all its arguments are truth (falsity).
Symbol
One way of expressing
p NAND
q is as , where the symbol signifies
AND and the line over the expression signifies
not, the logical negation of that expression.
Natural language/rhetoric/colloquial usage
NAND is not used in everyday sentences because it exhibits an inherent inversion, which makes it confusing like a double negative. Here's an example of a sentence using:
- NAND operator: We will surely die if we have food nand water.
- Common terms: We will surely die if we do not have both food and water.
- Or, by DeMorgan's Law: We will surely die if we lack either food or water.
Introduction, elimination, and equivalencies
The Sheffer stroke "|" is equivalent to the negation of conjunction:
Expressed in terms of NAND, the usual operators of propositional logic are:
"not p" is equivalent to "p NAND p" |
|
"p and q" is equivalent to "(p NAND q) NAND (p NAND q)" |
|
"p or q" is equivalent to "(p NAND p) NAND (q NAND q)" |
|
"p implies q" is equivalent to "p NAND (q NAND q)" |
|
Formal system based on the Sheffer stroke
The following is an example of a
formal systemIn logic, a formal system consists of a formal language together with a deductive system which consists of...
based entirely on the Sheffer stroke, yet having the functional expressiveness of the propositional logic:
Symbols
pn for natural numbers
n
( | )
The Sheffer stroke commutes but does not associate. Hence any formal system including the Sheffer stroke must also include a means of indicating grouping. We shall employ '(' and ')' to this effect.
We also write
p,
q,
r, … instead of
p0,
p1,
p2.
Syntax
Construction Rule I: For each natural number
n, the symbol
pn is a
well-formed formulaIn the formal languages used in mathematical logic and computer science, a well-formed formula or simply formula is an idea, abstraction or concept which is expressed using the symbols and formation rules of a particular formal language...
(wff), called an atom.
Construction Rule II: If
X and
Y are wffs, then (
X|
Y) is a wff.
Closure Rule: Any formulae which cannot be constructed by means of the first two Construction Rules are not wffs.
The letters
U,
V,
W,
X, and
Y are metavariables standing for wffs.
A decision procedure for determining whether a formula is well-formed goes as follows: "deconstruct" the formula by applying the Construction Rules backwards, thereby breaking the formula into smaller subformulae. Then repeat this recursive deconstruction process to each of the subformulae. Eventually the formula should be reduced to its atoms, but if some subformula cannot be so reduced, then the formula is not a wff.
Calculus
All wffs of the form
)|((
Y|(
Y|
Y))|((
X|
V)|((
U|
X)|(
U|
X)))))
are axioms. Instances of
),
U W
are inference rules.
Simplification
Since the only connective of this logic is |, the symbol | could be discarded altogether, leaving only the parentheses to group the letters. A pair of parentheses must always enclose a pair of
wffs. Examples of theorems in this simplified notation are
- (p(p(q(q((pq)(pq)))))),
- (p(p((qq)(pp)))).
The notation can be simplified further, by letting
- (U) := (UU)
- ((U)) U
for any
U. This simplification causes the need to change some rules:
- More than two letters are allowed within parentheses.
- Letters or wffs within parentheses are allowed to commute.
- Repeated letters or wffs within a same set of parentheses can be eliminated.
The result is a parenthetical version of the Peirce
existential graphAn existential graph is a type of diagrammatic or visual notation for logical expressions, proposed by Charles Sanders Peirce, who wrote his first paper on graphical logic in 1882, and continued to develop the method until his death in 1914.-The graphs:...
s.
Another way to simplify the notation is to eliminate parenthesis by using
Polish NotationPolish notation, also known as prefix notation, is a form of notation for logic, arithmetic, and algebra. Its distinguishing feature is that it places operators to the left of their operands. If the arity of the operators is fixed, the result is a syntax lacking parentheses or other brackets, that...
. For example, the earlier examples with only parenthesis could be rewritten using only strokes as follows
- (p(p(q(q((pq)(pq)))))) becomes
- |p|p|q|q||pq|pq, and
- (p(p((qq)(pp)))) becomes,
- |p|p||qq|pp.
This follows the same rules as the parenthesis version, with opening parenthesis replaced with a Sheffer stroke and the (redundant) closing parenthesis removed.
External links