ICT how mcuh

ICT how mcuh 

comp

2

022 Assignment 2 s2 2020

This assignment is due on Sunday

1

1 October, 2

3

:59. Submit a pdf (no handwriting) to
Gradescope. All work must be done individually without consulting someone else’s solutions in accor-
dance with the University’s “Academic Dishonesty and Plagiarism” policies. For more details on late
penalties, the level of justifications expected, repeated submissions, how to typeset, how to reference
other resources, what to do if you are stuck, etc., see the Ed Forum post “Assignment Guidelines”.
This assignment also uses an in-house tool called Logic Tutor for handling proofs in Natural Deduction.
You will be need to be on the VPN to access it, and you should include a copy of your proofs and the
url to your proof. Details on Logic Tutor, how to access it, etc., will be posted on Ed.

Problem 1.[40 Marks] Prove the following in Natural Deduction.

(a) (¬p → ¬q), ¬(p ∧ ¬r), ¬r ` ¬q (you can use De Morgan’s Law for this part).

(b) (p → ¬q), (¬r ∨ p) `((¬p → r) → ¬q)

(c) (r → ((p → ¬p) ∧ (q → ¬q))), (p ∨ q) ` ¬r

(d) ∃x(P (x) ∨ ¬Q(y)) `(Q(y) → ∃xP (x)).

In the remainder of the assignment we will see an application of predicate-logic to the design of
databases.

Problem 2.[20 marks] Entity-relationship diagrams (ERDs) are a graphical lan-
guage for expressing constraints on databases. ERDs consist of unary-predicate sym-
bols, the entity types, and k-ary predicate symbols for k > 1, the relationship types. In
this assignment, we use a simplified ERD notation, and we only have k = 2. A database
can be modeled by a structure D over the vocabulary of these symbols, and an ERD
can be modeled by a set Σ of sentences of predicate-logic.

Consider the following ERD:

It expresses that “Undergraduates are Students”. To model this in logic, express it
by the following sentence of predicate-logic:

∀x(U(x) → S(x))

Here the unary predicate-symbol U stands for the “Undergraduate” entity-type, and
the unary-predicate symbol S stands for the “Student” entity-type.

Consider the ERD on the last page of the assignment.

(a) The ERD expresses that

(i) “Undergraduates are Students”,

(ii) “Graduates are Students”,

(iii) “Students are either Undergraduates or Graduates”, and

(iv) “No Student is both an Undergraduate and a Graduate”.

Express each of these constraints in predicate-logic. Use the unary predicate-
symbol G to stand for “Graduate” entity-type.

1

https://sydney.edu.au/students/academic-dishonesty.html

https://edstem.org/courses/4385/discussion/284257

comp2022 Assignment 2 s2 2020

(b) The ERD expresses that “Lecturer Teaches Student”. Express this constraint
by a sentence of predicate-logic. Use the unary-predicate symbol L to stand for
the “Lecturer” entity-type, and the binary predicate-symbol T to stand for the
“Teaches” relationship.

Problem 3.[40 Marks] A database that satisifies the constraints of an ERD is called
legal. In logical terms, a database is legal if every sentence in Σ is true in D, where D
is the structure representing the database and Σ is the set of predicate-logic sentences
representing the ERD.

(a) An entity-type U is called inconsistent if it is empty in every legal database.
Inconsistency is an indication that there may be an error in the design of the
constraints. Express that U is inconsistent in logical terms.

(b) Two entity-types U, V are equivalent if they are equal in every legal database.
Express that U, V are equivalent in logical terms.

The following questions are with respect to the ERD on the last page of this assign-
ment.

(c) Show that “Undergraduate” entity-type is not inconsistent.

(d) Show that “Undergraduate” entity-type and the “Graduate” entity-type are not
equivalent.

(e) Show, using Natural Deduction, that the “Undergraduate” entity-type is inconsis-
tent if we add to the ERD the constraint “Students are Graduates”.

(f) Suppose we add to the ERD the constraints “Students are Undergraduates” and
“Undergraduates are Graduates”, and remove the constraint that “Undergradu-
ates” and “Graduates” are disjoint (i.e., we remove the constraint in Problem 2a
part (iv)). Show, using Natural Deduction, that the “Graduate” and “Undergrad-
uate” entity-types are now equivalent.

2

comp2022 Assignment 2 s2 2020
3