COMP1600 Assignment 1
Foundations of Computation
Question 1 Boolean Functions [4 + 5 Credits]
Copyright By PowCoder代写 加微信 powcoder
a) Consider the boolean function f given by the following truth table:
p q r f(p,q,r) TTT F TTF T TFT F TFF F FTT T FTF T FFT F FFF T
Give a boolean formula for f. (I.e., you may use any of the connectives ¬, ∧, and ∨, but no others.)
b) We now define a new operator ≺ as follows:
xyx≺y FFF FTT TFF TTF
Demonstrate that the set {≺,T} is expressively complete. You may use the fact that {¬,∧,∨} is an expressively complete set.
Question 2 Boolean Equations [7 + 9 Credits]
a) Prove the boolean equation (¬a ∨ b) ∧ a = b ∧ a (MP) using the valid boolean equations given in the Appendix. Specifically, you may only use associativity, commutativity, absorption, identity, distributivity, and complements; you may not use De Morgan’s Laws.
b) Prove ((¬p∨q)∧p)∧(¬q∨(p∨r)) = p∧q using the derived equation MP. Again you may use the rules in the Appendix but not DeMorgan’s Laws.
Question 3 Propositional Natural Deduction [13 + 17 Credits] Prove the following in the natural deduction proof system, using the notation from the course.
(p ∨ q) ∧ (r ∧ ¬s → ¬q) p ∨ (r → s)
[5 + 5 Credits] Recall our new operator ≺ from Question 1. We now give natural deduction rules for this operator.
p≺q p≺qp Fq (≺ER ) (≺EL ) (≺I )
Explain why the ≺EL and ≺I rules are appropriate. Specifically, argue why the rules are consistent with the truth table for ≺ given in Question 1. We expect that approx. 70 words or less will be enough, but you can also write more should you need more. Remember! This question must be submitted separately to Turnitin as a typed (not handwritten) PDF.
a) (p∧q→r)∧¬(p→r)→¬(p→q) b)
Question 4 Natural Deduction Rules
Question 5 First Order Natural Deduction [12 Credits] Prove the following in the natural deduction proof system, using the notation from the course:
∀x.P (x) → Q(x) ∃x.P (x) ∨ Q(x) ∃x.Q(x)
Question 6 Binary Relations [3 + 3 + 17 Credits]
Recall that an interpretation in first order logic needs a domain of objects D. Consider our domain to be all the sets of natural numbers, i.e. U = P(N) (the power set of natural numbers). We define a relation S(x,y) which relates sets of the same size. So for any two sets x and y, S(x,y) is true iff |x| = |y|.
For example, S({0}, {1}) = T and S(∅, {0, 1}) = F .
a) A relation R is transitive iff it satisfies the following condition:
∀x∀y∀z.R(x, y) ∧ R(y, z) → R(x, z) Is S transitive? State your answer and either
• explain in one to two sentences why it holds, or
• give a counter example (three sets x,y,z where this doesn’t hold for S).
b) A relation R is symmetric iff it satisfies the following condition: ∀x∀y.R(x, y) → R(y, x)
Is S symmetric? State your answer and either
• explain in one to two sentences why it holds, or
• give a counter example (two sets x,y where this doesn’t hold for S).
c) Consider the inference below:
∀x∀y∀z.R(x, y) ∧ R(y, z) → R(x, z) ∀x∀y.R(x, y) → R(y, x) ∀x∃y.R(x, y) ∀x.R(x, x)
• prove this in the natural deduction proof system, or
• show that it is not valid with a counter-example and an explanation in no more than 100 words (excluding any formulae/symbols you might need). Your counter-example must consist of a situation (i.e., a domain/universe U and Θ, which defines the relation) that does not satisfy the inference.
In this case, your answer must be typed up (just like Question 4) and submitted to Turnitin.
Appendix: Valid Boolean Equations
Associativity
a ∨ (b ∨ c) = (a ∨ b) ∨ c a ∧ (b ∧ c) = (a ∧ b) ∧ c Commutativity
a∨b=b∨a a∧b=b∧a Absorption.
a ∨ (a ∧ b) = a a ∧ (a ∨ b) = a Identity.
a∨F=a a∧T=a Distributivity.
a ∨ (b ∧ c) = (a ∨ b) ∧ (a ∨ c)
Complements.
a ∨ ¬a = T
a ∧ (b ∨ c) = (a ∧ b) ∨ (a ∧ c) a ∧ ¬a = F
Appendix: Natural Deduction Rules Propositional Calculus
pq p∧qp∧q (∧E )
[p] [q] . .
q pp→q (→ E)
F p ¬p (¬E )
Predicate Calculus
P(a) (a arbitrary) ∀x. P(x)
q (a arbitrary) q (aisnotfreeinq)
P (a) P (a)
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com