逻辑与建模作业代写 Final Exam Logic and Modelling

Final Exam Logic and Modelling

逻辑与建模作业代写 Formulate the soundness and completeness theorem of predicate logic in terms of the (symbols for the) syntactical and semantical

General information:  逻辑与建模作业代写

• The exam consists of 7 pages and 7 tasks.
• The maximal number of points is 90.
• The grade for this exam is (points + 10) / 10.

1. This task concerns validity, and (un)satisfiability in propositional and predicate logic. Determine for each of the formulas whether it is valid, satisfiable or a contradiction:

(the answer suffices, no explanation is needed)
(a) (a → b) ∧ (b → ¬a) (2 points)
(b) (a → b) ∧ (a → ¬b) ∧ a (2 points)
(c) ((a → b) → a) → a (2 points)
Determine for each of the sets whether they are consistent: (the answer suffices, no explanation is needed)
(d) { ∃x ∀y R(x, y), ∃y ∀x ¬R(x, y) } (2 points)
(e) { ∀xP(x) ∨ Q(x), ∃x ¬P(x), ∀x ¬Q(x) } (2 points)

2. This task concerns natural deduction and counter models. Determine for each of the given semantic implications whether it is valid.

– For the valid implications, give a derivation using natural deduction.
– For the invalid implications, give a counter model (in case of propositional logic give a truth assignment of the variables that shows that the implication is wrong).
(a) a → b, a → ¬b |= ¬a (5 points)
(b) ∀x R(x, x) |= ∀y ∃x R(x, y) (5 points)
(c) ∀x ∃y ∃zR(x, y) ∧ R(y, z) ∧ R(z, x)|= ∃x ∃yR(x, y) ∧ R(y, x)(5 points)
(d) ∀x ∀yR(x, y) → ¬R(y, x)|= ¬∃x R(x, x) (5 points)

3. This task concerns the translation of sentences in natural language to predicate logic (with or without equality).  逻辑与建模作业代写

The domain is a group of people. The meaning of the symbols is:
a : Alma K(x, y) : x knows y
g : Gustav L(x, y) : x loves y
H(x, y) : x was husband of y

Translate the following sentences into formulas of predicate logic (with or without equality).

(a) Nobody knows everybody. (2 points)
(b) Everybody who knows Gustav also knows Alma. (2 points)
(c) Not all of Alma’s lovers’ lovers love her. (3 points)
(d) Alma had precisely two husbands. (3 points)

4. This task concerns meta-theorems of predicate logic, and expressibility of properties in predicate logic.

(a) Formulate the soundness and completeness theorem of predicate logic in terms of the (symbols for the) syntactical and semantical entailment relations. Make clear the difference between soundness and completeness. (3 points)
(b) Formulate the compactness theorem of predicate logic. (3 points)
(c) Exhibit, for n = 2, n = 3, and schematically for general n, formulas φn in predicate logic with equality such that, for all n ∈ N, n ≥ 2, the formula φn is true in a model M if and only the domain of M contains at least n values. (4 points)
(d) Prove that model finiteness is not expressible by a formula in predicate logic. Make clear what theorems you use. (5 points)

5. This task concerns basic modal logic and Kripke structures.  逻辑与建模作业代写

Given is the Kripke model M = (W, R, L) as drawn in the following figure:

Determine for each world x whether or not the following holds (the answer suffices, no explanation is needed):
(a) M, x ✷p → q (3 points)
(b) M, x ✷✸q (3 points)
We now consider the underlying frame F = (W, R). Determine whether (the answer suffices, no explanation is needed):
(c) F |= ✸p → ✷(p ∨ q) (2 points)
(d) F |= ✸✸p → ✸✸✸p (2 points)
The following task is about correspondence of formulas with frame properties:
(e) Give a formula that characterises the frame property: transitivity. (2 points)
(f) Give a formula that characterises the frame property: every world has at most two successors (that is, at most two outgoing R-arrows). (3 points)

6. This task concerns decision problems and their solvability (decidability).

(a) When is a decision problem undecidable (unsolvable)? (2 points)
(b) Give an instance of Post’s Correspondence Problem (PCP) that has a no solution. (2 points)
(c) Formulate and explain the undecidability theorem for formula validity in predicate logic. (2 points)
(d) Is the decision problem for entailment statements Γ ` φ, where Γ is a finite set of formulas of predicate logic and φ a formula of predicate logic, decidable (solvable)? Justify your answer. (4 points)

7. This task concerns program logic and the proof system for partial correctness.  逻辑与建模作业代写

(a) Write down the partial while rule. (2 points)
(b) Write down the implied rule. (2 points)
(c) Fill the gaps in the following proof.

更多代写： HomeWork cs作业     金融代考    postgreSQL代写         IT assignment代写     统计代写    圣玛丽山大学代写