Logic
Table of Contents
1. Propositional Logic
The building block of logic is the notion of a proposition: a statement that is either true or false. These statements are examples of propositions:
- \(\sqrt{3}\) is irrational (true)
- \(6-2=3\) (false)
- Julius Caeser was 5'8" tall (indeterminate)
These statements are not propositions:
- \(2 + 2\) (this is an expression)
- \(3x + 17 = 42\) (what is \(x\)?)
Propositions should also not include fuzzy terms:
- 1 billion is a big number (what does "big" mean?)
1.1. Connectives
Propositions may be connected together using connectives. Three of the most basic logic connectives are:
- Conjunction: \(P \land Q\) (\(P\) AND \(Q\)) — true only when both \(P\) and \(Q\) are true.
- Disjunction: \(P \lor Q\) (\(P\) OR \(Q\)) — true when at least one of \(P\) and \(Q\) is true.
- Negation: \(\lnot P\) (NOT \(P\)) — true when \(P\) is false.
Statements like these, with variables, are called propositional forms.
A fundamental principle called the law of the excluded middle states that either \(P\) or \(\lnot P\) is true, but not both; thus, \(P \lor \lnot P\) is always true regardless of the truth value of \(P\). Such propositional forms, which are true regardless of the truth values of their variables, are called a tautology. Conversely, a statement like \(P \land \lnot P\), which is always false, is called a contradiction.
Perhaps one of the most important connective is the IMPLIES connective:
- Implication: \(P \implies Q\) (\(P\) IMPLIES \(Q\)) — this is the same as "if \(P\), then \(Q\)".
Here \(P\) is called the hypothesis of the implication, and \(Q\) the conclusion. An example of an implication is: "if you stand in the rain, then you will get wet." An implication is false only when \(P\) is true and \(Q\) is false: the example would only be false if you stood in the rain but didn't get wet. Note that not standing in the rain but still getting wet (when \(P\) is false but \(Q\) is true) does not prove the implication false.
Finally, there is also the IF AND ONLY IF connector:
- Biconditional: \(P \iff Q\) (\(P\) IF AND ONLY IF \(Q\), or \(P\) IFF \(Q\)) — this is true only if both \(P \implies Q\) and \(Q \implies P\) are true.
1.2. Truth Tables
We can define connectives formally using truth tables, which involve listing out all the possible combinations of inputs and the resulting output of the connectives:
| \(P\) | \(Q\) | \(P \land Q\) | \(P \lor Q\) | \(P \implies Q\) |
|---|---|---|---|---|
| T | T | T | T | T |
| T | F | F | T | F |
| F | T | F | T | T |
| F | F | F | F | T |
1.3. Logical Equivalencies
We can use logical equivalencies to transform propositional statements into other statements using connectives, which may help us analyze them. For example, we can transform the IMPLIES connective into a proposition using NOT and OR:
\begin{align} P \implies Q \equiv \lnot P \lor Q \end{align}Language can be used to intuitively grasp the truth of this equivalency: "if \(P\) then \(Q\)" is the same as "either \(P\) is false, otherwise \(Q\) is true." We can also prove this by checking the truth table:
| \(P\) | \(Q\) | \(P \implies Q\) | \(\lnot P\) | \(\lnot P \lor Q\) |
|---|---|---|---|---|
| T | T | T | F | T |
| T | F | F | F | F |
| F | T | T | T | T |
| F | F | T | T | T |
Given an implication \(P \implies Q\), we can also define its:
- Contrapositive: \(\lnot Q \implies \lnot P\)
- Converse: \(Q \implies P\)
The contrapositive is a logical equivalency, as it is always true: "if you stand in the rain, then you will get wet" is the same as "if you did not get wet, then you did not stand in the rain." However, the converse is not always true: getting wet did not imply you stood in the rain.
2. Predicates and Quantifiers
Sometimes, propositions like "Aristotle is a philosopher" and "Plato is a philosopher" are unwieldy to write, especially if you want to talk about lots of different people being philosophers. In these cases, we can introduce a predicate: a form that has a variable, and when replacing the variable makes that form either true or false. For example, instead of saying "Plato is a philosopher," we can write \(\text{Phil}(\text{Plato})\), where \(\text{Phil}(x)\) is a predicate that denotes "\(x\) is a philosopher."
Similarly, oftentimes we may also want to say something about a lot of simple propositions at once. For example, the proposition "for all natural numbers \(n\), \(n^2 + n + 41\) is prime" asserts all the propositions for \(n\) ranging over the natural numbers. In these cases, we introduce quantifiers, of which there are two types:
- Universal: \(\forall x\) — for all \(x\)
- Existential: \(\exists x\) — there exists \(x\)
Thus, given the set \(\mathbb{N}\) and the predicate \(P(x)\) to denote that \(x\) is prime, we can rewrite the proposition as \((\forall n \in \mathbb{N}) P(n^2 + n + 41)\). Note that quantifiers must act over some universe: here, the universe is \(\mathbb{N}\), the natural numbers.
Example: Quantifiers
We want to write the sentence "there are at most three distinct integers \(x\) that satisfy \(P(x)\)" using quantifiers. One way to do it is:
\begin{align} \exists x \exists y \exists z \forall d (P(d) \implies d = x \lor d = y \lor d = z) \notag \end{align}3. De Morgan's Laws
For \(P\) to be false is the same thing as for \(\lnot P\) to be true. De Morgan's laws provides rules for negating conjunctions and disjunctions:
\begin{align} \lnot (P \land Q) \equiv \lnot P \lor \lnot Q \\ \lnot (P \lor Q) \equiv \lnot P \land \lnot Q \end{align}Again, we can use language to understand these intuitively. If \(P \land Q\) is false, then that means that either \(P\) is false or \(Q\) is false. Similarly, if \(P \lor Q\) is false, then that means that both \(P\) and \(Q\) are false.
Similar laws also exist for quantifiers:
\begin{align} \lnot (\forall x P(x)) \equiv \exists x (\lnot P(x)) \\ \lnot (\exists x P(x)) \equiv \forall x (\lnot P(x)) \end{align}These are also intuitively grasped with language. The first one says that if \(P(x)\) is not true for all \(x\), then there exists some \(x\) such that \(P(x)\) is false. The second one says that if there does not exist some \(x\) for which \(P(x)\) is true, then for all \(x\) \(P(x)\) is false.