Welcome to Discrete Mathematics

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

This site contains all course materials, assignments, and resources for the Discrete Mathematics course.

🎯 Getting Started

New to the course?

• Start with Course Overview
• Review the Schedule
• Understand How You’re Graded

Need help?

• Check Support & Office Hours
• Browse Course Materials

Working on assignments?

• Homework Guidelines
• Test Information
• Colloquium Prep

📚 Lecture Slides (PDFs)

All lecture materials are available as downloadable PDFs:

📝 Homework Assignments

📄 Legacy Materials

📋 Course Documents

• Full Syllabus (PDF)
• Course Overview (PDF)

ℹ️ About This Course

Discrete Mathematics covers fundamental concepts essential for computer science:

• Set Theory - Operations, cardinality, axiomatic foundations
• Binary Relations - Equivalence, order, functions
• Boolean Algebra - Logic gates, circuit design
• Formal Logic - Propositional and predicate logic
• Automata & Languages - Regular languages, finite automata
• Combinatorics - Counting principles, generating functions

Repository: github.com/Lipen/discrete-math-course

Course Overview

Basic Information

What You’ll Learn

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

• 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
• Apply discrete math concepts to computer science problems

Course Structure

The course has 4 main modules:

1. Set Theory (Weeks 1-2, 6) - Sets, operations, cardinality, axioms
2. Binary Relations (Weeks 3-7) - Equivalence, order, functions, lattices
3. Boolean Algebra (Weeks 8-10) - Logic gates, circuits, minimization
4. Formal Logic (Weeks 11-16) - Propositional and predicate logic, proofs

Assessment Overview

Important: You must complete all homework and pass both 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
• Form study groups - explain concepts to each other
• Practice regularly - mathematical skill develops through repetition
• Ask questions - use office hours and Telegram

Syllabus

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

Course Modules

The course is organized into four main modules. Click each to see detailed topics:

• 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

Learning Objectives

Students will develop:

• Mathematical reasoning and proof-writing skills
• Ability to work with abstract mathematical structures
• Problem-solving techniques for discrete systems
• Foundations for advanced computer science topics

Course Policies

Attendance

• Lectures are mandatory
• Material covered in lectures is essential for success

Academic Integrity

• Homework: Discussion encouraged, but write solutions independently
• Tests & Exams: Individual work only
• Plagiarism: Results in zero score and course failure

Communication

• Telegram: Main channel for announcements
• GitHub: Course materials and issue tracker
• Office Hours: To be announced
• Email: Private matters only

Materials

Primary:

• Course lecture notes (PDF)
• Homework assignments
• Practice problems

Supplementary:

• Kenneth Rosen, Discrete Mathematics and Its Applications
• Susanna Epp, Discrete Mathematics with Applications
• Richard Hammack, Book of Proof (free online)

Important Notes

This course requires consistent effort throughout the semester. Discrete mathematics builds concepts cumulatively—missing lectures or falling behind makes catching up difficult.

Mathematical proof writing is a skill that develops over time. Expect initial difficulty, but persistence leads to mastery.

Success requires active engagement with the material, not just memorization of formulas.

Module 1: Set Theory

Duration: Weeks 1-2 + Week 6

Core Topics

Weeks 1-2: Foundations

• Set operations (∪, ∩, , ⊕, complement)
• Power sets and Boolean algebra of sets
• Venn diagrams
• Cartesian products
• Russell’s paradox
• Zermelo-Fraenkel axioms (ZFC)
• Axiom of choice

Week 6: Cardinality

• Finite vs infinite sets
• Countable and uncountable sets
• Pairing functions and encodings
• Cantor’s diagonal argument
• Cantor’s theorem: |A| < |𝒫(A)|
• Schroeder-Bernstein theorem
• Hilbert’s hotel paradox

Key Concepts

Set Operations: Union, intersection, difference, symmetric difference, complement

Power Set: 𝒫(A) = set of all subsets of A. If |A| = n, then |𝒫(A)| = 2ⁿ

Cardinality:

• Finite: |A| = n for some n ∈ ℕ
• Countable: |A| = |ℕ| (e.g., integers, rationals)
• Uncountable: |A| > |ℕ| (e.g., real numbers)

Applications

• Database theory and relational algebra
• Probability theory foundations
• Formal language theory

What You’ll Be Able To Do

• 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

Module 2: Binary Relations

Duration: Weeks 3-7

Core Topics

Properties of Relations

• Reflexive, irreflexive
• Symmetric, antisymmetric, asymmetric
• Transitive
• Composition and closures

Equivalence Relations (Weeks 3-4)

• Definition and properties
• Equivalence classes
• Partitions and quotient sets
• Fundamental theorem: equivalence ↔ partition

Order Relations (Weeks 4-5)

