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.

1. 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)
2. Disjunctive form statements are composed of disjunctions or conjunctions.

   • (¬P^{Q) &#711; (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.