# 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\)