CS2214 Assignment #1

CS2214
Assignment #1

Submission: on the OWL web site of the course
Format of the submission. You must submit a single file which must
be in PDF format. All other formats (text or Miscrosoft word format) will
be ignored and considered as null. You are strongly encouraged to type
your solutions using a text editor. To this end, we suggest the following
options:
1. Miscrosoft word and convert your document to PDF
2. the typesetting system LATEX; see https://www.latex-project.org/
and https://en.wikipedia.org/wiki/LaTeX#Example to learn about
LATEX; see https://www.tug.org/begin.html to get started
3. using a software tool for typing mathematical symbols, for instance
http://math.typeit.org/
4. using a Handwriting recognition system such as those equipping tablet
PCs
Hand-writing and scanning your answers is allowed but not encouraged:
1. if you go this route please use a scanning printer and do not take a
picture of your answers with your phone,
2. if the quality of the obtained PDF is too poor, your submission will
be ignored and considered as null.
Problem 1 (Undertsamding implication) [20 marks] Let p, q be two
Boolean variables. By definition, the implication p −→ q is true if and only
if p is false or q is true. Based on that, we have established the following
practical tautologies:
1. (p −→ q) ⇐⇒ (¬q −→ ¬p)
2. (p ↔ q) ⇐⇒ ((p −→ q) ∧ (q −→ p))
Would these two tautologies still be true if we were changing the truth value
of the implication p −→ q to that of
1. p ∧ q?
2. p ∨ q?
Justify your answer. Another way of phrasing the question would be the
following. Wuld the above tautologies still be tautologies if we were
1. repacing −→ with ∧?
2. repacing −→ with ∨?
1
Problem 2 (Proving theorems!) [20 marks] For each of the following
statements, translate it into predicate logic and prove it, if the statement is
true, or disprove it, otherwise:
1. for any two even integers, there exists a third integer (even or odd)
the double of which is equal to the sum of the first two integers.
2. for any two odd integers, there exists a third integer (even or odd) the
triple of which is equal to the sum of the first two integers.
Problem 3 (Finding a treasure!) [20 marks] In the back of an old cupboard you discover a note signed by a pirate famous for his bizarre sense of
humour and love of logical puzzles. In the note he wrote that he had hidden treasure somewhere on the property. He listed five true statements and
challenged the reader to use them to figure out the location of the treasure.
1. If there is an old shipwreck near the beach, then the treasure is buried
under a coconut palm tree.
2. There is a coconut palm tree growing either at the far end of the island
or near the cave.
3. Either there is a shipwreck near the beach, or the treasure is hidden
in a cave.
4. If there is a coconut palm tree at the far end of the island, then there
is no shipwreck on the beach
5. There is no coconut palm tree near the cave.
Problem 4 (Deciding consistency) [20 marks] A set of propositions is
consistent if there is an assignment of truth values to each of the propositional variables, that makes all propositions true. Is the following set of
propositions consistent?
1. The system is in multiuser state if and only if it is operating normally.
2. If the system is operating normally, the kernel is functioning.
3. The kernel is not functioning or the system is in interrupt mode.
4. If the system is not in multiuser state, then it is in interrupt mode.
5. The system is in interrupt mode.
Problem 5 (Deciding satisfiability) [20 marks] Let p, q, r be three Boolean
variables. For each of the following propositional formulas determine whether
it is satisfiable or not.
1. p ∧ (q ∨ ¬p) ∧ (¬q ∨ ¬r)
2. p ∧ (q ∨ ¬p) ∧ (¬q ∨ ¬p)
2