Discrete Mathematics for Computer Scientists -- Assignment 2

Discrete Mathematics for Computer Scientists -- Assignment 2 - Logic

DIT980, HT 2015

Fire | Forum | TimeEdit | Links | 2014

Assignment Week 2 - Logic

Please submit using the Fire system

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)

"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".

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.

∀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.

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.