Discrete Mathematics: Logic

(Up)

This is intended to be a recap of notation as covered in an introductory course on discrete mathematics or logic circuits.

Logic

We all know Venn diagrams. They support the operations of intersection

$A\cap B$, union

$A\cup B$, complement

$A^c$. If we forget that

$A,B$ are sets and we just take them as abstract 'propositions' we write instead

$A\wedge B$,

$A\vee B$,

$\mathrm{\neg }A$:

Name	Sets		Logic	Name
intersection	$A\cap B$		$A\wedge B$	and
union	$A\cup B$		$A\vee B$	or
complement	$A^c$		$\mathrm{\neg }A$	negation
			$A\to B$	implication

Implication can be defined as

$A\to B=\mathrm{\neg }A\vee B$. ^[1]

The laws of what is called Boolean logic or classical propositional logic are exactly the same as the laws for Venn diagrams. Some useful ones are the following. You don't need to remember them (just draw some Venn diagrams in case you forget).^[2]

$$\begin{array}{rl}\mathrm{\neg }\mathrm{\neg }A& =A\\ \mathrm{\neg }(A\vee B)& =\mathrm{\neg }A\wedge \mathrm{\neg }B\\ \mathrm{\neg }(A\wedge B)& =\mathrm{\neg }A\vee \mathrm{\neg }B\\ A\wedge (B\vee C)& =(A\wedge B)\vee (A\wedge C)\\ \mathrm{\neg }(A\to B)& =A\wedge \mathrm{\neg }B\end{array}$$

[Remark: There is a pattern here, namely that the negation of any operation (not, or, and, implication) can be "pushed down towards the leaves".]

Another usful one is "contraposition"

$$\begin{array}{rl}A\to B& =\mathrm{\neg }B\to \mathrm{\neg }A\end{array}$$

For example, if

$A=$ "doesn't kill you" and

$B=$ "makes you strong", then on the left we have "what doesn't kill you makes you strong" and on the right we have "what doesn't make you strong, kills you". ^[3]

It is also common to extend the logical notation to "quantifiers"

Logic	Name
$\mathrm{\forall }x.A(x)$	for all $x$ we have $A(x)$
$\mathrm{\exists }x.A(x)$	there is $x$ such that $A(x)$

We have used this above to write

$Even$ in symbolic notation.

Further Reading

• The Wikipedia articles on Boole, Venn, Boolean Algebra, Venn Diagrams, First-Order Logic.
• On the history of Boolean algebra I recommend Origins of Boolean Algebra in the Logic of Classes: George Boole, John Venn and C. S. Peirce also available as pdf.
• The Introductions of Boole's The Mathematical Analysis of Logic (1847) and Chapter I of An Investigation of the Laws of Thought (1853) are very much worth reading to gain a historical perspective. (Discusion topics: the seeds of modern computer science in these early works of the mid 1800s; the unity of logic and probability; the roots of modern logic in the Calculus of Newton and Leibniz; …)