关于算法:MATH1090-Problem

49次阅读

共计 1370 个字符,预计需要花费 4 分钟才能阅读完成。

MATH1090 Problem Set No2 October 2021
Lassonde School of Engineering
Dept. of EECS
Professor G. Tourlakis
MATH1090 B. Problem Set No2
Posted: Oct. 6, 2021
Due: Oct. 29, 2021; by 2:00pm, in eClass.
Q: How do I submit?
A:
(1) Submission must be a SINGLE standalone
file to eClass. Submission by email is not
accepted.
(2) Accepted File Types: PNG, JPEG, PDF,
RTF, MS WORD, OPEN OFFICE, ZIP
(3) Deadline is strict, electronically limited.
(4) MAXIMUM file size = 10MB
Post’s Theorem use is not allowed in any question
below.

  1. (3 MARKS)
    We proved in class that
    ` A ≡ A
    Page 1 G. Tourlakis
    MATH1090 Problem Set No2 October 2021
    using the“trick”of a Leibniz“mouth”-variable p that does not appear
    in A.
    Prove this again, Equationally, but without using this trick and without
    using Post’s Theorem.
  2. (5 MARKS) Prove Equationally that A, B ` A ≡ B.
  3. (5 MARKS) Is Statement (1) below True or False and WHY?
    Γ A≡B is equivalent to“Γ A IFF Γ ` B”(1)
    Note that the sub-statement in quotes is a METAstatement. Note also
    that we have two“iff”in (1) above!
     Caution. If a proof style is explicitly required in what follows, then any
    other style used gets 0 marks even if it is correct. 
  4. (5 MARKS) Prove Equationally that for any A and B
    A, ¬A ` B ≡ ¬B
  5. (4 MARKS) Prove Equationally that ` A → B → A.
  6. (4 MARKS) Prove Equationally that A → B ` ¬B → ¬A.
  7. (5 MARKS) Prove (choose your favourite: Equational or Hilbert proof)
    that A → B ` (B → C) → A → C.
  8. Prove that A → B, C → B ` (A ∨ C) → B.
    two proofs are required:
    • (3 MARKS) One with the Deduction theorem (and a Hilbert-style
    proof; CUT rule allowed in this subquestion).
    • (4 MARKS) One Equational, WITHOUT using the Deduction theorem.
    Page 2 G. Tourlakis
正文完
 0