SI242: Deduction

Deduction!

We have seen how tautologies that have equivalence ($\Leftrightarrow$) as their top-most operator give us rules we can use to rewrite formulas without changing their meaning (truth table). Like the fact that $(a\vee b) \Leftrightarrow (b \vee a)$ is a tautology allows us to switch the left and right sides of an "or" without changing meaning (i.e. $\vee$ is commutative). Tautologies with implication ($\Rightarrow$) as the top-most operator have a different (but at least as important) role: they allow us to make logical deductions.

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.

The justification for this is that $(a \Rightarrow b) \wedge a \Rightarrow b$ is a tautology, i.e. it is true for any interpretation. Let's see what we can do with this one rule of deduction.

Given: (u & ~v) => (w | z), (w | z) => (x & y), and u & ~v, prove x & y

   Things I know are true  How I know they are true
1: (u & ~v) => (w | z)     [Given]
2: (w | z)  => (x & y)     [Given]
3: u & ~v                  [Given]
4: w | z                   [Modus ponens with 1 and 3]
5: x & y                   [Modus ponens with 2 and 4]

From the given facts we made two deductions, both from Modus Ponens, ultimately deriving the new fact x & y. So what's new here? I mean, couldn't we have proved this by construting the truth table for ((u & ~v) => (w | z)) & ((w | z) => (x & y)) & (u & ~v) => x & y and checking that we have a tautology? Yes, but the truth table would have 64 rows, instead of the two deduction steps we just used. So deduction allowed us to prove this new result in many fewer steps. But also, deduction doesn't just verify or prove things we've already hypothesized for ourselves: deduction produces new facts! For example, we learned that w | z follows from the givens, which we didn't know or hypothesize before. Most importantly, deduction becomes the primary tool when we move to higher level logics, when we make logical arguments in math and CS proofs, and when we reason logically in other aspects of life.

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]

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!).]

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]

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 => c and ~(a|~b), prove c
1: b => 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: c         [Modus Ponens on 1 and 5]

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 (check with truth table!),
	so the argument is valid.

There is a standard deduction rule that we can use for this, by the way.

Contrapositive: if A => B is true, then ~B => ~A is true. [Note: applying the contrapositive to ~B => ~A just gets you back to A => B.]

This rule of deduction is valid because, as we can check, (A=>B) => (~B=>~A) is a tautology. Using the contrapositive rule of deduction, we get a nice derivation of ~A in propositional logic:

	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!