• Partial orders (posets)
• Linear (total) orders
• Well-orderings
• Hasse diagrams
• Maximal/minimal, greatest/least elements
• Chains and antichains
• Dilworth’s theorem

Functions (Week 5)

• Functions as special relations
• Domain, codomain, range, image, preimage
• Injective (one-to-one)
• Surjective (onto)
• Bijective (one-to-one correspondence)
• Composition and inverses
• Pigeonhole principle

Lattices (Week 7)

• Meets (∧) and joins (∨)
• Complete lattices
• Modular and distributive lattices
• Boolean algebras as lattices

Key Concepts

Equivalence Relation: Reflexive + Symmetric + Transitive

Partial Order: Reflexive + Antisymmetric + Transitive

Function: Relation where each input has exactly one output

Bijection: Function that is both injective and surjective

Applications

• Database design and normalization
• Program analysis and verification
• Scheduling problems
• Cryptography

What You’ll Be Able To Do

• Determine properties of given relations
• Find equivalence classes and quotient sets
• Draw and interpret Hasse diagrams
• Prove functions are injective/surjective/bijective
• Compose functions and find inverses
• Apply pigeonhole principle to counting problems

Module 3: Boolean Algebra

Duration: Weeks 8-10

Core Topics

Boolean Functions (Week 8)

• Truth tables
• Basic operations: AND, OR, NOT, XOR, NAND, NOR
• Boolean laws and duality
• Normal forms: DNF and CNF
• Perfect normal forms

Digital Circuits (Week 9)

• Logic gates
• Circuit design and analysis
• Multi-level circuits
• Functional completeness
• Universal gates (NAND, NOR)

Minimization (Week 10)

• Karnaugh maps (K-maps)
• Don’t care conditions
• Quine-McCluskey algorithm
• Prime implicants

Key Concepts

Boolean Function: f: {0,1}ⁿ → {0,1}

Normal Forms:

• DNF: Sum of products (OR of ANDs)
• CNF: Product of sums (AND of ORs)

Functionally Complete: A set of operations that can express any Boolean function

• Examples: {AND, OR, NOT}, {NAND}, {NOR}

K-Map: Visual method for minimizing Boolean expressions (works well for ≤4 variables)

Applications

• Digital circuit design
• Computer hardware architecture
• Compiler optimization
• SAT solvers

What You’ll Be Able To Do

• Construct truth tables for Boolean expressions
• Convert between DNF, CNF, and arbitrary forms
• Simplify expressions using Boolean laws
• Design circuits using logic gates
• Minimize functions with K-maps
• Prove functional completeness

Module 4: Formal Logic

Duration: Weeks 11-16

Core Topics

Propositional Logic (Weeks 11-12)

• Syntax: formulas, atoms, connectives
• Semantics: truth tables, models
• Tautologies, contradictions, satisfiability
• Logical equivalence and consequence
• Natural deduction proof system

Metalogic (Week 12)

• Soundness theorem
• Completeness theorem
• Compactness theorem
• Decidability

Predicate Logic (Week 13)

• Syntax: predicates, quantifiers (∀, ∃), terms
• Bound and free variables
• Interpretations and models
• Prenex normal form
• Gödel’s completeness theorem (overview)
• Gödel’s incompleteness theorems (overview)

Categorical Logic (Week 14)

• A, E, I, O statements
• Traditional square of opposition
• Categorical syllogisms
• Validity analysis
• Venn diagram methods

Key Concepts

Tautology: Formula true in all interpretations (e.g., P ∨ ¬P)

Logical Consequence: Γ ⊨ φ means φ is true in all models where all formulas in Γ are true

Soundness: If provable, then valid (⊢ implies ⊨)

Completeness: If valid, then provable (⊨ implies ⊢)

Quantifiers:

• ∀x P(x): “For all x, P(x) holds”
• ∃x P(x): “There exists x such that P(x) holds”

Applications

• Automated theorem proving
• Program verification
• Database query languages
• Knowledge representation
• Formal methods in software engineering

What You’ll Be Able To Do

• Determine if formulas are tautologies/contradictions
• Construct natural deduction proofs
• Show logical equivalence
• Translate between natural and formal languages
• Work with quantifiers
• Analyze validity of syllogisms

Course Schedule

See the detailed weekly plan and key deadlines.

Semester Overview

Assessment Timeline

Note: Homework is due the day before tests at 23:55 GMT+3.

Weekly Plan

Module 1: Set Theory

Week 1

• Introduction to sets and notation
• Set operations: ∪, ∩, , ⊕, complement
• Power sets and subsets
• Venn diagrams
• Cartesian products
• Russell’s paradox

Week 2

• Axiomatic foundations (ZFC)
• Zermelo-Fraenkel axioms overview
• Axiom of choice

