Welcome to Discrete Mathematics

ITMO University • Fall 2025 – Spring 2026 • Instructor: Konstantin Chukharev

This is the central hub for all course materials, assignments, and resources.

🚀 Quick Navigation

New to the course?

• 📖 Course Overview – Structure, topics, and assessment
• 📅 Schedule – Weekly topics and important dates
• 📊 Grading System – Points breakdown and requirements

Need help?

• 💬 Support & Mentors – Telegram group and office hours
• 📚 Course Materials – Lecture slides, textbooks, cheatsheets

Working on assignments?

• ✏️ Homework – Guidelines, submission, defense
• 📝 Tests – Format, preparation, sample problems
• 🎓 Theoretical Minimums – Requirements and preparation

� Course Content

🍁 Fall Semester:

• Module 1: Set Theory (Weeks 1–2, 6) – Operations, cardinality, axioms, Cantor’s theorem
• Module 2: Binary Relations (Weeks 3–7) – Equivalence, orders, functions, lattices
• Module 3: Boolean Algebra (Weeks 8–10) – Logic gates, circuits, K-maps, minimization
• Module 4: Formal Logic (Weeks 11–16) – Propositional logic, natural deduction, quantifiers

🌱 Spring Semester:

• Module 5: Graph Theory (Weeks 1–4) – Graphs, trees, paths, algorithms
• Module 6: Flow Networks (Week 5) – Max flow, min cut, Ford-Fulkerson
• Module 7: Automata Theory (Weeks 6–10) – DFA, NFA, regular languages, pumping lemma
• Module 8: Combinatorics (Weeks 11–16) – Counting, generating functions, recurrences

Course Overview

📋 Basic Information

• Course: Discrete Mathematics
• Semesters: Fall 2025 – Spring 2026
• Prerequisites: High school mathematics
• Language: Russian (lectures), English (materials)
• Instructor: Konstantin Chukharev

🎯 What You’ll Learn

By the end of this course, you will be able to:

🍁 Fall Semester:

• Work confidently with sets, operations, and cardinality
• Understand and apply binary relations (equivalence, order, functions)
• Design and analyze Boolean expressions and digital circuits
• Construct formal proofs using natural deduction

🌱 Spring Semester:

• Analyze graphs and trees using various algorithms
• Solve network flow problems
• Design and analyze finite automata and regular languages
• Apply combinatorial principles and generating functions

📚 Course Structure

Two-semester course covering 8 “modules”:

🍁 Fall Semester:

• Set Theory (Weeks 1–2, 6) Sets, operations, cardinality, axioms

• Binary Relations (Weeks 3–7) Equivalence, order, functions, lattices

• Boolean Algebra (Weeks 8–10) Logic gates, circuits, minimization

• Formal Logic (Weeks 11–16) Propositional and predicate logic, proofs

🌱 Spring Semester:

• Graph Theory (Weeks 1–4) Graphs, trees, paths, cycles, algorithms

• Flow Networks (Week 5) Max flow, min cut, applications

• Automata Theory (Weeks 6–10) Finite automata, regular languages, NFAs

• Combinatorics (Weeks 11–16) Counting principles, generating functions, recurrences

📊 Assessment Overview

In each semester, you will complete:

⚠️ Important: You must complete all homework and pass all Theoretical Minimums to receive a passing grade, regardless of total points.

🎓 Key Success Factors

• Attend all lectures - Material builds cumulatively
• Start homework early - Give yourself time to think and iterate
• Form study groups - Explain concepts to each other
• Practice regularly - Mathematical skill develops through repetition
• Ask questions - Use mentors and Telegram group actively

📖 Syllabus

This two-semester course covers fundamental discrete mathematics concepts essential for computer science.

📚 Course Modules

The course spans two semesters with eight modules total:

Fall Semester:

• 📐 Module 1: Set Theory – Weeks 1–2, 6
• 🔗 Module 2: Binary Relations – Weeks 3–7
• ⚡ Module 3: Boolean Algebra – Weeks 8–10
• 🧠 Module 4: Formal Logic – Weeks 11–16

Spring Semester:

• 🕸️ Module 5: Graph Theory – Weeks 1–4
• 🌊 Module 6: Flow Networks – Weeks 5–6
• 🤖 Module 7: Automata Theory – Weeks 7–12
• 🎲 Module 8: Combinatorics – Weeks 13–16

Click each module above to see detailed topics, learning outcomes, and applications.

🎯 Learning Objectives

By completing this course, students will develop:

• ✓ Mathematical reasoning – Construct and critique formal proofs
• ✓ Abstract thinking – Work with abstract mathematical structures
• ✓ Problem-solving – Apply techniques to discrete systems
• ✓ CS foundations – Build groundwork for algorithms, theory, and beyond

📋 Course Policies

Attendance

• Lectures: Mandatory – Material covered is essential for success
• Tests & Colloquiums: Attendance required on scheduled dates
• Defenses: Missing homework defense = zero score

Academic Integrity

⚠️ Plagiarism: Results in zero score, potential course failure, and academic misconduct report.

Communication

📚 Course Materials

Primary Resources

• Lecture Notes – Slides and PDFs for each module
• Homework Assignments – Practice problems with solutions
• Cheatsheets – Quick reference for key concepts

Recommended Textbooks

💡 Important Notes

⚠️ This course requires consistent effort throughout both semesters.

Discrete mathematics builds concepts cumulatively – missing lectures or falling behind makes catching up extremely difficult.

Key Points:

• Proof writing develops over time – expect initial difficulty
• Start homework early
• Use Telegram and mentors for questions

📐 Module 1: Set Theory

Duration: Weeks 1-2 + Week 6

📚 Core Topics

Weeks 1-2: Foundations

• Set Operations: Union, Intersection, Difference, Symmetric Difference, Complement
• Power Sets: Boolean algebra of sets
• Venn Diagrams: Visual representation
• Cartesian Products
• Paradoxes & Axioms: Russell’s paradox, Zermelo-Fraenkel axioms (ZFC), Axiom of choice

Week 6: Cardinality

• Finite vs Infinite Sets: Understanding size
• Countable & Uncountable Sets: Different infinities
• Pairing Functions: Encodings
• Cantor’s Results: Diagonal argument, Cantor’s theorem
• Classical Theorems: Schroeder-Bernstein theorem
• Paradoxes: Hilbert’s hotel

🔑 Key Concepts

💡 Applications

Where you’ll use this:

• 🗄️ Database theory and relational algebra
• 🎲 Probability theory foundations
• 📝 Formal language theory
• 🧮 Algorithm analysis and complexity

✅ Learning Outcomes

By the end of this module, you will be able to:

• Prove set identities using element arguments or algebraic laws
• Construct Venn diagrams for complex expressions
• Determine cardinality of finite and infinite sets
• Prove sets are countable or uncountable
• Apply Cantor’s diagonal argument correctly

🔗 Module 2: Binary Relations

Duration: Weeks 3-7

📚 Core Topics

Properties of Relations

• Reflexive & Irreflexive: Self-relationships
• Symmetric, Antisymmetric & Asymmetric: Bidirectional behavior
• Transitive: Chain relationships
• Composition & Closures: Building new relations

Equivalence Relations (Weeks 3-4)

• Definition and properties
• Equivalence classes
• Partitions and quotient sets
• Fundamental theorem: Equivalences <-> Partitions

Order Relations (Weeks 4-5)

• Partial Orders (Posets): ≤ relation
• Linear/Total Orders: Complete ordering
• Well-orderings: Every subset has minimum
• Hasse Diagrams: Visual representation
• Elements: Maximal/minimal, greatest/least
• Structures: Chains and antichains
• Dilworth’s Theorem: Chain decomposition

Functions (Week 5)

• Functions as special relations
• Components: Domain, codomain, range, image, preimage
• Types:
  • Injective (one-to-one)
  • Surjective (onto)
  • Bijective: Both injective and surjective
• Composition and inverses

Lattices (Week 7)

• Upper and lower bounds
• Suprema and infima
• Complete lattices
• Modular and distributive lattices
• Boolean algebras as lattices

🔑 Key Definitions

💡 Applications

