1. Nogmaals een vraag over syntactische bomen. Beschouw de volgende definitie:

    
   data Cat = S | NP | DET | CN | RCN | VP | TV deriving (Eq,Ord,Show) 
   
   data Structure = Word Cat String 
                  | Tree Cat Structure Structure deriving (Eq,Ord,Show)
   

   Hier is een definitie van een syntactische structuurboom voor "Barack respects Hilary":

   tree1 :: Structure 
   tree1 = Tree S (Word NP "Barack")
                  (Tree VP (Word TV "respects")
                           (Word NP "Hillary"))
   

   Maak nu zelf een tree2 definitie voor "some senator hates every democrat".
2. Een woordenboek kan er nu uitzien als een lijst van paren van woorden (strings) en categorieen. Bij voorbeeld:

    
   dict :: [(String,Cat)]
   dict = [("Barack", NP), ("Hillary", NP), 
           ("respects", TV), ("hates", TV),
           ("wins", VP), ("loses", VP), 
           ("some", DET), ("every", DET), 
           ("senator", CN),("democrat", CN)]
   

   Als een structuurboom (of een verzameling structuurbomen) gegeven is kun je daar zelf een woordenboek uit destilleren. Bij voorbeeld:

   Main> wrds tree1
   [("Barack",NP),("Hillary",NP),("respects",TV)]
   

   Schrijf de functie wrds die dit doet.
3. Nu kun je een structuurboom gaan checken aan een woordenboek, door te kijken of de categorisering die de structuurboom gebruikt overeenkomt met wat het woordenboek zegt. Schrijf een functie check :: Structure -> [(String,Cat)] -> Bool die dit doet. Een voorbeeld-aanroep:

   Main> check tree1 dict
   True
   

4. 1. Ga na of ~ p een logisch gevolg is van p -> q en q.
   2. Ga na of ~ p een logisch gevolg is van p -> q en ~ q.
   3. Volgt uit ~ p <-> ~ q dat p <-> q ?
   4. Zijn p -> (q -> r) en (p & q) -> r logisch equivalent?
5. Laat het volgende datatype voor (propositionele) formules gegeven zijn:

   data Form = Prop String
             | Not Form
             | Conj [Form]
             | Disj [Form]
             deriving (Eq,Ord) 
   
   instance Show Form where
     show (Prop name) = name
     show (Not f) = '~' : '(' : show f ++ ")"
     show (Conj fs) = '&' : show fs
     show (Disj fs) = 'v' : show fs
   

   Let op. Formules van de vorm Conj fs drukken de conjunctie uit van de lijst van formules fs. Formules van de vorm Disj fs drukken de disjunctie uit van de lijst van formules fs. Voorbeelden van formules zijn:

   p1 = Prop "p1" ; p2 = Prop "p2" ; p3 = Prop "p3"
   q1 = Prop "q1" ; q2 = Prop "q2" ; q3 = Prop "q3"
   r1 = Prop "r1" ; r2 = Prop "r2" ; r3 = Prop "r3"
   
   form1 = Disj [p1, Not p1]
   form2 = Conj [p1, Not p1]
   

   Schrijf een functie collectVars die de variabelen uit een formule haalt. Het type is collectVars :: Form -> [String]. Het is de bedoeling dat de lijst van variabelen geen duplikaten bevat. Een paar voorbeeld-aanroepen:

   Main> collectVars (Conj [form1, form2])
   ["p1"]
   Main> collectVars (Conj [form1, form2, Not p2, Disj [r1,r2]])
   ["p1","p2","r1","r2"]
   

6. Om een formule te kunnen evalueren, dat wil zeggen om te kunnen nagaan of de formule waar is of niet, moeten we weten of de propositievariabelen die erin voorkomen waar zijn. Wat we daarvoor nodig hebben is een lijst van paren van variabelen-namen en waarheidswaarden. Het Haskell type daarvoor is [(String,Bool)].

   Schrijf een functie eval :: [(String,Bool)] -> Form -> Bool die propositielogische formules evalueert. Een paar voorbeeld-aanroepen:

    
   Main> eval [("p1",True)] form1
   True
   Main> eval [("p2",True)] form1
   
   Program error: no info about p1
   
   Main> eval [("p1",False)] form1
   True
   

7. Als we eenmaal weten welke variabelen namen in een propositionele formule voorkomen willen we graag de lijst genereren van alle mogelijke valuaties voor die lijst van variabelen namen. Schrijf daarvoor een functie allVals :: [String] -> [[(String,Bool)]]. Een voorbeeld-aanroep:

    
   Main> allVals ["p1","p2"]
   [[("p1",True),("p2",True)],[("p1",True),("p2",False)],[("p1",False),("p2",True)],[("p1",False),("p2",False)]]
   

   NB: vanaf hier zijn de vragen bonusvragen.

8. Schrijf een functie tautology :: Form -> Bool die waar geeft als een propositielogische formule een tautologie is en anders onwaar, en een functie contrad :: Form -> Bool die waar geeft als een propositielogische formule een contradictie is en anders onwaar. Hint: gebruik de functie allVars uit de vorige opdracht. Een paar voorbeeld-aanroepen:

    
   Main> tautology form1
   True
   Main> tautology p1
   False
   Main> tautology form1
   True
   Main> tautology form2
   False
   Main> contrad p1
   False
   Main> contrad form1
   False
   Main> contrad form2
   True
   

9. Gebruik een van de functies uit de vorige opdracht om een implementatie te geven van propositielogisch gevolg: implies f1 f2 moet waar opleveren wanneer formule f1 formule f2 logisch impliceert, en anders onwaar. Een paar voorbeeld-aanroepen:

    
   Main> implies  p1 (Disj [p1,p2])
   True
   Main> implies  p1 (Conj [p1,p2])
   False
   

Huiswerk: Tekstbestand met alle antwoorden. Let op: de laatste twee vragen zijn bonusvragen. Deadline: maandag 9 juni, 12 uur 's middags. Per email inleveren bij Arno Bastenhof, met een cc naar Jan van Eijck.