COMP2022: Formal Languages and Logic Assignment 3

计算理论 Theory of Computation

COMP2022: Formal Languages and Logic Assignment 3

Due: 11:00am Thursday morning 1st November 2018
This assignment can be completed individually, or in a pair of two students.

Two students came up with the following wffs to reflect the meaning of the statement “if A then B else C”. The aim of this assignment is to prove formally that these two wffs are equivalent, using the Natural Deduction System:

1 Proofs

  1. 1.1  “Assignment Qn 1”:
  2. 1.2  “Assignment Qn 2”:

((A → B) ∧ (¬A → C)) ((A∧B)∨(¬A∧C))

((A → B) ∧ (¬A → C)) ⊢ ((A∧B)∨(¬A∧C))

((A∧B)∨(¬A∧C)) ⊢ ((A → B) ∧ (¬A → C))

These questions have both been pre-loaded in the Logic Tutor (with the names above). You must enter your proofs in the Logic Tutor, as answers to the corresponding questions.

You are free to use any strategy, but for both arguments conditional proofs are very handy.

2 Marking

There are five marks available:

  • Question 1: If the proof is correct, 2 marks.
  • Question 2: If the proof is correct, 2 marks.
  • Efficiency: The last mark is based on the length of your proofs. For each of the two questions, you will be assigned between 0 and 0.5 marks based on how long your shortest proof is compared to the other students! (up to 1 mark in total)

    Marking will be based on the shortest correct proof made by you (or by your partner, if in a pair) which satisfies these restrictions (i.e. it doesn’t need to be your most recent attempt, although it should be the one submitted to Canvas.)

1

3 Submission details

Due: 11:00am Thursday morning 1st November 2018 .

NO LATE SUBMISSION: No submissions will be accepted after 11:00am Thursday morning 1st Novem- ber, as we will look at some of the best proofs in the lecture. Where Special Consideration is warranted, alternative assessments or adjustments will be applied instead of an extension beyond this date, as appro- priate.

3.1

•

•

•

3.2

Canvas submission

On Canvas, you must submit a copy of your proofs (copy paste from the Logic Tutor, or take screenshots)

If you worked in a group, you must also include a signed assignment cover sheet in your submission, and you must join an assignment group on Canvas before submitting.

Details on this is included on the submission point in Canvas.

Proof submission on Logic Tutor

Submit your proofs to the corresponding questions on the Logic Tutor website:

   http://logic-comp2022.it.usyd.edu.au

Your login details were provided on tutorial sheet 10.
Reminder: you will need to use the VPN to access this if you are outside the university network.

   https://staff.ask.sydney.edu.au/app/answers/detail/a_id/334/

2

Related Posts