Real-world uses:

• 🗄️ Database design and normalization
• 🔍 Program analysis and verification
• 📅 Scheduling and task ordering
• 🔐 Cryptographic hash functions
• 🎯 Algorithm optimization

✅ Learning Outcomes

By the end of this module, you will be able to:

• ✓ Determine and prove properties of relations
• ✓ Find equivalence classes and construct quotient sets
• ✓ Draw and interpret Hasse diagrams for partial orders
• ✓ Prove functions are injective/surjective/bijective
• ✓ Compose functions and find inverses
• ✓ Apply pigeonhole principle to solve counting problems

⚡ Module 3: Boolean Algebra

Duration: Weeks 8-10

📚 Core Topics

Boolean Functions (Week 8)

• Truth Tables: Complete function specification
• Basic Operations: AND (∧), OR (∨), NOT (¬), XOR (⊕), NAND (↑), NOR (↓)
• Boolean Laws: Commutative, associative, distributive, De Morgan’s
• Duality Principle: Swapping ∧↔∨ and 0↔1
• Normal Forms:
  • DNF (Disjunctive): Sum of products
  • CNF (Conjunctive): Product of sums
  • Perfect/Canonical forms

Digital Circuits (Week 9)

• Logic Gates: Physical implementation of Boolean operations
• Circuit Design: From truth table to circuit
• Analysis: From circuit to Boolean expression
• Multi-level Circuits: Optimization and complexity
• Functional Completeness: Minimal operation sets
• Universal Gates: NAND and NOR alone suffice

Minimization (Week 10)

• Karnaugh Maps (K-maps): Visual minimization (2-4 variables)
• Don’t Care Conditions: Flexible outputs for optimization
• Quine-McCluskey: Algorithmic minimization (any number of variables)
• Prime Implicants: Essential and non-essential

🔑 Key Concepts

💡 De Morgan’s Laws: ¬(x ∧ y) = ¬x ∨ ¬y ¬(x ∨ y) = ¬x ∧ ¬y

💡 Applications

Where you’ll use this:

• 💻 Digital circuit design and hardware
• 🖥️ Computer architecture (ALU, CPU design)
• 🧩 SAT solvers and automated reasoning

✅ Learning Outcomes

By the end of this module, you will be able to:

• Construct and analyze truth tables for Boolean expressions
• Convert between DNF, CNF, and arbitrary Boolean forms
• Simplify expressions using Boolean laws and duality
• Design and analyze digital circuits using logic gates
• Minimize Boolean functions with Karnaugh maps
• Prove sets of operations are functionally complete

🧠 Module 4: Formal Logic

Duration: Weeks 11-16

📚 Core Topics

Propositional Logic (Weeks 11-12)

• Syntax: Formulas, atoms, connectives (∧, ∨, →, ¬, ↔)
• Semantics: Truth tables, interpretations, models
• Classification: Tautologies, contradictions, contingencies
• Relationships: Logical equivalence (≡) and consequence (⊨)
• Proof System: Natural deduction rules

Metalogic (Week 12)

• Soundness Theorem: Provable → Valid (⊢ ⇒ ⊨)
• Completeness Theorem: Valid → Provable (⊨ ⇒ ⊢)
• Compactness Theorem: Infinite satisfiability
• Decidability: Algorithmic verification

Predicate Logic (Week 13)

• Syntax: Predicates, quantifiers (∀, ∃), terms, variables
• Scope: Bound vs free variables
• Semantics: Interpretations, domains, models
• Normal Forms: Prenex normal form
• Gödel’s Theorems (overview):
  • Completeness: Every valid formula is provable
  • Incompleteness: Arithmetic has unprovable truths

Categorical Logic (Week 14)

• Statement Types: A (All), E (No), I (Some), O (Some…not)
• Square of Opposition: Logical relationships
• Syllogisms: Three-part arguments
• Validity Analysis: Rule-based and diagrammatic
• Venn Diagrams: Visual proof method

🔑 Key Concepts

💡 Quantifier Semantics: ∀x P(x): “For all x in the domain, P(x) holds” ∃x P(x): “There exists at least one x such that P(x) holds”

💡 Applications

Real-world impact:

• 🤖 Automated theorem proving and AI reasoning
• ✅ Program verification and correctness proofs
• 🗄️ Database query languages (SQL logic)
• 🧩 Knowledge representation systems
• 🔬 Formal methods in software engineering
• 🎯 Smart contract verification

✅ Learning Outcomes

By the end of this module, you will be able to:

• ✓ Classify formulas as tautologies/contradictions/contingencies
• ✓ Construct rigorous natural deduction proofs
• ✓ Prove logical equivalence between formulas
• ✓ Translate between natural language and formal logic
• ✓ Manipulate quantifiers and work with predicate formulas
• ✓ Analyze validity of categorical syllogisms using multiple methods

📅 Course Schedule

📖 See the detailed Weekly Plan and Key Deadlines for complete information.

🗓️ Semester Overview

✅ Assessment Timeline

⚠️ Important: Homework is due the day before tests at 23:55 GMT+3.

📆 Weekly Plan

📐 Module 1: Set Theory

Week 1: Foundations

• Introduction to sets and notation
• Set Operations: Union, intersection, difference, complement
• Power sets and subsets
• Euler diagrams, Venn diagrams
• Cartesian products
• Russell’s paradox

Week 2: Ordered Structures

• Tuples, n-tuples, ordered pairs
• Kuratowski’s definition
• Cartesian product and geometric interpretation

🔗 Module 2: Binary Relations

Week 3: Relations & Equivalence

• Binary relations as sets: definition and representations
• Graph and matrix representations
• Properties: reflexive, symmetric, transitive, etc.
• Equivalence relations
• Set partitions and quotient sets
• Composition and powers or relations

📌 Homework 1 due | Test 1

Week 4: Order Relations

• Orders, partial orders, total/linear orders
• Partially ordered sets (posets)
• Hasse diagrams
• Covering relation
• Maximal, minimal, greatest, least elements
• Chains and antichains
• Dilworth’s Theorem

Week 5: Functions

• Functions as special relations
• Domain, codomain, range
• Injective (1-1), surjective (onto), bijective
• Composition of functions
• Inverse functions
• Monotonic functions
• Characteristic function

Week 6: Cardinality

• Finite vs infinite sets
• Cardinality of sets
• Countable sets
• Uncountable sets
• Cantor’s diagonal argument
• Cantor’s theorem
• Schroeder-Bernstein theorem

Week 7: Lattices

• Upper and lower bounds
• Supremum and infimum
• Lattices
• Modular and distributive lattices
• Boolean algebras as lattices

📌 Homework 2 due | Test 2 | TM1 (Set Theory + Relations)

⚡ Module 3: Boolean Algebra

Week 8: Boolean Functions

• Boolean functions
• Truth tables
• Normal forms: DNF (sum of products), CNF (product of sums)
• Boolean laws and duality principle

Week 9: Digital Circuits

• Logic gates
• Circuit design and analysis
• Functional completeness
• Standard Boolean basis
• NAND and NOR
• Post’s criterion
• Multi-level circuits

Week 10: Minimization

• Karnaugh maps (K-maps)
• Don’t care conditions
• Circuit optimization
• Quine-McCluskey algorithm

📌 Homework 3 due | Test 3

🧠 Module 4: Formal Logic

Week 11: Propositional Logic

• Syntax: Formulas, atoms, connectives
• Semantics: Truth tables, models
• Tautologies, contradictions, contingencies
• Logical equivalence

Week 12: Proof Systems

• Natural Deduction: Inference rules
• Proof techniques and strategies
• Metalogic: Soundness and completeness theorems

Week 13: Predicate Logic

• First-Order Logic (FOL)
• Universal and existential quantifiers
• Interpretations, domains, models
• Gödel’s Theorems (overview):
  • Completeness: Valid -> Provable
  • Incompleteness: Arithmetic has unprovable truths

Week 14: Categorical Logic

• Categorical statements: A (All), E (No), I (Some), O (Some…not)
• Square of opposition
• Syllogisms: Three-part arguments
• Validity analysis with Venn diagrams

Week 15: Review & Advanced Topics

