Boolean Operators

Overview:

Boolean operators are the stuff with which digital hardware is designed, they play a role in programming languages, and are the subject matter of propositional logics.
0-ary
Boolean constants.
1-ary
Monadic operations.
2-ary
Dyadic operations.
n-ary
For n>2, use expressions (or wiring diagrams) of 1/2-ary operators.
not
Universal
scheffer strokenor
Almost Universal
and or if implies
The Rest
equivnot equalnifnimp
Universal Sets
A universal set of operators is a set from which all others can be defined. Here are the minimal universal sets.
index
All the names symbols and diagrams I could think of.

0-ary:

Boolean Constants

namescontext of use
falsetrueused in logic and philosophy
FTabbreviations for truth tables
01used in electronic engineering
bottomtopin some logics
0-ary operators
Its just a matter of convenience that we sometime think and talk of constants as operators which take no arguments (though it does look like a contradiction in terms). As it happens it works out well in this exposition, since the availability of the boolean constants allows us to dispense with some other trivial 1-ary and 2-ary operators.
just two constants
It is of the essence of boolean logic that there are just two truth values. In the application of the logic to everyday reasoning this is an oversimplification, and its necessary to be aware of the possibility that a sentence may no have a truth value and to avoid using classical logic if there is any possibility that any of the sentences involved might be neither true nor false (as in slythy toads gyre and gimbling).
false, true, 0,1
In digital electronics the choice is deliberately made to use only two distinct signal states, since this simplifies circuit design and makes the hardware more reliable. Numeric values were used, but this practice may be receding now that hardware design is done with hardware description languages instead of wiring diagrams.

1-ary:

There are two unary boolean operators, but one does nothing, leaving only negation or not.

not

not, -

not

AnotA
FT
TF

2-ary:

There are 16 possible truth tables for binary boolean operators.
constants
Two of the tables are entirely filled with one value and therefore can be dispensed with in favour of the two constants true and false.
1-ary
Four of the tables represent operators which ignore one argument and use the other, either negated or unchanged. These can be dispensed with in favour of appropriate use of not.
named operators
Of the remaining ten, eight are used and have names: and, or, implies, if, iff, xor, nand, nor.
unnamed operators
The couple for which I know no name can be given one by extending the convention that adding an "n" at the front of the name gives a name for the operator negated (already used in nand and nor). Negating implies gives nimplies or nimp for short. Negating if gives nif, which is short enough.
names and symbols
There are lots of different ways of naming these operators, and lots of symbols/diagrams used to represent them. Most of the ones I know of are mentioned below.

Key to Truth Tables
The table on the right shows combinations of truth values for the two operands A and B to the truth function, in the position of the table which will be used for recording the result of the operation for those operand values.
A = T
B = T
A = T
B = F
A = F
B = T
A = F
B = F
true or if A implies B iff and
TT
TT
TT
TF
TT
FT
TT
FF
TF
TT
TF
TF
TF
FT
TF
FF
nand xor not B nimp not A nif nor false
FT
TT
FT
TF
FT
FT
FT
FF
FF
TT
FF
TF
FF
FT
FF
FF

or
disjunction,
inclusive or

or

or

ABA or B
TTT
TFT
FTT
FFF

if
reverse material implication

if, if

ABA if B
TTT
TFT
FTF
FFT

implies
material implication,
only if

implies, implies

ABA implies B
TTT
TFF
FTT
FFT
The implication operator is called "material implication" to distinguish it from the use of the word "implies" in natural english. Implies suggests some connection between the antecedent and the conclusion and is therefore not strictly truth-functional. Relevance logics have been devised to provide better accounts of the logic of "implies".

iff (if and only if)
biconditional,
equivalent,
equals,
eq

equivalent
equivalent

ABA iff B
TTT
TFF
FTF
FFT

and
conjunction

and, &

and

ABA and B
TTT
TFF
FTF
FFF

nand - not and

nand, |

nand

ABA nand B
TTF
TFT
FTT
FFT
This operator is also known as the "Sheffer stroke", after H.M.Sheffer. It is "universal" in that it can be used to define all the other boolean operators.

xor - exclusive or

neq (not equivalent)

not equal

xor

ABA xor B
TTF
TFT
FTT
FFF

nimp
not implies
ABA nimp B
TTF
TFT
FTF
FFF

nif - not if
ABA nif B
TTF
TFF
FTT
FFF

nor - not or

nor

nor

ABA nor B
TTF
TFF
FTF
FFT

n-ary:

For n>2 there are too many different operators to enumerate them. A method for building them from 2-ary operators is provided.
We assume that we know the truth table of the required operator. Using the truth table we will write down an expression using only dyadic operators which gives the right results. The table on the right shows part of an adder which computes a carry bit from three input bits.
ABCxxx(A, B, A)
TTTT
TTFT
TFTT
TFFF
FTTT
FTFF
FFTF
FFFF
First we simplify the table by discarding all rows which give the result "F". Since the result column no longer contains any information we discard it. We now have a table of all the combinations of input values for which the output is to be true.
ABC
TTT
TTF
TFT
FTT
Next we split the table up into its individual rows, pretend that these are formulae and form their disjunction.
ABC
TTT
ABC
TTF
ABC
TFT
ABC
FTT
Finally, each row of the table is translated into a conjunction in which all the input variables occur, either plain or negated according to whether they are required to be true or false in the row being translated.
(A B C)
(A B C)
(A B C)
(A B C)

universal sets:

A universal set of operators is a set from which all others can be defined. Here are the minimal universal sets.
nand
nor
bottom implies
bottom if
not and
not or
not implies
not if
not nimp
not nif
noteq and
noteq or
noteq implies
noteq if
noteq nimp
noteq nif
bottom equiv and
bottom equiv or
bottom equiv nimp
bottom equiv nif

index:

A hyperlinked table of all the names, symbols and diagrams.
0
1
biconditional
and
conjunction
disjunction
eq
equals
equivalent
exclusive or
false
if
iff
implies
inclusive or
material implication
nand
nimp
nor
not
not and
not equivalent
not if
not implies
not or
only if
or
true
xor
top

bottom

and

&

or

not

-

not equal

equiv

equivalent

implies

implies

if

if

|

scheffer stroke

nor

and

or

xor

not

nand

nor


UP HOME © RBJ created 1999/9/27 modified 2000/3/5