boolean-logic.org

Boolean logic

The most basic, yet somewhat useful, form of logic is Boolean logic (named after George Boole, 1815-1864). In this logic, we have variables that can be true or false, and we have ways of “connecting” or “relating” these variables. In fact, Boole (and De Morgan) described an algebra over these variables and relations, so we have a variety of equivalences that allow us to translate one form into another.

Logical relations

Besides variables (which, again, are just true or false), we have the following relations:

• $∧$ which we call “and”
• $∨$ which we call “or”
• $¬$ which we call “not”

$∧$ and $∨$ relate two variables: $x ∧ y$ and $x ∨ y$. $¬$ can be applied to one entity: $¬ x$.

This can all be composed, too: $¬ (x ∨ (y ∧ ¬ z))$.

Truth tables

Having a bunch of symbols (regardless of what we call them) does not do much for us. We need a way of determining whether the value of a sentence is true or false. (A “sentence” is a composition of variables and relations.)

The truth tables for the basic relations are so simple we’ll just describe them: $x ∧ y$ is true if and only if both $x$ and $y$ are true; $x ∨ y$ is true if and only if at least one of $x$ or $y$ is true; and $¬ x$ is true only if $x$ is false.

Now, we can figure out the truth of a complicated sentence by finding the truth-value of each part. We build a table for this operation because we need to keep track of all the different values that the variable may hold.

For what values of $x$, $y$, and $z$ make this true? $¬ (x ∨ (y ∧ ¬ z))$

We break the sentence into its main parts and put them all in the table.

$x$	$y$	$z$	$¬ z$	$y ∧ ¬ z$	$x ∨ (y ∧ ¬ z)$	$¬ (x ∨ (y ∧ ¬ z))$
T	T	T	F	F	T	F
T	T	F	T	T	T	F
T	F	T	F	F	T	F
T	F	F	T	F	T	F
F	T	T	F	F	F	T
F	T	F	T	T	T	F
F	F	T	F	F	F	T
F	F	F	T	F	F	T

We see that there are three variable assignments that make the whole expression true: $x$ is false, $y$ is true, and $z$ is true; $x$ is false, $y$ is false, and $z$ is true; and $x$ is false, $y$ is false, and $z$ is false.

Boole’s and De Morgan’s Laws

• $¬ F ≡ T$
• $¬ T ≡ F$
• $x ∨ ¬ x ≡ T$
• $x ∨ F ≡ x$
• $x ∨ T ≡ T$
• $x ∧ T ≡ x$
• $x ∧ F ≡ F$
• $x ∨ y ∨ z ≡ x ∨ (y ∨ z) ≡ (x ∨ y) ∨ z$
• $x ∧ y ∧ z ≡ x ∧ (y ∧ z) ≡ (x ∧ y) ∧ z$
• $x ∨ y ≡ y ∨ x$
• $x ∧ y ≡ y ∧ x$
• $x ∧ (y ∨ z) ≡ (x ∧ y) ∨ (x ∧ z)$
• $x ∨ (y ∧ z) ≡ (x ∨ y) ∧ (x ∨ z)$
• $¬ (x ∨ y) ≡ (¬ x) ∧ (¬ y)$
• $¬ (x ∧ y) ≡ (¬ x) ∨ (¬ y)$
• $x ∨ x ≡ x$
• $x ∧ x ≡ x$
• $¬ ¬ x ≡ x$
• $x ∧ (x ∨ y) ≡ x$
• $x ∨ (x ∧ y) ≡ x$

Examples

Using the above rules, we can simplify complex expressions into equivalent simpler expressions:

• $z ∨ ¬ (y ∧ z) ≡ z ∨ (¬ y ∨ ¬ z) ≡ (z ∨ ¬ z) ∨ ¬ y ≡ T ∨ ¬ y ≡ T$
• $¬ (x ∧ y) ∧ (¬ x ∨ y) ∧ (¬ y ∨ y) ≡ ¬ (x ∧ y) ∧ (¬ x ∨ y) ≡ (¬ x ∨ ¬ y) ∧ (¬ x ∨ y) ≡ ¬ x ∨ (¬ y ∧ y) ≡ ¬ x$