• Comprehensive review of formal logic
• Advanced topics

📌 Homework 4 due | Test 4 | TM2 (Boolean Algebra + Logic)

Week 16: Special Topics

• Ordinals and cardinals
• Metalogical concepts
• Course wrap-up

🎯 Exam Period

Final Exam: Comprehensive assessment of all course material (Weeks 1-16)

Format:

• ✍️ Written: Definitions, theorems, consistent notes
• 🔧 Practical: Problem solving and proofs
• 💬 Verbal: Conceptual explanations

⏰ Key Deadlines

📍 Timezone: All times are 23:55 GMT+3 unless otherwise specified.

✏️ Homework Deadlines

💡 Submission: Upload via Dropbox link (shared in Telegram group)

📝 Test Schedule

Format: Open book, individual work

🎓 Theoretical Minimums (TM)

Format: Closed book, individual work

⚠️ Critical: You must pass BOTH TMs to receive course credit, regardless of your total points!

🎯 Final Exam

Coverage: All modules (Weeks 1-16)

Format & Duration:

Date: During university exam period (announced later)

📌 Important Policies

• Defense Required: All homework must be defended orally (scheduled individually via Telegram)
• Make-ups: Available only for documented emergencies (medical, family, etc.)
• Review Sessions: Scheduled before TMs and Final Exam

💡 Pro Tip: Start homework immediately when assigned. Cramming before deadlines leads to poor understanding and rushed defenses!

Grading System

Your final grade is based on 100 total points from four components.

See details on:

• Components breakdown
• Grade scale & requirements
• Policies

Quick Overview

Grade Scale

⚠️ Critical Requirements

To pass the course, you MUST:

1. Complete all 4 homework assignments (minimum passing score on each)
2. Pass both Theoretical Minimums (≥50% on each)
3. Achieve total ≥60 points

Failure to meet ANY requirement = failing grade, regardless of total points

Quick Tips

• Start homework early
• Attend all lectures
• Form study groups
• Practice regularly
• Ask questions
• Review graded work
• Plan ahead for deadlines

📊 Grading Components

✏️ Homework Assignments (40 points)

Purpose: Practice concepts, prepare for assessments, receive feedback

📖 See Homework section for complete details

📝 Module Tests (20 points)

Coverage: Each test focuses on one module

Purpose: Assess computational skills and problem-solving abilities

📖 See Tests section for complete details

🎓 Theoretical Minimums (20 points)

⚠️ Critical: You must pass both TMs (≥50% each) to receive course credit, regardless of total points!

Purpose: Evaluate deep theoretical understanding and proof skills

📖 See Colloquiums section for complete details

🎯 Final Exam (20 points)

Purpose: Integrate knowledge across all course topics

📖 See Final Exam section for complete details

Grade Scale & Requirements

Final Grade Conversion

Minimum Requirements

⚠️ You MUST satisfy ALL three conditions

1. Complete all homework (minimum passing score on each)
2. Pass both TMs (score ≥50% on each TM)
3. Total points ≥60

Failing ANY requirement results in a failing grade.

Example: Failing Despite High Points

Scenario: Student earns 85 total points but scores 45% on TM1 Result: FAIL (did not pass TM1)

Calculation Example

Result: 83 points → Grade 4 (Good)

✅ All requirements met:

• All homework completed ✅
• Both TMs passed (≥50%) ✅
• Total ≥60 ✅

FAQs

Q: Can I skip homework if I’m doing well on tests? A: No. All homework must be completed regardless of other scores.

Q: What if I fail a TM? A: You must retake it. One retake is allowed per TM.

Q: Can I improve my grade after the final? A: No. The final exam is the last graded component.

Q: What if I score 59.9 points? A: That rounds to 60, which passes (if other requirements met).

Grading Policies

Late Work

Homework

• 0-24 hours late: -1 point from max (max 9/10 possible)
• 1-7 days late: -2 points from max (max 8/10 possible)
• More than 7 days late: max 5/10 possible

Tests & Exams

• Make-ups only for documented emergencies
• No extensions on TMs or final exam

Penalties

Homework Quality

• Formatting issues: -1 point
• Illegible handwriting: -2 points
• Missing name/ID: -1 point
• Plagiarism: 0 points (assignment failed)

Bonuses

• Exceptional solutions
• Active participation
• Course contributions: GitHub PRs, error reports
• Helping peers: study groups, tutoring, answering questions

Academic Integrity

Allowed:

• Discussing approaches
• Study groups
• Asking questions

Prohibited:

• Copying solutions
• Sharing written work
• Using prior years’ solutions
• AI-generated solutions

Penalty: Zero score, course failure, university report

Collaboration Policy

Rule: You must write solutions independently and defend them orally.

Attendance

• Not directly graded
• Essential for success
• Material may not be in notes

Homework Assignments

Latest revisions of homework assignments:

Homework	PDF
Homework 1: Set Theory
Homework 2: Relations
Homework 3: Boolean Algebra
Homework 4: Formal Logic
Homework 5: Graph Theory
Homework 6: Automata Theory
Homework 7: Combinatorics
Homework 8: Recurrences

📋 Overview

• 8 assignments total (4 per semester)
• 10 points each (80 points total for both semesters)
• ~10 problems per assignment
• Oral defense required for each
• Must pass all to receive course credit

📅 Assignment Schedule

🍁 Fall Semester:

🌱 Spring Semester:

⏰ Deadline: Day before the corresponding test, 23:55 GMT+3

📚 Problem Structure

Each assignment contains ~10 problems divided by difficulty:

🎯 Why Homework Matters

1. Practice – Reinforce concepts through hands-on problem-solving
2. Preparation – Build skills needed for tests and exams
3. Feedback – Identify knowledge gaps early
4. Independence – Develop mathematical thinking and rigor

✅ Passing Requirements

• Minimum score: Typically 80% (8/10 points)
• Below threshold → Resubmission required
• All homework must be passed to complete the course

⚠️ Important: Even with high test scores, you cannot pass the course without completing all homework!

🔗 Key Pages

• Submission Guidelines – Format, deadlines, submission process
• Defense Process – What to expect, preparation tips
• Tips & FAQs – Common questions, success strategies

📤 Homework Submission Guidelines

📄 Format Requirements

Required on first page:

• Full name
• Group number
• ISU identifier
• Assignment number (e.g., “Homework 3”)
• Assignment topic (e.g., “Set Theory”)
• Assignment revision (e.g. “v5”)

🚀 How to Submit

1. Prepare – Write solutions clearly, compile to PDF
2. Check – Verify all requirements are met
3. Upload – Use Dropbox link (shared in Telegram)
4. Verify – Receive submission confirmation email

💡 Tip: Multiple submissions are allowed before the deadline – only the latest version is graded.

⚠️ Warning: Don’t submit at the last minute! Network issues or technical problems could cause you to miss the deadline.

⏰ Deadlines

• Due: Day before the corresponding test
• Time: 23:55 GMT+3 (strict)
• Announced: At least 2 weeks in advance
• Defense: Scheduled after submission deadline

⏱️ Late Submission Policy

Note: Late submissions still require defense and must meet the minimum passing score (typically 8/10, not including penalties).

❌ Common Mistakes to Avoid

✅ Quality Checklist

Before submitting, verify:

• All problems attempted and solved
• Solutions clearly written
• Work shown for all steps
• Final answers highlighted
• PDF is readable on screen
• Title page is complete
• File size under limit
• Uploading to correct link

💬 Homework Defense

🎯 What is Defense?

All homework must be defended orally in a 10–15 minute discussion with the instructor or mentor.

Purpose: Verify that you genuinely understand your own solutions and can explain the reasoning behind them.

⏰ When & Where

• Scheduled: After submission deadline
• Sign-up: Posted in Telegram group
• Location: During organized hours or dedicated defense slots
• Attendance: Mandatory — missing defense = zero score

📅 Tip: Sign up early to get a convenient time slot!

🗣️ What to Expect

During the defense, you may be asked to:

1. Explain your solution to a specific problem
2. Justify particular steps in your reasoning
3. Answer “what if” variations or edge cases
4. Define mathematical terms you used
5. Solve a similar problem on the spot

