Computerlinguistik II, WS 2004/05              Aufgabenblatt 8
--------------------------------------------------------------
Ausgabe: Mi, 17.01.07                          Abgabe: Di, 23.1.07

Aufgabe 14
----------
a) Schreibe ein Prolog-Programm, freevars(+LamTerm,-VarList), das zu
   jedem LambdaTerm LamTerm die Menge der darin frei vorkommenden
   Variablen berechnet und als Liste VarList (in irgend einer Ordnung) 
   ausgibt. D.h. implementiere die Definition von free(t) aus
   den Folien. ['freevars', da Prolog schon ein 'free' hat]  Punkte 3

b) Auf den Folien steht keine Definition fuer die in einem Lambda-Term
   t gebunden vorkommenden Variablen. Gib eine (mathematische)
   Definition

     geb(t)

   für die Menge der in t gebundenen Variablen an. Wir haben ja schon
   oefter intuitiv benutzt, dass jedes lam(X,T) alle freien Vorkommen 
   von X in T 'bindet'. Mache die Definition so, dass auch das
   gezeigte Vorkommen von X in lam(X,_) als gebunden gilt.   Punkte 2

c) Schreibe ein Prolog-Programm gebvars(+LamTerm,-VarList), das zu
   jedem Lambda-Term eine Liste aller darin gebunden vorkommenden
   Variablen ausgibt.                                        Punkte 2

Hinweis: Benutze beim Vergleichen von Variablen nicht die Unifikation 
         (X = Y), sondern den Symbolvergleich (X == Y) von Prolog!

Aufgabe 15
----------
Wir haben in einer Aufgabe 7 (und der Musterloesung dazu) eine 
Grammatikregel fuer die Konjunktion von Nominalphrasen geschrieben,
die eine syntaktische Analyse fuer Nominalphrasen wie

    Kepler und Galilei      
    einige Planeten und alle Monde

liefert. Diese Ausdruecke sollten Nominalphrasen im Plural sein.

Die Bedeutung von Nominalphrasen NP definieren wir so, dass sie 
"auf die Bedeutung des Praedikats angewendet werden" (nicht
umgekehrt!), weshalb sie von der Form

     SemNP = lam(P,Quantor(X,(... P*X ...)))   oder
     SemNP = lam(P,          (... P*c ...)))   (fuer Konstante c)

ist, wobei fuer P eine Eigenschaft von Individuen X bzw. c eingesetzt
werden wird. (Z.B. erhaelt die NP "jeder Astronom" eine Bedeutung, 
deren Normalform 

             lam(P,all(X,(astronom(X) => P*X)))  

lautet.) Die Bedeutung einer einfachen Aussage wird dann durch die
Anwendung 

(1)          SemNP * P

auf eine geeignete Eigenschaft P ausgedrueckt.

a) Wie sollte Deiner Meinung nach der Lamda-Term lauten, der die
   Bedeutung von 

       Kepler und Galilei

   (in einfachen Saetzen) ausdrueckt? 

   Hinweis: Man nehme einen einfachen Satz wie

(2)    Kepler und Galilei arbeiten,

   gebe eine logische Formel Phi an, die das ausdrueckt, und
   abstrahiere dann vom verwendeten Praedikat.         Punkte 3

   Zeige, dass der vorgeschlagene Lambda-Term SemNP auf das 
   Praedikat P = lam(X,arbeitet(X)) angewendet (und normalisiert)
   die logische Formel Phi ergibt, d.h. 

       SemNP * lam(X,arbeitet(X))  --->  Phi  (mehrere Schritte).
   
b) Wie sollte entsprechend die Bedeutung der komplizierteren 
   Konjunktion 

       einige Planeten und alle Monde

   lauten?                                            Punkte 3

c) Und wie sollte also die Auswertungsregel fuer die Konjunktion
   beliebiger Nominalphrasen sein, d.h. die Klausel fuer sem/2
   im Fall

       sem([np(Art,[pl,Kas]),NP1,[und],NP2], SemNP) :-

           ... ? ...
   
   Die Klausel sollte als Spezialfall die Beispiele aus a) und 
   b) ergeben (nach Termvereinfachung).               Punkte 4
   
   (Es kann vorausgesetzt werden, dass NP1 und NP2 tatsaechlich
    die Syntaxbaeume von Nominalphrasen sind.)