PlanetMath (more info)
 Math for the people, by the people.
Encyclopedia | Requests | Forums | Docs | Wiki | Random | RSS  
Login
create new user
name:
pass:
forget your password?
Main Menu
Owner confidence rating: Very high Entry average rating: No information on entry rating
[parent] derived Boolean operations (Definition)

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

  1. two binary operations: the meet $ \wedge$ and the join $ \vee$,
  2. one unary operation: the complementation $ '$, and
  3. two nullary operations (constants): 0 and $ 1$.

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

  1. (subtraction) $ a-b:=a\wedge b'$,
  2. (symmetric difference or addition) $ a\Delta b$ (or $ a+b$) $ :=(a-b)\vee (b-a)$,
  3. (conditional) $ a\to b:=(a-b)'$,
  4. (biconditional) $ a\leftrightarrow b:=(a\to b)\wedge (b\to a)$, and
  5. (Sheffer stroke) $ a\vert b:=a'\wedge b'$.

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
$ '$ 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
$ \to$ conditional implication  
$ \leftrightarrow$ biconditional logical equivalence  
$ \vert$ Sheffer stroke Sheffer stroke  

Some of the elementary properties of these derived Boolean operators are:

  1. $ a-0=a$ and $ a-a=0-a=a-1=0$,
  2. $ (A,+,\wedge,0,1)$ is a ring (a Boolean ring),
  3. all Boolean operations can be defined in terms of the Sheffer stroke $ \vert$.

The proofs of these properties mimic the proofs for the properties of the corresponding operators found in naive set theory and propositional logic, such as this entry.



"derived Boolean operations" is owned by CWoo.
(view preamble)

View style:

Also defines:  symmetric difference, conditional, biconditional

This object's parent.
Log in to rate this entry.
(view current ratings)

Cross-references: propositional logic, terms, Boolean ring, ring, properties, equivalence, implication, set difference, universe, top, empty set, bottom, logical not, complement, logical and, union, logical or, Boolean, set theory, logic, connectives, theory, entire, operators, Sheffer stroke, subtraction, unary, join, meet, binary operations, operations, algebraic system, Boolean algebra
There are 15 references to this entry.

This is version 6 of derived Boolean operations, born on 2008-04-08, modified 2008-04-26.
Object id is 10489, canonical name is DerivedBooleanOperations.
Accessed 225 times total.

Classification:
AMS MSC03G10 (Mathematical logic and foundations :: Algebraic logic :: Lattices and related structures)
 06B20 (Order, lattices, ordered algebraic structures :: Lattices :: Varieties of lattices)
 03G05 (Mathematical logic and foundations :: Algebraic logic :: Boolean algebras)
 06E05 (Order, lattices, ordered algebraic structures :: Boolean algebras :: Structure theory)

Pending Errata and Addenda
None.
[ View all 1 ]
Discussion
Style: Expand: Order:
forum policy

No messages.

Interact
post | correct | update request | add derivation | add example | add (any)