💡 Key Point: The goal is to demonstrate understanding, not memorization!

📚 How to Prepare

• ✓ Review all your solutions thoroughly
• ✓ Understand why each step works (not just that it works)
• ✓ Practice explaining solutions aloud (to yourself or a friend)
• ✓ Bring a copy of your submission for reference
• ✓ Be ready to solve similar problems

⚠️ Warning: Solutions copied from others will be immediately obvious during defense!

📊 Possible Outcomes

🎓 Tips for Success

• Think first – Take a moment before answering, don’t rush
• Structure clearly – Organize your explanation logically
• Use examples – Illustrate abstract concepts with concrete cases
• Be honest – Admit uncertainty rather than guess confidently
• Listen carefully – Pay attention to follow-up questions
• Stay calm – It’s a learning experience, not an interrogation!

❓ Common Defense Questions

• “Can you explain why you used this approach?”
• “What would happen if we changed this condition?”
• “Can you define this term in your own words?”
• “How would you solve this similar problem?”
• “What’s the intuition behind this step?”

💡 Pro Tip: If you can teach the concept to someone else, you’re ready for defense!

💡 Homework Tips & FAQs

🎯 Success Strategies

1. Start early – Begin 1–2 weeks before the deadline
2. Read carefully – Understand what each problem is asking
3. Try alone first – Struggling builds real understanding
4. Discuss when stuck – Get hints, but write solutions independently
5. Check your work – Verify answers and reasoning
6. Write clearly – Pretend you’re teaching someone
7. Show all steps – Partial credit requires visible work
8. Prepare for defense – Truly understand your solutions

🤝 Collaboration Guidelines

When working on homework assignment, you are allowed and forbidden from the following:

✅ Allowed

• Discussing problem-solving approaches and strategies
• Explaining mathematical concepts to peers
• Working through example problems together
• Asking clarifying questions about problem statements
• Forming study groups to learn together

❌ Not Allowed

• Using LLM/AI tools (ChatGPT, Claude, etc.)
• Copying solutions from anyone (classmates, internet, previous years)
• Sharing your written solutions with others
• Dividing problems among group members
• Submitting work you don’t understand

Golden Rule: If you can’t defend it in 10 minutes, it’s not yours.

📚 Resources You Can Use

❓ Common Questions

🦫 Q: Can I submit handwritten solutions?
👨🏻‍🏫 A: Yes, this is the intended format. Just ensure your handwriting is legible.

🦫 Q: Can I submit electronically typed solutions?
👨🏻‍🏫 A: Typed solutions (LaTeX/Typst) are welcome. Word files are discouraged.

🦫 Q: What if I’m stuck on a problem?
👨🏻‍🏫 A: Struggle for at least 30 minutes, then ask for hints (not solutions) from mentors or in study groups.

🦫 Q: Can I resubmit after the deadline?
👨🏻‍🏫 A: Yes, but late penalties may apply. Better to submit something on time than nothing at all.

🦫 Q: What exactly counts as plagiarism?
👨🏻‍🏫 A: Copying any part of a solution from anyone or anywhere without working it out yourself.

🦫 Q: What if I miss my defense appointment?
👨🏻‍🏫 A: Zero score until you manage to re-schedule the defense with a mentor.

🦫 Q: How detailed should my solutions be?
👨🏻‍🏫 A: Show enough work that someone could follow your reasoning. Include definitions, justifications, and key steps. During defense, you may be asked to explain any part of your solution. After several defenses, you’ll get a sense of how much detail is expected by your instructor.

🦫 Q: Can I submit early?
👨🏻‍🏫 A: Yes! Early submission gives you peace of mind and time to prepare for defense (or do other homeworks…).

⏰ Time Management Plan

💡 Remember: Homework is where you learn, not just where you’re evaluated. The goal is understanding, not just points.

🚀 Pro Tips

• Use mentors’ help – Don’t waste time stuck when help is available
• Form study groups – Teaching others solidifies your understanding
• Test edge cases – Check if your answer works for simple/extreme values
• Read problem statements twice – Many mistakes come from misreading
• Start with what you know – Build from familiar concepts
• Take breaks – Fresh eyes catch errors better

📝 Module Tests

📋 Overview

• 8 tests total (4 per semester), one per module
• 5 points each (40 points total for both semesters)
• 90 minutes duration
• Open book – Notes, textbooks, and course materials allowed
• Individual work – No collaboration during test

📅 Test Schedule

🍁 Fall Semester:

🌱 Spring Semester:

🎯 What Tests Assess

💡 Focus: Tests are less theoretical than Colloquiums (TMs) but more practical than homework – they emphasize problem-solving speed and accuracy.

📄 Test Format

• 5–8 problems with multiple parts
• Problem types: Computation, short proofs, examples, analysis
• Point values: Clearly marked for each problem
• Time per problem: ~10–15 minutes average

🔗 Related Pages

• Format & Topics – Detailed test structure
• Test 1: Set Theory – Sample problems and topics
• Test 2: Relations – Sample problems and topics
• Test 3: Boolean Algebra – Sample problems and topics
• Test 4: Logic – Sample problems and topics
• Tips & FAQs – Preparation strategies and common questions

📝 Test Format & General Information

⏰ Test Logistics

📚 Materials Policy

✅ Allowed

• Your handwritten or typed notes
• Course textbooks and materials
• Calculators (if needed for specific tests)
• Cheatsheets provided by instructor

❌ Prohibited

• Electronic devices (phones, laptops, tablets)
• Communication with others
• Internet access
• Collaboration of any kind

📄 Question Structure

• 5–8 problems per test
• Multiple parts (a, b, c, etc.) for each problem
• Point values clearly marked for each part
• Mixed types – See below

🎯 Question Types

📊 Grading Criteria

💡 Partial Credit: Awarded generously for valid approaches and correct partial work – show all your steps!

📋 Test-Taking Guidelines

Before the Test

• Review relevant lecture materials
• Complete and understand corresponding homework
• Practice similar problems from textbook
• Organize your allowed materials
• Get adequate sleep the night before

During the Test

• Work independently – no communication
• Use only your own materials
• Raise hand for clarifications (not hints!)
• Show all work clearly
• Budget time wisely (~12 minutes per problem)
• Check your answers if time permits

After the Test

• Grading: Completed within one week
• Feedback: Common errors and solutions discussed
• Regrade requests: Submit within one week with justification

🔄 Make-Up Policy

✅ Valid Reasons

❌ Invalid Reasons

• Oversleeping or alarm failure
• Personal travel plans
• Other coursework deadlines
• Non-emergency scheduling conflicts
• “I wasn’t prepared”

Procedure

1. Contact instructor/mentor ASAP (before test if possible)
2. Provide documentation within 48 hours
3. Schedule make-up within one week of original test
4. Expect a different (possibly harder) test version

⚠️ Warning: Make-up tests are not guaranteed and may be more challenging than the original.

📐 Test 1 – Set Theory

📅 Test Details

📚 Topics Covered

• Set operations (union, intersection, difference, symmetric difference, complement)
• Venn diagrams
• Power sets
• Cardinality
• Cartesian products
• Set identities (De Morgan’s, distributive, etc.)
• Basic proofs with sets

🎯 Sample Problem Types

• Operations: Compute set expressions
• Venn Diagrams: Draw and shade regions for given formulas
• Proofs: Prove set identities using element method
• Power Sets: Calculate power set size for given set
• Cartesian Products: Find Cartesian products for specific sets
• Cardinality: Apply inclusion-exclusion principle

📖 Preparation Guide

Review Materials

1. Lecture Notes: Module 1 (Set Theory)
2. Homework: HW 1
3. Textbook: Kenneth Rosen

Practice Problems

• Basic: All set operations on 2–3 sets
• Venn Diagrams: Shade regions for complex expressions
• Proofs: Element method for 5–10 identities
• Power Sets: Calculate for sets of size 0–5
• Products: Cartesian products with different cardinalities

Common Pitfalls

⚠️ Watch Out!

• Don’t confuse “element of” with “subset of”
• Remember: set difference is not commutative
• Power set of empty set has one element (the empty set itself)
• Venn diagrams: label all regions clearly

