Hello, dear friend, you can consult us at any time if you have any questions, add WeChat: daixieit

MAT2362: Foundations of Mathematics

Homework Assignment #1.

Instructions.

● This assignment should be submitted before 5pm on Sept. 24 on BrightSpace.

● Make sure you write legibly and that your name and student ID are on each page you submit.

● You are encouraged to discuss the problems with your class mates, but the work you submit should be your own. Copying someone else’s solutions counts as academic fraud.

● All questions are long answer questions, and you need to provide clear and complete justification. You will get most of your marks by writing correct and clearly structured justification. Your job is to convince me that you understand the structure and contents of your arguments. Be advised that some questions require substantially more thought than others.

● If anything is unclear or you have questions, contact me.

(1) Construct the truth-table for the following propositional formulas. In each case, explain whether the formula is a tautology, a contradiction, or neither. (Explain how you arrive at this conclusion.)

(a) (p → (q ∨ r)) → (¬r → ¬p)

(b) (p ∨ ¬q) → (q → p)

(2) Consider the following formulas:

Of these formulas, two are logically equivalent. Which ones? (You may use any method you like, as long as you explain how you arrive at your answer.) Also show that the remaining formula is not logically equivalent to the other two.

(3) Consider the following dictionary:

Using this dictionary, translate the following sentences to propositional logic. Stay as close to the original English as possible.

(a) Fries are not healthy if there is mayo on them.

(b) It is not the case that if there is mayo or ketchup on the fries then they are delicious.

(c) Either fries are delicious or they are healthy, but not both.

(d) There being mayo on the fries is a sufficient but not a necessary condition for them being unhealthy.

(4) Consider the statement:

“If the Twin Prime conjecture is false then the liberals win the election.”

(a) State the contrapositive and the converse of this statement. (You don’t need to explain your answer.)

(b) Suppose I tell you that the negation of the statement is true. What can you conclude (if anything) about the election?

(5) Suppose we have a propositional formula M that has the following truthtable.

(a) Give an example of a formula M with this truth table.

(b) Find a formula N that is logically equivalent to M such that N only has the connectives ¬ and →.