HOMEWORK #4

Propositional Logic II

In what follows, I omit parentheses and set-theoretic braces where there is no ambiguity or where they would be distracting. Also, I have fixed the symbol for the material biconditional and for Greek-letter metavariables, which did not print on some browsers.

1. to use metavariables!

   Here are the elimination and introduction rules for inclusive disjunction:

   vIntro:  From                 From 
            -----------           -----------
            Infer (v)           Infer (v)
   
   
   vElim:   From (v)            From (v)
            and  ¬               and  ¬
            ----------            ----------
            Infer                Infer 
   

   Using these and any other rules of inference introduced in lecture, give natural-deduction proofs of the following:

   1. ¬P ^ (P v Q) Q
   2. ¬P ^ (P v Q) ^ (¬Q v R) R
   • Note: The following is not a rule of inference:

     From (¬v)
     and 
     -----------
     Infer 
     

     Nor do you need it to prove (b), above. (You may, however, need to use ¬Intro.) The rule above is, however, a derivable rule of inference. Thus, if you derive it and give it a name, you can then invoke it as a kind of "macro" or "procedure call".

   ---

2. Show, using truth tables, that the following wffs are tautologies:
   1. (¬P ^ (P v Q)) Q
   2. (¬P ^ (P v Q) ^ (¬Q v R)) R

   ---

3. Using a truth table, semantically verify that DeMorgan's Law of Distributivity of ¬ (negation) over ^ (conjunction) is a tautology:
   ¬(P ^ Q) (¬P v ¬Q)

   ---

4. Consider the following syntax and semantics for a propositional KR language:

   Syntax: The following are all and only the atomic wffs:

   Smoke, Fire, Heat

   Semantics:

   [[Smoke]]	=	There is smoke.
   [[Fire]]	=	There is fire.
   [[Heat]]	=	There is heat.

   Using the semantics given above, translate the following wffs into English:

   1. (Smoke Smoke)
   2. (Smoke Fire)
   3. (Smoke Fire) (¬Smoke ¬Fire)
   4. Smoke v Fire v ¬Fire
   5. ((Smoke ^ Heat)  Fire)   ((Smoke  Fire) v (Heat  Fire))
   6. (Smoke Fire) ((Smoke ^ Heat) Fire)

   ---

5. to clarify scope of question.

   Using truth tables, determine which of the wffs in 4(a)--4(f) are:

   • tautologies
     • i.e., true under all interpretations
     • i.e., true in all models
     • i.e., true for all possible assignments of truth values to the wffs' atomic subpropositions.

   • contradictions
     • i.e., false under all interpretations
     • i.e., false in all models
     • i.e., false for all possible assignments of truth values to the wffs' atomic subpropositions.

   • neither (sometimes called "contingent" wffs)

   ---