💡 Pro Tips

• Show all work – even for “obvious” set operations
• Use element method – “let \(x \in A\)…” is your friend
• Draw diagrams – Venn diagrams help verify your work
• Check edge cases – test with empty set, singletons
• Double-check notation – { } vs ( ) matters!

🔗 Test 2 – Binary Relations

📅 Test Details

📚 Topics Covered

• Relation properties (reflexive, symmetric, transitive, antisymmetric)
• Equivalence relations and partitions
• Order relations and Hasse diagrams
• Functions (injective, surjective, bijective)
• Composition of functions
• Cardinality (finite, countable, uncountable)

🎯 Sample Problem Types

• Properties: Determine which properties a given relation satisfies
• Equivalence Classes: Find equivalence classes for given relation
• Hasse Diagrams: Draw diagram for partial order
• Functions: Prove given function is bijective
• Composition: Compute composition of given functions
• Cardinality: Show rationals are countable using diagonalization

📖 Preparation Guide

Review Materials

1. Lecture Notes: Module 2 (Binary Relations)
2. Homework: HW 2
3. Textbook: Kenneth Rosen

Practice Problems

• Relations: Check properties for 10+ different relations
• Equivalence: Find equivalence classes for modular arithmetic
• Hasse Diagrams: Draw for divisibility, subset, lexicographic order
• Functions: Prove injectivity/surjectivity for various \( f : A \to B \)
• Composition: Compute compositions and verify associativity
• Cardinality: Review proofs that \(\mathbb{N}\), \(\mathbb{Z}\), \(\mathbb{Q}\) are countable; \(\mathbb{R}\) is uncountable

Common Pitfalls

⚠️ Watch Out!

• Antisymmetric is NOT the same as “not symmetric” (check definition!)
• In Hasse diagrams, don’t draw transitive edges
• Composition order: \( f \circ g \) means “\(f\) after \(g\)”
• Equivalence classes must partition the set (disjoint and cover all)
• Injection and surjection are different concepts!

💡 Pro Tips

• Test systematically – for properties, check all pairs methodically
• Use counterexamples – one pair can disprove a property
• Hasse diagrams – start with minimal/maximal elements
• Function proofs – use “suppose \(f(a) = f(b)\)” for injection
• Cardinality – know diagonalization and zig-zag arguments
• Partition check – equivalence classes should be disjoint and exhaustive

⚡ Test 3 – Boolean Algebra

📅 Test Details

📚 Topics Covered

• Boolean functions and truth tables
• Normal forms (DNF, CNF)
• Logic gates and circuits
• Karnaugh maps for minimization
• Boolean simplification using laws
• Functional completeness

🎯 Sample Problem Types

• Truth Tables: Construct truth table for given Boolean expression
• Normal Forms: Convert given function to DNF and CNF
• Simplification: Simplify Boolean expressions using laws
• Circuits: Design circuit for majority function
• K-Maps: Use K-map to minimize given function
• Completeness: Prove {NAND} is functionally complete

📖 Preparation Guide

Review Materials

1. Lecture Notes: Module 3 (Boolean Algebra)
2. Homework: HW 3
3. Textbook: Kenneth Rosen

Practice Problems

• Truth Tables: Build tables for 5–10 complex expressions
• DNF/CNF: Convert between forms for various functions
• Boolean Laws: Simplify 10+ expressions step-by-step
• Circuits: Draw circuits for common functions (adders, multiplexers)
• K-Maps: Minimize 20+ random functions (including don’t cares)
• Completeness: Practice expressing AND, OR, NOT with NAND

Common Pitfalls

⚠️ Watch Out!

• De Morgan’s Laws: \( \overline{x \vee y} = \overline{x} \wedge \overline{y} \), and \( \overline{x \wedge y} = \overline{x} \vee \overline{y} \)
• K-map groupings: must be rectangles with power-of-2 sizes (1, 2, 4, 8…)
• Circuit notation: distinguish AND from OR gate symbols
• DNF vs CNF: DNF is OR of ANDs; CNF is AND of ORs
• Don’t forget: NOT gate inverts (circles on circuit diagrams)

💡 Pro Tips

• Truth tables first – when stuck, build truth table
• K-maps are visual – look for largest groupings first
• Simplify before circuits – smaller expressions = fewer gates
• Test with cases – verify circuit with sample inputs
• Know your laws – memorize De Morgan’s, distributive, absorption
• Draw clearly – messy circuits lead to errors

🧠 Test 4 – Formal Logic

📅 Test Details

📚 Topics Covered

• Propositional logic (syntax and semantics)
• Natural deduction proofs
• Logical equivalence and consequence
• Predicate logic basics
• Quantifiers (universal and existential)
• Categorical logic and syllogisms

🎯 Sample Problem Types

• Tautologies: Determine if given formula is a tautology
• Proofs: Prove arguments using natural deduction
• Equivalence: Show logical equivalences using truth tables
• Translation: Translate English sentences to predicate logic
• Validity: Determine if arguments are valid
• Syllogisms: Analyze classical syllogisms

📖 Preparation Guide

Review Materials

1. Lecture Notes: Module 4 (Formal Logic)
2. Homework: HW 4
3. Textbook: Kenneth Rosen

Practice Problems

• Tautologies: Test 10–15 formulas using truth tables
• Proofs: Complete natural deduction proofs for common theorems
• Equivalences: Show logical equivalence for 5–10 pairs
• Translation: Convert 20+ English sentences to predicate logic
• Quantifiers: Negate complex quantified formulas
• Syllogisms: Analyze validity of classical argument forms

Common Pitfalls

⚠️ Watch Out!

• Quantifier negation: \( \neg \forall x ~ P(x) \) means “there exists \(x\) such that \( \neg P(x) \)”
• Scope matters in predicate logic
• In proofs: justify every step with a rule name
• Translation: “only” is not the same as “all” (contrapositive!)
• Syllogisms: check for fallacies (undistributed middle, etc.)

💡 Pro Tips

• Truth tables work – when unsure about tautology, build the table
• Proof strategy – work backwards from conclusion to find needed steps
• Name your rules – explicitly cite modus ponens, ∧-intro, etc.
• Quantifier scope – use parentheses to clarify scope clearly
• Practice translation – “all”, “some”, “no”, “only” have precise meanings
• Check validity – valid argument = impossible for premises true and conclusion false

💡 Test Tips & Success Strategies

⏰ Time Management

Pro Time Tips

• Quick wins first – boost confidence with easy problems
• Don’t get stuck – if problem takes >20 min, move on
• Watch the clock – check time every 20–25 minutes
• Always review – use any remaining time to verify work
• Partial credit – write what you know even if incomplete

📝 During the Test

Essential Practices

Step-by-Step Approach

1. Read problem carefully – underline key information
2. Plan approach – think before writing
3. Show intermediate steps – justify your reasoning
4. Box or circle final answer – make it prominent
5. Quick sanity check – does answer make sense?

🎒 What to Bring

✅ Required

• Writing materials: Pens (blue/black), pencils
• Eraser: For diagrams and scratch work
• Notes: Handwritten or typed (printed)

✅ Optional but Helpful

• Textbook: For reference formulas
• Calculator: If needed for specific tests
• Highlighters: To mark key parts of problems
• Cheatsheet: Your own summary of key concepts

❌ Not Allowed

• Collaboration with others
• ChatGPT and similar LLM/AI tools

❓ Frequently Asked Questions

Test Logistics

🦫 Q: Can I use my laptop for notes?
👨🏻‍🏫 A: Yes, you can use the laptop to access the materials, unless it is specifically prohibited by you instructor!

🦫 Q: What if I finish early?
👨🏻‍🏫 A: Review your work thoroughly. Most students use the full 90 minutes — you should too!

🦫 Q: Can I ask questions during the test?
👨🏻‍🏫 A: Yes, but only clarification questions about problem wording — not hints on how to solve.

🦫 Q: What happens if I’m late?
👨🏻‍🏫 A: You’ll receive whatever time remains. Tests start promptly — arrive 5 minutes early.

Preparation

