SI242: Deduction

Modus ponens review

Recall from last class: Logical deduction is concerned with deriving new facts from facts you already know. We have rules of deduction that provide a mechanism for doing this. In propositional logic, the tautologies with implication as the top-most operator are the deduction rules. Here's an example with what is arguably the most important rule of deduction: modus ponens.

Modus ponens: For any two formulas $F$ and $G$, if $F\Rightarrow G$ and $F$ are both known to be true then you may deduce (by modus ponens) that $G$ is also true. More precisely, under any interpretation in which $F\Rightarrow G$ is true and $F$ is true, $G$ is also true.

We saw two examples last class of modus ponens in action. Here's one more super-simple example to remind you:

Given: $u \wedge \neg v \Rightarrow (w \vee z)$ and $u \wedge \neg v$, prove $w \vee z$.
Things I know are true		How I know they are true
1:	$(u \wedge \neg v) \Rightarrow (w \vee z)$	[Given]
2:	$u \wedge \neg v$	[Given]
4:	$w \vee z$	[Modus ponens with 1 and 2]

In some sense, Modus Ponens is the only deduction rule in propositional logic, as long as we recognize that a tautology can always be introduced as a new "known fact". Why? Because using another deduction rule boils down to applying modus ponens anyway. For example, the proof to the left that uses and-elimination

Given: x => ~y and x & (z|y), prove ~y.

1: x => ~y        [Given]
2: x & (z|y)      [Given]
3: x & (z|y) => x [Tautology A & B => A with A = x, B = z|y]
4: x              [Modus ponens on 3 and 2]
5: ~y             [Modus ponens on 1 and 3]

A few other deduction rules

Any tautology with implication ($\Rightarrow$) at the top-level give us something we can use as a deduction rule. For example, here are a few more deduction rules:

And-elimination: if $A \wedge B$ is known to be true, then $A$ is true. [This deduction rule is valid because $A \wedge B \Rightarrow A$ is a tautology (do a truth table check if you need to!).]

Or-introduction: if $A$ is known to be true, then $A \vee B$ is true. [This deduction rule is valid because $A \Rightarrow (A \vee B)$ is a tautology (do a truth table check if you need to!).]

And-introduction: if $A$ is known to be true and $B$ is known to be true, then $A \wedge B$ is true. [Yes this is very obvious!]

Warning There is no "Or-elimination" rule!

Here is a simple proof using some of our deduction rules:

Given: x => ~y and x & (z|y), prove ~y.
1: x => ~y    [Given]
2: x & (z|y)  [Given]
3: x          [And-elimination on 2] Note: A&B=>A is the tatuology here, with A=x, B=(z|y)
4: ~y         [Modus ponens on 1 and 3]

Some simplification rules

associativity/commutitivity/distributivity
De Morgan's Laws
$\neg(a\vee b) \Leftrightarrow \neg a \wedge \neg b$
$\neg(a\wedge b) \Leftrightarrow \neg a \vee \neg b$
$\neg \neg a \Leftrightarrow a$ : double negation
$(a \Rightarrow b) \Leftrightarrow (\neg b \Rightarrow \neg a)$ : equivalence of the contrapositive
$\neg(a \Leftrightarrow b) \Leftrightarrow (a \Leftrightarrow \neg b)$ : negation-of-equivalence
$a \Rightarrow b \Leftrightarrow \neg a \vee b$ : implication rewriting

It's important to keep in mind that the rewriting/simplifications we have been doing are also valid steps in a proof. The big difference is that they restate something already known to be true in a different, but equivalent, form. Deduction rules like Modus Ponens give us a new fact --- a new formula known to be true that is, in general, not equivalent to anything already known. So here is a proof that mixes deductions and rewriting:

