# Discrete Mathematics: Logic

([Up](https://hackmd.io/@alexhkurz/SJ1cc-dDr))

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$, $\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$ || $\neg A$ | negation
|||| $A\to B$ | implication

Implication can be defined as $A\to B = \neg A \vee B$. [^implication]

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).[^equationsproplog]

[^equationsproplog]: Some observations:
- The laws are formally similar to the ones that we use for arithmetic, such as $--a=a$ or $-(a\cdot b)=(-a)\cdot (-b)$ or $a\cdot(b+c)=a\cdot b + a\cdot c$. This similarity can be made precise if we think of the laws of propositional logic as laws for computing with the 'truth values' $\{0,1\}$ instead of integers. (Historically, that was how Boole discovered Boolean algebra.)
- There is a duality principle: For every law there is a 'dual law' obtained from replacing $\wedge$ by $\vee$ and vice versa.

\begin{align}
\neg\neg A & = A\\
\neg(A\vee B) & = \neg A\wedge\neg B \\
\neg(A\wedge B) & = \neg A\vee\neg B \\
A\wedge(B\vee C) & = (A\wedge B)\vee (A\wedge C) \\
\neg(A\to B) & = A \wedge\neg B \\
\end{align}

[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{align}
A\to B & = \neg B\to\neg A \\
\end{align}

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". [^languagelogic]

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

| Logic |Name
|:---|:---|
| $\forall x. A(x)$ | for all $x$ we have $A(x)$
| $\exists x. A(x)$ | there is $x$ such that $A(x)$

We have used this above to write $Even$ in symbolic notation.

[^implication]: The truth table of implication is

| $A$ | $B$ | $A\Rightarrow B$
|:---:|:---:|:---:|
|false | false | true
|false | true | true
|true | false | false
|true | true | true

In particular $false \Rightarrow true$ is $true$.

**Challenge:** Is this the only reasonable truth table for implication?

[^languagelogic]: While the sentences "what doesn't kill you makes you strong" and "what doesn't make you strong, kills you" are logically equivalent, one sounds plausible and the other doesn't. Why?

## Further Reading

- The Wikipedia articles on [Boole](https://en.wikipedia.org/wiki/George_Boole), [Venn](https://en.wikipedia.org/wiki/John_Venn), [Boolean Algebra](https://en.wikipedia.org/wiki/Boolean_algebra), [Venn Diagrams](https://en.wikipedia.org/wiki/Venn_diagram), [First-Order Logic](https://en.wikipedia.org/wiki/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](https://www.maa.org/press/periodicals/convergence/origins-of-boolean-algebra-in-the-logic-of-classes-george-boole-john-venn-and-c-s-peirce) also available as [pdf](https://www.maa.org/sites/default/files/images/upload_library/46/Pengelley_projects/Project-7/Project-7-boole-venn-peirce.pdf).
- The Introductions of Boole's [The Mathematical Analysis of Logic](https://www.gutenberg.org/files/36884/36884-pdf.pdf) (1847) and Chapter I of [An Investigation of the Laws of Thought](https://www.gutenberg.org/files/15114/15114-pdf.pdf) (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; ...)

<!---