Propositional Calculus Problem Set

1.       Draw a set of recursive transition networks which define well-formed formulas in the propositional calculus

R:
2.       Thinking of the propositional calculus in the terms that Hofstadter presents it, that is, as the formal system he constructs in the chapter:

a)      How many axioms in the formal system?

R: Infinite axioms

b)      How many rules in the formals system

R:Nine

c)       What are the names that he gives to these rules?

R: Joining, Separation, Double-tilde, Fantasy, Carry-over, Detachment, Contrapositive, De Morgan`s. Switcheroo

d)      What is the one rule that you absolutely must use if you are to derive a theorem in this system?

R: The fantasy rule.

3.       Write down each of the rules of the system, just as Hofstadter does on page 187.

R: Joining Rule: If x and y are theorems, then < x /\ y > is a theorem

Separation Rule: if <x /\ y> is a theorem, then both x and y are theorems

Double-Tilde Rule: The string ‘ ~~’ ‘ can be deleted from any theorem. It can also be inserted into any theorem, provided that the resulting string is itself well-formed

Fantasy Rule: If y can be derived when x is assumed to be a theorem, then < x ) y > is a theorem

Carry-Over Rule: Inside a fantasy, any theorem from the reality one level higher can be brought in and used.

Rule of Detachment: If x and < x ) y> are both theorems, then y is a theorem

Contrapositive Rule: <x ) t> and < ~x) ~ y > are interchangeable

De Morgan`s Rule: <~x /\ ~y> and ~< x \/ y> are interchangeable

Switcheroo Rule: <x \/ y> and <~x  Y> are interchangeable

4.       Derive <<< P /\ Q > /\R >  < P /\ <Q /\ R >>>

R: (1)[                                    push

     (2)<<P/\ Q> /\R>        premise

     (3)P                                   separation

     (4)Q                                  separation

     (5)R                                   separation

     (6)Q/\R                           joining

     (7)<P /\ <Q /\R>>       joining

     (8)]                                    pop

      (9)<<<P/\Q>/\R>    < P /\<Q/\R>>>            fantasy rule

5.       Derive <<< P \/ Q >  < P \/ Q >>

R: (1)[                    push

    (2)<P\/Q>       premise

    (3)      [              push

    (4)      P\/Q      premise

    (5)      ]              pop

    (6)]                     pop

    (7) <<P \/Q>  <P \/Q>>       fantasy rule

6.       Derive a theorem in the propositional calculus that you think is a little bit interesting, one that neither I asked you to derive nor Hofstadter derived in his book

R: (1)[                                    push

(2)  P/\Q                              premise

(3) P                                       separation

(4)Q                                       separation

(5)          [                              push again

(6)                          ~P           premise

(7)          ]                              pop

(8)~P -> Q                           fantasy rule

(9) P \/ Q                             Switcheroo

(10)]                                      pop

(11)P /\Q -> P \/ Q           fantasy rule

7.       As Hofstadter mentions mid-way through the chapter, there is a decision procedure for WFFs in the propositional calculus, the method of truth tables. Learn what this method entails, if you are not already clear that, and write a description of the method that is clear and complete enough that one could easily apply it by referencing your description. That is, describe the process featuring truth tables by which one could determine whether or not a WFF is a theorem in the propositional calculus.

R: 1: Count how many variables you have.

2: Do 2^numberOfVariables. This is going to tell you how many rows your truth table will have

3: Create a column to each variable

4: Now you know the number of rows, make all possible combinations of values True(T or 1) and False(F or 0) using the column of yours variables

5: Look at the operators of your WFF and do the operations:

                Negation: (~F) is true if F is false, false if F is true

                Conjunction: (F and G) is true if both F and G are true. False otherwise

                Disjunction:  ( F V G) is true if at F or G are true. False otherwise.

                Implication: (F -> G) is true unless F is true and G is false

                Equivalence : ( F <-> G)  is true if F and G have the same value

                6: A formula F is said to be true under interpretation if F(formula) evaluates to true in the                 interpretation. Otherwise it is False in the interpretation

8.       Using the truth table based decision procedure, show that he heads will be cut off! Perhaps I should say a bit more, I Am referring to the section on Gantos Ax. And I am assignin you to show by means of a truth table that he following WFF is a theorem <<< P -> Q > /\ < ~P ) Q>> -> Q>

R:

P Q  P->Q    /\     ~P -> Q   ->Q

F F      T         F             F          T

T F      F         F             T          T

F T      T         T             T          T

T T      T         T             T          T

9.       Choose another interpretation for P and Q in Ganto`s statement – one that does not involve heads or axes. Write down the words for your proposition P. Write down the words for your proposition Q. Write down a sentence corresponding to Ganto`s Statement ( what he says to the praying monks) under your interpretation.

R: P= someone go back in the past

Q= the history will change

If someone go back in the past the history will change, and if someone do not go back in the past the history will also change.

10.   Write down in a meaningful manner, in no more than a few sentences, what you think is the most salient idea that Hofstadter has embedded in the text contained within the section titled Shortcuts and Derived Rules
R: Use shortcuts ( Derived Rules) can look like a good idea and seems reasonable, the problem is, once you use a derived rule the system will lose his formality because this rules are derived working outside the system.

11.   Write down in a meaningful manner, in no more than a few sentences, what you think is the most salient idea that Hofstadter has embedded in the text contained within the section titled Formalizing Higher Levels

R: Never mix levels of understanding. Identify when you are working in M-Mode and I-Mode is important.

12.   Write down in a meaningful manner, in no more than a few sentences, what you think is the most salient idea that Hofstadter has embedded in the text contained within the section titled Reflections on the Strengths and Weakness of the System

R: The propositional calculus is a simple system that produce very simple concepts, but it can be changed to incorporate new symbols and new rules.

13.   Write down in a meaningful manner, in no more than a few sentences, what you think is the most salient idea that Hofstadter has embedded in the text contained within the section titled Proofs vs Derivations

R: A derivation and a proof are “simple” in complementary senses of the word.

14.   Write down in a meaningful manner, in no more than a few sentences, what you think is the most salient idea that Hofstadter has embedded in the text contained within the section titled The handling of contradictions

R: Contradiction is a major source of clarification and progress in all domains of life.

15.   Opinion about the chapter

R:  I did like the chapter, the way that Hofstadter shows the propositional calculus and how simple and strong it can be if you understand how to use and do not pass its limitations. For me, the fantasy (push or pop) is really reasonable and I like this rule. 

PDF