This

**preview**shows page 1. to view the full**5 pages of the document.**CS 245 Winter 2009

Assignment 5

Due: Thu 12 Mar 2009 10am in the CS245 Drop Boxes

35 marks

SOLUTION SET

There may be multiple correct answers to some of these questions.

1. (9 marks) Formalize the following sentences in set theory. Do not use types, quantiﬁers,

or set comprehension. Use only the following sets and relations in your formulas:

•Dwellings – the set of dwelling

•People – the set of people

•Houses – the set of houses

•Students – the set of students

•owns :People ↔Dwellings

The relationship between people and the dwellings that they own.

•rents :People ↔Dwellings

The relationship between people and the dwellings that they rent.

where Students ⊆People,Houses ⊆Dwellings.

1

###### You're Reading a Preview

Unlock to view full version

Only page 1 are available for preview. Some parts have been intentionally blurred.

Sentences to formalize:

(a) All houses that are rented are owned.

(3 marks)

(ran rents)∩Houses ⊆ran owns

(b) Not every student owns a house.

(3 marks)

¬(Students ⊆dom (owns ⊲Houses))

or

dom (Students ⊳(owns ⊲Houses)) ⊂Students

(c) Students who rent houses do not own any dwelling.

(3 marks)

(dom (Students ⊳(rents ⊲Houses))) ⊳owns =∅

or

(dom (Students ⊳(rents ⊲Houses))) ∩(dom owns) = ∅

or

owns(|(dom (Students ⊳(rents ⊲Houses))) |) = ∅

###### You're Reading a Preview

Unlock to view full version