Problem Set 1
Home Syllabus Lecture Slides Learning Haskell Problem Set 1 Problem Set 2 Problem Set 3 Problem Set 4 Problem Set 5 Problem Set 6 Problem Set 7 Problem Set 8 Problem Set 9

 

Due on Tuesday September 18

Semantics of Predicate Logic

  1. State the following propositions in predicate logic:
    bulletp is a prime number.
    bulleta is the greatest common divisor of b and c.
    bulletFermat's Last Theorem.
     
  2. Learn to run GHCi (the GHC Haskell interpreter) by running the Predicate Logic Interpreter, which you can find here.  The best way to do this is to save the file as "PredicateLogic.lhs" (it is currently a .txt file) and then load it from the command line in GHCi.  Read through the program and make sure that you understand all parts of it.  Try running a few of the examples at the command line to familiarize yourself with GHCi.
     
  3. Create a new file called "PS1.lhs" (in the same folder in which you saved PredicateLogic.lhs), whose first two lines of code should be:
     
    > module PS1 where
    > import PredicateLogic
     
    In this file, add your solutions to problem 1 above, and try running them in GHCi.
     
  4. Make the following extensions to the language of predicate logic:
    bulletAdd an exclusive or operator to the assertion language.
    bulletAdd an exponentiation operator to the integer expression language.
    bulletAdd integer expressions of the form:
        sum <var>: <intexp> to <intexp> . <intexp>
    such that, for example, "sum x: 1 to 5 . x+1" will evaluate to 20.

    For each of these extensions, provide the following:
    bulletan abstract grammar rule,
    bulleta denotational semantics equation,
    bulleta definition of the set of free variables, and
    bulleta substitution rule
    (the propositions regarding binding and substitution for for the predicate calculus should not change)

    Finally, modify the Predicate Logic Interpreter to implement these extensions, and test your code.

Solutions:

PS1Soln.txt
PS1Test.txt