View source for Constraint-based Grammar: Semantics, Logic

<!-- This is a comment -->
<!--  &forall;''x'' ('''cat'''(''x'') : &exist;''y''('''likes(''y'', ''x'')) -->
<!--  &sup;  &and; &not;  &or; &equiv; &forall;   &exist; &aelig; &oplus; &Oslash; &rArr; <u>Unterstrichen</u> &rarr; &rArr; -->
<!--  
Text davor
<blockquote>Blockquote</blockquote>
Text danach
-->
<!--

Definitionsliste:

;Begriff 1
: Beschreibung 1
;Begriff 2
: Beschreibung 2-1
: Beschreibung 2-2

Text einrücken:

: Einfache Einrückung
:: Doppelte Einrückung
::::: Mehrfache Einrückung

Nummered list:

# Erstes Element der ersten Ebene
## Erstes Element der zweiten Ebene
## Zweites Element der zweiten Ebene
# Zweites Element

Bulleted lists:

* Erstes Element der ersten Ebene
** Erstes Element der zweiten Ebene
** Zweites Element der zweiten Ebene
* Zweites Element


-->
=== Quantification ===
----

For the following exercises, assume the existence of a model with the universe of discourse below:

''U'' = { ''cat1,cat2,cat3,dog1,dog2,dog3'' }


Now do the following exercises about the interpretation function I of the model.


'''Exercise 1'''  For I('''cat<sup>1</sup>''') and I('''lilly'''), specify one plausible value each so that the formula '''cat<sup>1</sup>(lilly)''' becomes true in M.

<div class="toccolours mw-collapsible mw-collapsed" style="width:800px">
Check your answer
<div class="mw-collapsible-content">
I('''cat<sup>1</sup>''') = {<''cat1''>,<''cat2''>,<''cat3''>}

For I('''lilly'''), each of the following 3 values will now make '''cat<sup>1</sup>(lilly)''' true in M:<br>
a. I('''lilly''') = ''cat1'' , or<br>
b. I('''lilly''') = ''cat2'' , or<br>
c. I('''lilly''') = ''cat3'' .

We prove this for case (b):

1. [[<nowiki />'''cat'''<sup>1</sup>('''lilly''')]]<sup>M</sup> = 1 iff <[[<nowiki />'''lilly''']]<sup>M</sup>> &isin; I('''cat<sup>1</sup>''')<br>
2. iff <I('''lilly''')> &isin; I('''cat<sup>1</sup>''')<br>
3. iff <''cat2''> &isin; {<''cat1''>,<''cat2''>,<''cat3''>}<br>

Hence: since (3) is the case, so are (2) and the righthand side of (1). Finally, since the righthand side of (1) is the case, the lefthand side is the case as well. Hence [[<nowiki />'''cat'''<sup>1</sup>('''lilly''')]]<sup>M</sup> is true in model M. That is what we intended to prove!
</div>
</div>


'''Exercise 2''' Assume that I('''cat'''<sup>1</sup>) = {<''cat1''>,<''cat2''>,<''cat3''>}. What values of I('''lilly''') would make the formula '''&not;cat<sup>1</sup>(lilly)''' true in M?

<div class="toccolours mw-collapsible mw-collapsed" style="width:800px">
Check your answer
<div class="mw-collapsible-content">

For I('''lilly'''), each of the following 3 values will make &not;'''cat<sup>1</sup>(lilly)''' true in M.:<br>
a. I('''lilly''') = ''dog1'' , or<br>
b. I('''lilly''') = ''dog2'' , or<br>
c. I('''lilly''') = ''dog3''.

We prove this for case (a):

1. [[<nowiki />'''&not;cat<sup>1</sup>(lilly)''']]<sup>M</sup> = 1 iff [[<nowiki />'''cat<sup>1</sup>(lilly)''']]<sup>M</sup> = 0<br>
2. iff <[[<nowiki />'''lilly''']]<sup>M</sup>> &notin; I('''cat'''<sup>1</sup>)<br>
3. iff <I('''lilly''')> &notin; I('''cat'''<sup>1</sup>)<br>
4. iff <''dog1''> &notin; {<''cat1''>,<''cat2''>,<''cat3''>}.<br>

Hence: since (4) is the case, so are (3), (2), and the righthand side of (1). Finally, since the righthand side of (1) is the case, the lefthand side is the case as well. Hence  [[<nowiki />'''&not;cat<sup>1</sup>(lilly)''']]<sup>M</sup> is true in model M. That is what we intended to prove!
</div>
</div>


'''Exercise 3''' Look at the following English sentences:

i. Every cat is an animal.<br>
ii. Every dog is an animal.<br>
iii. Every animal is either a dog or a cat.<br>
iv. No cat is a dog.

Suppose that for each of these sentences we have a formula of first order logic with the same meaning as the sentence. Assume furthermore that '''cat'''<sup>1</sup>, '''dog'''<sup>1</sup>, and '''animal'''<sup>1</sup> are predicates in the logical language.

Without specifying precise logical formalae at this point, give plausible values of I('''cat'''<sup>1</sup>),  I('''dog'''<sup>1</sup>), and I('''animal'''<sup>1</sup>) that will make the logical formulae corresponding to the 4 English sentences above true in M.

<div class="toccolours mw-collapsible mw-collapsed" style="width:800px">
Check your answer
<div class="mw-collapsible-content">

I('''cat'''<sup>1</sup>) = {<''cat1''>,<''cat2''>,<''cat3''>}<br>
I('''dog'''<sup>1</sup>) = {<''dog1''>,<''dog2''>,<''dog3''>}<br>
I('''animal'''<sup>1</sup>) = {<''cat1''>,<''cat2''>,<''cat3''>,<''dog1''>,<''dog2''>,<''dog3''>} 

Note that I('''animal'''<sup>1</sup>) = I('''cat'''<sup>1</sup>) &cup; I('''dog'''<sup>1</sup>).
</div>
</div>


'''Exercise 4''' Assume a model M = <''U'',I> as described below:

''U'' = {''cat1,cat2,cat3,dog1,dog2,dog3''}<br>

I('''lilly''') = ''cat1''<br>
I('''fido''') = ''dog2''<br>
I('''cat'''<sup>1</sup>) = {<''cat1''>,<''cat2''>,<''cat3''>}<br>
I('''dog'''<sup>1</sup>) = {<''dog1''>,<''dog2''>,<''dog3''>}<br>
I('''animal'''<sup>1</sup>) =  {<''cat1''>,<''cat2''>,<''cat3''>,<''dog1''>,<''dog2''>,<''dog3''>}

a. What has to be true of I('''likes'''<sup>2</sup>) if the formula '''likes<sup>2</sup>(lilly,fido)''' is true in M and the formula '''likes<sup>2</sup>(fido,lilly)''' is false in M?

<div class="toccolours mw-collapsible mw-collapsed" style="width:800px">
Check your answer
<div class="mw-collapsible-content">

The pair <''cat1,dog2''> is a member of I('''likes'''<sup>2</sup>), whereas the pair <''dog2,cat1''> is not a member of I('''likes'''<sup>2</sup>).
</div>
</div>


b. What has to be true of I('''likes'''<sup>2</sup>) if the formula corresponding to the English sentence ''Lilly likes a dog.'' is true in M?

<div class="toccolours mw-collapsible mw-collapsed" style="width:800px">
Check your answer
<div class="mw-collapsible-content">

At least one of the pairs <''cat1,dog1''>, <''cat1,dog2''>, <''cat1,dog3''> is a member of I('''likes'''<sup>2</sup>).
</div>
</div>


c. What has to be true of I('''likes'''<sup>2</sup>) if the formula corresponding to the English sentence ''Lilly likes every dog.'' is true in M?

<div class="toccolours mw-collapsible mw-collapsed" style="width:800px">
Check your answer
<div class="mw-collapsible-content">

All the pairs <''cat1,dog1''>, <''cat1,dog2''>, <''cat1,dog3''> are members of I('''likes'''<sup>2</sup>).
</div>
</div>


d. What has to be true of I('''likes'''<sup>2</sup>) if the formula corresponding to the English sentence ''Every cat likes every dog.'' is true in M?

<div class="toccolours mw-collapsible mw-collapsed" style="width:800px">
Check your answer
<div class="mw-collapsible-content">

All the pairs <''cat1,dog1''>, <''cat1,dog2''>, <''cat1,dog3''>, <''cat2,dog1''>, <''cat2,dog2''>, <''cat2,dog3''>, <''cat3,dog1''>, <''cat3,dog2''>, <''cat3,dog3''> are members of I('''likes'''<sup>2</sup>).
</div>
</div>


e. What has to be true of I('''likes'''<sup>2</sup>) if the formula corresponding to the English sentence ''There is some cat which likes every dog.'' is true in M?

<div class="toccolours mw-collapsible mw-collapsed" style="width:800px">
Check your answer
<div class="mw-collapsible-content">

Either the three pairs <''cat1,dog1''>, <''cat1,dog2''>, <''cat1,dog3''> are members of I('''likes'''<sup>2</sup>) or the three pairs <''cat2,dog1''>, <''cat2,dog2''>, <''cat2,dog3''> are members of I('''likes'''<sup>2</sup>), or the three pairs <''cat3,dog1''>, <''cat3,dog2''>, <''cat3,dog3''> are members of I('''likes'''<sup>2</sup>).
</div>
</div>


f. What has to be true of I('''likes'''<sup>2</sup>) if the formula corresponding to the English sentence ''Some cat likes some dog.'' is true in M?

<div class="toccolours mw-collapsible mw-collapsed" style="width:800px">
Check your answer
<div class="mw-collapsible-content">

One of the pairs <''cat1,dog1''>, <''cat1,dog2''>, <''cat1,dog3''>, <''cat2,dog1''>, <''cat2,dog2''>, <''cat2,dog3''>, <''cat3,dog1''>, <''cat3,dog2''>, <''cat3,dog3''> is a member of I('''likes'''<sup>2</sup>).
</div>
</div>


g. What has to be true of I('''likes'''<sup>2</sup>) if the formula corresponding to the English sentence ''A cat likes a dog and a dog likes a cat'' is true in M?

<div class="toccolours mw-collapsible mw-collapsed" style="width:800px">
Check your answer
<div class="mw-collapsible-content">

Note that the sentence does not require that the cats and the dogs in the two relationships are the same. Hence:

There are a and b &isin; {''cat1, cat2, cat3''} and there are c and d &isin; {''dog1, dog2, dog3''} such that<br>
<a,c> and <d,b> are both members  of I('''likes'''<sup>2</sup>).
</div>
</div>


h. What has to be true of I('''likes'''<sup>2</sup>) if the formula corresponding to the English sentence ''There is a cat and there is a dog for whom''<br>
''it is true that the cat likes the dog and the dog likes the cat'' is true in M?

<div class="toccolours mw-collapsible mw-collapsed" style="width:800px">
Check your answer
<div class="mw-collapsible-content">

This time the cat and the dog have to be the same. Hence: 

There is an a &isin; {''cat1, cat2, cat3''} and there is a c &isin; {''dog1, dog2, dog3''} such that<br>
<a,c> and <c,a> are both members  of I('''likes'''<sup>2</sup>).
</div>
</div>

i. What has to be true of I('''likes'''<sup>2</sup>) if the formula corresponding to the English sentence ''Every cat likes herself'' is true in M?

<div class="toccolours mw-collapsible mw-collapsed" style="width:800px">
Check your answer
<div class="mw-collapsible-content">

 All the pairs <''cat1,cat1''>,  <''cat2,cat2''>, and <''cat3,cat3''> are members of I('''likes'''<sup>2</sup>).
</div>
</div>


'''Exercise 5''' Translate the following English sentences into first order predicate logic. Give what you think is the most likely reading of the English sentence.

 a. Lucy is a student.	

<div class="toccolours mw-collapsible mw-collapsed" style="width:800px">
Check your answer
<div class="mw-collapsible-content">

 '''student(lucy)'''
</div>
</div>

b. Lucy knows a student.	

<div class="toccolours mw-collapsible mw-collapsed" style="width:800px">
Check your answer
<div class="mw-collapsible-content">

&exist;''x''('''student'''(''x'') : '''know'''('''lucy''',''x''))
</div>
</div>

c. Every student likes linguistics.

<div class="toccolours mw-collapsible mw-collapsed" style="width:800px">
Check your answer
<div class="mw-collapsible-content">

&forall;''x'' ('''student'''(''x'') : '''like'''(''x'','''linguistics'''))
</div>
</div>

d. Not every student likes linguistics.

<div class="toccolours mw-collapsible mw-collapsed" style="width:800px">
Check your answer
<div class="mw-collapsible-content">

&not;&forall;''x''('''student'''(''x'') : '''like'''(''x'','''linguistics'''))
</div>
</div>

e. If every student likes linguistics, then Lucy likes linguistics.

<div class="toccolours mw-collapsible mw-collapsed" style="width:800px">
Check your answer
<div class="mw-collapsible-content">

&forall;''x''('''student'''(''x'') : '''like'''(''x'','''linguistics''')) &sup; '''like'''('''lucy''','''linguistics''')
</div>
</div>

f. Some student does't like linguistics.

<div class="toccolours mw-collapsible mw-collapsed" style="width:800px">
Check your answer
<div class="mw-collapsible-content">

&exist;''x''('''student'''(''x'') : &not;'''like'''(''x'','''linguistics'''))
</div>
</div>

g. Not one student likes linguistics.

<div class="toccolours mw-collapsible mw-collapsed" style="width:800px">
Check your answer
<div class="mw-collapsible-content">

&not;&exist;''x''('''student'''(''x'') : '''like'''(''x'','''linguistics'''))
</div>
</div>

h. Every smart student takes linguistics.

<div class="toccolours mw-collapsible mw-collapsed" style="width:800px">
Check your answer
<div class="mw-collapsible-content">

&forall;''x''(('''student'''(''x'') &and; '''smart'''(''x'')) : '''take'''(''x'','''linguistics'''))
</div>
</div>

i. No smart student gives a bad presentation.

<div class="toccolours mw-collapsible mw-collapsed" style="width:800px">
Check your answer
<div class="mw-collapsible-content">

&not;&exist;''x''(('''student'''(''x'') &and; '''smart'''(''x'')) : &exist;''y''(('''presentation'''(''y'') &and; '''bad'''(''y'')) : '''give'''(''x'',''y'')))
</div>
</div>

j. Every student likes an interesting presentation.

<div class="toccolours mw-collapsible mw-collapsed" style="width:800px">
Check your answer
<div class="mw-collapsible-content">

&forall;''x''('''student'''(''x'') : &exist;''y''(('''presentation'''(''y'') &and; '''interesting'''(''y'')) : '''like'''(''x'',''y'')))
</div>
</div>

k. One presentation intrigued every student but that presentation did not intrigue any professor.

<div class="toccolours mw-collapsible mw-collapsed" style="width:800px">
Check your answer
<div class="mw-collapsible-content">

&exist;''x''('''presentation'''(''x'') : (&forall;''y''('''student'''(''y'') : '''intrigue'''(''x'',''y'') &and; &not;&exist;''z''('''professor'''(''z'') : '''intrigue'''(''x'',''z'')))))
</div>
</div>

l. For every student there is a professor that this student does not like.

<div class="toccolours mw-collapsible mw-collapsed" style="width:800px">
Check your answer
<div class="mw-collapsible-content">

&forall;''x''('''student'''(''x'') : &exist;''y''('''professor'''(''y'') : &not;'''like'''(''x'',''y'')))
</div>
</div>

m. Some student does not like any professor.

<div class="toccolours mw-collapsible mw-collapsed" style="width:800px">
Check your answer
<div class="mw-collapsible-content">

&exist;''x''('''student'''(''x'') : &not;&exist;''y''('''professor'''(''y'') : '''like'''(''x'',''y'')))
</div>
</div>

n. Not every student likes a professor.

<div class="toccolours mw-collapsible mw-collapsed" style="width:800px">
Check your answer
<div class="mw-collapsible-content">

&not;&forall;''x''('''student'''(''x'') : &exist;''y''('''professor'''(''y'') : '''like'''(''x'',''y'')))
</div>
</div>

o. A professor likes every student who likes linguistics.

<div class="toccolours mw-collapsible mw-collapsed" style="width:800px">
Check your answer
<div class="mw-collapsible-content">

&exist;''x''('''professor'''(''x'') : &forall;''y''(('''student'''(''y'') &and; '''like'''(''y'','''linguistics''')) : '''like'''(''x'',''y'')))
</div>
</div>

p. A professor likes every student who gives a good presentation.

<div class="toccolours mw-collapsible mw-collapsed" style="width:800px">
Check your answer
<div class="mw-collapsible-content">

&exist;''x''('''professor(''x'') : &forall;''y''(('''student'''(''y'') &and; &exist;''z''(('''presentation'''(''z'') &and; good(''z'')) : give(''y'',''z'')) : '''like'''(''x'',''y''))
</div>
</div>

q. Some professor who smokes likes no student who smokes.

<div class="toccolours mw-collapsible mw-collapsed" style="width:800px">
Check your answer
<div class="mw-collapsible-content">

&exist;''x''(('''professor'''(''x'') &and; '''smoke'''(''x'')) : &not;&exist;''y''(('''student'''(''y'') &and; '''smoke'''(''y'')) : '''like'''(''x'',''y'')))
</div>
</div>

r. A professor who smokes likes every student who does not smoke.

<div class="toccolours mw-collapsible mw-collapsed" style="width:800px">
Check your answer
<div class="mw-collapsible-content">

&exist;''x''(('''professor'''(''x'') &and; '''smoke'''(''x'')) : &forall;''y''(('''student'''(''y'') &and; &not;'''smoke'''(''y'')) : '''like'''(''x'',''y'')))
</div>
</div>

s. Every student likes herself.

<div class="toccolours mw-collapsible mw-collapsed" style="width:800px">
Check your answer
<div class="mw-collapsible-content">

&forall;''x''('''student'''(''x'') : '''like'''(''x'',''x''))
</div>
</div>

t. One student does not like herself.

<div class="toccolours mw-collapsible mw-collapsed" style="width:800px">
Check your answer
<div class="mw-collapsible-content">

&exist;''x''('''student'''(''x'') : &not;'''like'''(''x'',''x''))
</div>
</div>

u. No student likes herself.

<div class="toccolours mw-collapsible mw-collapsed" style="width:800px">
Check your answer
<div class="mw-collapsible-content">

&not;&exist;''x''('''student'''(''x'') : '''like'''(''x'',''x''))
</div>
</div>

v. Not every student likes herself.

<div class="toccolours mw-collapsible mw-collapsed" style="width:800px">
Check your answer
<div class="mw-collapsible-content">

&not;&forall;''x''('''student'''(''x'') : '''like'''(''x'',''x''))
</div>
</div>

w. Lucy likes herself.

<div class="toccolours mw-collapsible mw-collapsed" style="width:800px">
Check your answer
<div class="mw-collapsible-content">

'''like'''('''lucy,lucy''')
</div>
</div>

x. One student knows a professor who does not know him.

<div class="toccolours mw-collapsible mw-collapsed" style="width:800px">
Check your answer
<div class="mw-collapsible-content">

&exist;''x''('''student'''(''x'') : &exist;''y''(('''professor'''(''y'') &and; &not;'''know'''(''y'',''x'')) : '''know'''(''x'',''y'')))
</div>
</div>