Activity: more applying propositional logic to understand arguments

Consider the following logical argument, where we would like to prove something about what courses MIDN Jones has taken.
Prereq rules
The prerequisites for IC211 are that you have taken IC210 or you have taken SI204. If you don't satisfy the prerequisites, you cannot enroll in IC211. If you do satisfy the prerequisites, and you have not taken IC211, you may enroll in IC211.

Given that MIDN Jones is enrolled in IC211 and he has not taken IC210, prove that he has taken SI204.

Your job is to convert this into propositional logic, and write a propositional logic proof that MIDN Jones has taken SI204. When you have done that, try to translate your proof into english. The english proof might skip obvious steps, and shouldn't refer to things like "modus ponens" or "and elimination", which we sort of take for granted in english speech and writing.

Follow-on problem: Consider the original and a new version (Version B below) of the rules:

Prereq Rules Version A (original) Prereq Rules Version B (new)
The prerequisites for IC211 are that you have taken IC210 or you have taken SI204. If you don't satisfy the prerequisites, you cannot enroll in IC211. If you do satisfy the prerequisites, and you have not taken IC211, you may enroll in IC211. The prerequisites for IC211 are that you have taken IC210 or you have taken SI204. If you satisfy the prerequisites, you can enroll in IC211. If you don't satisfy the prerequisites, you cannot enroll in IC211. If you have already taken IC211, you may not enroll in IC211.

Are these two rulesets (ignoring the MIDN Jones specific part of the original) the same? Or are there situations in which you get different results? How can we test this?

We can encode the two rulesets in propositional logic and use the prop. log. tool to generate a truth table. They are equivalent if the results column has all trues. Try it! 

( # Version A
  (~(t210 | t204) => ~e211)       # If you don't satisfy the prerequisites, you cannot enroll in IC211.
  &
  ((t210 | t204) & ~t211 => e211) # If you do satisfy the prerequisites, and you have not taken IC211, you may enroll in IC211.
)
<=>
( # Version B
  ((t210|t204) => e211)           # If you satisfy the prerequisites, you can enroll in IC211.
  &
  (~(t210 | t204) => ~e211)       # If you don't satisfy the prerequisites, you cannot enroll in IC211.
  &
  (t211 => ~e211)                 # If you already taken IC211, you may not enroll in IC211.
)
If you construct a truth table for this formula, you'll see there are several false's in the results column (so these two versions of the rules are not equivalent!), for example in the row corresponding to the interpretation 
t210=false, t204=true, e211=false, t211=true
The Version A formula evaluates to true for this interpretation, so the original rules are satisfied. However, the Version B formula evaluates to false, so the interpretation violates those rules. Should this be OK? Which rule set is correct?

Danger!!!

Simplification rules and deduction rules are different, and you can get into trouble by being sloppy about the difference.