🦫 Q: Is there a practice test available?
👨🏻‍🏫 A: Nope. Just do the homework, watch the lectures, and you will be ready!

🦫 Q: How should I study?
👨🏻‍🏫 A: Review notes, do homework early, practice similar problems from the books, try to understand the concepts (not just memorize).

🦫 Q: Can I collaborate on studying?
👨🏻‍🏫 A: Absolutely! Study groups are encouraged before the test.

Grading

🦫 Q: How much fancy my work should be?
👨🏻‍🏫 A: Work must be legible. Extremely messy answers may lose points (-1 of max).

🦫 Q: Do I lose points for wrong answers?
👨🏻‍🏫 A: No extra penalty for incorrect work — you only earn points for correct reasoning.

🦫 Q: Can I get a regrade?
👨🏻‍🏫 A: No.

🎯 Success Strategies

Before the Test

During the Test

After the Test

🧠 Mental Preparation

💭 Mindset Tips

• You’ve prepared – trust your preparation
• Partial credit means every step counts
• It’s okay to skip hard problems temporarily
• Mistakes are learning opportunities, not failures
• The test measures understanding, not speed

Stress Management

• Before: Exercise, good sleep, positive self-talk
• During: Deep breathing, skip and return, focus on what you know
• After: Reflect constructively, don’t catastrophize

📊 Common Mistakes to Avoid

Good luck on your tests! Remember: preparation + strategy = success. 🎓

🎓 Theoretical Minimums (Colloquiums)

📖 Overview

Theoretical Minimums (TMs) are comprehensive oral/written examinations testing deep understanding of mathematical theory and proof techniques. Called “minimums” because passing them is a minimum requirement for course completion.

⚠️ Critical Requirement: You must pass both TMs (score ≥50%) to receive credit for the course, regardless of your other grades.

TM Structure

📅 Schedule

Fall Semester

Spring Semester

🎯 Purpose

TMs ensure you can:

• ✓ State definitions and theorems precisely – word-perfect recall
• ✓ Construct rigorous proofs – logical, complete arguments
• ✓ Explain concepts clearly – demonstrate understanding, not memorization
• ✓ Make connections between topics – see the big picture
• ✓ Demonstrate mathematical maturity – write like a mathematician

💡 Key Insight: You cannot pass this course through computation alone. Theoretical understanding is mandatory.

📚 Key Pages

• 📐🔗 TM1: Set Theory & Binary Relations
• ⚡🧠 TM2: Boolean Algebra & Formal Logic
• 📖 Preparation Guide

⚖️ Difference from Tests

🔄 Retake Policy

If You Score < 50% on a TM

Important Notes

⚠️ Retake Strategy

• Take retake seriously – it may be more challenging
• Oral format requires explaining concepts verbally
• Study gaps identified in original attempt
• Schedule retake ASAP while material is fresh
• Use office hours/mentors before retake

💪 Success Strategy

Understanding vs. Memorization

Preparation Timeline

📊 What to Expect

Question Categories

Grading Criteria

• Precision: Definitions and statements must be exact
• Rigor: Proofs must be logically complete
• Clarity: Explanations must be clear and well-organized
• Correctness: Right answers with valid justification

💡 Partial Credit: While more limited than regular tests, you can still earn points for:

• Correct definitions even if proof fails
• Valid proof strategies even if details are wrong
• Clear explanations of concepts

Good luck on your TMs! Remember: deep understanding is the goal. 🎓

📐🔗 TM 1 – Set Theory + Binary Relations

📅 Exam Details

📚 Coverage

The first theoretical minimum covers fundamental concepts from the initial modules of the course:

📐 Set Theory (Weeks 1–2, 6)

• Set operations and laws
• Power sets
• Cartesian products
• Russell’s paradox
• Axiomatic set theory (ZFC)
• Cardinality
• Countable vs uncountable sets
• Cantor’s diagonalization
• Schroeder-Bernstein theorem

🔗 Binary Relations (Weeks 3–7)

• Relation properties (reflexive, symmetric, transitive, antisymmetric)
• Equivalence relations and partitions
• Order relations and Hasse diagrams
• Functions (injection, surjection, bijection)
• Composition and inverses
• Lattices

📝 Sample Questions

Definitions

• Define equivalence relation (with example)
• What is a well-ordering?
• Define power set and its cardinality
• Define bijection
• What is a partition?

Theorems

• State equivalence-partition correspondence theorem
• State Cantor’s theorem
• State Schroeder-Bernstein theorem
• Composition associativity

Proofs

• Prove real numbers are uncountable
• Show composition of bijections is bijective
• Prove every finite poset has maximal element

Conceptual

• Why does Russell’s paradox matter?
• Difference between maximal and greatest element?
• Example of injective but not surjective function
• Why are rationals countable but reals uncountable?

✅ What You Must Know

• Set operations (union, intersection, difference, symmetric difference) and laws
• Relation properties (reflexive, symmetric, transitive, antisymmetric)
• Equivalence relations and partitions
• Partial orders, total orders, well-orders
• Injective, surjective, bijective functions
• Composition of relations and functions
• Cardinality (finite, countable, uncountable)
• Key theorems: Cantor’s theorem, Schroeder-Bernstein, equivalence-partition correspondence
• Proof techniques: element method, double inclusion, diagonalization

📖 Preparation Checklist

✅ Week 6 (2 weeks before)

• Review all lecture notes from Weeks 1–7
• Create flashcards for definitions
• List all theorem statements
• Identify 5 hardest concepts

✅ Week 7 (1 week before)

• Practice 10+ proofs without looking
• Join study group, quiz each other
• Can recite all definitions precisely?
• Attend review session

✅ Day Before

• Light review of materials
• Get 8 hours sleep!
• Prepare mentally, stay calm

💡 Pro Tips

🎯 Success Strategy

• Definitions first: If you can’t define it, you can’t use it
• Proof structure matters: Introduction → Body → Conclusion
• Use examples: Verify your reasoning with concrete cases
• Time management: Don’t spend 60 min on one proof
• Partial credit: Write what you know, even if incomplete

Common Pitfalls to Avoid

• ❌ Confusing “injective” and “surjective”
• ❌ Writing “obvious” instead of proving rigorously
• ❌ Circular reasoning in proofs
• ❌ Mixing up “element of” and “subset of”
• ❌ Forgetting to check all relation properties

What Graders Look For

• ✓ Precise definitions (exact wording)
• ✓ Complete proofs (no gaps in logic)
• ✓ Clear explanations (not just symbols)
• ✓ Correct examples and counterexamples
• ✓ Proper mathematical notation

⚡🧠 TM2 – Boolean Algebra + Formal Logic

📅 Exam Details

📚 Coverage

The second theoretical minimum covers key concepts from the latter modules of the course:

⚡ Boolean Algebra (Weeks 8–10)

• Boolean functions and truth tables
• Boolean laws and duality principle
• Normal forms (DNF, CNF)
• Logic gates (AND, OR, NOT, NAND, NOR, XOR)
• Functional completeness
• Karnaugh maps
• Quine-McCluskey algorithm

🧠 Formal Logic (Weeks 11–15)

• Propositional logic (syntax and semantics)
• Tautologies, contradictions, contingencies
• Logical equivalence and consequence
• Natural deduction proof systems
• Soundness and completeness
• Predicate logic with quantifiers
• Categorical logic and syllogisms

📝 Sample Questions

Definitions

• Define tautology, contradiction, contingency
• What is functional completeness?
• Define logical consequence
• What is DNF? What is CNF?
• Define soundness vs completeness

Theorems

• State the completeness theorem
• Show {NAND} is functionally complete
• Every Boolean function has DNF representation
• De Morgan’s laws

Proofs

• Prove transitivity of implication using natural deduction
• Show De Morgan’s law using truth table or Boolean algebra
• Prove a tautology is valid in all interpretations
• Show {NAND} can express AND, OR, NOT

Conceptual

• Relationship between Boolean algebra and logic?
• Difference between soundness and completeness?
• Why can’t we use truth tables for predicate logic?
• What makes a gate set universal?

✅ What You Must Know

