In progress

- Scribe - Rob Quimby
- Editor - Matt Colyer
- Editor -

# Notes from Tuesday, October 19

## Logic

Logic is fundamentally an attempt to describe how thought works. A classic example is:

All men are mortals Socrates is a man ==================== Socrates is a mortal

The logic we're most concerned with is Propositional Logic (Boolean Algebra). The main distinguishing feature of propositional logic is that everything is either true or false, there are no states inbetween.

## Notation

- True: T, 1, #t
False: F, ┴, 0, #f

Conjunction: ^, &, ab, and

Disjunction: |, +, ˇ, or

Negation: ¬, ~, overbar (ā), !, not

Implication: ->,=>, the like

Equivalence: =, <=>, <->, ≡

## Rules

- If ¬¬p, then p (Double Negation Elimination)
- If p^q, then p (Rule of Inference)
- If p implies q, and p, then q (modus ponens!)
- p^q implies p is a tautology (statement that is always true)
(¬p)ˇ(p) Another tautology (the law of excluded middles)

pˇq = ¬((¬p)^(¬q)) De Morgan's Law

p^q = ¬((¬p)ˇ(¬q)) Also De Morgan's Law

**Soundness** means that true premises always lead to true conclusions.

**Completeness** means that anything that is true can be derived or proved.

## Forms

There are two main forms commonly used to express boolean algebra statements: Conjunctive and disjunctive.

- Conjunctive form statements are composed of conjunctions of disjunctions
(PˇQ) ^ (¬Pˇ¬Q) is a conjunctive XOr.

- Verifying truth for this form is generally O(n), but finding it can be (2^n)

- Disjunctive form statements are composed of disjunctions or conjunctions.
(¬P

^{Q) ˇ (P}¬Q) is a disjunctive XOr.- Both finding and verifying these statements tends to be O(n).

## Truth Tables

A truth value is a value of T or F for a proposition. These often end up in truth tables, like the one below.

p |
q |
p^q |

0 |
0 |
0 |

0 |
1 |
0 |

1 |
0 |
0 |

1 |
1 |
1 |