Concepts and Definitions

In this document the basic definitions and important laws of Boolean algebra are stated.

Basic Definitions

Boolean Algebra

This is the main entry point. An algebra is define by the actual classes used for its domain, functions and variables.

Boolean Domain

S := {1, 0}

These base elements are algebra-level singletons classes (only one instance of each per algebra instance), called TRUE and FALSE.

Boolean Variable

A variable holds an object and its implicit value is TRUE.

Implemented as class or subclasses of class Symbol.

Boolean Function

A function \(f: S^n \rightarrow S\) (where n is called the order).

Implemented as class Function.

Boolean Expression

Either a base element, a boolean variable or a boolean function.

Implemented as class Expression - this is the base class for BaseElement, Symbol and Function.

NOT

A boolean function of order 1 with following truth table:

x NOT(x)
0 1
1 0

Instead of \(NOT(x)\) one can write \(\sim x\).

Implemented as class NOT.

AND

A boolean function of order 2 or more with the truth table for two elements

x y AND(x,y)
0 0 0
0 1 0
1 0 0
1 1 1

and the property \(AND(x, y, z) = AND(x, AND(y, z))\) where \(x, y, z\) are boolean variables.

Instead of \(AND(x, y, z)\) one can write \(x \& y \& z\).

Implemented as class AND.

OR

A boolean function of order 2 or more with the truth table for two elements

x y OR(x,y)
0 0 0
0 1 1
1 0 1
1 1 1

and the property \(OR(x, y, z) = OR(x, OR(y, z))\) where \(x, y, z\) are boolean expressions.

Instead of \(OR(x, y, z)\) one can write \(x|y|z\).

Implemented as class OR.

Literal

A boolean variable, base element or its negation with NOT.

Implemented indirectly as Expression.isliteral, Expression.literals and Expression.literalize().

Disjunctive normal form (DNF)

A disjunction of conjunctions of literals where the conjunctions don’t contain a boolean variable and it’s negation. An example would be \(x\&y | x\&z\).

Implemented as BooleanAlgebra.dnf.

Full disjunctive normal form (FDNF)

A DNF where all conjunctions have the same count of literals as the whole DNF has boolean variables. An example would be \(x\&y\&z | x\&y\&(\sim z) | x\&(\sim y)\&z\).

Conjunctive normal form (CNF)

A conjunction of disjunctions of literals where the disjunctions don’t contain a boolean variable and it’s negation. An example would be \((x|y) \& (x|z)\).

Implemented as BooleanAlgebra.cnf.

Full conjunctive normal form (FCNF)

A CNF where all disjunctions have the same count of literals as the whole CNF has boolean variables. An example would be: \((x|y|z) \& (x|y|(\sim z)) \& (x|(\sim y)|z)\).

Laws

In this section different laws are listed that are directly derived from the definitions stated above.

In the following \(x, y, z\) are boolean expressions.

Associativity

  • \(x\&(y\&z) = (x\&y)\&z\)
  • \(x|(y|z) = (x|y)|z\)

Commutativity

  • \(x\&y = y\&x\)
  • \(x|y = y|x\)

Distributivity

  • \(x\&(y|z) = x\&y | x\&z\)
  • \(x|y\&z = (x|y)\&(x|z)\)

Identity

  • \(x\&1 = x\)
  • \(x|0 = x\)

Annihilator

  • \(x\&0 = 0\)
  • \(x|1 = 1\)

Idempotence

  • \(x\&x = x\)
  • \(x|x = x\)

Absorption

  • \(x\&(x|y) = x\)
  • \(x|(x\&y) = x\)

Negative absorption

  • \(x\&((\sim x)|y) = x\&y\)
  • \(x|(\sim x)\&y = x|y\)

Complementation

  • \(x\&(\sim x) = 0\)
  • \(x|(\sim x) = 1\)

Double negation

  • \(\sim (\sim x) = x\)

De Morgan

  • \(\sim (x\&y) = (\sim x) | (\sim y)\)
  • \(\sim (x|y) = (\sim x) \& (\sim y)\)

Elimination

  • \(x\&y | x\&(\sim y) = x\)
  • \((x|y) \& (x|(\sim y)) = x\)