Discrete Mathematics for Computer Scientists -- Assignment 2

Discrete Mathematics for Computer Scientists -- Assignment 2 - Logic and Proofs

DIT980, HT 2017

Fire | Forum | TimeEdit | Links

Assignment Week 2 - Logic and Proofs

Please submit using the Fire system

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)

"Simplify" means: find the simplest/smallest formula that means the same thing.

(2.) Write a logic formula for each of the following statements:

(a) "There exists a natural number that is larger than some odd natural number".

(b) "Every odd integer can be written in the form 2m+1, for some integer m".

You may use the following predicates:

Odd(x) = "x is an odd number"
x > y = "x is larger than y"

(For examples on how to write formulas, please look at Extra Exercises on Predicate Logic.)

(3.) For each of the following statements, say if it is true or not, and then prove or disprove the statement.

(a) "for all prime numbers p greater than 2, it is the case that (p+2) or (p+4) is also a prime number"

(b) "for all natural numbers n, if n is odd, then n²-1 is divisible by 4"

State clearly what you try to establish in your argument, and why your argument proves or disproves the statement.

(For examples on how to write down proofs, please look at ProofMethods (pdf) and/or Extra Exercises on Predicate Logic.)

(4.) Find examples of formulas with the following characteristics. Explain why your formula is a correct example.

(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 ℚ.

(b) Find an example of a formula with one ∀-quantifier and one ∃-quantifier that is true. But also, your formula should become false when we replace the ∀-quantifier with an ∃-quantifier and the ∃-quantifier with a ∀-quantifier. Concretely:

Your formula	∀x ^... ∃y ^...	is true
but	∃x ^... ∀y ^...	is false

(You fill in the ^...!) Don't forget to say what set you are quantifying over.

(Hint: in the lecture and in the book, we have seen examples of formulas that change meaning when we swap the order of the quantifiers. Some of these may work here, too.)

Submission

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

The submission deadline is Wednesday, September 13, 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 25 (midnight) to submit a completely correct version.

You can submit your answers in any of the following formats:

A simple text file, ending in .txt. You can make text files in any text editor, and then upload it to the Fire system.
(When using a text file, you may sometimes need to "invent" notation. Please be clear about what your notation means. A list of suggested notation for text files is provided by us. You may also use Unicode.)
A picture you have made in a painting program, ending in .gif, .jpg, or .png. You can use for example MS Paint, or Google Docs to make a picture, and upload it to the Fire system.
A PDF-file, ending in .pdf. You can make PDF files by for example using OpenOffice, LibreOffice, Microsoft Word, or Google Docs, and choosing export as PDF. Then, upload the PDF-file to the Fire system.
A scanned in document, ending in .pdf or .jpg. You can write your answer on a piece of paper, and use a scanner to scan it in and convert to a PDF-file. Or you can use your mobile phone to take pictures of the papers, and upload these to the Fire system.

If you submit multiple files, please name and/or number them such that the order in which we should read them is obvious. You can also write a text file, and have it refer to pictures that you upload separately.