Sessions 1–8 · DMIA Chapter 1 — from truth tables to formal proof strategy.

1. S1Introduction to the course · Fundamentals of propositional logiclive

   Course overview and the building blocks of logic: propositions, logical connectives and their applications to computer science.

   • Proposition — a declarative sentence that is either true or false but not both; the atom from which all formulas are built.
   • Connectives — negation $\neg p$, conjunction $p\land q$, disjunction $p\lor q$, conditional $p\rightarrow q$ and biconditional $p\leftrightarrow q$, each defined by its truth table.
   • Truth tables & CS applications — bit operations, system specifications and Boolean search all reduce to evaluating these connectives.

   Key ideaThe conditional $p\rightarrow q$ is false only when $p$ is true and $q$ is false — so "if false then anything" is vacuously true, a fact that trips up most beginners.

   DMIA Ch. 1, pp. 1–25. Rosen §1.1 (propositional logic) and §1.2 (applications) — definitions of the connectives and worked specification/translation examples.

   DMIA Ch.1 · pp.1–25demo: truth tables
2. S2Propositional logic (cont.) · Propositional equivalenceslive

   Continue propositional logic and study logical equivalences used to simplify and verify formulas.

   • Tautology / contradiction / contingency — formulas that are always true, always false, or neither.
   • Logical equivalence $p\equiv q$ — two formulas with identical truth tables, i.e. $p\leftrightarrow q$ is a tautology.
   • Key laws — De Morgan $\neg(p\land q)\equiv\neg p\lor\neg q$, distributive, and $p\rightarrow q\equiv\neg p\lor q$; used to simplify and to prove equivalences.

   Worked ideaTo show $p\rightarrow q \equiv \neg q \rightarrow \neg p$ (contrapositive), rewrite both as $\neg p\lor q$ via the conditional law — they collapse to the same disjunction.

   DMIA Ch. 1, pp. 25–36. Rosen §1.3 — the table of logical equivalences and how to use them to verify formulas without full truth tables.

   DMIA Ch.1 · pp.25–36demo: truth tables
3. S3Predicate logic: predicates and quantifierslive

   Move beyond propositions to predicates parameterized by variables, with universal and existential quantifiers.

   • Predicate $P(x)$ — a statement whose truth depends on a variable from a domain; becomes a proposition once $x$ is fixed.
   • Universal $\forall x\,P(x)$ — true when $P$ holds for every element of the domain.
   • Existential $\exists x\,P(x)$ — true when $P$ holds for at least one element.

   Key ideaNegation flips the quantifier: $\neg\forall x\,P(x)\equiv\exists x\,\neg P(x)$ — "not everything works" means "something fails".

   DMIA Ch. 1, pp. 40–57. Rosen §1.4 — predicates, the domain of discourse, and quantifier semantics.

   DMIA Ch.1 · pp.40–57demo: quantifiers
4. S4Predicates & quantifiers · Nested quantifierslive

   Deepen quantifier reasoning and study the order and scoping of nested quantifiers.

   • Nested quantifiers — formulas such as $\forall x\,\exists y\,P(x,y)$, where one quantifier lies in the scope of another.
   • Order matters — $\forall x\,\exists y$ and $\exists y\,\forall x$ generally differ in meaning (the second is stronger).
   • Translation — rendering English statements about "every/some" relationships into nested-quantifier form.

   Key idea$\forall x\,\exists y\,(x+y=0)$ is true over $\mathbb{Z}$ (each $x$ has its own $y=-x$), but $\exists y\,\forall x\,(x+y=0)$ is false (no single $y$ works for all $x$).

   DMIA Ch. 1, pp. 51–57 & 60–72. Rosen §1.4 (continued) and §1.5 — quantifier scope, binding and nested-quantifier translation.

   DMIA Ch.1 · pp.51–72demo: quantifiers
5. S5Lab session — DNF, Karnaugh maps & circuitslab

   Hands-on: derive propositions from truth tables, minimize them, and build the corresponding logic circuit.

   • Disjunctive normal form (DNF) — read a formula straight off a truth table as an OR of AND-terms, one per true row.
   • Karnaugh maps — a grid layout that groups adjacent minterms to find the minimal equivalent expression by eye.
   • Circuit synthesis — realise the minimised formula as AND/OR/NOT gates in Logisim (open-source).

   Why it mattersMinimisation is the bridge from logic to hardware: fewer gates means cheaper, faster circuits — the same algebra that simplifies a proof also shrinks a chip.

   lab · Logisimdemo: truth tables
