BSIT Survival Kit

Prelim Exam Blueprint & Study Plan

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.

What the Prelim Covers

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 Types You Will See

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

Your Exact Memorize List

Do not walk into the prelim without these cold:

The five connective truth tables — ¬P, P ∧ Q, P ∨ Q, P → Q, P ↔ Q. Especially: P → Q is false only when P is true and Q is false.
The equivalence laws — De Morgan's, Material Implication (P → Q ≡ ¬P ∨ Q), Involution (¬¬P ≡ P), Commutative, Associative, Distributive, Idempotence, Identity laws, Exportation, Material Equivalence.
The inference rules — Modus Ponens, Modus Tollens, Disjunctive Syllogism, Hypothetical Syllogism, Addition, Simplification, Conjunction, Constructive Dilemma, Destructive Dilemma.
The conditional's three related forms — inverse (¬P → ¬Q), converse (Q → P), contrapositive (¬Q → ¬P). Only the contrapositive is equivalent to the original.
Set identities — De Morgan's for sets ((A ∪ B)' = A' ∩ B'), |A × B| = |A| × |B|, and inclusion-exclusion: |A ∪ B| = |A| + |B| − |A ∩ B|.
Quantifier patterns — "All A are B" is ∀x[A(x) → B(x)]; "Some A are B" is ∃x[A(x) ∧ B(x)]. Note the ∀ pairs with →, the ∃ pairs with ∧.

Top Mistakes That Cost Points

Marking P → Q false when P is false. A false antecedent makes the conditional true — always.
Writing the inverse when asked for the converse (or vice versa). Converse swaps; inverse negates; contrapositive does both.
Building 2ⁿ⁻¹ rows instead of 2ⁿ. Three variables means 8 rows, no exceptions.
Pushing ¬ inside parentheses without flipping the connective. ¬(P ∧ Q) is ¬P ∨ ¬Q, not ¬P ∧ ¬Q.
Computing B − A when the item asks for A − B. Set difference is not commutative.
Counting duplicate elements in cardinality. |{1, 2, 3, 3}| = 3, not 4.
Forgetting to subtract the overlap in inclusion-exclusion word problems.

7-Day Study Plan

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.

Free Practice Set — 15 Items with Answer Key

Work through all 15 items before scrolling to the key. Everything here comes straight from Lessons 1–4.

Items

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?

Answer Key

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.