Discrete Computational Structures Assignment #1

CS 230 : Discrete Computational Structures

Homework Assignment #1

Suggested Reading: Rosen Sections 1.1 - 1.3; LLM Sections 1.1, 3.1 - 3.4
These are the problems that you need to hand in for grading. Always explain your
answers and show your reasoning.
1. [6 Pts] Translate the following English sentences into logic. First, define your basic
propositions and use logical operations to connect them.
(a) Passing the final or attending class regularly is sufficient to pass the class.
(b) To pass the class, it is necessary to attend class regularly.
(c) You will pass the class if and only if you attend class regularly and you pass the
final.
2. [6 Pts] Determine whether → is associative, i.e., whether ((p → q) → r) ↔ (p →
(q → r)) is a tautology. Prove your answer using a truth table.
3. [5 Pts] Prove that (p → ¬q) ∧ (q → ¬r) and (p ∨ r) → ¬q are logically equivalent by
deduction using a series of logical equivalences studied in class.
4. [6 Pts] To be initiated into a club, a recruit needs to solve a logical puzzle. Two
members, Tom and Sue, introduce themselves. Tom says, “I am a CS major and Sue
is an SE major.” Sue says “One of us is a CS major and the other is an SE major.”
You know that one of them is lying while the other is telling the truth. Who is lying
and who is telling the truth? Who is the CS major and who is the SE major? Prove
your answers using logical reasoning.
5. [6 Pts] A proposition is said to be in CNF (conjunctive normal form) if it is a conjunction (and) of one or more clauses, where each clause is a disjunction (or) of basic
propositions or their negations. For example, (p∨¬q)∧(¬p∨¬q∨r)∧(q∨r) is in CNF.
Now prove that any compound proposition is logically equivalent to some proposition
in CNF.
6. [6 Pts] Prove that {XOR, AND, TRUE} is functionally complete, i.e.,any propositional
formula is equivalent to one whose only connectives are XOR and AND, along with
the constant TRUE. You may assume that {XOR}is logically equivalent to (p ∧ ¬q) ∨
(q ∧ ¬p). You may also assume that {¬, ∧, ∨} is functionally complete. Prove using a
series of logical equivalences.
For more practice, you are encouraged to work on the problems given at the end of Rosen,
Sections 1.1 - 1.3.