Given: b|d => c and ~(a|~b), prove c
1: b|d => c   [Given]
2: ~(a | ~b)  [Given]
3: ~a & ~~b   [Rewriting with De Morgan's laws on 2]
4: ~~b        [And-elimination on 3]
5: b          [Rewriting using double negation on 4]
6: b|d        [Or-introduction on 5]
7: c          [Modus Ponens on 1 and 6]

ACTIVITY

Here is a proof that gives the "facts" from each deduction step, but not justifications. Your job is to add for each step the justification, either "given" or the deduction rule (or simplifcation rule) that justify each step. If the deduction step is based on a rule we've given a name to, you can use the name. Otherwise, write down the tautology that justifies the step.
```
Given x => y, ~x => z, and ~z, prove y
1: x => y
2: ~x => z
3: ~z => ~~x
4: ~z
5: ~~x
6: x
7: y	  
```
Here is a puported proof (it's actually invalid!) that gives just the "facts" from each deduction step, but not the justifications. Identify the erroneous step, i.e. the step that is not a valid deduction. This should correspond to a supposed "deduction step" that is not actually a tautology!
```
Given y => z, x and x=>(y|w), prove z
1: x => (y|w)
2: x         
3: y|w       
4: y
5: y => z
6: z	  
```
Given: $x \Rightarrow z$, $w \Rightarrow x \wedge y$, and $w$, Prove $z$.

Understanding logical arguments

The first item on our list of reasons to study logic is understanding logical arguments. Here is one example we gave:

 	EXAMPLE PROBLEM ABOUT LOGICAL ARGUMENT
	Suppose traffic law in a town states:

	LAW: if 20 more more mph over speed limit, then fine must be greater than or equal to $150
	Consider the following two arguments (each is about a different scenario):
	ARG1: "My fine was less than $150, therefore I must not have been 20 or more mph over the limit!"
	ARG2: "Your fine was greater than or equal to $150, therefore you were speeding by 20 or more mph!"
	One of these arguments is logically sound, the other is flawed.  Which?  Why?  How to convince
	others that one is logically sound and the other is not?

ARG1: Now let's try to see if our understanding of deduction in propositional logic can help us here.

	LAW: if 20 more more mph over speed limit, then fine must be greater than or equal to $150
	
	let A = "20 more more mph over speed limit"
        let B = "fine greater than or equal to $150"
	
	ARG1 is that given the LAW (which in prop. logic is A => B) and that the
	person's fine was less than $150 (which in prop. logic is ~B),
	they want to deduce that they were not going 20 or more over
	the limit (which in prop. logic is ~A).  Here is their
	argument:
	1: A => B [given]
        2: ~B     [given]
	3: ~A     [?????]
	The conclusion is valid if (A => B) ⇔ (~B => ~A) is a tautology
	(i.e. that 1 and 2 imply 3).  It is ... it is the equivalence
	of the contrapositive (or you can check with truth table!), 
	so the argument is valid. The full argument is thus:
	
	1: A => B   [given]
        2: ~B       [given]
	3: ~B => ~A [contrapositive of 1]
	4: ~A       [modus ponens on 3 and 2]

ARG2: Now let's try to see if our understanding of deduction in propositional logic can help us with ARG2.

	LAW: if 20 more more mph over speed limit, then fine must be greater than or equal to $150
	
	let A = "20 more more mph over speed limit"
        let B = "fine greater than or equal to $150"

	ARG2 is that given the LAW (which in prop. logic is A => B) and that 
	your fine is greater than or equal to $150 (which in prop. logic is B),
	they want to deduce that you were speeding by 20 or more mph
	(which in prop. logic is A).  So here is their argument:
	1: A => B [given]
	2: B      [given]
	3: A      [?????]
	The conclusion is valid if (A => B) & B => A is a tautology
	(i.e. that 1 and 2 imply 3) ... but it is not!  In fact, the
	truth table for (A => B) & B => A shows us that A=false,B=true
	is an interpretation under which (A => B) & B => A evaluates
	to false.  Thus, A is not a logical consequencde of A => B and
	B, and ARG2 is an invalid argument!

	Note: this is an example of a common mistake in logical
	reasoning.  Essentially this argument assumes that A=>B being
	true implies that B=>A is true... which it is not!  "B => A"
	is called the "converse" of A=>B.  And it is not true that a
	statement implies its converse!