计算机代写｜Comp2022/2922 Assignment 5 (80 marks) s2 2022

这是一篇来自澳洲的关于解决一些万圣节相关问题的计算机代写

Consider the domain of Halloween creatures with the following predicates:

G(x) means that x is a ghost.
Z(x) means that x is a zombie.
S(x) means that x is scary.
A(x, y) means that x is afraid of y.

This will be used in the first three problems.

Problem 1. (5 marks) The Halloween creatures want to scare people who have not taken this course by expressing statements about themselves in predicate logic.

1. There is a scary ghost.

2. Somebody is afraid of everything.

3. For every scary zombie, some ghost is afraid of them.

4. If everybody is afraid of a ghost, that ghost is scary.

No additional explanation is needed.

Problem 2. (10 marks) The creatures are developing Logical Principles of Unnatural Philosophy, a book that contains laws about monsters that are true in all possible universes. However, they need help determining which laws are valid or not.

Show the following using the equivalence laws taught in this course.

1. ∃x(G(x) → S(x)) ≡ ∃x∃y(S(y) ∨ ¬G(x))

2. ∀xS(x) ↔ ∃xS(x) ≡ ∀x(S(x) → ∀yS(y))

Problem 3. (10 marks) The proof-readers of the book are skeptical about two of the claimed equivalences. Show the following by providing, for each one, a counterexample over a finite domain.

1. ∀x(∃yA(y, x) → S(x)) ̸≡ ∀x∃y(A(y, x) → S(x))

2. ∀x∃y∀z(A(x, y) ∧ A(y, z)) ̸≡ ∃x∀y(A(x, y) ∧ A(y, x))

Problem 4. (25 marks, 5/5/5/10) Prove the following consequents using the most horrifying thing of all, natural deduction.

1. ∀x(P(x) → ¬Q(x)), ∀x(R(x) → P(x)) ⊢ ∀x(Q(x) → ¬R(x))

2. ∀x(P(x) ∨ Q(y)) ⊢ ∀xP(x) ∨ Q(y)

3. ∃y∃z∀x(P(x, y) ∨ P(x, z)) ⊢ ∀x∃yP(x, y)

∀x∀y∀z((P(x, y) ∧ P(y, z)) → P(x, z)),

∃x∃y(P(x, y) ∧ ∀z(P(z, x) ∧ P(y, z))) ⊢ ∀x∀yP(x, y)

Problem 5. (30 marks, 10/10/10) Let Σ = {a, b}. For each of the following languages, provide a Context-free Grrrrrammar that generates it:

1. L(a ∗ b ∗ a ∗ ).
2. {a 2n+1 b n : n ≥ 0}.
3. {x : 2|x|b ≤ |x|a ≤ 3|x|b}. Here |x|a is the number of a’s in x, and |x|b is the number of b’s in x. For instance ϵ, baa, aaab, ababaaa, abaaabbaabaaa are in the language while a, b, aabaa, aaabb, ababababaaa are not in the language.