comp2022 Assignment 2 s2 2020
This assignment is due on Sunday 11 October, 23: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
comp2022 Assignment 2 s2 2020
(b) The ERD also expresses that lecturers teach students, i.e., if x teaches y then x is a lecturer and y is a 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