• Boolean operations (AND, OR, NOT) and laws
• DNF and CNF normal forms
• Functional completeness concept
• Tautologies, contradictions, contingencies
• Logical equivalence and consequence
• Soundness vs completeness distinction
• Natural deduction inference rules (modus ponens, modus tollens, etc.)
• Quantifier negation rules
• Key theorems: Completeness theorem, De Morgan’s laws, functional completeness proofs
• Proof techniques: truth tables, Boolean algebra, natural deduction, gate construction

📖 Preparation Checklist

✅ Week 14 (2 weeks before)

• Review all lecture notes from Weeks 8–15
• Memorize all Boolean laws
• List all natural deduction rules
• Practice proofs in natural deduction

✅ Week 15 (1 week before)

• Can recite all definitions precisely?
• Practice functional completeness proofs
• Join study group, quiz on theorems
• Attend review session

✅ Day Before

• Review materials once
• Get 8 hours sleep!
• Stay calm and confident

💡 Pro Tips

🎯 Success Strategy

• Laws are your tools: Memorize Boolean laws cold
• Name your inference rules: In proofs, cite “Modus Ponens”, “∧-Intro”, etc.
• Truth tables work: When stuck, build truth table
• K-maps are visual: Practice grouping patterns
• Quantifiers are tricky: Double-check negations

Common Pitfalls to Avoid

• ❌ Confusing semantic consequence and syntactic provability
• ❌ Wrong quantifier negation (negating “for all” gives “there exists…not”, not “for all…not”)
• ❌ Forgetting to justify proof steps
• ❌ K-map groups not power-of-2 sizes
• ❌ Mixing up soundness and completeness

What Graders Look For

• ✓ Exact definitions (word-for-word accuracy)
• ✓ Named inference rules in proofs
• ✓ Clear step-by-step Boolean simplifications
• ✓ Correct gate constructions for completeness
• ✓ Proper quantifier manipulation
• ✓ Understanding of soundness/completeness distinction

📖 TM Preparation Guide

📅 Study Timeline

4 Weeks Before TM

3 Weeks Before TM

2 Weeks Before TM

1 Week Before TM

2–3 Days Before TM

Day Before TM

🛠️ Proof Techniques

Essential Proof Methods

Proof Writing Tips

✍️ Structure Every Proof

1. Opening: State what you’re proving
2. Setup: Define variables, state assumptions
3. Body: Logical argument with clear steps
4. Conclusion: “Therefore, …” or “Thus, …” or \(\square\)

Bad: “It’s obvious that…” Good: “By definition of X, we have… Therefore…”

📚 What to Memorize

📐 Set Theory Essentials

🔗 Relations Essentials

⚡ Boolean Algebra Essentials

🧠 Formal Logic Essentials

🧠 Study Strategies

Effective Techniques

• Active Recall: Test yourself without looking at notes – strengthens memory retrieval
• Spaced Repetition: Review material at increasing intervals to fight forgetting
• Teach Others: Explain concepts to study partners – best test of true understanding
• Practice Exams: Simulate exam conditions to build familiarity and reduce anxiety
• Whiteboard Practice: Work problems standing at a whiteboard – engages different thinking patterns

Study Group Best Practices

✅ Do This:

• Meet regularly (2–3 times per week)
• Quiz each other on definitions/theorems
• Work through proofs together
• Explain difficult concepts to each other
• Share different solution approaches

❌ Don’t Do This:

• Just socialize without studying
• Let one person do all the explaining
• Skip individual preparation before meeting
• Argue about minutiae; ask instructor to clarify
• Study only in groups (need solo time too!)

📖 Resources to Use

Supplementary Resources

• Online Videos: When reading isn’t clicking
• Math StackExchange: For alternative perspectives
• Practice Problems: Throughout preparation
• Old Exams: Final week preparation

⚠️ Common Mistakes

Logical Errors

Proof-Writing Errors

🌙 Day Before TM

What TO DO

✅ Light review (1 hour max):

• Skim definition flashcards
• Glance at theorem list
• Review 1–2 key proofs

✅ Self-care:

• 8 hours of sleep (non-negotiable!)
• Healthy meals throughout the day
• Light exercise or walk
• Relaxation techniques (deep breathing, meditation)

✅ Logistics:

• Confirm exam time and location
• Prepare ID and any allowed materials
• Set multiple alarms
• Plan to arrive 10 min early

What NOT TO DO

• ❌ Don’t cram new material – if you don’t know it now, won’t learn it tonight
• ❌ Don’t stay up late studying – sleep > cramming
• ❌ Don’t drink excessive caffeine – disrupts sleep quality
• ❌ Don’t panic – trust your preparation
• ❌ Don’t compare yourself to others – focus on your own readiness

💪 Mental Preparation

Confidence Builders

🎯 Positive Self-Talk

• “I’ve prepared thoroughly for this.”
• “I know the material well.”
• “Partial credit means every bit of knowledge counts.”
• “I can handle difficult questions – I’ll do my best.”
• “One exam doesn’t define me or my understanding.”

During the Exam

🎓 Final Wisdom

Remember: TMs test understanding, not just memorization. Focus on:

• Why definitions are structured that way
• How theorems connect to each other
• When to apply different proof techniques
• What the big ideas are, not just details

Trust your preparation, stay calm, and do your best. Good luck! 🍀

🎓 Final Exams

⚠️ WARNING: This page is a work in progress.

Some details may be incomplete or subject to change!

📋 Overview

The course has two final exams – one after each semester.

Each exam consists of three components designed to assess different aspects of your mastery.

Exam Structure

📅 Schedule

🍁 Fall Semester Exam

🌱 Spring Semester Exam

📚 Coverage

🍁 Fall Semester Final Exam

Emphasis: Boolean Algebra (~40%), Formal Logic (~40%), Earlier topics (~20%)

🌱 Spring Semester Final Exam

Emphasis: Automata (~40%), Combinatorics (~40%), Earlier topics (~20%)

🎯 Exam Components Explained

📝 Written Component

• Duration: 120 minutes
• Format: Closed book (no materials allowed)
• Questions: 6–8 problems mixing theory and computation
• Grading: Correctness, completeness, clarity, rigor

Problem types: Definitions (2–3 pts), Theorems (3–4 pts), Computations (2–3 pts), Proofs (4–5 pts)

🗣️ Verbal Component

• Duration: 15–20 minutes per student
• Format: One-on-one with instructor
• Process: Draw random topic → brief prep (2–3 min) → explain concept → answer questions
• Evaluation: Knowledge, understanding, depth, connections

Topics: Any major theorem, key definition, proof technique, or conceptual connection

💻 Practical Component

• Released: End of Week 15
• Due: Before your verbal exam slot
• Format: Individual take-home assignment
• Requirements: Working solution + documentation + explanation + test cases

Examples: Implement algorithm, build solver, design circuit, analyze structure

📖 Key Pages

• 📋 Exam Structure Details

⚠️ Critical Requirements

To pass the course, you must:

1. Pass all TMs (≥50% each)
2. Complete all homework assignments
3. Earn ≥60 points

💡 Note: Even if you pass all TMs and earn enough points, incomplete homework may result in course failure.

💪 Success Tips

For Written Exam

• Review all lecture materials systematically
• Redo homework without looking at solutions
• Practice under timed conditions
• Memorize key theorems and proofs
• Focus on recent modules (more heavily weighted)

For Verbal Exam

• Practice explaining concepts aloud
• Prepare examples for all major topics
• Understand connections between concepts
• Stay calm, think before speaking
• It’s OK to say “I don’t know” and reason from what you do know

For Practical Component

• Start early – don’t wait until last minute!
• Read problem carefully, plan before coding
• Test with simple cases first
• Document your approach as you work
• Ask clarifying questions early

🎓 Final Thoughts

The final exam is comprehensive but fair. It tests what you’ve learned throughout the semester. Trust your preparation, manage your time well, and demonstrate your understanding.

Good luck! 🍀

📋 Exam Structure Details

⚠️ WARNING: This page is a work in progress.

Some details may be incomplete or subject to change!

📝 Written Component (16 points)

Format Overview

Problem Types

Coverage Distribution

Fall Semester Exam

Spring Semester Exam

