Assignment 2 - Logic and Proofs
Please submit using the Fire system
Question 1
Simplify the following logic formulas. Use a truth table to show that your simplification is correct.
(a.) \((p \wedge q) \vee q\)
(b.) \(p \rightarrow (p \rightarrow q)\)
(c.) \(\neg (\neg p \wedge \neg q)\)
"Simplify" means: find the simplest/smallest formula that means the same thing.
Question 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.)
Question 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 n2-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 and/or Extra Exercises on Predicate Logic.)
Question 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 \(\mathbb{N}\), but true when we quantify over the rational numbers \(\mathbb{Q}\).
(b.) Find an example of a formula with one \(\forall\)-quantifier and one \(\exists\)-quantifier that is true. But also, your formula should become false when we replace the \(\forall\)-quantifier with an \(\exists\)-quantifier and the \(\exists\)-quantifier with a \(\forall\)-quantifier. Concretely: \[ \begin{eqnarray} \text{Your formula} & \; \dots \forall x \dots \exists y \dots \; & \text{is true} \\ \text{but} & \; \dots \exists x \dots \forall y \dots \; & \text{is false} \end{eqnarray} \] (You fill in the \(\cdots\)!) 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 Wed, Sep 18, 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 Mon, Sep 30, at midnight to submit a completely correct version.
You can submit your answers (in Swedish or English) 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 a camera or 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.