## 502 – Propositional logic

September 7, 2009

1. Introduction

These notes follow closely notes originally developed by Alexander Kechris for the course Math 6c at Caltech.

Somewhat informally, a proposition is a statement which is either true or false. Whichever the case, we call this its truth value.

Example 1 “There are infinitely many primes”; “${5>3}$”; and “14 is a square number” are propositions. A statement like “${x}$ is odd,” (a “propositional function”) is not a proposition since its truth depends on the value of ${x}$ (but it becomes one when ${x}$ is substituted by a particular number).

Informally still, a propositional connective combines individual propositions into a compound one so that its truth or falsity depends only on the truth or falsity of the components. The most common connectives are:

• Not (negation), ${\lnot,}$
• And (conjunction), ${\wedge,}$
• Or (disjunction), ${\vee,}$
• Implies (implication), ${\rightarrow,}$
• Iff (equivalence), ${\leftrightarrow.}$