In
propositional logic, the Sheffer stroke is an
operator, or
connective, which is
semantically complete.
Each
connective in
Logic has an associated
truth table. These connectives can be combined to create new
truth tables. The Sheffer stroke is a
connective that allows one to create a
formula for any truth table using this
operator alone.
The Sheffer stroke is analagous to a NAND operation, and is
symbolized with the '|' char.
P Q | ~(P^Q) | (P|Q)
-----------------
T T | F T T TFT
T F | T T F TTF
F T | T F T FTT
F F | T F F FTF
From this figure it can be seen that a Sheffer stroke is only
false if both of its
operands are true.
By combining the Sheffer stroke with itself, any truth table can be contrived.
Here is the
truth table for the
negation operator:
P | ~P | (P|P)
-------
T | FT | TFT
F | TF | FTF
For another example, here is the
implication (conditional)
P Q P->Q | (P|(P|Q))
-----------------
T T TTT | TT TF T
T F TFF | TF TT F
F T FTT | FT FT T
F F FTF | FT FT F
Here is AND
P^Q (P|Q)|(P|Q)
Here is OR
PvQ (P|P)|(Q|Q)
For the same reason that the Sheffer stroke may be used to create any truth table, any
logical circuit consisting of AND, OR GATES and
inverters can be created using only
NAND Gates