Grading Criteria

💡 Partial Credit: Awarded for correct approach even if final answer is wrong. Show your work!

🗣️ Verbal Component (8 points)

Verbal Format Details

Process

Possible Topics

🍁 Fall Semester

• Equivalence relations and partitions theorem
• Cantor’s diagonalization argument
• Functional completeness proofs
• Soundness vs completeness distinction
• Boolean duality principle
• Natural deduction rule systems
• Cardinality comparison methods

🌱 Spring Semester

• Pumping lemma for regular languages
• Myhill-Nerode theorem
• Inclusion-exclusion principle
• Max-flow min-cut theorem
• Generating functions techniques
• NFA to DFA conversion
• Recurrence solving methods

Evaluation Criteria

Tips for Success

✅ Do This:

• Start with precise definition
• Give concrete example
• Explain significance/applications
• Connect to related concepts
• Be honest if you don’t know something

❌ Don’t Do This:

• Memorize without understanding
• Rush through explanation
• Ignore the question asked
• Make up false information
• Panic if you don’t know everything

💻 Practical Component (6 points)

Practical Format Details

Typical Problem Types

Fall Semester Examples

Spring Semester Examples

Requirements

Practical Evaluation Criteria

|———–|––––|—————–| | Correctness | ~50% | Does it solve the problem correctly? | | Efficiency | ~20% | Is the approach reasonable? (Not necessarily optimal) | | Documentation | ~20% | Is explanation clear and complete? | | Completeness | ~10% | Are all parts addressed, edge cases handled? |

Submission Checklist

Before submitting, verify:

• Code compiles/runs without errors
• At least 3–5 test cases included with expected output
• README file explains problem, approach, and usage
• Code is well-commented
• Edge cases are handled (empty input, large input, etc.)
• Time/space complexity mentioned (rough estimate OK)
• All files organized in clear directory structure
• Your name and student ID in submission

Common Pitfalls

⚠️ Avoid These Mistakes

• Starting too late – budget 10–15 hours total work
• No documentation – code without explanation loses points
• No test cases – how do we know it works?
• Overcomplicated – simple correct solution beats complex buggy one
• Not asking questions – clarify requirements early!

🎯 Strategy for Success

Prioritization

1. Week 14: Start reviewing for written exam
2. End of semester: Begin practical component immediately when released
3. Before written part: Intensive review, finish practical
4. After written part: Prepare for verbal part, submit practical
5. Verbal exam day: Light review, stay calm

Balance Strategy

• Don’t neglect practical to study for written
• Do budget time for all three components
• Don’t assume verbal part will be easy
• Do practice explaining concepts aloud
• Don’t overcomplicate the practical solution
• Do test thoroughly and document well

Good luck with your exams! 🎓

Course Materials

📘 Primary Textbook

📖 Discrete Mathematics and Its Applications by Kenneth H. Rosen

• Comprehensive coverage of all course topics
• Extensive examples and practice problems
• Available in course Google Drive

Alternative Textbooks

• Discrete Mathematics with Applications by Susanna S. Epp – Excellent for beginners
• Book of Proof by Richard Hammack – Great for proof techniques

📚 Lecture Slides

All lectures available as PDFs:

Topic	PDF
Lecture: Set Theory
Lecture: Binary Relations
Lecture: Boolean Algebra
Lecture: Formal Logic
Lecture: Flow Networks
Lecture: Formal Languages
Lecture: Regular Languages
Lecture: Non-determinism
Lecture: Combinatorics

📋 Quick Reference

Cheatsheets for exam preparation and quick lookups:

Topic	PDF
Cheatsheet: Set Theory
Cheatsheet: Relations
Cheatsheet: Boolean Algebra
Cheatsheet: Formal Logic
Cheatsheet: Graph Theory
Cheatsheet: Automata Theory
Cheatsheet: Combinatorics

💡 Tip: Print cheatsheets and bring them to tests (open book policy)!

🌐 External Resources

Online Courses

• MIT 6.042J: Mathematics for Computer Science – Video lectures and problem sets
• Stanford CS103 – Mathematical foundations with great visualizations
• Coursera: Discrete Mathematics – Alternative explanations

Interactive Tools

• Wolfram Alpha – Verify calculations, explore concepts
• Truth Table Generator – Check logic formulas
• Graph Editor – Visualize graphs

Video Resources

• 3Blue1Brown – Beautiful mathematical visualizations
• MIT OpenCourseWare – Full course lectures

📝 Homework Preparation Tools

Handwritten Solutions

• Scan with phone apps
• Ensure high contrast and readability
• Combine pages into single PDF

Typesetting

• Typst (typst.app) – Modern, easier than LaTeX

  • Web-based editor with live preview
  • Faster compilation, cleaner syntax
  • Great for mathematical documents

• LaTeX/Overleaf (overleaf.com) – Traditional but powerful

  • Industry standard for academic writing
  • Many templates available
  • Steeper learning curve

• Microsoft Word submissions are prohibited!

Drawing Tools

• Draw.io – Free diagrams (Venn, Hasse, graphs)
• GeoGebra – Mathematical visualizations
• Excalidraw – Quick sketches

Getting Help

💬 Telegram Group

Main Communication Channel

The Telegram group is our primary platform for:

• 📢 Course announcements and updates
• ❓ Quick questions and clarifications
• 💡 Discussion of concepts and approaches
• 👥 Finding study partners
• 📅 Schedule changes and reminders

Link: Provided in class or by instructor

Guidelines

• ✅ Ask conceptual questions, discuss problem-solving strategies
• ✅ Help classmates understand concepts
• ✅ Search chat history before asking repeated questions
• ❌ Don’t share complete homework solutions
• ❌ Don’t ask for answers without showing your work

🎓 Mentors & Office Hours

When to Seek Help:

• Understanding homework problems
• Clarifying lecture material
• Reviewing proof techniques
• Preparing for exams
• Getting feedback on your approach

What Mentors Can Do:

• Explain concepts in different ways
• Point you in the right direction
• Help debug your reasoning
• Suggest practice problems
• Review your proof strategy

What Mentors Won’t Do:

• Solve homework for you
• Give you exam answers
• Write proofs for you

Contact: Via Telegram group or scheduled office hours

👥 Study Groups

Why Study Groups Work

• Explain concepts to solidify understanding
• Learn different problem-solving approaches
• Stay motivated and accountable
• Practice mathematical communication
• Catch each other’s mistakes

Finding Study Partners

1. Post in Telegram: “Looking for study group for Module X”
2. Connect with classmates after lectures
3. Form groups of 3–5 students

Running Effective Sessions

Good practices:

• Schedule regular meetings (2–3 times per week before deadlines)
• Work through problems together on a whiteboard
• Take turns explaining solutions
• Quiz each other on definitions
• Prepare individually before meeting

Avoid:

• Just copying each other’s work
• Letting one person do all the explaining
• Only socializing without studying
• Meeting only right before deadlines

Remember: See Academic Integrity for collaboration rules

❓ How to Ask Good Questions

Effective Question Structure

❌ Ineffective: “I don’t understand Cantor’s theorem.”

✅ Effective: “I understand that Cantor’s theorem proves \(|A| < |\mathcal{P}(A)|\), but I’m confused about why the diagonal argument works. Specifically, how does constructing a set \(S\) that differs from every set in the supposed surjection lead to a contradiction?”

Include

1. What you know: Show your current understanding
2. What you tried: Explain your attempts
3. Where you’re stuck: Pinpoint the specific confusion
4. Relevant context: Problem statement, theorem, concept

Homework Question Guidelines

📧 Instructor Contact

For:

• Course policy questions
• Grade concerns
• Special circumstances (illness, conflicts)
• Feedback on course content

Best method: Telegram direct message or as announced in class

💡 Self-Help Resources

Before asking, try:

• Re-read lecture notes
• Check textbook explanations
• Review similar homework problems
• Search the Telegram chat history
• Attempt the problem for at least 30 minutes

🔄 Feedback Welcome

Help us improve the course:

• Suggest topics for review sessions
• Report confusing material
• Share what’s working well
• Propose alternative explanations

Your input shapes the course!