Module 2: Binary Relations

Week 3

• Binary relations: definition and representations
• Graph and matrix representations
• Properties: reflexive, symmetric, transitive
• Equivalence relations and partitions
• Closures of relations

📌 Homework 1 due | Test 1

Week 4

• Order relations (partial, linear, well-orders)
• Hasse diagrams
• Chains and antichains
• Dilworth’s theorem
• Composition of relations

Week 5

• Functions as relations
• Domain, codomain, range
• Injective, surjective, bijective
• Function composition and inverses
• Pigeonhole principle

Week 6: Cardinality

• Finite vs infinite sets
• Countable and uncountable
• Cantor’s diagonal argument
• Cantor’s theorem
• Schroeder-Bernstein theorem

Week 7

• Partially ordered sets (posets)
• Lattices: meets and joins
• 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 and truth tables
• Normal forms: DNF, CNF
• Boolean laws and duality

Week 9

• Logic gates and digital circuits
• Functional completeness
• Multi-level circuits

Week 10

• Karnaugh maps
• Circuit minimization
• Quine-McCluskey algorithm

📌 Homework 3 due | Test 3

Module 4: Formal Logic

Week 11

• Propositional logic: syntax and semantics
• Tautologies, contradictions
• Logical equivalence

Week 12

• Natural deduction proof system
• Soundness and completeness
• Proof techniques

Week 13

• Predicate logic (first-order logic)
• Quantifiers: ∀ and ∃
• Interpretations and models
• Gödel’s theorems (overview)

Week 14

• Categorical logic
• A, E, I, O statements
• Square of opposition
• Syllogisms and validity

Week 15

• Review of formal logic
• Advanced topics (time permitting)

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

Week 16

• Special topics
• Ordinals and cardinals
• Metalogical concepts

Exam Period

Final Exam: All course material (Weeks 1-16)

• Written portion: problem solving
• Oral portion: concepts and explanations
• Practical portion: applications

Key Deadlines

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

Homework Deadlines

Test Schedule

Format: 90 minutes, open book, individual work

Theoretical Minimums

Format: 120 minutes, closed book, individual work

Critical: Must pass BOTH to receive course credit

Final Exam

Coverage: All modules (Weeks 1-16)

Components:

• Written (60 min): Problem solving
• Oral (30 min): Concepts and explanations
• Practical (30 min): Applications

Date: During university exam period (TBA)

Important Notes

• Homework: Submit via Dropbox link (provided in Telegram)
• Defense: All homework requires oral defense (scheduled individually)
• Make-ups: Available only for documented emergencies
• Review sessions: Scheduled before major assessments

Pro tip: Start homework immediately when assigned. Don’t wait until the deadline!

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)

• 4 assignments × 10 points = 40 points total
• ~10 problems per assignment
• Mix of basic, medium, and challenge problems
• Oral defense required

Purpose: Practice, preparation, feedback

See Homework section for details

Module Tests (20 points)

• 4 tests × 5 points = 20 points total
• 90 minutes each
• Open book
• Covers one module each

Purpose: Computational skills and problem-solving

See Tests section for details

Theoretical Minimums (20 points)

• 2 comprehensive exams × 10 points = 20 points total
• TM1: Set Theory + Relations (Week 7)
• TM2: Boolean Algebra + Logic (Week 15)
• 120 minutes each
• Closed book
• Must pass both (≥50%) to receive course credit

Purpose: Deep theoretical understanding and proof skills

See Colloquiums section for details

Final Exam (20 points)

• 1 comprehensive exam = 20 points
• Three parts: Written (12), Oral (5), Practical (3)
• Covers all modules

Purpose: Integration across all topics

See Final Exam section for 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)
• $>$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

Overview

• 4 assignments covering all modules
• 10 points each (40 total)
• ~10 problems per assignment
• Must pass all to receive course credit
• Oral defense required

Quick Facts

Deadline: Day before test, 23:55 GMT+3

Key Pages

• Submission Guidelines - Format, deadlines, where to submit
• Defense Process - What to expect, how to prepare
• Tips & FAQs - Common questions, success strategies

Problem Structure

Each assignment has ~10 problems divided by difficulty:

• Basic (3-4 problems): Practice fundamentals
• Medium (4-5 problems): Apply techniques
• Challenge (1-2 problems): Extend understanding

Why Homework Matters

1. Practice: Reinforce concepts through problem-solving
2. Preparation: Build skills for tests and exams
3. Feedback: Identify gaps early
4. Independence: Develop mathematical thinking

Minimum Passing Score

• Typically 80% (8/10 points)
• Below threshold = resubmission required
• Must achieve passing score to complete course

Homework Submission Guidelines

Format Requirements

Required on first page:

