Logic

Based on 21-127 Concepts of Mathematics

• A proposition is a statement to which it makes sense to assign a truth value (either ’true’ or ‘false’)
• A proof is an argument that demonstrates its truth (they have audiences!)

• true proposition:
  • $\pi$ is irrational
  • Clive has 2 eyes
• false proposition:
  • It is currently raining
  • Clive has 3 eyes
  • $2+2=3$
• unknown/unproven proposition:
  • Every even number > 2 can be expressed as the sum of two prime numbers (aka Goldbach conjecture)
  • There is alien in space

• assumptions are things we know or assume to be true
• gaol is what we are trying to show.

(Some are from other units)

• WTS = want to show
• AFSOC = as for sake of contradiction
• WLOG = with out loss of generality
• IS = induction step
• BC = base case
• IH = induction hypothesis
• s.t. = such that

• logical structure - the skeleton of the proposition
• symbolic logic - the formal system we use to examine the structure of a proposition
• propositional formula - a symbolic expression that represents a proposition using:
  • propositional variables (usually $p, q, r$) for simpler propositions inside the big one
  • logical operators - symbols that combine things like ‘and’, ’not’, ‘or’, ‘if… then’…

• Conjunction $\wedge$ approximately as “and”
• Disjunction $\vee$ approximately as “or” (inclusive)
• Implication $\Rightarrow$ if something is true then something else is true
• Bidirectional $\Leftrightarrow$ if and only if (shortened as “iff”) viz. $(p \Rightarrow q) \wedge (q \Rightarrow p)$
• negation $\neg$ approximately as “not”

• Universal Quantifier $\forall$ - reads “for all”
  • $\forall x \in X, p(x)$ reads “all elements $x$ in $X$ satisfies $p(x)$”
• Existential Quantifier $\exists$ - reads “there exists”
  • $\exists x \in X, p(x)$ reads “there exists an $x$ in $X$ satisfies $p(x)$”

• A logical formula is an expression built using:
  • predicates i.e. statements e.g. $x > y$, $p(x)$, etc.
  • logical operators
  • quantifier

Every theorem we want to prove in 21-127 Concepts of Mathematics can be expressed as a logical formula!!!

Given logical formulae $\varphi$ and $\psi$, they are logically equivalent if $\varphi \Leftrightarrow \psi$. We then write $\varphi \equiv \psi$.

Truth table is a good way to determine if logical formulae are logically equivalent.

A truth table of propositional formula $\varphi$ is a tabular representation of the truth value of $\varphi$ and its sub formulae depending on all possible combination of truth value of its propositional variables.

Truth table of some logical formulae

Notice F $\Rightarrow$ T and F $\Rightarrow$ F. This is called “vacuous truth”.

Theorem: Given logical formulae $\varphi$ and $\psi$, then $\varphi \equiv \psi$ iff columns in their truth tables are the same.

Some useful logical equivalence:

• $(p \Rightarrow q) \equiv (\neg p \vee q)$
• $(p \Rightarrow q) \Leftrightarrow (\neg q \Rightarrow \neg p)$ aka contrapositive

A logical formula is maximally negated if no $\neg$ sign is outside of other operators or quantifiers.

Informally, deMorgan’s laws talk about duality viz. there’s a way to go between $\wedge$ and $\vee$ and a way to go between $\forall$ and $\exists$.

Ways to “push” negation inward (provable, but omitted):

• Law of double negation
  • $\neg (\neg p) \equiv p$
• DeMorgan’s law for logical operators
  • $\neg (p \wedge q) \equiv (\neg p) \vee (\neg q)$
  • $\neg (p \vee q) \equiv (\neg p) \wedge (\neg q)$
• DeMorgan’s law for quantifiers. Let $X$ be a set:
  • $\neg(\forall x \in X, p(x)) \equiv \exists x \in X,(\neg p(x))$
  • $\neg(\exists x \in X, p(x)) \equiv \forall x \in X,(\neg p(x))$
• Equivalency for implications
  • $\neg(p \Rightarrow q) \equiv p \wedge(\neg q)$
  • $\neg(p \Leftrightarrow q) \equiv (p \wedge(\neg q)) \vee ((\neg p) \wedge q)$

• Direct proof - assume what’s known, derive the conclusion
• Proof by contradiction - assume the opposite of the conclusion, derive a contradiction
• Proving universally quantified statements - prove the statement true for any arbitrary element
  • e.g. “every integer is rational”. Proof: let $x \in \mathbb{Z}$, then $x = \frac{x}{1}$. $1 \in \mathbb{Z}$ => $x$ rational.
• Proving existential statements - find one that satisfies the desired property!
  • e.g. “there exists a rational integer”. Proof: $2 \in \mathbb{Z}$ and $2 \in \mathbb{Q}$ as required.