What is this blog?

I did this blog in purpose to show my work during the class " Generative Process and Formal Systems " . In this class we learned about formal systems, fractals, lambda calculations, propositional calculus, context free grammar and others subjects. Here you will find all my problem sets based in the book : GEB: an Eternal Golden Braid. And some problem sets based in class notes.

You also will find all music productions and presentations that I did during the course. Moreover, on the right there is two extras pages 'Escher"  and "Fractals". I hope you enjoy the stuff that you can see here, and sorry about my English, I am just a Brazilian international student who loves computer science and math ;D.

"I study Mathematics as a product of the human mind not as absolute." (Emil Post, 1920)

Logical Forms +

1)      Write a paragraph which says something significant about Jacques Herbrand and his contribution to symbolic logic.

R) Jacques Herbrand made contributions to mathematical logic creating the Herbrand`s theorem that stablishes a link between quantification theory and sentential logic which is important in that it gives a method to test a formula in quantification theory by successively testing formulas for sentential validity.

2)      Write a paragraph which says something significant about Alfred Horn and his contribution to symbolic logic.

R) Alfred Horn wrote the paper “On sentences which are true of direct unions of algebra”, and in this paper he describes Horn Clauses and Horn sentences. Later that clauses turned into the foundation of logic programming.

3)      Write a paragraph which says something significant about John Alan Robinson and his contribution to symbolic logic.

R) John Alan Robinson major contribution is to the foundation of automated theorem proving. Robinson also created the resolution principle. In 1996 he received the Herbrand Awards because of his research.

4)      Define disjunctive normal form.

R) A formula is said to be in disjunctive normal form if it has this form F1 \/ F2 \/ ….. Fn. Where each F is a conjunction of literals. Example: ( P /\ Q )\/( Q /\ P).

5)      Transform the following into disjunctive normal forms:

a)      (~P /\ Q) -> R

~(~P /\ Q ) \/ R    LQ2

 ( P \/ ~Q) \/ R      LQ5

b)      ~(P \/ ~Q)/\ (S ->T)

~(P \/ ~Q) /\ ( ~S \/ T) LQ2

 ( ~P /\ Q) /\ ( ~S \/ T)  LQ4

((~P /\ Q) /\ ~S) \/ (( ~P /\ Q) /\ T))   LQ7

c)       (P -> Q ) -> R

( ~P \/ Q) -> R LQ2

~( ~P \/ Q) \/ R   LQ2

( P/\ ~Q) \/ R    LQ4

6)      Define conjunctive normal form

R) Conjunctive normal form if it has this form F1 /\ F2 /\ ….Fn. Where each F is a disjunction of literals. Example: (p\/q) /\ ( p\/ q)

7)      Transform the following into conjunctive normal forms:

a)      P \/ (~P /\ Q /\ R)

(P \/ ~P) /\ ( P \/ Q) /\ (P \/ R)   LQ6

 True /\ ( P \/ Q) /\ ( P \/ R)

b)      ~(P -> Q)

~( ~ P \/ Q)   LQ2

(P /\ ~Q) LQ4

c)       (P -> Q) -> r

( ~P \/ Q) -> r LQ2

~( ~P \/ Q) \/ R LQ2

( P /\ ~Q) \/ R  LQ4

(R \/ P) /\ ( R \/ ~Q) LQ6

8)      State the resolution principle

                R) any two clauses C1 and C2, if there is a literal L1 and C1 that is complementary to a literal L2 in C2,then delete L1 and L2 from C1 and C2 , and construct disjunction of the remained clauses .The constructed clause is called the resolve of C1 and C2              

9)      Define what is meant by resolution deduction

R) Given a set S of clauses, a resolution deduction of clause C from S is a finite sequence C1,C2,…Cn

Of clauses such that C = cn and each Ci is either a clause in S or A resolve of clauses preceding Ci, A deduction of square from S is said to be a proof of j.

10)   Show by means of resolution that the formula U is logical consequence of the three formulas ( P ->S) and ( S -> U) and P

R)

1) (P -> S) part of G

 2) (S -> U) part of G

3) P part of G

4) ~U negation of Goal

5) (~P \/ S)  DNF

6) (~S \/ U) DNF'
7) S ( Resolving of 5+3)
8)~S(Resolving of  6+4)

9) SQUARE

11)   Show by means of the inconsistency truth table approach that the formula U is  a logical consequence of the three formulas ( P->S) and ( S -> U) and P

R)

12)   Define Horn clause

R) A Horn clause is a clause (a disjunction of literals) with at most one positive, unnegated  , literal. Conversely, a disjunction of literals with at most one negated literal is called a dual-Horne Clause.

13)   Can the formula ( P/\ Q /\ R) -> s be converted to a Horn clause

R) Yes.

~(P /\ Q /\ R) \/ S

(~P /\ ~Q /\ ~R ) \/ S

(~P \/ S) /\ (~Q \/ S) /\ (~R\/S)

(P -> S) /\ ( Q -> S) /\ (R -> S)

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