Discrete Mathematics for Computer Scientists -- Assignment 2 - LogicDIT980, HT 2015
Home | Schedule | Assignments | Exercises | Exam | AboutFire | Forum | TimeEdit | Links | 2014
Assignment Week 2 - Logic

Extra Proof Examples (pdf)

Assignments

 (1.) Simplify the following logic formulas. Use a truth table to show that your simplification is correct. (a) (p /\ q) \/ q (b) p -> (p -> q) (c) ~(~p /\ ~q) "Simplify" means: find the simplest/smallest formula that means the same thing.

 (2.) Write a logic formula for each of the following statements: (a) "All natural numbers are either even or odd, and not both". (b) "There exists a natural number that is larger than all other natural numbers". (c) "There exists a natural number that is larger than some even number". You may use the following predicates: Even(x) = "x is an even number" Odd(x) = "x is an odd number" x > y = "x is larger than y" (d) For each of your formulas above, say whether it is true or false. Support your claim by proving or disproving ("bevisa" / "motbevisa") the formula. Note: In your proofs, you may make use of basic arithmetic common sense reasoning regarding even and odd numbers. But you need to be explicit in your handling of the quantifiers and logical connectives.

 (3.) (a) Find an example of a formula with at least one quantifier that is false when we quantify over the natural numbers ℕ, but true when we quantify over the rational numbers ℚ. Explain. (b) Find an example of a formula that contains at least one ∀-quantifier and one ∃-quantifier that is true. But also, your formula should become false when we replace the ∀-quantifiers with ∃-quantifiers and the ∃-quantifiers with ∀-quantifiers. (Don't forget to say what set you are quantifying over.) Explain. (c) Anna has found a set A with the following property: ∀x∈A : P(x)     is equivalent to     ∃x∈A : P(x) This property holds for any P she tries! What can you say about Anna's set A?

Submission

Submission of this assignment should be done electronically through the Fire system.

The submission deadline is Wednesday, September 16, at 13:00. At this time, you should have submitted a serious attempt to solve the assignment. A serious attempt is either an answer you believe to be correct, or a partial answer plus a detailed explanation of what you have tried to come up with a full answer. An empty document is not a serious attempt.

After submitting, you have until September 28 (midnight) to submit a completely correct version.