• Full name
• Group number
• ISU identifier
• Assignment number
• Submission date

How to Submit

1. Prepare solution as PDF
2. Check all requirements
3. Upload to Dropbox link (in Telegram)
4. Verify upload successful
5. Wait for confirmation

Multiple submissions allowed before deadline - only latest is graded.

⚠️ Don’t submit last minute! Network issues could cause you to miss the deadline.

Deadlines

• Day before test at 23:55 GMT+3
• Exact dates announced 2+ weeks in advance
• Defense scheduled after deadline

Late Policy

Common Mistakes to Avoid

• ❌ Non-PDF format (rejected)
• ❌ File >10 MiB (rejected)
• ❌ Missing name/ID (-1 point)
• ❌ Illegible writing (-2 points)
• ❌ Poor formatting (-1 point)
• ❌ Last-minute submission (risky!)

Homework Defense

What is Defense?

All homework must be defended orally in a 10-15 minute discussion with instructor or TA.

Purpose: Verify you understand your own solutions

When & Where

• Scheduled after submission deadline
• Sign-up sheet posted in Telegram
• During office hours or dedicated slots
• Attendance mandatory - missing = zero score

What to Expect

You may be asked to:

1. Explain your solution to a problem
2. Justify a step in your reasoning
3. Answer “what if” variations
4. Define terms you used
5. Solve a similar problem

Preparation

• Review all solutions beforehand
• Understand why each step works
• Be ready to solve similar problems
• Bring copy of submission
• Practice explaining aloud

Possible Outcomes

Tips for Success

• Take time to think before answering
• Structure your response clearly
• Use examples to illustrate concepts
• Admit uncertainty (better than wrong confident answer)
• Listen carefully to follow-up questions

Homework Tips & FAQs

Success Strategies

1. Start early (1-2 weeks before deadline)
2. Read problems carefully (understand what’s asked)
3. Try alone first (struggle builds understanding)
4. Discuss when stuck (but write independently)
5. Check your work (verify answers)
6. Write clearly (pretend teaching someone)
7. Show reasoning (partial credit requires work shown)
8. Prepare for defense (understand your solutions)

Collaboration Guidelines

✅ Allowed

• Discussing problem approaches
• Explaining concepts to peers
• Working through examples together
• Asking clarifying questions
• Study groups

❌ Not Allowed

• LLM tools (e.g., ChatGPT)
• Copying solutions from anyone
• Sharing written solutions
• Dividing problems among group
• Using prior years’ solutions
• Online homework help sites

Rule: If you can’t defend it, it’s not yours.

Resources You Can Use

• Course lecture notes
• Textbooks (Rosen, Epp, Hammack)
• Course Telegram (general questions)
• Office hours
• Study group discussions

Common Questions

Q: Can I submit handwritten solutions? A: Yes, if clearly legible and scanned at ≥300 DPI. Typed preferred.

Q: What if I’m stuck on a problem? A: Try for 30+ minutes, then ask for hints (not solutions) in office hours.

Q: Can I resubmit after deadline? A: Yes, but late penalties apply. Better to submit something on time.

Q: What counts as plagiarism? A: Copying any part of a solution from anyone/anywhere without doing it yourself.

Q: Can I use LaTeX/Typst? A: Absolutely! Digital typesetting is encouraged.

Q: What if I miss defense? A: Zero score unless you have documented emergency.

Time Management

Remember: Homework is where you learn, not just where you’re evaluated.

Module Tests

Overview

• 4 tests, one per module
• 5 points each (20 total)
• 90 minutes duration
• Open book (notes, textbooks allowed)
• Individual work only

Test Schedule

What Tests Assess

• Computational skills
• Problem-solving ability
• Concept application
• Working under time pressure
• Accuracy

Focus: Less theoretical than TMs, more practical than homework

Format

• 5-8 problems with multiple parts
• Mix: computation, short proofs, examples
• Clear point values
• ~10-15 minutes per problem

Key Pages

• Format & Topics - What to expect
• Test 1: Set Theory
• Test 2: Relations
• Test 3: Boolean Algebra
• Test 4: Logic
• Tips & FAQs

Test Format & General Topics

Format

Timing

• Duration: 90 minutes
• Location: Regular classroom
• When: During regular class time

Materials

• Allowed: Your notes, textbooks, calculator (if needed)
• Prohibited: Electronic devices, communication, collaboration

Question Structure

• 5-8 problems
• Multiple parts (a, b, c)
• Point values clearly marked
• Mix of question types

Question Types

1. Computation: Perform algorithms and calculations
2. Short proofs: Prove small claims (3-5 lines)
3. Examples/counterexamples: Construct specific instances
4. Analysis: Determine properties or relationships
5. Application: Apply techniques to concrete problems

Grading Criteria

