propositional-logic.org

Propositional logic

Boolean logic gave us a collection of equivalences that allows us to simplify (or complicate) expressions involving true/false variables and logical relations. That’s all fine and good, but (our presentation of) it was lacking any guidance about how to make an argument of the form “if we know $x ∨ ¬ y$ is true and we know $y$ is true, then it must be the case that $x$ is true.

Note that we will be adding the following logical relations.

$→$ (“if… then…”)

$x$	$y$	$x → y$
T	T	T
T	F	F
F	T	T
F	F	T

$↔$ (“if and only if… then…”)

$x$	$y$	$x ↔ y$
T	T	T
T	F	F
F	T	F
F	F	T

Besides Boole’s and De Morgan’s rules in the Boolean logic notes, we have some equivalences relating to $→$ and $↔$:

• $x → y ≡ ¬ y → ¬ x$ (“contrapositive”)
• $x → y ≡ ¬ x ∨ y$
• $x → (y → z) ≡ (x ∧ y) → z$
• $x ↔ y ≡ (x → y) ∧ (y → x) ≡ (x ∧ y) ∨ (¬ x ∧ ¬ y)$

Logical consequences and rules of inference

Suppose we have three sentences: $φ$, $ψ$, and $ρ$ (these variables are just names for possibly complex arrangements of variables and logical relations, from the Boolean logic notes).

We can make an argument of the form: $φ$ and $ψ$; therefore, $ρ$. This is either true or false. For example:

• $φ = x → y$
• $ψ = ¬ y → x$
• $ρ = y$

This argument is true if (and only if) there is no configuration of truth values for $x$ and $y$ such that both $φ$ and $ψ$ are true but $ρ$ is false. We say then that $ρ$ is a logical consequence of the compound statement “$φ$ and $ψ$.”

The idea is that $ρ$ cannot be a “consequence” of $φ$ and $ψ$ if both $φ$ and $ψ$ can be true but nevertheless $ρ$ is false.

As an example, consider these assignments of the variables:

• $φ =$ “All humans are mortal.”
• $ψ =$ “Socrates is a human.”
• $ρ =$ “Socrates is mortal.”

It’s not possible for $ρ$ to be false if both $φ$ and $ψ$ are true. Thus, $ρ$ is a logical consequence of $φ$ and $ψ$ (collectively).

There are many patterns of logical consequences. Here are some that will be useful in our journey:

• Modus ponens (MP):
  • $φ = x → y$
  • $ψ = x$
  • $ρ = y$
• Modus tollens (MT):
  • $φ = x → y$
  • $ψ = ¬ y$
  • $ρ = ¬ x$
• Disjunctive syllogism (DS):
  • $φ = x ∨ y$
  • $ψ = ¬ x$
  • $ρ = y$

  There is another form of this:

  • $φ = x ∨ y$
  • $ψ = ¬ y$
  • $ρ = x$
• Addition (Add):
  • $φ = x$
  • $ρ = x ∨ y$ (for any $y$; we have no need for $ψ$ here)
• Simplification (Simp):
  • $φ = x ∧ y$
  • $ρ = x$ (for any $y$)
• Conjunction (Conj):
  • $φ = x$
  • $ψ = y$
  • $ρ = x ∧ y$
• Hypothetical syllogism (HS):
  • $φ = x → y$
  • $ψ = y → z$
  • $ρ = x → z$
• Constructive dilemma (CD):
  • $φ = (x → y) ∧ (w → z)$
  • $ψ = x ∨ w$
  • $ρ = y ∨ z$
• Absorption (Abs):
  • $φ = x → y$
  • $ρ = x → (x ∧ y)$

Practice deductions

Now, given our relations and inference rules, we can collect some sentences and then deduce logical consequences of those sentences.

Suppose we know the following (don’t worry about what the variables actually mean; we’ll get to that issue later):

1. $c ∨ d$
2. $c → o$
3. $d → m$
4. $¬ o$

Ok, can we deduce that $m$ is a logical consequence? Yes:

5. $¬ c$ because of premises 2 and 4 plus modus tollens.
6. $d$ because of premise 1 and consequence 5 and disjunctive syllogism.
7. $m$ because of premise 3 and consequence 6 and modus ponens.