CS 205: Discrete Structures I Rutgers University
Discrete Structures I
MIDTERM
Date: November 5, 2025
Name:
NetID:
Section:
Instructions
1. Write your name, NetID, and section in the boxes above.
2. You are permitted four 8.5" x 11" sheets of handwritten notes (both sides). No other
resources are allowed.
3. The exam consists of [Number] problems worth [Total] points. Point values are indi-
cated for each problem.
4. You must write your solutions in the space provided.
5. Show all your work and provide clear justifications and proofs for your
answers. Answers without supporting work will not receive any credit.
6. For proofs, write clearly and logically. State your assumptions and any facts
used.
7. You may use any theorems or results proved in class without re-proving them, unless
the question explicitly asks for the proof.
Problem Points Score
1 [Points]
2 [Points]
Total [Total]
Page 1
,CS 205: Discrete Structures I Rutgers University
Problem 1: Logic and Predicates
(a) Let p, q, and r be propositions. Using a truth table, determine if the compound
proposition (p → q) ∧ (q → r) is logically equivalent to (p → r). Justify your
conclusion.
Solution
The propositions are not logically equivalent. Let A = (p → q) ∧ (q → r) and
B = (p → r). We construct the truth table:
p q r A B
T T T T T
T T F F F
T F T F T
T F F F F
F T T T T
F T F F T
F F T T T
F F F T T
For equivalence, the truth columns for A and B must be identical. Since they differ
(e.g., in row 3, where v(p) = T, v(q) = F, v(r) = T yields v(A) = F and v(B) = T ),
we conclude A ̸≡ B.
Page 2
,CS 205: Discrete Structures I Rutgers University
(b) Let p and q be two atomic propositions. By only Boolean Algebra equivalences
(and known equivalences such as De Morgan’s law or the ones given in the slides),
determine if the following is a tautology, contingent, or a contradiction.
(p ∧ (q ∧ ¬q)) =⇒ ¬(p =⇒ ¬q)
Solution
The proposition is a tautology.
We simplify the premise of the implication:
p ∧ (q ∧ ¬q) ≡ p ∧ F (Negation Law)
≡F (Domination Law)
Let the consequence of the implication be B = ¬(p → ¬q). The original proposition
is now F → B.
F → B ≡ ¬F ∨ B (Implication Equivalence)
≡T∨B (Negation)
≡T (Domination Law)
Since the expression simplifies to T regardless of the truth value of B (and thus p
and q), it is a tautology.
Page 3
, CS 205: Discrete Structures I Rutgers University
(c) Translate the following statements into symbolic logic using predicates, quantifiers,
and a specified domain.
(i) There is no integer x such that x2 − x = −1.
(ii) For every real number x, there is a real number y such that xy = 1.
Solution:
(i) There is no integer x such that x2 − x = −1.
Let the domain be Z. The statement is ¬∃x ∈ Z (x2 −x = −1), or equivalently,
∀x ∈ Z (x2 − x ̸= −1).
(ii) For every real number x, there is a real number y such that xy = 1.
Let the domain be R. The statement is ∀x ∈ R ∃y ∈ R (xy = 1).
If the domain is understood from context, these can be written as ¬∃x (x2 −x = −1)
and ∀x ∃y (xy = 1), respectively.
Page 4
Discrete Structures I
MIDTERM
Date: November 5, 2025
Name:
NetID:
Section:
Instructions
1. Write your name, NetID, and section in the boxes above.
2. You are permitted four 8.5" x 11" sheets of handwritten notes (both sides). No other
resources are allowed.
3. The exam consists of [Number] problems worth [Total] points. Point values are indi-
cated for each problem.
4. You must write your solutions in the space provided.
5. Show all your work and provide clear justifications and proofs for your
answers. Answers without supporting work will not receive any credit.
6. For proofs, write clearly and logically. State your assumptions and any facts
used.
7. You may use any theorems or results proved in class without re-proving them, unless
the question explicitly asks for the proof.
Problem Points Score
1 [Points]
2 [Points]
Total [Total]
Page 1
,CS 205: Discrete Structures I Rutgers University
Problem 1: Logic and Predicates
(a) Let p, q, and r be propositions. Using a truth table, determine if the compound
proposition (p → q) ∧ (q → r) is logically equivalent to (p → r). Justify your
conclusion.
Solution
The propositions are not logically equivalent. Let A = (p → q) ∧ (q → r) and
B = (p → r). We construct the truth table:
p q r A B
T T T T T
T T F F F
T F T F T
T F F F F
F T T T T
F T F F T
F F T T T
F F F T T
For equivalence, the truth columns for A and B must be identical. Since they differ
(e.g., in row 3, where v(p) = T, v(q) = F, v(r) = T yields v(A) = F and v(B) = T ),
we conclude A ̸≡ B.
Page 2
,CS 205: Discrete Structures I Rutgers University
(b) Let p and q be two atomic propositions. By only Boolean Algebra equivalences
(and known equivalences such as De Morgan’s law or the ones given in the slides),
determine if the following is a tautology, contingent, or a contradiction.
(p ∧ (q ∧ ¬q)) =⇒ ¬(p =⇒ ¬q)
Solution
The proposition is a tautology.
We simplify the premise of the implication:
p ∧ (q ∧ ¬q) ≡ p ∧ F (Negation Law)
≡F (Domination Law)
Let the consequence of the implication be B = ¬(p → ¬q). The original proposition
is now F → B.
F → B ≡ ¬F ∨ B (Implication Equivalence)
≡T∨B (Negation)
≡T (Domination Law)
Since the expression simplifies to T regardless of the truth value of B (and thus p
and q), it is a tautology.
Page 3
, CS 205: Discrete Structures I Rutgers University
(c) Translate the following statements into symbolic logic using predicates, quantifiers,
and a specified domain.
(i) There is no integer x such that x2 − x = −1.
(ii) For every real number x, there is a real number y such that xy = 1.
Solution:
(i) There is no integer x such that x2 − x = −1.
Let the domain be Z. The statement is ¬∃x ∈ Z (x2 −x = −1), or equivalently,
∀x ∈ Z (x2 − x ̸= −1).
(ii) For every real number x, there is a real number y such that xy = 1.
Let the domain be R. The statement is ∀x ∈ R ∃y ∈ R (xy = 1).
If the domain is understood from context, these can be written as ¬∃x (x2 −x = −1)
and ∀x ∃y (xy = 1), respectively.
Page 4