Partial credit: Awarded generously for valid approaches and correct partial work

Policies

Before Test

• Review relevant lectures
• Complete corresponding homework
• Practice similar problems
• Prepare allowed materials
• Get good sleep

During Test

• Work individually
• Use only your materials
• Raise hand for clarifications
• Show all work
• Budget time wisely

After Test

• Graded within one week
• Feedback on common errors
• Regrade requests within one week

Make-Up Policy

Valid reasons only:

• Medical emergency (doctor’s note)
• Family emergency (documentation)
• University-sanctioned activity

Not valid:

• Oversleeping
• Travel plans
• Other coursework
• Scheduling conflicts

Procedure: Contact instructor ASAP, provide documentation

Test 1: Set Theory

Week: 3
Coverage: Weeks 1-2
Duration: 90 minutes

Topics Covered

• Set operations (∪, ∩, , ⊖, complement)
• Venn diagrams
• Power sets
• Cardinality of finite sets
• Cartesian products
• Set identities and proofs

Sample Problem Types

1. Operations: Given sets A, B, C, compute A ∪ (B \ C)
2. Venn diagrams: Draw diagram for (A ∩ B) ∪ (A ∩ C)
3. Proofs: Prove A \ (B ∪ C) = (A \ B) ∩ (A \ C)
4. Power sets: Find |𝒫(A)| for given A
5. Cartesian products: Determine A × B for specific sets

Key Skills

• Fluency with set notation
• Visual reasoning (Venn diagrams)
• Proof techniques (element method, double inclusion)
• Understanding power sets
• Cartesian product calculations

Preparation

• Review Lecture 1 notes
• Rework Homework 1 problems
• Practice textbook exercises (Rosen Ch 2.1-2.2)
• Create formula/identity reference sheet

Test 2: Binary Relations

Week: 7
Coverage: Weeks 3-7
Duration: 90 minutes

Topics Covered

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

Sample Problem Types

1. Properties: Determine which properties R satisfies
2. Equivalence classes: Find equivalence classes for given relation
3. Hasse diagrams: Draw diagram for partial order
4. Functions: Prove f is bijective
5. Composition: Compute f ∘ g
6. Cardinality: Show set is countable/uncountable

Key Skills

• Classifying relations
• Working with equivalence classes
• Drawing Hasse diagrams
• Analyzing functions
• Composing correctly
• Cardinality arguments

Preparation

• Review Lectures 2-4 notes
• Rework Homework 2 problems
• Practice Hasse diagram construction
• Review cardinality proofs

Test 3: Boolean Algebra

Week: 10
Coverage: Weeks 8-10
Duration: 90 minutes

Topics Covered

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

Sample Problem Types

1. Truth tables: Construct table for given formula
2. Normal forms: Convert expression to DNF/CNF
3. Simplification: Simplify using Boolean laws
4. Circuits: Design circuit for given function
5. K-maps: Use K-map to minimize function
6. Completeness: Prove set is functionally complete

Key Skills

• Truth table construction
• Normal form conversions
• Expression simplification
• Circuit design
• K-map technique
• Understanding completeness

Preparation

• Review Lecture 5 notes
• Rework Homework 3 problems
• Practice K-maps (2-4 variables)
• Review Boolean laws

Test 4: Formal Logic

Week: 15
Coverage: Weeks 11-15
Duration: 90 minutes

Topics Covered

• Propositional logic (syntax, semantics)
• Natural deduction proofs
• Logical equivalence/consequence
• Predicate logic basics
• Quantifiers (∀, ∃)
• Categorical logic and syllogisms

Sample Problem Types

1. Tautologies: Determine if formula is tautology/contradiction
2. Proofs: Prove formula using natural deduction
3. Equivalence: Show formulas are logically equivalent
4. Translation: Translate English to predicate logic
5. Validity: Determine validity of quantified formula
6. Syllogisms: Analyze syllogism validity

Key Skills

• Semantic analysis
• Proof construction
• Logical reasoning
• Quantifier manipulation
• Translation skills
• Syllogistic logic

Preparation

• Review Lectures 6-8 notes
• Rework Homework 4 problems
• Practice natural deduction
• Review proof techniques

Test Tips & FAQs

Time Management

1. Read all problems first (2-3 min)
2. Do easiest first (build confidence)
3. Allocate ~10-15 min per problem
4. Reserve 5-10 min for review

During the Test

• Show all work (partial credit!)
• Write clearly
• State final answers clearly
• If stuck, move on and return later
• Check your work

What to Bring

• Writing materials
• Eraser
• Notes and textbooks
• Calculator (if needed)
• Student ID

FAQs

Q: Can I use my laptop for notes?
A: No. Only physical notes allowed.

Q: What if I finish early?
A: Review your work. Most students use full 90 minutes.