6. S6Introduction to proofslive

   Formal arguments and the first proof techniques.

   • Direct proof — assume the hypothesis $p$ and derive $q$ through a chain of valid inferences.
   • Proof by contraposition — prove $\neg q\rightarrow\neg p$ instead of $p\rightarrow q$ (logically equivalent).
   • Proof by contradiction — assume $\neg p$ and derive an impossibility, forcing $p$ to be true.

   Worked idea"If $n^2$ is even then $n$ is even" is awkward directly but easy by contraposition: if $n$ is odd, $n=2k+1$, so $n^2=2(2k^2+2k)+1$ is odd.

   DMIA Ch. 1, pp. 80–92. Rosen §1.7 — terminology (theorem, lemma, axiom) and the core direct/indirect proof techniques.

   DMIA Ch.1 · pp.80–92
7. S7Proof methods and strategylive

   A toolkit of proof strategies and how to choose among them.

   • Proof by cases — partition the hypothesis into exhaustive scenarios and prove each.
   • Existence proofs — constructive (exhibit a witness) vs. non-constructive (prove one must exist).
   • Counterexamples — a single instance disproves a universally quantified claim.

   Key ideaChoosing a strategy is itself a skill: try a direct proof first, switch to contraposition/contradiction when the hypothesis is hard to use, and reach for a counterexample when a claim "feels" false.

   DMIA Ch. 1, pp. 96–110. Rosen §1.8 — proof methods, strategy, and the role of conjecture and counterexample.

   DMIA Ch.1 · pp.96–110
8. S8Proof methods and strategy (cont.)live

   Continued practice with proof strategies and worked examples.

   • Extended worked proofs combining several strategies in one argument.
   • Common pitfalls: circular reasoning, affirming the consequent, and unjustified "obvious" steps.
   • Writing proofs clearly enough that another reader can verify every step.

   Practice focusA proof is a piece of communication: the goal is not just to be right but to make the reader certain you are right.

   DMIA Ch. 1, pp. 96–110 (continued). Rosen §1.8 — additional examples and exercises consolidating proof strategy.

   DMIA Ch.1 · pp.96–110

Sessions 9–15 · DMIA Chapter 2 — sets, functions, and the midterm.

1. S9Sets: theory and operationslive

   Sets, subsets, the power set, and the algebra of set operations.

   • Set & subset — an unordered collection of distinct elements; $A\subseteq B$ when every element of $A$ is in $B$.
   • Operations — union $A\cup B$, intersection $A\cap B$, difference $A\setminus B$, complement $\bar A$, defined via set-builder notation $\{x \mid P(x)\}$.
   • Power set — $\mathcal{P}(A)$, the set of all subsets; $|\mathcal{P}(A)| = 2^{|A|}$.

   Key ideaSet operations mirror the logical connectives: union ↔ OR, intersection ↔ AND, complement ↔ NOT — so the laws of logic carry over directly to sets.

   DMIA Ch. 2, pp. 115–138. Rosen §2.1–§2.2 — sets, subsets, set operations and identities.

   DMIA Ch.2 · pp.115–138demo: set algebra (Venn)
2. S10Sets: theory and operations (cont.)live

   Continued set operations, identities and cardinality.

   • Set identities — De Morgan $\overline{A\cup B}=\bar A\cap\bar B$, distributive and absorption laws, proved via membership tables or double-inclusion.
   • Cartesian product — $A\times B=\{(a,b)\mid a\in A, b\in B\}$, the basis of relations and coordinates.
   • Cardinality — the size $|A|$ of a set, and the inclusion–exclusion count $|A\cup B|=|A|+|B|-|A\cap B|$.

   Worked ideaTo prove $A\subseteq B \iff A\cap B = A$: if $A\subseteq B$ every $x\in A$ is also in $B$, so $A\cap B$ collects exactly the elements of $A$ — and conversely.

   DMIA Ch. 2, pp. 115–138 (continued). Rosen §2.2 — set identities, Cartesian products and cardinality.

   DMIA Ch.2 · pp.115–138demo: set algebra (Venn)
