# derived Boolean operations

Recall that a Boolean algebra is an algebraic system $A$ consisting of five operations:

1. 1.

two binary operations: the meet $\wedge$ and the join $\vee$,

2. 2.

one unary operation: the complementation ${}^{\prime}$, and

3. 3.

two nullary operations (constants): $0$ and $1$.

From these operations, define the following “derived” operations (on $A$): for $a,b\in A$

1. 1.

(subtraction) $a-b:=a\wedge b^{\prime}$,

2. 2.

(symmetric difference or addition) $a\Delta b$ (or $a+b$)$:=(a-b)\vee(b-a)$,

3. 3.

(conditional) $a\to b:=(a-b)^{\prime}$,

4. 4.

(biconditional) $a\leftrightarrow b:=(a\to b)\wedge(b\to a)$, and

5. 5.

(Sheffer stroke) $a|b:=a^{\prime}\wedge b^{\prime}$.

Notice that the operators $\to$ and $\leftrightarrow$ are dual of $-$ and $\Delta$ respectively.

It is evident that these derived operations (and indeed the entire theory of Boolean algebras) owe their existence to those operations and connectives that are found in logic and set theory, as the following table illustrates:

symbol $\backslash$ operation Boolean Logic Set
$\vee$ or $\cup$ join logical or union
$\wedge$ or $\cap$ meet logical and intersection
${}^{\prime}$ or $\neg$ or ${}^{\complement}$ complement logical not complement
$0$ bottom element falsity empty set
$1$ top element truth universe
$-$ or $\setminus$ subtraction set difference
$\Delta$ or $+$ symmetric difference symmetric difference (http://planetmath.org/SymmetricDifference)
$\to$ conditional implication
$\leftrightarrow$ biconditional logical equivalence
$|$ Sheffer stroke Sheffer stroke

${{{{}\end{center}\inner@par SomeoftheelementarypropertiesofthesederivedBooleanoperatorsare% :\begin{enumerate} \enumerate@itema-0=a and a-a=0-a=a-1=0, \enumerate@item(A,+,\wedge,0,1) is a ring (a Boolean ring), \enumerate@item all Boolean operations can be defined in terms of the Sheffer % stroke |. \end{enumerate}\inner@par Theproofsofthesepropertiesmimictheproofsforthepropertiesofthecorrespondingoperatorsfoundinnaivesettheoryandpropositionallogic% ,suchasthisentry(\texttt{http://planetmath.org/LogicalConnective}).% \begin{flushright}\begin{tabular}[]{|ll|}\hline Title&derived Boolean % operations\\ Canonical name&DerivedBooleanOperations\\ Date of creation&2013-03-22 17:58:49\\ Last modified on&2013-03-22 17:58:49\\ Owner&CWoo (3771)\\ Last modified by&CWoo (3771)\\ Numerical id&9\\ Author&CWoo (3771)\\ Entry type&Definition\\ Classification&msc 06E05\\ Classification&msc 03G05\\ Classification&msc 06B20\\ Classification&msc 03G10\\ Defines&symmetric difference\\ Defines&conditional\\ Defines&biconditional\\ \hline}\end{tabular}}}\end{flushright}\end{document}$