derived Boolean operations


Recall that a Boolean algebraMathworldPlanetmath is an algebraic system A consisting of five operationsMathworldPlanetmath:

  1. 1.

    two binary operationsMathworldPlanetmath: the meet and the join ,

  2. 2.

    one unary operation: the complementation , and

  3. 3.

    two nullary operations (constants): 0 and 1.

From these operations, define the following “derived” operations (on A): for a,bA

  1. 1.

    (subtraction) a-b:=ab,

  2. 2.

    (symmetric differenceMathworldPlanetmathPlanetmath or additionPlanetmathPlanetmath) aΔb (or a+b):=(a-b)(b-a),

  3. 3.

    (conditionalMathworldPlanetmath) ab:=(a-b),

  4. 4.

    (biconditionalMathworldPlanetmath) ab:=(ab)(ba), and

  5. 5.

    (Sheffer strokePlanetmathPlanetmath) a|b:=ab.

Notice that the operators and are dual of - and Δ respectively.

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

symbol \ operation Boolean Logic Set
or join logical or union
or meet logical and intersectionMathworldPlanetmathPlanetmath
or ¬ or complementPlanetmathPlanetmath logical not complement
0 bottom element falsity empty setMathworldPlanetmath
1 top element truth universePlanetmathPlanetmath
- or subtraction set differenceMathworldPlanetmath
Δ or + symmetric difference symmetric difference (http://planetmath.org/SymmetricDifference)
conditional implicationMathworldPlanetmath
biconditional logical equivalence
| Sheffer stroke Sheffer stroke

SomeoftheelementarypropertiesofthesederivedBooleanoperatorsare: 1. = - a 0 a and - a a = - 0 a = - a 1 = 0 , 2. ( A , + , ∧ , 0 , 1 ) is a ring (a Boolean ring), 3. all Boolean operations can be defined in terms of the Sheffer stroke | . Theproofsofthesepropertiesmimictheproofsforthepropertiesofthecorrespondingoperatorsfoundinnaivesettheoryandpropositionallogic,suchasthisentry(http://planetmath.org/LogicalConnective).Titlederived Boolean operationsCanonical nameDerivedBooleanOperationsDate of creation2013-03-22 17:58:49Last modified on2013-03-22 17:58:49OwnerCWoo (3771)Last modified byCWoo (3771)Numerical id9AuthorCWoo (3771)Entry typeDefinitionClassificationmsc 06E05Classificationmsc 03G05Classificationmsc 06B20Classificationmsc 03G10Definessymmetric differenceDefinesconditionalDefinesbiconditional