MATH 1090 Lecture Notes - Boolean Algebra, Dno, Metatheorem
3 Jul 2018
School
Department
Course
Professor
York University
Faculty of Science and Engineering
MATH 1090, Section M
Final Examination, April 2013
NAME (print, in ink):
(Family name) (Given name)
Instructions, remarks:
1. In general, carefully read all instructions in a problem before beginning
it. Make sure you have problems 1 through 14.
2. You have 180 minutes. If you run out of space, continue on the backs
of pages. Do not waste your time giving more detail than is
asked for.
3. Note: Everywhere in this exam, unless otherwise indicated,
the word “prove” in a problem means “give a syntactic proof
of”. You are NOT allowed to use Completeness (i.e., “tau-
tological implication”, i.e., Post’s theorem) in ANY step of
ANY proof on this exam. Proofs can be either Hilbert-style or
equational or a mix, unless one type or the other is required in the in-
structions. (And, as we know, “bullet” proofs are always equational.)
4. Unless otherwise stated in a problem, it is understood that in solving
a problem, you may use any result from an earlier problem
on this exam or from an earlier part of the same problem,
EVEN IF you did not prove the earlier result.
5. The marks assigned to a problem do NOT necessarily
correspond to its difficulty. There are 127 marks available
on this exam, but it will be marked “out of 100”.
Problem Marks
1 10
2 4
3 18
4 8
5 15
6 8
7 5
8 7
9 12
10 6
11 12
12 8
13 6
14 6
Name 2
Total 127
find more resources at oneclass.com
find more resources at oneclass.com
MATH 1090 Final Exam
Page 1
April 2013
1. Give a bullet proof that ⊢p∧(q≡p)≡p∧q.
(I guess I know of only one way to “start” the proof – or at least only one
“best” way according to our general strategy for approaching bullet proofs –
the troublesome connective here is ∧– find a way to get rid of it.
“Bullet” always means no ping-pong, no D.T.)
2. Give a bullet proof that, for any wffs Aand B,
⊢(¬A≡B)≡(A≡ ¬B).
find more resources at oneclass.com
find more resources at oneclass.com
MATH 1090 Final Exam
Page 2
April 2013
3. One of the following wffs A,Bis a theorem; the other is not.
Ais ( (p→q)∧ ¬q)−→ ¬p.
Bis ( (p→q)∧ ¬p)−→ ¬q.
(a) Give a bullet proof of the theorem. (The Deduction Theorem is NOT allowed
in this problem. You may use any theorems on your lists; you may also use
Shunting: ⊢(C∧D)→E≡C→(D→E). You may not use other theorems
than the ones mentioned above unless you prove them first.)
(b) Explain carefully, using and naming facts from the course, how we know
that the other wff is not a theorem.
find more resources at oneclass.com
find more resources at oneclass.com
Document Summary
Name (print, in ink): (family name) (given name) Instructions, remarks: in general, carefully read all instructions in a problem before beginning it. Make sure you have problems 1 through 14. If you run out of space, continue on the backs of pages. Do not waste your time giving more detail than is asked for: note: everywhere in this exam, unless otherwise indicated, the word prove in a problem means give a syntactic proof of . You are not allowed to use completeness (i. e. , tau- tological implication , i. e. , post"s theorem) in any step of. Even if you did not prove the earlier result: the marks assigned to a problem do not necessarily correspond to its di culty. There are 127 marks available on this exam, but it will be marked out of 100 . April 2013: give a bullet proof that.
