# Concepts and Definitions

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

Contents

- Concepts and Definitions

  - Basic Definitions

  - Laws

## Basic Definitions

### Boolean Algebra

This is the main entry point. An algebra is defined 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\)