CS5002 Discrete Structures Profs. Amor-Tijani and Rachlin
Fall 2021 September 22, 2021
Homework # 3
Assigned: Wednesday September 22, 2021
Due: Tuesday September 28, 2021 @ 11:59:00 pm
Instructions:
• Homework is due on Tuesday at 11:59 pm Boston Time. Homeworks received up to 24 hours late will
be penalized 10 percent. NO assignment will be accepted after that.
• We expect that you will study with friends and often work out problem solutions together, but you
must write up your own solutions, in your own words. Cheating will not be tolerated. Professors,
TAs, and peer tutors will be available to answer questions but will not do your homework for you.
One of our course goals is to teach you how to think on your own.
• Assignments should be typed using Word or LateX, or hand-written neatly. When submitting to
gradescope be sure to indicate the page containing your answer to each problem.
• To get full credit, SHOW YOUR WORK!
Problem 1 [25 pts (5 pts each)]: Logical Equivalence
Prove each of the following by applying equivalence rules. State the equivilence rule you are
applying with each step.
i. p→ (q → r) ≡ q → (p→ r)
ii. ¬(p→ q) ≡ p ∧ ¬q
iii. p→ q ≡ ¬q → ¬p
iv. p→ (q ∧ r) ≡ (p→ q) ∧ (p→ r)
v. ((p→ q) ∧ (q → r))→ (p→ r) ≡ T (a tautology)
Problem 2 [25 pts] (5,5,5,10): Circuit Design
Design a circuit with three inputs, a2, a1, a0, and one output, out. The circuit outputs a 1
whenever the unsigned binary number represented by a2a1a0 is either a multiple of 2 or a multiple
of 3. Follow the steps below.
i. Create a truth table for the circuit
ii. Write down the DNF and CNF expressions for the circuit
iii. Draw a circuit using AND, OR, and NOT gates based on either the DNF or the CNF expres-
sion, whichever requires fewer gates.
1
iv. Simplify your circuit by applying the laws of logical equivalence to either the DNF or CNF ex-
pression and redraw your circuit. Explain what law you are applying with each simplification
step. Then redraw the circuit corresponding to your simplified logical expression.
Problem 3 [20 pts]: Charlie
For this problem, the domain is the set of Northeastern students. Consider the following two
predicates
Charlie(x) meaning “ Charlie knows x ”
CS(x) meaning “ x is a CS student ”
Using only variables, logic symbols (selected from ¬,∨,∧,→,↔,∃,∀), and the predicates Charlie()
and CS(), formulate the statements:
i. Charlie doesn’t know every CS student.
ii. The only students known to Charlie are CS students.
iii. Charlie knows at least two students. Here you may also use symbols “=” and “ 6=”, in addition
to those listed above.
iv. Charlie knows at most two students. Here again, you may use symbols “=” and “6=”.
Problem 4 [30 pts (10,10,10)]: Shapes
Use the following predicates when describing an object: Green, Blue, Red, Rectangle, Oval,
Diamond, Border
For example:
a. Green(H) = True because object H is green
b. Border(H) = False because object H has no border
For each statement below, write the contrapositive, the converse, and the inverse using english
(no logical operators needed). Tell which of the four statements (the three you wrote, in addition
to the original statement) is true or false. If a statement is false, provide a counter-example.
Example:
a. Original Conditional Statement (P → Q):
2
• If an object is green, then it is a rectangle.
• False. Object H is green but it is also not a rectangle.
b. Contrapositive (¬Q→ ¬P ):
• If an object is not a rectangle then it is not green.
• False. Object H is not a rectangle but it is also green.
c. Converse (Q → P)
• If an object is a rectangle then it is green.
• False. Object P is a rectangle but it is also not green.
d. Inverse ( ¬p→ ¬q)
• If an object is not green then it is not a rectangle.
• False. Object P is not green but it is also a rectangle.
i. If an object is red, then it has a border.
ii. If an object is a rectangle, then it is red and has a border.
iii. If an object is red or blue then it has a border.
3