Boolean Operators

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 Almost Universal The Rest nif nimp

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 names context of use false true used in logic and philosophy F T abbreviations for truth tables 0 1 used in electronic engineering in 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 , - A notA F T T F

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.

or disjunction, inclusive or A B A or B T T T T F T F T T F F F

if reverse material implication , A B A if B T T T T F T F T F F F T

implies material implication, only if , A B A implies B T T T T F F F T T F F T 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 A B A iff B T T T T F F F T F F F T

and conjunction , & A B A and B T T T T F F F T F F F F

nand - not and , | A B A nand B T T F T F T F T T F F T 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) A B A xor B T T F T F T F T T F F F

nimp not implies A B A nimp B T T F T F T F T F F F F

nif - not if A B A nif B T T F T F F F T T F F F

nor - not or A B A nor B T T F T F F F T F F F T

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. A B C xxx(A, B, A) T T T T T T F T T F T T T F F F F T T T F T F F F F T F F F F F

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. A B C T T T T T F T F T F T T

Next we split the table up into its individual rows, pretend that these are formulae and form their disjunction. A B C T T T A B C T T F A B C T F T A B C F T T

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.

nimp nif

nimp nif

nimp 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

& -

|

---

© created 1999/9/27 modified 2000/3/5