3. S11Introduction to functions · Types of functionlive

   Functions as a special kind of relation; domain, codomain and range.

   • Function $f:A\to B$ — assigns to every $a\in A$ exactly one $f(a)\in B$; $A$ is the domain, $B$ the codomain, $f(A)$ the range.
   • Injective (one-to-one) — $f(a_1)=f(a_2)\Rightarrow a_1=a_2$; no two inputs collide.
   • Surjective (onto) — every $b\in B$ is hit; bijective — both at once.

   Key ideaA function is just a relation in which each input has exactly one output — bijections are precisely the functions that can be reversed.

   DMIA Ch. 2, pp. 138–156. Rosen §2.3 — functions, one-to-one/onto, graphs and floor/ceiling functions.

   DMIA Ch.2 · pp.138–156demo: functions
4. S12Types of functions (cont.)live

   Composition, inverses, and the classification of functions.

   • Composition $(g\circ f)(x)=g(f(x))$ — chaining functions; associative but not commutative.
   • Inverse $f^{-1}$ — exists exactly when $f$ is a bijection, and satisfies $f^{-1}\circ f=\mathrm{id}$.
   • Identifying which standard functions are injective/surjective and why.

   Worked idea$f(x)=2x+3$ on $\mathbb{R}$ is a bijection, so it inverts: solve $y=2x+3$ for $x$ to get $f^{-1}(y)=(y-3)/2$.

   DMIA Ch. 2, pp. 138–156 (continued). Rosen §2.3 — inverse and composite functions.

   DMIA Ch.2 · pp.138–156demo: functions
5. S13Practice exercises for functionslive

   Consolidation through problem-solving on functions.

   • Determine injectivity/surjectivity/bijectivity for given functions with justification.
   • Build composites and inverses; reason about domains and ranges.
   • Mixed problems linking functions back to sets and logic.

   Practice focusProving a function is not injective needs only one colliding pair; proving it is requires a general argument — know which side of the claim you are on.

   DMIA Ch. 2, pp. 138–156. Rosen §2.3 exercises (see Bibliography) — the problem set underpinning this session.

   DMIA Ch.2 · pp.138–156demo: functions
6. S14Review for the midterm examlive

   Consolidation and Q&A across Modules 1 & 2.

   • Recap of propositional/predicate logic, equivalences and quantifiers.
   • Recap of proof strategies, set algebra and function classification.
   • Worked exam-style questions and clarification of common errors.

   Exam noteThe midterm date is tentative and confirmed at least two weeks ahead — use this session to surface gaps before it counts.

   review
7. S15Midterm examexam

   In-class assessment covering the first two modules.

   • Scope: Modules 1 & 2 — logic, proofs, sets, functions.
   • Contributes to the intermediate tests component (30% of the course grade).

   AssessmentPart of continuous evaluation; in the June/July re-sit, continuous marks are discarded in favour of a single comprehensive exam.

   midterm · part of intermediate tests (30%)

Sessions 16–20 · relations, graphs & sequences — properties, closures, graph paths, a Prolog lab.

1. S16Introduction to relationslive

   Relations as subsets of a Cartesian product, and how to represent them.

   • Binary relation — a subset $R\subseteq A\times B$; we write $a\,R\,b$ when $(a,b)\in R$.
   • Relations vs. functions — every function is a relation, but a relation may pair an element with zero, one or many partners.
   • Representations — sets of ordered pairs, a Boolean adjacency matrix, or a directed graph (digraph).

   Key ideaThe same relation has three faces — pairs, matrix, digraph — and each makes different properties obvious; switching view is a core skill.

   DMIA Ch. 9 (Relations). Rosen §9.1 & §9.3 — relations on a set and their matrix/digraph representations.

   relationsdemo: relations
