The file a3.hs will not compile until you add your student ID number by writing it after the =:

— Your student ID:

student_id :: Integer

student_id =

You do not need to write your name. When we download your submission, onQ includes your

name in the filename.

If you are working in a group of 2, put the second student ID in a comment, like this:

— Your student ID:

student_id :: Integer

student_id = 11112222 — 33334444

2 Q2: Truth tables

2.1 Formulas

In this assignment, we represent a logical formula as the data type Formula. Every Formula has one of the following forms:

type Variable = String

data Formula = Top — truth (always true)

| Bot — falsehood (contradiction)

| And Formula Formula — conjunction

| Or Formula Formula — disjunction

| Implies Formula Formula — implication

| Not Formula — negation

| Atom Variable — atomic proposition (“propositional variable”)

deriving (Eq, Show)

For example, if vA, vB and formula2 are defined as follows:

vA = Atom “A”

vB = Atom “B”

formula2 = Implies Bot (And vA vB)

then formula2 represents “if false then (A and B)”, and can be drawn as the tree

2.2 Valuations and truth tables

A Valuation maps each atomic proposition variable to a Boolean:

type Valuation = [(Variable, Bool)]

For example, the valuation [(“A”, False), (“B”, True)] indicates that Atom “A” is considered false, and Atom “B” is considered true. Under this valuation, the formula And vA vB would be false (because vA is False in the valuation), but the formula Implies vA vB would be true (because vB is true in the valuation).

2.3 Q2a: getVariables

Complete the function getVariables, which gathers all the variables (like “A”, “B”, etc.) that appear in a formula. getVariables should never return any duplicates: given the formula And vA vA, that is, And (Atom “A”) (Atom “A”), your implementation of getVariables should return

[“A”], not [“A”, “A”].

(Hint: Read the comment in a3.hs about the Haskell library function nub.)

getVariables :: Formula -> [Variable]