The Austalian National University (compiled: 22:59, Tuesday 9th August, 2022) S2 2022
School of Computing
Lecturer of the respective content: and
Assignment 1
Copyright By PowCoder代写 加微信 powcoder
Released: Due: Mode: Submit:
Wednesday 10 August, 2022
Wednesday, 24 August, 2022, 23:55 AEST
individual submissions only
Question 4 and (depending on your answer) Question 6(c) must be typed and submitted
to Turnitin; all other questions as one PDF via Wattle
(scans of legible handwritten solutions are perfectly acceptable)
Foundations of Computation
Pledge of Academic Integrity and Originality statement1
I am committed to being a person of integrity. I pledge, as a member of the Australian National University community, to abide by and uphold the standards of academic integrity outlined in the ANU statement on honesty and plagiarism. I understand that it is wrong to ever misrepresent another person’s work as my own.
I am aware of the relevant legislation, and understand the consequences of me breaching those rules. I have read the COMP1600/COMP6260 academic integrity and pledge to abide by it.
I declare that everything I have submitted in this assignment was entirely my own work.
Name: UID:
Signature:
1Submissions without your name, UID and signature will not be marked. 1
Question 1 Boolean Functions [4 + 5 Credits]
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