A valid proof step     An invalid proof step 
1: a ∧ (¬b ∨ c) ⊕ c [Given]
2: a ∧ (b => c) ⊕ c [Implication rewriting on #1]
We can replace one subformula within a larger formula with another subformula, but only if the original subformula and the new subformula are equivalent. Our simplification/rewriting rules are based on an equivalence, so it's OK. The equivalnce in this case is the tautology: (x => y) <=> (¬x ∨ y) 

1: a ∧ (¬b ∧ c) ⊕ c [Given]
2: a ∧ (  ¬b  ) ⊕ c [And-elimination on #1]
Deduction rules are based on implication (=>) rather than equivalence. For example, And-elimination is based on the tautology: x ∧ y => x. The left and right hand sides here are definitely not equivalent, so we change the meaning of the formula when we replace (¬b ∧ c) with (¬b).

So the moral of the story is that you can deduce a new fact applying a deduction rule to existing facts, but not to pieces of existing facts. However, you can replace pieces of existing facts with equivalent pieces based on simplification/rewrite rules.

Equivalence splitting

In logical arguements, especially mathematical proofs, we see both $\Leftrightarrow$ and $\Rightarrow$. In fact, $A \Leftrightarrow B$ is equivalent to $(A\Rightarrow B) \wedge (B \Rightarrow A)$ (you can check that this with the propositional logic tool). Which means we have the following rewriting/simplifcation rule:

equivalence-splitting: $(A \Leftrightarrow B) \Leftrightarrow (A\Rightarrow B) \wedge (B \Rightarrow A)$

We can view these as deduction rules instead
  1. equivalence-splitting: if A <=> B is true, then (A=>B) & (B=>A) is true    (you can check that (A<=>B)=>(A=>B)&(B=>A) is a tautology)
  2. equivalence-introduction: if A=>B is true and B=>A is true, then A <=> B is true    (you can check that (A=>B)&(B=>A) => (A<=>B) is a tautology)

Example: Given a & b <=> c and c, prove b. 

1: a & b <=> c                   [given]	  
2: c                             [given]
3: (a & b => c) & (c => a & b)   [Equivalence splitting on 1]
4: c => a & b                    [And-elimination (with commutativity of ∧)]
5: a & b                         [Modus ponens on 4 and 2]
6: b                             [And-elimination on 5]
Note: When we split an equivalence up into two implications, we almost always immediately apply and-elimination to deduce whichever of the two implications we really care about. Since we do it often, we will typlically collapse the two into one step. So in the above, we make 3 and 4 a single step that we justify with equivalence splitting with and-elimination.

"If and only if" vs "If" (i.e. $\Leftrightarrow$ vs $\Rightarrow$) and definitions

We know that "if-then" usually indicates that there is an implication (=>) behind the scenes. Similarly, when you see "if-and-only-if", that means that we have an equivalence (<=>). For example, in mathematics we might write:

$x + y = x(1 + y/x)$ if and only if $x \neq 0$

If we let $a$ stand for "$x + y = x(1 + y/x)$" and $b$ stand for "$x \neq 0$", the above is stating $a \Leftrightarrow b$. And since we can deduce $b \Rightarrow a$ from $a \Leftrightarrow b$ (this is equivalence splitting), knowing $x \neq 0$ allows us to deduce $x + y = x(1 + y/x)$.

Important: Definitions are always "if-and-only-if" statements!

For example, we have: "Definition: a square is a rectangle with all sides equal." Logically, this is $Square \Leftrightarrow Rectangle \wedge AllSidesEqual$. To give another example: "Definition: if $P$ has four sides and all interior angles are 90 degrees, then we call it a rectangle." Because this is defining "rectangle", it is logically the equivalence $Rectangle \Leftrightarrow FourSides \wedge AllAngles90$, despite being in "if-then" form.

Important: Definitions can be introduced as given into proofs whenever you need them.

So let's look at a proof using these ideas. Given that $S$ is a square, prove that $S$ has four sides. 

varibles: SQ  = "S is a square" 
          SR  = "S is a rectangle" 
          S4  = "S has four sides" 
          SE  = "S has all sides equal"
          S90 = "S has all interior angels 90 degrees"

given: SQ, prove S4

---------in propositional logic----------      ------------in English-------------------------------------
1 SQ              [Given]                      }-- We are given that S is a square.
2 SQ <=> SR & SE  [Definition of "square"]     \
3 SQ => SR & SE   [Equivalence splitting on 2]  \_ Since S is a square, by definition it is a rectangle
4 SR & SE         [Modus Ponens on 3 and 1]     /
5 SR              [And-elimination on 4]       /
6 SR <=> S4 & S90 [Definition of "rectangle"]  \
7 SR => S4 & S90  [Equivalence splitting on 6]  \_ Since S is a rectangle, by definition it has four sides
8 S4 & S90        [Modus Ponens on 7 and 5]     /
9 S4              [And-elimination on 8]       /

Deducing an implication: assume A, prove B, deduce A => B

Sometimes you want to prove an implication. We allow ourselves another kind of proof step in order to make this easier. Specifically, we can introduce any formuala $A$ we like as new fact referred to as an assumption. Note, this is not a numbered fact like we are used to. It and anything we derive from it are given temporary numbers outside of the usual system. Eventually we close the assumption by reverting to the original numbering and adding $A \Rightarrow B$ as a fact, where $B$ is something derived from the assmption. Here is an example: 
Given: (x | y) => z, prove x => z
  1: (x | y) => z      [Given]
A.1: x                 [New assumption]
A.2: x | y             [Or-introduction on A.1]
A.3: z                 [Modus Ponens on 1 and A.2]
  4: x => z            [Closing assumption A.1 with A.3]
Let's apply this to prove: if a shape is not a rectangle, then it is not a square. Note that the way I've written this, we're trying to prove an implication, and that means we should be thinking about using assumptions. 
R : is a rectangle
S : is a square
E : all sides equal
Prove: ~R => ~S

  1: S <=> R & E     [Definition of square]
  2: ~(R & E) => ~S  [Equivalence splitting on 1 (with and-elimination)] 
  3: (~R | ~E) => ~S [De Morgan on 2]
A.1: ~R              [Assumption]
A.2: ~R | ~E         [Or-introduction]
A.3: ~S              [Modus ponens 3 and A.2]  
  4: ~R => ~S        [Closing assumption A.1 with A.3]

Deducing a contradiction

Suppose we are given: (a => b) => c, ~a => ~c and ~a. Consider the following deductions: 
	1: ~a => ~c      [Given]
	2: ~a            [Given]
	3: ~c            [Modus Ponens on 1 and 2]
	4: ~a|b          [Or-introduction 2]
	5: a => b        [Rewriting 4 using the tautology (a => b) <=> (~a | b)]
	6: (a => b) => c [Given]
	7: c             [Modus Ponens on 6 and 5]
	Huh?!?! 3 says ~c is true, and 7 says c is true!!!
So what happend here? Every step of our proof was valid, so given that (a => b) => c, ~a => ~c and ~a are all true, we proved that both c and ~c are true. Since, c and ~c both true is impossible, it must be that thee three "givens" all being true for the same interpretation is also possible. More concretely: ((a => b) => c) & (~a => ~c) & ~a is a contradiction! (You can check with a truth table.) This is a general idea:

Important: If using formulas $F_1, F_2, \ldots, F_k$ as givens you "prove" a contradiction (like $c \wedge \neg c$), then $F_1 \wedge F_2 \wedge \cdots F_k$ is a contradiction (i.e. evaluates to false for all interpretations).

Proof by contradiction

A common kind of proof argument in mathematics is proof by contradiction. To prove $X$, we assume (we often say "suppose" in this context) $\neg X$ is true and show that it leads to a contradiction, which means the assumption $\neg X$ must be false, from which we get that $X$ is true.
Here is an example of a typical "proof by contradiction" in mathematics.

$-1$ has no square root in the real numbers.
Assume $-1$ has a real square root, i.e. that there is a real number $x$ such that $x\cdot x = -1$. There are three cases: $x < 0$, $x = 0$ and $x > 0$. We will go through all three cases to prove by exhaustion that $x \cdot x \neq -1$.
  1. If $x < 0$, then $x\cdot x > 0$ and so $x \cdot x \neq -1$.
  2. If $x = 0$, then $x\cdot x = 0$ and so $x \cdot x \neq -1$.
  3. If $x > 0$, then $x\cdot x > 0$ and so $x \cdot x \neq -1$.
So we conclude that $x \cdot x \neq -1$. But this is a contradiction since we have both that $x\cdot x = -1$ and $x\cdot x \neq -1$. The assumption that $-1$ has a real square root led to a contradiction, therefore $-1$ does not have a real square root.

We can do the same thing in our propositional logic proofs.

Important: When you add assumption $X$ and deduce a contradiction from it, you can close the assumption with the deduction of $\neg X$.

For example: 
Given: a=>c, d & ~b and ~a => b, prove c
1: ~a => b [Given]
2: d & ~b  [Given]
3: ~b      [And-elimination]
A.1: ~a    [assumption]
A.2: b     [M.P. on 1 and A.1]
4: a       [Contradiction (3 and A.2) of assumption A.1]
5: a => c  [Given]
6: c       [Modus ponens 5 and 4]
Here's the justification for this deduction rule. A contradiction occurs when you derive false. In proof by contradiction, we make assumption $X$ and derive false from it. Thus, in closing the assumption we have derived $X \Rightarrow false$. But $X \Rightarrow false$ is equivalent to $\neg X$ ... just check the truth table.

Proof by contradiction makes some thing easier to prove. Here's an example: 

Given x => z & y, and z => ~y, prove ~x.
  1: x => z & y  [Given]
A.1: x           [Assumption]
A.2: z & y       [Modus ponens 1 and A.1]
A.3: z           [And-elimination A.2]
A.4: y           [And-elimination A.2]
A.5: z => ~y     [Given]
A.6: ~y          [Modus ponens A.5 and A.3]
  2: ~x          [Contradiction (A.4 and A.6) of assupmtion A.1]
Challenge: Prove this without proof by contradiction!

Christopher W Brown