逻辑学代写-COMP6262/PHIL20802-Assignment 1
时间:2022-04-08
Assignment 1, Logic course1
COMP2620/COMP6262/PHIL20802
Pascal Bercher3
Semester 1, 20224
compiled last: Tuesday 22nd March, 2022, 13:265
General Comments6
• The three questions in this assignment account for 15% of the final course mark.7
• You have to use the turnitin plugin to hand in your solutions – one file per question. Please add8
your information (name and ANU id) at the top of each PDF.9
• The plugin is configured in a way that you can’t submit within the first week. This gives us time10
to make improvements to the descriptions should that be required before submissions are made.11
• Please check the announcement forum regularly in case this PDF gets updated/improved. (Line12
numbers were added to make changes more transparent in our update history.)13
• There are further notes right below the plugin for the assignment. Read them carefully14
as they contain important information, e.g., regarding academic misconduct and due dates.15
• Do not copy our questions into your answers! Just provide their numbers and your answers.16
• All text must be written with a computer (word, LATEX etc.), you are not allowed to write by17
hand and insert a photograph. Such photographs are fine for truth tables, Semantic Tableaux, and18
Natural Deduction proofs, but not for text.19
• Do not reveal potential solutions when asking questions in the forum! Be careful!20
Exercise 1 (Natural Deduction) (7 points)21
In nutshell, you will have to provide a valid sequent X ` A in propositional Logic and prove its validity22
both via the formal definition as well as via Natural Deduction (ND). Your sequent will however have23
to adhere certain restrictions (these restrictions are both of a syntactical nature, but they also refer to24
which ND rules are used/required to prove it). So make sure you satisfy all requirements!25
List of Requirements for your Valid Sequent26
You must construct your sequent on your own!27
1. X = {A1, A2, A3}, |X| = 3, and P = {p, q, r}, where P is the set of propositional symbols used.28
That is, your sequent must be based on three distinct assumptions (formulae), and X ∪ {A} must29
depend on p, q, and r. The next point states on how many proposition symbols each formula must30
be based.31
2. Each assumption in X as well as A must contain at least two different proposition symbols. (I.e.,32
neither A1, A2, A3, nor A may consist of a single proposition symbol.)33
3. X may not be contradictory, i.e., A1 ∧A2 ∧A3 must be satisfiable.34
4. None of your assumptions may be redundant, i.e., in addition to demanding that A1, A2, A3 ` A35
is valid, we also demand:36
• A1, A2 ` A is invalid37
• A1, A3 ` A is invalid38
• A2, A3 ` A is invalid39
1
5. Your sequent must enable to perform a ND proof that allows for the following rule applications:40
• Disjunction elimination (at least once),41
• Any rule that performs a vacuous discharge.42
Note that your proof is not allowed to contain redundant lines. I.e., if a certain number of lines
can be removed from your proof without violating its correctness, you have to do so. Note that
this does not mean that your proof has to be optimal, you can still submit a proof with, say, 15
lines, even though one with 10 lines might exist! But that 10-liner may not be a subproof of the
longer one. For example, consider the following proof showing p ∧ q ` q ∧ p:
α1 (1) p ∧ q A
α1 (2) q 1 ∧E
α1 (3) p→ q 2 →I[]
α1 (4) p 1 ∧E
α1 (5) q 3,4 →E
α1 (6) q ∧ p 5,4 ∧E
This is an example with an unnecessary detour. The proof still works if lines (3), (4), and (5) get43
eliminated as lines (2) and (5) are identical. Adding such loops (e.g., to apply some rules like here44
→I with a vacuous discharge) is not allowed. If lines can be removed, they have to be removed.45
Your Exercises46
1. Proving validity and further constraints. (3 points)47
(a) Write down a sequent that satisfies all requirements that are demanded above.48
(b) Prove that your sequent is valid using the formal definition of validity, i.e., via truth tables.49
Explain in a few sentences why and how your truth table(s) do actually prove validity. You50
don’t have to write much just for the sake of it – a few sentences are fine. But we need to be51
convinced that you actually understand why your table(s) prove validity. If we are in doubt52
you lose marks. Just the table might score zero.53
(c) Explain in at most a few sentences why/how your table(s) show(s) that X is not contradictory54
and why none of the assumptions are redundant.55
Note that you can score fully for this part even if your sequent only satisfies all criteria 1 to 4, but56
not all from 5.57
2. Proving validity via Natural Deduction. (4 points)58
For the sequent you presented in the first part of this exercise (satisfying constraints 1. to 4.),59
present your proof that also satisfies all restrictions listed in constraint number 5. Use the notation60
from the course.61
Hints62
• We can’t forbid or prevent tool support (from/for our course), so use what’s there!63
• Double-check that you did not accidentally miss a constraint that we demand!64
• How to find an appropriate sequent? That’s the hard part! This requires both an understanding of65
the semantics of formulae and sequents, as well as how the ND proof steps/rule work (e.g., think66
about which formulae are required at which part of the sequent for a certain rule application).67
Exercise 2 (Semantic Tableau) (5 points)68
In nutshell, you will have to provide an invalid sequent X ` A in propositional Logic and prove its69
invalidity both via the formal definition as well as via Semantic Tableau (and then relate the two). Your70
sequent will however have to adhere certain restrictions. So make sure you satisfy all requirements!71
2
List of Requirements for your Invalid Sequent72
You must construct your sequent on your own!73
1. X = {A1, A2}, |X| = 2, and P = {p, q}, where P is the set of propositional symbols used. That74
is, your sequent must be based on two distinct assumptions (formulae), and X ∪{A} must depend75
on p and q. The next point states on how many proposition symbols each formula must be based.76
2. Neither assumption in X nor A may exist of just a single proposition symbol (negated or not).77
(I.e., A1, A2, and A must be a formula that contains at least one connective different from the78
negation symbol.)79
3. Though A1, A2 ` A must be invalid, A ` A1 ∧A2 must be valid.80
Your Exercises81
1. Proving invalidity and validity. (2 points)82
(a) Write down your invalid sequent A1, A2 ` A that satisfies all requirements that are demanded83
above.84
(b) Prove that your sequent is invalid using the formal definition of validity, i.e., via truth tables.85
Explain in a few sentences why and how your truth table(s) do actually prove invalidity. As86
for Exercise 1, briefly explain why your table(s) prove invalidity.87
(c) Also prove, again with truth tables and a short explanation, the validity of A ` A1 ∧A2.88
2. Proving invalidity via Semantic Tableau. (3 points)89
(a) Prove invalidity of your sequent A1, A2 ` A via Semantic Tableau. Use the notation from90
the lecture. Make sure to include all required annotations, e.g., indicate whether a branch is91
contradictory (and if so, why) or whether it’s open. Also indicate for each line where it comes92
from.93
(b) Extract an interpretation from your tableau that proves invalidity and explain (in at most a94
few sentences) how it relates to the first part of this exercise.95
Exercise 3 (Question about Natural Deduction) (3 points)96
Assume you are given a sequent X ` A in Propositional Logic and you are able to derive, using Natural97
Deduction, both some formula B from X as well as its negation ¬B. Assume that the rule RAA is not98
available to you, otherwise all Natural Deduction rules we taught can be used.99
• Can you infer any property (satisfiable, unsatisfiable, tautology) of the formula A1 ∧ · · · ∧ An,100
provided X = {A1, . . . , An}?101
• Can you say anything about the validity of the sequent? Does its validity depend on which formula102
A represents?103
• In which way does the fact that we don’t have RAA available influence your response?104
Answer these questions as precisely as possible. If it supports your arguments, refer to the respective105
Natural Deduction rules as required. Provide your explanation in at most 200 words.106
Academic Misconduct / Collaboration (and More)107
Again, note that any form of collaboration is strictly forbidden for this assignment and any other!108
Assignments (and the exam) contribute towards the final course mark, so every collaboration is strictly109
forbidden. Please read our rules on Academic Integrity, Academic Misconduct, and Deadlines110
and Late Submissions on our Wattle page.111
3

essay、essay代写