Q: Can I ask questions during?
A: Only clarification questions about problem statements.

Q: Is there a practice test?
A: Sample problems provided. Review homework and textbook exercises.

Q: How much does neatness matter?
A: Must be legible. Extremely messy work may lose clarity points.

Success Strategies

• Before: Review notes, practice problems, prepare materials
• During: Stay calm, manage time, show work
• After: Learn from mistakes, prepare for next assessment

Theoretical Minimums (Colloquiums)

Overview

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

• 2 exams × 10 points = 20 total
• 120 minutes each
• Closed book
• Must pass both (≥50%) to receive course credit

Schedule

Purpose

Ensure you can:

• State definitions and theorems precisely
• Construct rigorous proofs
• Explain concepts clearly
• Make connections between topics
• Demonstrate mathematical maturity

You cannot pass this course without theoretical understanding.

Key Pages

• TM1: Set Theory & Relations
• TM2: Boolean Algebra & Logic
• Preparation Guide

Difference from Tests

Retake Policy

If you fail a TM (< 50%):

• One retake allowed
• Scheduled 1-2 weeks later
• May be more difficult or oral format
• Retake score is final

TM1: Set Theory + Binary Relations

When: Week 7 (after Test 2) Duration: 120 minutes Format: Closed book

Coverage

Set Theory (Weeks 1-2, 6)

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

Binary Relations (Weeks 3-7)

• Properties of relations
• Equivalence relations ↔ partitions
• Order relations
• Hasse diagrams
• Functions and their properties
• Composition and inverses
• Lattices and Boolean algebras

Sample Questions

Definitions

• Define equivalence relation. Give example.
• What is a well-ordering?
• Define power set. What is |𝒫(A)| if |A| = n?

Theorems

• State and prove: equivalence ↔ partition
• State Cantor’s theorem. Sketch proof.
• Prove composition of functions is associative.

Proofs

• Prove ℝ is uncountable.
• Show: if f, g bijective, then g ∘ f bijective.
• Prove every finite poset has maximal element.

Conceptual

• Explain why Russell’s paradox matters.
• Difference between maximal and greatest element?
• Example: injective but not surjective function.

Preparation

• Review all definitions (can recite precisely?)
• Know major theorem statements
• Practice proof techniques
• Create concept maps
• Form study groups
• Attend review session

TM2: Boolean Algebra + Formal Logic

When: Week 15 (after Test 4) Duration: 120 minutes Format: Closed book

Coverage

Boolean Algebra (Weeks 8-10)

• Boolean functions
• Boolean laws and duality
• Normal forms (DNF, CNF)
• Logic gates and circuits
• Functional completeness
• Karnaugh maps
• Quine-McCluskey

Formal Logic (Weeks 11-15)

• Propositional logic: syntax, semantics
• Tautologies, contradictions
• Logical equivalence/consequence
• Natural deduction
• Soundness and completeness
• Predicate logic basics
• Quantifiers
• Categorical logic

Sample Questions

Definitions

• Define tautology, contradiction, contingency.
• What is functional completeness?
• Define logical consequence.

Theorems

• State completeness theorem. What does it mean?
• Prove {NAND} is functionally complete.
• Show every Boolean function has DNF.

Proofs

• Prove (P → Q) ∧ (Q → R) ⊢ (P → R) using natural deduction.
• Show ¬(P ∨ Q) ≡ ¬P ∧ ¬Q.
• Prove tautology is valid in all interpretations.

Conceptual

• Relationship between Boolean algebra and logic?
• Difference between soundness and completeness?
• Why can’t we use truth tables for predicate logic?

Preparation

• Memorize key definitions
• Practice proof construction
• Understand theorem statements
• Review proof techniques
• Create summary sheets
• Study group discussions

TM Preparation Guide

Study Timeline

3 Weeks Before

• Review all lecture notes
• Create concept maps
• List all theorems and definitions
• Identify weak areas

2 Weeks Before

• Practice proofs daily
• Form study group
• Create flashcards
• Attend office hours

1 Week Before

• Review session
• Practice problems
• Memorize key definitions
• Sleep well

Proof Techniques

What to Memorize

Set Theory

• 9 set laws (commutative, associative, distributive, etc.)
• Power set: |𝒫(A)| = 2^|A|
• Cantor’s theorem statement
• Schroeder-Bernstein statement

Relations

• 5 relation properties
• Equivalence ↔ partition theorem
• Function composition: (g ∘ f)(x) = g(f(x))
• Poset properties

Boolean Algebra

• Boolean laws (≈18)
• DNF/CNF definitions
• Functional completeness: {AND, OR, NOT}, {NAND}, {NOR}
• Gate symbols

Logic

