Continue work on activity from last class!

Problems 3 and 4 from last class's activity are super important. These rules are known as De Morgan's Laws. Problem 5a is also super important. So here they are:

1. De Morgan's Laws: $\neg(a\vee b) \Leftrightarrow \neg a \wedge \neg b$ is a tautology, as is $\neg(a\wedge b) \Leftrightarrow \neg a \vee \neg b$.
2. Implication rewriting: $(a \Rightarrow b) \Leftrightarrow (\neg a \vee b)$ is a tautology.

Another application of logic - modeling programs

Number three on our list of reasons for Computer Scientists to study logic is to model and reason about programs and circuits (the building blocks of the physical computer). Here's an example of such an application. Suppose you and a partner are working on a program together. You've written the code

if (a && b) { // original
   X;
}
else {
  if (!b && !c) 
    Y;
  else
    X;
}

which your partner has suggested simplifying to:

if (a && b || c) // suggested simplification
  X;
else
  Y;

Are these two pieces of code equivalent, or are there circumstances in which one does "X" but the other does "Y"?

The original code does "X" when "a && b" is true and also when "a && b" is false and "!b && !c" is also false. Otherwise it does "Y". The suggested simplification does "X" when "a && b || c" is true, and does "Y" in all other cases. So, let's check whether the "X" cases are the same for both (we'll write it using C++'s boolean operators where we can):

Is (a && b || !(a && b) && !(!a && !c)) equivalent to (a && b || c)?

Of course truth tables give us a tool to use to check this:

From the truth table we see that (a,b,c)=(true,false,false), the two programs do different things - one does "X" but the other does "Y". Therefore, your partner's "simplification" is invalid! Silly partner.

ACTIVITY

• After writing and some debugging, your code includes

  if (x > 0 || y == 3)
    ;
  else
    x = abs(x/(y - 3));	

  Although the code works, you are (rightfully!) embarrassed to have that empty then-block to the if. Rewrite as an equivalent "if" with no "else" block. Explicitly show how the rewriting is done (i.e. justify steps) so you can be 100% sure the new "if" is equivalent to the old!

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 for 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.

Example 1: Suppose that both turbo ⇒ ¬stockbrakes and strockbrakes are known to be true. What can we prove?

   Things I know are true   How I know they are true
1: turbo ⇒ ¬stockbrakes     [Given]
2: strockbrakes             [Given]
3: ¬¬stockbrakes ⇒ ¬turbo   [Equivalence of contrapositive applied to 1 (rewriting rule)]
4: stockbrakes ⇒ ¬turbo     [double negation applied to 3]
5: ¬turbo                   [Modus ponens with 4 and 2]	

So we have deduced the new fact: ¬turbo. In fact, the above is a proof of ¬turbo given the facts turbo ⇒ ¬stockbrakes and strockbrakes. In other words, under any interpretation: if turbo ⇒ ¬stockbrakes and strockbrakes are both true then ¬turbo is true. In case you are sceptical, we can verify this with truth tables. In fact, there are two different ways to do so.

Version 1: verify our proof with truth tables	Version 2: verify our proof with truth tables
Consider the truth table for turbo ⇒ ¬stockbrakes The only interpretation in which turbo ⇒ ¬stockbrakes and strockbrakes are both true (the second row) is the interpretation in which turbo is false, i.e. ¬turbo is true.	We have proved that: if turbo ⇒ ¬stockbrakes and strockbrakes are both true then ¬turbo is true. Translating the if-then into a formula gives (turbo⇒¬stockbrakes)∧stockbrakes⇒¬turbo and we can verify that this statement is true for all interpretation with a truth table: Clearly this is a tautology.

Important: Deduction is a big deal because ...

1. We discover new facts through deduction. With truth tables or SAT solvers, we can only verify.
2. Deductive arguments are explanations. By contrast, SAT solvers are black boxes, we do not get to see how or why they give the answers they give.
3. Deduction models human reasoning.
4. Deduction works even in "higher order" logics where truth tables and SAT Solvers are not available to us.

A bigger example

Example 2: >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.