HOMEWORK #4: PROPOSITIONAL LOGIC II

---

1. (R&N, §7.8, p. 237, #7.7)
   Using a truth table, semantically verify that DeMorgan's Law of Distributivity of ~ (negation) over ^ (conjunction) is a tautology:

   ~(P ^ Q) <-> (~P v ~Q)

   ---

2. (R&N, §7.8, p. 238, #7.9)
   Given the following, can you prove that the unicorn is mythical? How about magical? Horned?

   If the unicorn is mythical, then it is immortal, but if it is not mythical, then it is a mortal mammal. If the unicorn is either immortal or a mammal, then it is horned. The unicorn is magical if it is horned.

   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:

   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:

   • Schagrin, Morton L.; Rapaport, William J.; & Dipert, Randall R. (1985), Logic: A Computer Approach (New York: McGraw-Hill) (SEL: BC138 .S32 1985)

   • Rapaport, William J. (1992), "Logic, Propositional", in Stuart C. Shapiro (ed.), Encyclopedia of Artificial Intelligence, 2nd edition (New York: John Wiley): 891-897.

   ---

3. Let's add to the definition of a well-formed formula of propositional logic the following 3-place connective:

   If P, Q, R are wffs, then so is if P then Q else R.

   (a) Give a truth table for it.

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