§ — — Discrete Structures 1
Your prelim in Discrete Structures 1 almost always covers the first four lessons. Here is exactly what to expect, what to memorize, and how to prepare in one week.
| Lesson | Typical Weight | What Gets Tested |
|---|---|---|
| Lesson 1: Propositional Logic | 30% | Propositions vs. non-propositions, connectives, translation, truth tables, tautology/contradiction/contingency, converse/inverse/contrapositive |
| Lesson 2: Proof Techniques in Propositional Logic | 25% | Naming equivalence laws, naming inference rules, step-by-step validity proofs, testing validity with truth tables |
| Lesson 3: Predicate Logic and Quantifiers | 20% | ∀ and ∃ translation, quantifier inference rules, direct proof, contrapositive proof, proof by cases |
| Lesson 4: Set Concepts | 25% | Roster and set-builder form, cardinality, union/intersection/complement/difference, Cartesian product, inclusion-exclusion word problems |
| Question Type | What It Looks Like | Where It Comes From |
|---|---|---|
| Truth-table construction | "Construct the truth table for ¬P ∨ (Q ∧ P) and classify it." | Lesson 1 |
| English → symbols | "Translate: If the server is down, we cannot submit." | Lessons 1 and 3 |
| Symbols → English | "Read R → ¬L in words." | Lessons 1 and 3 |
| Identify the rule/law | "P → Q, ¬Q ∴ ¬P is which rule of inference?" | Lesson 2 |
| Set computations | "Given U, A, B, find A' ∩ B." | Lesson 4 |
| Inclusion-exclusion word problems | "40 like hockey, 35 like cricket, 20 like both..." | Lesson 4 |
Do not walk into the prelim without these cold:
| Day | Focus | Do This |
|---|---|---|
| Day 1 | Lesson 1: Propositional Logic | Re-read the content section. Write the five connective truth tables from memory three times. Redo Exercise 1.4. |
| Day 2 | Lesson 1 translation drills | Redo Exercises 1.1–1.3. For every sentence, underline the connective keyword before symbolizing. |
| Day 3 | Lesson 2: Proof Techniques in Propositional Logic | Memorize the equivalence-law table and rules-of-inference table. Redo Exercise 2.1 and 2.2 without looking at the tables. |
| Day 4 | Lesson 2 validity + Lesson 3: Predicate Logic and Quantifiers | Redo Exercise 2.3 (truth-table validity). Then drill ∀/∃ translation with Exercise 3.1. |
| Day 5 | Lesson 3 proofs + Lesson 4: Set Concepts | Redo Exercise 3.2 (contrapositive, direct proof). Then run through every set operation in Lesson 4 with your own small examples. |
| Day 6 | Mixed practice | Take the Free Practice Set in the next section under time pressure (45 minutes), then check the key. |
| Day 7 | Mock exam day | Take a full 30-item mock exam in one sitting, mark it, and re-study only the items you missed. |
Done with this module? Track it — your progress shows on the subject list.
You've finished this subject
Work through all 15 items before scrolling to the key. Everything here comes straight from Lessons 1–4.
Which of the following is a proposition? a. "Submit your activity!" b. "9 + 6 = 14" c. "Why is the lab closed?" d. "x < 10"
P is false and Q is true. What is the truth value of P → Q?
Given "If it rains tonight, I will sleep well," write the converse, the inverse, and the contrapositive. Which one is logically equivalent to the original?
Let R = "Leo reviews," S = "Leo sleeps early," P = "Leo passes." Translate: "If Leo reviews and sleeps early, then he passes."
What is the main connective of (P ∧ Q) ∨ ¬R?
A formula uses the variables P, Q, and R. How many rows does its truth table need?
Construct the truth table for P → (P ∨ Q). Classify it as a tautology, contradiction, or contingency.
Which equivalence law justifies ¬¬P ≡ P?
Which rule of inference is this? P → Q, P ∴ Q
Let B(x) = "x is a BSIT student," D(x) = "x takes Discrete Structures." Symbolize: "All BSIT students take Discrete Structures."
Let A(x) = "x is an app," F(x) = "x is free." Symbolize: "Some apps are free."
Given U = {1,2,3,4,5,6,7,8,9}, A = {1,3,5,7,9}, B = {3,6,9}. Find A ∩ B.
Using the same sets: find A − B and B'.
If |A| = 4 and |B| = 3, what is |A × B|?
In a class of 50 students, 30 use Android, 28 use iOS, and 12 use both. How many use at least one of the two? How many use neither?
b. "9 + 6 = 14" is declarative with a definite truth value (false). (a) is a command, (c) is a question, (d) has a free variable, so none of those carries a truth value.
True. A conditional is false only when the antecedent is true and the consequent is false. Here the antecedent is false, so P → Q is true.
Converse: "If I sleep well, it rains tonight" (Q → P). Inverse: "If it does not rain tonight, I will not sleep well" (¬P → ¬Q). Contrapositive: "If I do not sleep well, it does not rain tonight" (¬Q → ¬P). Only the contrapositive is equivalent to the original.
(R ∧ S) → P. "And" builds the conjunction; "if...then" makes the whole thing a conditional, so the conjunction sits inside the antecedent.
∨. The ∧ is trapped inside parentheses and the ¬ applies only to R, so the disjunction joins the two main parts.
8 rows. Rows = 2ⁿ with n = 3, and 2³ = 8.
Full table:
| P | Q | P ∨ Q | P → (P ∨ Q) |
|---|---|---|---|
| T | T | T | T |
| T | F | T | T |
| F | T | T | T |
| F | F | F | T |
The final column is all T, so it is a tautology.
Involution (double negation): ¬¬P ≡ P.
Modus Ponens. From a conditional and its antecedent, conclude the consequent.
∀x[B(x) → D(x)]. "All A are B" always uses ∀ with →.
∃x[A(x) ∧ F(x)]. "Some A are B" always uses ∃ with ∧.
A ∩ B = {3, 9} — the elements in both sets.
A − B = {1, 5, 7} (in A but not in B). B' = {1, 2, 4, 5, 7, 8} (everything in U outside B).
12. |A × B| = |A| × |B| = 4 × 3.
At least one: |A ∪ B| = 30 + 28 − 12 = 46. Neither: 50 − 46 = 4.
The two full 30-item prelim mocks, two full 30-item final mocks, complete explained answer keys, and the trap drills below come with the subject unlock.
ProReviewer — locked
Drills, code labs, and full solutions.
ProReviewer — locked
Drills, code labs, and full solutions.
ProReviewer — locked
Drills, code labs, and full solutions.
ProReviewer — locked
Drills, code labs, and full solutions.
ProReviewer — locked
Drills, code labs, and full solutions.
ProReviewer — locked
Drills, code labs, and full solutions.
ProReviewer — locked
Drills, code labs, and full solutions.
ProReviewer — locked
Drills, code labs, and full solutions.