• Truth tables for connectives
• Natural deduction rules
• Soundness vs completeness
• Quantifier negation: ¬∀x P(x) ≡ ∃x ¬P(x)

Study Strategies

1. Active recall: Don’t just read—recite
2. Spaced repetition: Review multiple times
3. Practice proofs: Write them out completely
4. Explain to others: Best way to test understanding
5. Use whiteboards: Work through problems standing up

Resources

• Lecture slides
• Textbook chapters
• Homework solutions
• Review session notes
• Study group
• Office hours

Common Mistakes

• Circular reasoning in proofs
• Using “obvious” without justification
• Confusing necessary vs sufficient
• Mixing quantifier order
• Incomplete case analysis

Day Before

• Light review (no cramming)
• Get 8 hours sleep
• Eat well
• Review flashcards once
• Stay calm

Final Exam

Format

The final exam has 3 components:

1. Written exam (16 points)
2. Oral defense (8 points)
3. Practical problems (6 points)

Total: 30 points (30% of course grade)

Schedule

• Written: Week 16, 120 minutes
• Oral: Individual, 15-20 min each
• Practical: Take-home, submit before oral

Grading

Combined with:

• Homework (30%)
• Tests (20%)
• TMs (20%)

Final grade = Homework + Tests + TMs + Exam

See Grading Scale for conversion.

Coverage

Written Component

• All course material (weeks 1-16)
• Emphasis on modules 3-4 (Boolean Algebra, Logic)
• Theory + computation

Oral Component

• Random topic from course
• Explain concepts
• Answer follow-up questions
• Demonstrate understanding

Practical Component

• Applied problem set
• Programming or computation
• 1 week to complete
• Submit documented solution

Preparation

See detailed guides:

• Exam Structure
• Preparation Timeline

Critical Requirements

To pass course, you must:

• Pass both TMs (≥50% each)
• Complete all homework
• Earn ≥50 points overall

Exam Structure

Written Component (16 points)

Duration: 120 minutes Format: Closed book Questions: 6-8 problems

Problem Types

Coverage Distribution

• Boolean Algebra: ~40%
• Formal Logic: ~40%
• Earlier topics: ~20%

Grading Criteria

• Correctness: Is answer right?
• Completeness: All steps shown?
• Clarity: Easy to follow?
• Rigor: Justified properly?

Oral Component (8 points)

Duration: 15-20 minutes Format: One-on-one with instructor

Process

1. Draw random topic card
2. Brief prep time (2-3 min)
3. Explain concept (~5 min)
4. Answer questions (~10 min)
5. Grading discussion

Possible Topics

• Any major theorem
• Any key definition
• Proof techniques
• Connections between topics
• Applications

Evaluation

• Knowledge: Do you know the topic?
• Understanding: Can you explain clearly?
• Depth: Beyond surface level?
• Connections: See the big picture?

Practical Component (6 points)

Given: End of Week 15 Due: Before oral exam Format: Individual work

Typical Problems

• Implement Boolean minimization
• Build truth table solver
• Design logic circuit
• Solve graph problem
• Compute cardinalities

Requirements

• Working solution
• Clear documentation
• Explanation of approach
• Code (if applicable)
• Test cases

Evaluation

• Correctness: Does it work?
• Efficiency: Reasonable approach?
• Documentation: Clear explanation?
• Completeness: All parts addressed?

Exam Preparation

Timeline

Week 14-15

• Review all materials
• Create comprehensive notes
• Practice problems from all modules
• Form study groups

Week 15

• Practical component released
• Start working immediately
• Budget 10-15 hours
• Ask questions early

Week 16 (Exam Week)

• Written exam: Closed-book review
• Practical due: Final testing/documentation
• Oral exam: Review random topics

Written Prep

Study Strategy

1. Review lecture slides (all 16 weeks)
2. Redo homework problems without solutions
3. Practice test problems under time pressure
4. Memorize key theorems and proofs
5. Create formula sheet (then DON’T bring it—memory aid only)

Focus Areas

Practice Plan

• Week 14: Review modules 1-2
• Week 15: Review modules 3-4
• Week 16: Mixed practice, timing

Oral Prep

Possible Topics

You might be asked about any major concept. Common ones:

• Equivalence relations ↔ partitions
• Cantor’s theorem
• Functional completeness
• Soundness vs completeness
• Boolean duality
• Natural deduction rules

Preparation

• Explain aloud: Practice with study partner
• Anticipate questions: “Why?”, “Example?”, “Proof?”
• Know connections: How topics relate
• Have examples ready: Concrete instances

During Oral

• Take a breath before starting
• Organize thoughts (30 sec OK)
• Start with definition
• Give example
• Explain significance
• Be honest if unsure

Practical Prep

Getting Started

