Truth Table Exercise

PDF

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

L-System Melody Assignment

To this assignment I am using the following L-System:
Koch Curve
Example:
Vocabulary: {A, B, C}
Start: A
Productions... A-> A B A C A C A B A
B-> B
C-> C
Derivation: G0= A
G1= A B A C A C A B A
G2= A B A C A C A B A B A B A C A C A B A C A B A C A C A B A C A B A C A C A B A B A B A C A C A B A

 For my melody, I will use G1.
A B A C A C A B A
My notes:
A=FQ AQ CQ AQ DQ CQ EQ DW
B=DQ EQ DQ EQ GQ
C=DQ FW DQ DQ FQ DQ

Final melody:

Title:

"This is far from a melody"

FQ AQ CQ AQ DQ CQ EQ DW DQ EQ DQ EQ GQ FQ AQ CQ AQ DQ CQ EQ DW DQ FW DQ DQ FQ DQ FQ AQ CQ AQ DQ CQ EQ DW DQ FW DQ DQ FQ DQ FQ AQ CQ AQ DQ CQ EQ DW DQ EQ DQ EQ GQ FQ AQ CQ AQ DQ CQ EQ DW


 Song

The ND (L-Tree+ CFG) melody generation task

Steps: 
  1) Generate the L-Treedefined by the following two sproot growing processes :

A|_ a _|B      B|_ b _|A

2)      Draw the three of level 5

3)      Twice derive a string of terminals from nonterminal BAR 3 in CFG for  that we have been  using – arranging for two different sequence  to result

4)      Associate A with the result of one bar 3 derivation associate B with the other result of bar 3 derivation.

5)      Replace each instance of A and B in the level 5 of the tree.

6)      Write down the melody that is generated as a sequence of JFugue symbols

7)      Generate a sound file

Result of each step:

1-2)

3)

Bar3 => (3 p3 d3)

            => (12) (3 pitch pitch pitch d3)

            => (26) (3 f pitch pitch d3)

            => (25) (3 f e pitch d3)

            => (28) ( 3 f e a d3)

            => (16) ( 3 f e a h q  q)

 Bar3 => (3 p3 d3)

          => (12) (3 pitch pitch pitch d3)

          => (23) (3 c pitch pitch d3)

          => (24) (3 c d pitch d3)

          => (25) ( 3  c d e d3)

          => (15) ( 3 c d e q h h) 
4)

 A =     FH EQ AQ

 B =   CQ DH EH

5)

A B B A B A A B B A A B A B B A B A A B A B B A A B B A B A A B

6)

FH EQ AQ CQ DH EH CQ DH EH FH EQ AQ CQ DH EH FH EQ AQ FH EQ AQ CQ DH EH CQ DH EH FH EQ AQ FH EQ AQ CQ DH EH FH EQ AQ CQ DH EH CQ DH EH FH EQ AQ CQ DH EH FH EQ AQ FH EQ AQ CQ DH EH FH EQ AQ CQ DH EH CQ DH EH FH EQ AQ FH EQ AQ CQ DH EH CQ DH EH FH EQ AQ CQ DH EH FH EQ AQ FH EQ AQ CQ DH EH

7)

Song

Recursive Transitional Network

Song Generated using a die and the networks:

(1 e w) (4 f g a c h q i i) (3 c d e  q h q )( 2 a b h h) (4 c d g a h i i q ) ( 3 e d g q q h)(2 b b h h) (1 a w )

EW FH GQ AI CI CQ DH EQ AH BH CH DI GI AQ EQ DQ GH BH BH AW

Music
Pdf

Context Free Grammar Assignment 2

Production rules:

1)      Expression -> Symbol

2)      Symbol -> { Star } | [ Star ] | ( Star )

3)      Star -> “void”

4)      Star -> *

5)      Star -> * Star

6)      Star -> Symbol Star

Terminals: * [] {} () “void”

NonTerminals: Expression Symbol Star

Start Symbol: Expression

Test 1:

{[**][](***)}

Expression=>1 Symbol

                =>2 { Star }

                =>6 { Symbol Star}

                =>2 { [ Star ] Star}

                =>5 { [ * Star] Star}

                =>4 { [ * *] Star}

                =>6 { [ * *] Symbol Star}

                =>2 { [ * *] [Star] Star}

                =>3 { [ * *] [] Star}

                =>6 { [ * *] [] Symbol Star}

                =>2 { [ * *][] (Star) Star}

                =>5 {{**}[] (* Star) Star}

                =>5 {{**}[] (* * Star) Star}

                =>5 {{**}[] (* * * Star) Star}

                =>4 {{**}[] (* * * *) Star}

                =>3{{**}[] (* * * *) }

Test 2:

{}

Expression =>1 Symbol

                  =>2 { Star }

                  =>3 {}

Test 3:

[ (*) *]

Expression =>1 Symbol

                   =>2 [ Star]

                   =>6 [ Symbol Star ]

                   =>2 [ ( Star) Star]

                   =>4 [(*)Star]

                   =>4 [(*)*]


PDF

Context Free Grammar Assignment

In this assignment I was supposed to produce a melody using a context free grammar. Based in the grammar and using a generator of random numbers( to choose the rules), I did this directly derivations : 
             Note : The number before the string is the rule number.

