CS1231S: pass the exams, not just read the notes
Your complete guide to National University of Singapore's discrete structures course. See where the marks are, work real practice questions, and study with an AI tutor that knows CS1231S.
Sia generates CS1231S practice questions, walks through propositional logic and arguments step by step, and quizzes you on the material the exam weights most heavily.
Worked example
Which of the following is the correct negation of the statement: for every student x, there exists a tutorial class y such that × is registered for y?
Write the statement formally. It is: for all × in S, there exists y in T, R(x, y).
Push the negation through the inner quantifier. Not (there exists y, R(x, y)) becomes for all y, not R(x, y).
Combine: there exists × in S such that for all y in T, not R(x, y). In words, there is some student who is not registered for any tutorial class. Note that both quantifiers flip; changing only one is the standard error.
The trap: Option B flips only the inner predicate and leaves both quantifiers as they were, which says something entirely different and much weaker. Option C flips the outer quantifier but wrongly leaves the inner one existential. The rule is mechanical: every quantifier in the scope of the negation flips, in order, and the negation ends up attached to the predicate. classic slip!
One exam decides 50% of your grade. Open book, conducted physically. This whole page is built around that.
Overview
What CS1231S is, and where it sits
CS1231S is the School of Computing's discrete structures course and the mathematical foundation of the computing degree. It is worth 4 units and runs in Semester 1, with weekly two-hour tutorials beginning in Week 3 at which attendance is taken.
The course is a proof course. It moves through propositional logic and proof technique, predicate logic, sets, relations including equivalence relations and partial orders, functions, mathematical induction, cardinality, counting and probability, and finishes with graphs and trees. For most students this is their first sustained encounter with writing mathematics rather than computing answers, and that shift is what makes the course demanding.
Assessment is tutorial attendance 5%, two assignments worth 20% in total, a mid-term test at 25% and a final examination at 50%. Both the midterm and the final are open-book and are conducted physically. The midterm date is fixed and clashes must be raised with the lecturer well in advance.
Official outline: comp.nus.edu.sg · CS1231S outline. Always treat the official outline and the exam timetable as authoritative.
Difficulty & time commitment
Is CS1231S hard, and how much time does it take?
CS1231S is manageable if you keep a weekly rhythm and treat the back half as the main event. The pattern is consistent: it starts gently and steepens, and the heaviest assessment is the part that separates grades.
The difficulty curve and the assessment weighting point the same way: the back half is harder and worth more. Front-loading effort there is the highest-return decision in the course.
Is this course for you
Who tends to do well, and who tends to struggle
You will likely do well if
- You write proofs out in full from early in the semester, rather than reading proofs and assuming you could reproduce them.
- You are comfortable being slow at first. Proof fluency arrives suddenly after a few weeks of deliberate practice, and students who quit before that point never reach it.
- You treat quantifier manipulation as a mechanical rule set and drill it until negation and nesting are automatic.
- You prepare tutorial answers before the session, which is what the course explicitly asks and what makes the two hours useful.
You may struggle if
- You expect open book to carry you. The papers ask you to construct derivations, which no reference sheet does for you.
- You skip steps because they feel obvious. The course grades rigour and citation explicitly, and 'obvious' is where marks disappear.
- You leave induction and counting until revision. Both are technique-heavy and neither is learnable quickly.
- You treat the tutorials as optional because attendance is only 5%. The tutorial questions are the closest available model of assessment standard.
- Build a laws reference you have actually used: the logical equivalences, set identities, counting rules and induction template, each with one worked application.
- Practise writing the same proof twice, once roughly and once to submission standard with every step cited. The gap between the two is what the marking rewards.
- For counting, always state which rule you are applying and why order or repetition does or does not matter, since that reasoning is where the marks sit.
- Work the released tutorial answers as problems first. They are written by the course and show exactly the standard expected.
Syllabus
The 12 topics, tutorial by tutorial
The exam-weight marker on each topic shows where the marks concentrate. The amber topics carry the highest exam weight.
T1 · Propositional logic and proofs
Course lectures, Week 3 tutorialTruth tables, logical equivalence, the laws of propositional logic, and proving statement forms rigorously step by step.
T2 · Arguments and validity
Course lecturesPremises and conclusions, the critical row method, and testing whether an argument form is valid.
T3 · Predicate logic
Week 4 tutorialPredicates, universal and existential quantifiers, the uniqueness quantifier, and negating quantified statements correctly.
T4 · Sets
Week 5 tutorialSet operations, subset proofs, power sets and Cartesian products.
T5 · Relations and equivalence relations
Week 6 tutorialRelation properties, equivalence relations, equivalence classes and partitions.
T6 · Relations and partial orders
Week 7 tutorialPartial and total orders, Hasse diagrams, and maximal, minimal, greatest and least elements.
T7 · Functions
Week 8 tutorialInjective, surjective and bijective functions, composition, and inverse functions.
T8 · Mathematical induction
Week 9 tutorialOrdinary and strong induction, structuring the base case and inductive step, and writing the proof completely.
T9 · Cardinality
Week 10 tutorialComparing infinite sets, countable and uncountable sets, and proving cardinality by bijection.
T10 · Counting and probability I
Week 11 tutorialThe multiplication and addition rules, permutations and combinations, and the pigeonhole principle.
T11 · Counting and probability II, and graphs I
Week 12 tutorialInclusion-exclusion, conditional probability and expected value, and the basic definitions of graph theory.
T12 · Graphs II and trees
Week 13 tutorialPaths, circuits, isomorphism, connectivity, trees and spanning trees.
How it's assessed
Assessment structure
| Component | Weight | Format & timing |
|---|---|---|
| Final examination | 50% | Open-book final examination, conducted physically. NUS examination period. Open book, conducted physically. |
| Mid-term test | 25% | Open-book mid-term test, conducted physically, on a fixed date. Clashes with other courses must be raised with the lecturer in advance. Mid-semester, fixed date. Open book, conducted physically. |
| Assignments | 20% | Two assignments at 10% each, covering propositional and predicate logic, proof, and the later topics. Across the semester. Individual work. |
| Tutorial attendance | 5% | Weekly two-hour tutorials from Week 3. Attendance is taken and active participation is expected. Weekly from Week 3. Attendance recorded. |
- The four components sum to 100%. No separate component hurdle is published.
- Both the midterm and the final are open book and are conducted physically on campus. Because the material is proof-based, open book helps less than students expect: you can bring the laws, but you still have to construct the derivation. Assignment questions indicate the expected standard, including instructions to complete every step and cite the law justifying each one.
This is an exam-cram course. With the exams at 50% of the grade and the final examination alone at 50%, your result is overwhelmingly decided by how well you perform under time pressure. Open book, conducted physically.
Final exam timing: During the NUS examination period. Confirm the exact date and venue on the official exam timetable.
How to actually pass it
A weekly rhythm, two checklists, and the traps to avoid
The course rewards consistency over cramming, and practice over re-reading. Here is the loop that works, then what to have nailed before each exam.
The weekly loop
Before the mid-semester checklist
- Build truth tables, prove logical equivalences, and simplify statement forms citing a law at every step.
- Translate English statements into predicate logic with correct quantifiers, including the uniqueness quantifier, and negate them correctly.
- Prove subset and set-identity results directly from the definitions.
- Determine relation properties, and work with equivalence relations, equivalence classes and partial orders including Hasse diagrams.
Before the final heaviest topics
- Classify functions as injective, surjective or bijective and prove it, and construct inverses and compositions.
- Write complete ordinary and strong induction proofs with a properly stated base case and inductive step.
- Reason about cardinality, including countability arguments established by bijection.
- Apply counting rules, inclusion-exclusion, the pigeonhole principle and probability, and handle graph and tree definitions, isomorphism, connectivity and spanning trees.
The mistakes that cost marks
Flipping only one quantifier when negating. Every quantifier within the scope of the negation flips, in order, and the negation lands on the predicate. Changing only the outer one produces a different and usually much weaker statement.
Skipping steps in a derivation. The course asks for every step to be present and justified by a named law, and grades that strictly. A correct final line with gaps does not earn full marks.
Using = instead of the equivalence symbol. Logical statements are equivalent, not equal. The course flags this explicitly in its tutorial materials, and it signals imprecision to a marker.
Assuming what you are proving in an induction. The inductive step assumes the statement for the previous case and derives the next one. Assuming the case you are trying to prove is the most common structural failure in induction proofs.
Teaching team
Who teaches CS1231S
The bios below are factual. We do not rate lecturers; any star ratings are submitted by students who have taken CS1231S.
Tan Tuck Choy, Aaron
Associate Professor in the School of Computing at the National University of Singapore. He lectures CS1231S and is the named contact on the official course site for mid-term test scheduling.
Teaching team as listed in the course materials reviewed. AskSia does not rate lecturers; star ratings are submitted by students who have taken CS1231S.
Formula & concept sheet
The vocabulary and formulas you must own
- Logical equivalence
- Two statement forms are equivalent when they have identical truth values in every row of the truth table, written with the equivalence symbol rather than an equals sign.
- Conditional statement
- The statement p implies q, which is false only when p is true and q is false, and true in every other case.
- Biconditional
- p if and only if q, equivalent to the conjunction of p implies q and q implies p, capturing a necessary and sufficient condition.
- Quantifier negation
- The negation of a universal statement is an existential statement of the negated predicate, and vice versa. Nested quantifiers flip in order.
- Equivalence relation
- A relation that is reflexive, symmetric and transitive, which partitions its set into disjoint equivalence classes.
- Partial order
- A relation that is reflexive, antisymmetric and transitive, representable as a Hasse diagram.
- Injective function
- A function under which distinct inputs always give distinct outputs, so no value in the codomain is hit twice.
- Surjective function
- A function whose image is the whole codomain, so every target value is attained by at least one input.
- Mathematical induction
- A proof method establishing a base case and then showing that the statement holding for one case forces it to hold for the next.
- Pigeonhole principle
- If more objects than containers are distributed among them, at least one container holds more than one object.
- Inclusion-exclusion
- A counting rule that corrects for double counting by adding the sizes of the sets, subtracting pairwise intersections, adding triples, and so on.
- Spanning tree
- A subgraph that is a tree and includes every vertex of a connected graph.
Common acronyms: CA · GCD · iff · LCM · QED.
Set texts
The prescribed reading
The syllabus references map straight onto these.
Course lecture notes and the official CS1231S books page
NUS School of Computing.
Where it fits
Prerequisites, related courses & why it matters
CS1231S is a 4-unit Level 1 course in the School of Computing, taken in Semester 1 as part of the computing core. Weekly two-hour tutorials begin in Week 3 and attendance is recorded.
Your CS1231S study toolkit
Study the course with Sia, not just read about it
Each tool already knows CS1231S: your syllabus, your texts, and where the marks are. Grouped by how you study, from first contact to exam week.
FAQ
Frequently asked questions
Is CS1231S hard?
It rates moderately hard, and the difficulty is concentrated in one place: most students have never written a rigorous mathematical proof before. The arithmetic is not the obstacle. Constructing a complete derivation where every step is justified is, and that skill takes weeks of practice rather than a revision push.
How is CS1231S assessed?
Tutorial attendance 5%, two assignments worth 20% in total, a mid-term test at 25% and a final examination at 50%. Both the midterm and the final are open book and conducted physically.
Does open book make it easier?
Less than you would hope. You can bring the laws of logic and the standard theorems, but the assessment asks you to construct proofs, and a reference sheet does not construct anything. What open book removes is memorisation; what it leaves is the actual skill being tested.
What if the midterm clashes with another course?
The midterm date is fixed and you are expected not to miss it. The official course site asks students to alert the lecturer by the stated deadline if it clashes with another course's test, giving the other course code and timing.
What topics does CS1231S cover?
Following the official tutorial sequence: propositional logic and proofs, predicate logic, sets, relations and equivalence relations, relations and partial orders, functions, mathematical induction, cardinality, counting and probability across two tutorials, then graphs and trees.
How strictly is proof rigour marked?
Strictly, and the course says so. Assignment instructions require you to complete every step without skipping and to cite the law that justifies each one, and state that grading will be strict on exactly that. Getting the right final line with gaps in the derivation does not earn the marks.
Study CS1231S with Sia
Work through propositional logic, arguments, predicate logic and the rest of the course with a tutor that knows it and quizzes you on the topics the assessments weight most heavily.
Start studying with Sia
