HOMEWORK #4

Propositional Logic II

In what follows, the following conventions are observed:

• I omit parentheses and set-theoretic braces where there is no ambiguity or where they would be distracting.

• "|-" is the "turnstile", representing the syntactic inference relation.

• ">" is used instead of the "horseshoe" to represent the material conditional.

• represents conditional.

• "=" is used instead of the "triple bar" to represent the material biconditional.

• "≡" for biconditional

1. Here are the elimination and introduction rules for inclusive disjunction:

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

   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 (¬PvQ)
     and P
     -----------
     Infer Q
     

     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. Using truth tables, determine which of the above wffs 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)

   ---