xuebaunion@vip.163.com

3551 Trousdale Rkwy, University Park, Los Angeles, CA

留学生论文指导和课程辅导

无忧GPA：https://www.essaygpa.com

工作时间：全年无休-早上8点到凌晨3点

微信客服：xiaoxionga100

微信客服：ITCS521

逻辑学代写-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

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