1. Read problem carefully
2. Plan approach before coding
3. Test with simple cases
4. Document as you go
5. Leave time for writeup

Common Pitfalls

• Starting too late
• No test cases
• Poor documentation
• Overcomplicated solution
• Not asking for clarification

Submission Checklist

• Code runs without errors
• Test cases included
• README with explanation
• Approach documented
• Edge cases handled
• Time complexity noted

Study Resources

Official

• All lecture slides
• Homework with solutions
• Test problems
• TM questions
• Textbook chapters

Additional

• Office hours (increased before exam)
• Review sessions
• Study groups
• Telegram channel

Week Before Tips

1. Sleep: 8 hours nightly
2. Exercise: Reduces stress
3. Eat well: Brain needs fuel
4. No cramming: Spaced review better
5. Stay calm: You’ve prepared all semester

Day Of

Written Exam

• Arrive early
• Bring writing materials
• Read all problems first
• Manage time (15 min/problem)
• Show all work

Oral Exam

• Review notes once lightly
• Stay relaxed
• Listen carefully to question
• Think before speaking
• Ask for clarification if needed

After Exam

Grades posted within 1 week. If you have concerns:

1. Review grading rubric
2. Check your work
3. Attend office hours
4. Discuss specific points

Course Materials

Required Textbook

Discrete Mathematics and Its Applications by Kenneth Rosen

Covers all course topics with extensive examples and exercises.

Lecture Materials

All slides available as PDFs:

• Lecture: Set Theory
• Lecture: Binary Relations
• Lecture: Boolean Algebra
• Lecture: Formal Logic
• Lecture: Flow Networks
• Lecture: Automata Theory
• Lecture: Combinatorics

Cheatsheets

Cheatsheets are available for quick reference:

• Set Theory Cheatsheet
• Relations Cheatsheet
• Boolean Algebra Cheatsheet
• Formal Logic Cheatsheet
• Graph Theory Cheatsheet
• Automata Theory Cheatsheet
• Combinatorics Cheatsheet

Online Resources

Recommended

• MIT OpenCourseWare: Mathematics for CS
• Stanford CS103: Mathematical Foundations

Tools

• Typst: For writing mathematical documents (recommended for homework)
• LaTeX: Alternative for mathematical typesetting
• Wolfram Alpha: Checking computations

Getting Help

Office Hours

When: See schedule Where: Room TBD / Online (link in Telegram) How: Drop-in (no appointment needed)

Best for:

• Homework questions
• Concept clarification
• Exam preparation
• General advice

Tip: Come with specific questions prepared.

Telegram Channel

Link: Provided in class

• Announcements
• Quick questions
• Peer discussion
• Study groups forming

Rules:

• Keep discussions respectful
• No homework solutions
• Search before asking
• Help fellow students

Study Groups

Finding a Group

• Ask in Telegram
• Form with classmates
• Post in course channel
• Office hours meetups

Effective Group Study

• Meet regularly (weekly)
• Rotate leader
• Work problems together
• Explain to each other
• Review before exams

Remember: Collaboration ≠ copying. See Academic Integrity.

Teaching Assistants

TAs hold additional help sessions:

• Review sessions before tests/TMs
• Homework help hours
• Proof writing workshops

Check Telegram for schedule.

Writing Center

For help with:

• Proof writing
• Mathematical exposition
• Homework presentation

Location: Library, 2nd floor Hours: M-F, 10am-4pm

Accessibility Services

If you need accommodations:

1. Register with Accessibility Office
2. Obtain documentation
3. Email instructor ASAP
4. Arrange specific accommodations

Common accommodations:

• Extended test time
• Separate testing room
• Note-taking assistance
• Format alternatives

Tutoring

Free Tutoring

• Mathematics Help Room (Main Building, Room 101)
• Peer tutoring program
• TA help sessions

Private Tutoring

• Student tutoring board
• Professional tutors
• Online platforms

How to Ask for Help

Effective Questions

✅ Good: “I don’t understand why the proof of Cantor’s theorem uses contradiction. Could you explain the key idea?”

❌ Bad: “I don’t get Cantor’s theorem.”

Include

• What you’ve tried
• Specific confusion point
• Relevant context
• Your current understanding

Homework Questions

• Allowed: Clarify problem statement, discuss approach
• Not allowed: Ask for complete solution, share answers

Emergency Situations

Medical/Personal Crisis

Contact:

1. Student Services
2. Course instructor (email)
3. Request incomplete grade if needed

Academic Difficulties

If struggling:

1. Attend office hours ASAP
2. Form study group
3. Use tutoring resources
4. Consider reduced course load

Don’t wait until it’s too late!

Feedback

Help improve the course:

• Mid-semester survey
• End-of-semester evaluation
• Direct feedback to instructor
• Anonymous suggestion box

Your input matters!