Melody    => (1) bar bar bar bar bar bar bar bar

                => (2) bar1 bar bar bar bar bar bar bar

                => (6) (1 p1 d1) bar bar bar bar bar bar bar

                => (10) (1 pitch d1) bar bar bar bar bar bar bar

                => (23) (1 c d1) bar bar bar bar bar bar bar

                => (14) (1 c w) bar bar bar bar bar bar bar

                => (3) (1 c w) bar2 bar bar bar bar bar bar

                => (7) (1 c w) (2 p2 d2) bar bar bar bar bar bar

                => (11) (1 c w) (2 pitch pitch d2) bar bar bar bar bar bar

                => (24) (1 c w) (2 d pitch d2) bar bar bar bar bar bar

                => (23) (1 c w) (2 d d d2) bar bar bar bar bar bar

                => (15) (1 c w) (2 d d h h) bar bar bar bar bar bar

                => (4) (1 c w) (2 d d h h) bar3 bar bar bar bar

                => (8) (1 c w) (2 d d h h) (3 p3 d3) bar bar bar bar

                => (12) (1 c w) (2 d d h h) (3 pitch pitch pitch d3 ) bar bar bar bar

                => (26) (1 c w) (2 d d h h) (3 f pitch pitch d3) bar bar bar bar

                => (25) (1 c w) (2 d d h h) (3 f e pitch d3) bar bar bar bar

                => (28) (1 c w) (2 d d h h) ( 3 f e a d3) bar bar bar bar

                => (16) (1 c w) (2 d d h h) ( 3 f e a h q  q) bar bar bar bar

                =>  (3) (1 c w) (2 d d h h) ( 3 f e a h q  q) bar2 bar bar bar

                =>  (7) (1 c w) (2 d d h h) ( 3 f e a h q  q) (2 p2 d2) bar bar bar

                =>  (11) (1 c w) (2 d d h h) ( 3 f e a h q  q) (2 pitch pitch d2) bar bar bar

                =>  (29) (1 c w) (2 d d h h) ( 3 f e a h q  q) (2 b pitch d2) bar bar bar

                =>  (28) (1 c w) (2 d d h h) ( 3 f e a h q  q) (2 b a d2) bar bar bar

                => (15) (1 c w) (2 d d h h) ( 3 f e a a h q  q) (2 b a h h) bar bar bar

                => (3) (1 c w) (2 d d h h) ( 3 f e a a h q  q) (2 b a h h) bar2 bar bar

                => (7) (1 c w) (2 d d h h) ( 3 f e a a h q  q) (2 b a h h) (2 p2 d2 ) bar bar

                => (11) (1 c w) (2 d d h h) ( 3 f e a a h q  q) (2 b a h h) (2 pitch pitch d2 )bar bar

                => (23) (1 c w) (2 d d h h) ( 3 f e a a h q  q) (2 b a h h) (2 c pitch d2 )bar bar

                => (27) (1 c w) (2 d d h h) ( 3 f e a a h q  q) (2 b a h h) (2 c g d2 )bar bar

                => (15) (1 c w) (2 d d h h) ( 3 f e a a h q  q) (2 b a h h) (2 c g  h h )bar bar

                => (2) (1 c w) (2 d d h h) ( 3 f e a a h q  q) (2 b a h h) (2 c g  h h )bar1 bar

                => (6) (1 c w) (2 d d h h) ( 3 f e a a h q  q) (2 b a h h) (2 c g  h h ) (1 p1 d1) bar

                => (10) (1 c w) (2 d d h h) ( 3 f e a a h q  q) (2 b a h h) (2 c g  h h ) (1 pitch d1) bar bar

                => (25) (1 c w) (2 d d h h) ( 3 f e a a h q  q) (2 b a h h) (2 c g  h h ) (1 e d1) bar

                => (14) (1 c w) (2 d d h h) ( 3 f e a a h q  q) (2 b a h h) (2 c g  h h ) (1 e w) bar

                => (3) (1 c w) (2 d d h h) ( 3 f e a a h q  q) (2 b a h h) (2 c g  h h ) (1 e w) bar2

                => (7) (1 c w) (2 d d h h) ( 3 f e a a h q  q) (2 b a h h) (2 c g  h h ) (1 e w) (2 p2 d2)

                => (11) (1 c w) (2 d d h h) ( 3 f e a a h q  q) (2 b a h h) (2 c g  h h ) (1 e w)(2 pitch pitch d2)

                => (24) (1 c w) (2 d d h h) ( 3 f e a a h q  q) (2 b a h h) (2 c g  h h ) (1 e w) (2 d pitch d2)

                => (28) (1 c w) (2 d d h h) ( 3 f e a a h q  q) (2 b a h h) (2 c g  h h ) (1 e w) (2 d a d2)

                => (15) (1 c w) (2 d d h h) ( 3 f e a a h q  q) (2 b a h h) (2 c g  h h ) (1 e w) (2 d a h h)

 After that, I transformed the last string to a JFugue string :

Last String: (1 c w) (2 d d h h) ( 3 f e a a h q  q) (2 b a h h) (2 c g  h h ) (1 e w) (2 d a h h)

Result of the combination: cw dh dh fh eq aq bh ah ch gh ew dh ah

Finally, putting this string in the SimplePlayer it produced this song file:

Song File

Pdf version of this assignment