2. S17Properties & closures of relationslive

   The defining properties of relations and how to close a relation under them.

   • Properties — reflexive ($a\,R\,a$ for all $a$), antireflexive, symmetric ($a\,R\,b\Rightarrow b\,R\,a$), antisymmetric, and transitive ($a\,R\,b\land b\,R\,c\Rightarrow a\,R\,c$).
   • Special relations — equivalence relations (reflexive + symmetric + transitive) partition a set; partial orders (reflexive + antisymmetric + transitive) rank it.
   • Closures — the smallest extension of $R$ that is reflexive, symmetric or transitive (transitive closure via Warshall's algorithm).

   Key ideaAn equivalence relation and a partition of a set are two descriptions of the same thing — the classes are the partition.

   DMIA Ch. 9 (Relations). Rosen §9.1, §9.4 (closures) and §9.5 (equivalence relations) — properties and the transitive closure.

   relations · closuresdemo: relations & closures
3. S18Graphs · paths · Euler & Hamiltonlive

   Graphs as a model for relations, with classic path problems.

   • Graph types — directed/undirected, simple vs. multigraph, weighted; stored as adjacency lists or matrices.
   • Euler path — uses every edge exactly once; exists iff the graph is connected with 0 or 2 odd-degree vertices.
   • Hamilton path — visits every vertex exactly once; no simple efficient test is known (NP-hard).

   Worked ideaEuler's "Seven Bridges of Königsberg": four landmasses each touched by an odd number of bridges means more than two odd vertices — so no Euler walk exists.

   DMIA Ch. 10 (Graphs). Rosen §10.1–§10.5 — graph models, representation, connectivity and Euler/Hamilton paths.

   graphsdemo: Euler & Hamilton
4. S19Lab session — relations in Prologlab

   Express relations declaratively and query them.

   • Facts & rules — encode a family tree as base facts (parent/2) and derived rules (grandparent, sibling).
   • Queries — let Prolog's unification and backtracking search for all solutions.
   • Build up from simple to multi-step relational queries.

   Why it mattersProlog turns the theory of relations into a programming paradigm: you state what is true and the engine works out how to answer.

   lab · Prologdemo: relations
5. S20Sequences and sumslive

   Bridge into arithmetic: sequences, series and summation notation.

   • Sequence — a function from $\mathbb{N}$ to a set; arithmetic and geometric progressions and recurrences.
   • Summation notation — $\sum_{i=1}^{n} a_i$, with closed forms such as $\sum_{i=1}^{n} i = \tfrac{n(n+1)}{2}$.
   • Geometric series $\sum_{i=0}^{n} ar^i = a\tfrac{r^{n+1}-1}{r-1}$ and their use in complexity analysis.

   Key ideaClosed-form sums turn a loop's running time into a single formula — the same series that count steps also describe algorithm cost.

   DMIA Ch. 2, pp. 156–170. Rosen §2.4 — sequences, recurrences and summations.

   DMIA Ch.2 · pp.156–170

Sessions 21–24 · DMIA Chapter 4 — number theory, integer representation, applications, Python lab.

1. S21Divisibility and modular arithmeticlive

   The arithmetic of remainders and congruences.

   • Divisibility — $a \mid b$ means $b=ak$ for some integer $k$; primes, gcd and the Euclidean algorithm.
   • Division algorithm — for $a$ and $d>0$ there are unique $q,r$ with $a=dq+r$, $0\le r
   • Congruence — $a\equiv b \pmod{n}$ iff $n\mid(a-b)$; arithmetic carries through addition and multiplication.

   Key ideaWorking "mod $n$" replaces infinitely many integers with the $n$ remainders $\{0,\dots,n-1\}$ — clocks, hash buckets and cyclic structures all live here.

   DMIA Ch. 4, pp. 251–259. Rosen §4.1 — divisibility, the division algorithm and modular arithmetic.

   DMIA Ch.4 · pp.251–259demo: modular arithmetic
2. S22Integer representation & operationslive

   How integers are encoded in different bases and how arithmetic operates on them.

   • Base-$b$ expansion — every integer is uniquely $\sum d_i b^i$ with $0\le d_i
   • Conversion — repeated division by $b$ extracts digits; grouping bits converts binary↔hex quickly.
   • Base arithmetic — addition and multiplication algorithms operating directly on the representation.

   Worked idea$(1011)_2 = 1\cdot8+0\cdot4+1\cdot2+1 = 11$; grouped into a nibble it is simply $(\text{B})_{16}$ — why hex is the natural shorthand for bytes.

   DMIA Ch. 4, pp. 260–265. Rosen §4.2 — integer representations and algorithms for base conversion and arithmetic.

   DMIA Ch.4 · pp.260–265demo: integer representation
3. S23Applications of number theorylive

   Where modular arithmetic powers real systems.

   • Hash maps — $h(k)=k \bmod m$ spreads keys across buckets for $O(1)$ average lookup.
   • Cryptographic hashes & proof of work — one-way functions whose outputs are infeasible to invert or pre-image.
   • Cryptography — modular exponentiation and the difficulty of related problems secure public-key schemes.

   Why it mattersThe same congruences from S21 secure web traffic and underpin blockchains — number theory is far from "pure" abstraction.

   DMIA Ch. 4. Rosen §4.5–§4.6 — applications of congruences and an introduction to cryptography.

   number theory · cryptodemo: modular & gcd
4. S24Lab session — arithmetic algorithms in Pythonlab

   Implement core arithmetic from scratch.

   • gcd via the Euclidean algorithm and its extended form.
   • Modular exponentiation by fast (binary) exponentiation.
   • Base conversion between binary, decimal and hexadecimal.

   Why it mattersImplementing these by hand reveals why the textbook algorithms are efficient — e.g. fast exponentiation does $O(\log n)$ multiplications, not $n$.

   lab · Pythondemo: integer representation

Sessions 25–30 · DMIA Chapter 13 — languages, grammars, finite-state machines, and finals.

1. S25Languages and grammarslive

   Formal languages and the grammars that generate them.

   • Alphabet, string, language — a language is a (possibly infinite) set of strings over a finite alphabet $\Sigma$.
   • Phrase-structure grammar — terminals, non-terminals and production rules that derive strings from a start symbol.
   • Chomsky hierarchy — regular ⊂ context-free ⊂ context-sensitive ⊂ unrestricted grammars.

   Key ideaA grammar is a finite recipe for a potentially infinite language — exactly what a programming-language specification needs to be.

   DMIA Ch. 13, pp. 885–898. Rosen §13.1 — languages, grammars and the Chomsky classification.

   DMIA Ch.13 · pp.885–898demo: finite-state machine
2. S26Finite-state machines with outputlive

   Automata that produce output as they read input.

   • FSM with output — states, input/output alphabets and a transition function emitting symbols.
   • Mealy vs. Moore — output attached to transitions (Mealy) or to states (Moore).
   • Practice exercises designing small output machines (e.g. a binary adder, a vending controller).

   Worked ideaA Mealy machine for a serial binary adder needs just two states — "no carry" and "carry" — outputting each sum bit as it reads paired input bits.

   DMIA Ch. 13, pp. 899–903. Rosen §13.2 — finite-state machines with output (Mealy/Moore models).

   DMIA Ch.13 · pp.899–903demo: finite-state machine
3. S27Finite-state machines with no outputlive

   Language recognition: deterministic and nondeterministic acceptors.

   • Acceptor (DFA) — states with accepting/non-accepting status; a string is accepted if it ends in an accepting state.
   • NFA — nondeterministic acceptors, equivalent in power to DFAs (subset construction).
   • Regular languages — exactly those recognised by finite automata; practice exercises on language recognition.

   Key ideaFinite memory = finite states: an FSM can recognise "even number of 1s" but cannot count unbounded nesting — which is why it cannot match balanced parentheses.

   DMIA Ch. 13, pp. 903–913. Rosen §13.3–§13.4 — finite-state machines without output and language recognition.

   DMIA Ch.13 · pp.903–913demo: finite-state machine
4. S28Final project presentationspresentation

   Students present their final projects.

   • 15-minute slots: 10 minutes of presentation plus 5 minutes of questions from the professor.
   • Assesses the group presentation component (10% of the course grade).

   AssessmentApplies the semester's concepts to a chosen problem — the capstone of the active, applied methodology.

   group presentation (10%)
5. S29Review for the final examlive

   Comprehensive review across all five modules.

   • Synthesis of logic & proofs, sets & functions, relations & graphs, arithmetic, and computation models.
   • Worked exam-style problems and targeted clarification of weak spots.

   Exam noteThe final-exam date is fixed and cannot be rescheduled — unlike the tentative midterm.

   review
6. S30Final examexam

   Comprehensive in-class final assessment.

   • Covers the full program across all five modules.
   • Worth 40% of the grade; a minimum of 3.5/10 here is required to pass, regardless of the weighted average.

   AssessmentThis is the hard gate of the course — see the Pass & re-sit rules above for thresholds and the June/July re-sit policy.

   final exam (40%)