CSE 472/572, Spring 2002

#### HW #5: PROPOSITIONAL LOGIC

 Last Update: 5 March 2002 Note: material is highlighted
1. Russell & Norvig, Ch. 6, p. 180: #6.2, Distributivity of over , De Morgan's Law (first one)

2. Russell & Norvig, Ch. 6, p. 181: #6.4

3. Russell & Norvig, Ch. 6, p. 181: #6.5

In doing this problem, you might find the following additional rules of inference for the natural-deduction system that I am introducing in lecture to be useful (though note that you do not need anything that is not in Ch. 6):

```vIntro:  From P                From Q
-----------           -----------
Infer (PvQ)           Infer (PvQ)

vElim:   From (PvQ)            From (PvQ)
and  -P               and  -Q
----------            ----------
Infer Q               Infer P

<=>Intro:  From (P => Q)       From (P => Q)
and  (Q => P)       and  (Q => P)
---------------     ---------------
Infer (P <=> Q)     Infer (Q <=> P)

<=>Elim:   From (P <=> Q)      From (P <=> Q)
--------------      --------------
Infer (P => Q)      Infer (Q => P)
```

Also: You can't use natural deduction (or any other syntactic proof-technique) to prove that you can't prove something. But you can prove that you can't prove something, by using semantic proof-techniques, such as truth tables or Wang's Algorithm.

For more details on the natural-deduction system introduced in lecture, see:

4. Let's add to the definition of a well-formed formula of propositional logic the 3-place connective:
if P then Q else R

(a) Give a truth table for it.

(b) Define it in terms of , , and . (I.e., your definition will use some or all of those binary connectives.)

 DUE AT START OF LECTURE: WED., MAR. 6