Discrete Structure (CS-302) Unit 3 Notes

How unit 3 is examined

Logic, inference, normal forms, quantifiers and finite state machines; the marks sit in tautologies, logical implications (arguments), normal forms, quantifiers and FSM as language recognizers.

Proposition

<span style="display:inline-block;padding:.16em .6em;border:1.5px solid currentColor;border-radius:999px;font-size:.68em;font-weight:700;letter-spacing:.06em;text-transform:uppercase;opacity:.75">Not asked since 2022</span>

Definition. A proposition is a declarative sentence that is either true or false, but not both.

Key points.

"5 is prime" is a proposition; questions, commands and "x + 1 = 3" are not.
Simple statements are joined by connectives into compound propositions.

<mark>A proposition is a declarative statement that is either true or false, not both.</mark>

First order logic

Definition. First order (predicate) logic extends propositional logic with predicates, variables and the quantifiers $\forall$ and $\exists$.

Key points.

It can express statements about objects, such as "every student is enrolled", which propositional logic cannot.
Its ingredients are constants, variables, predicates $P(x)$, connectives and quantifiers.

<mark>First order logic is propositional logic plus predicates and quantifiers over a domain.</mark>

Basic logical operation

Definition. The basic operations are negation $\sim p$, conjunction $p\land q$, disjunction $p\lor q$, conditional $p\to q$ and biconditional $p\leftrightarrow q$.

Key points.

$p\to q$ is false only when $p$ is T and $q$ is F; $p\leftrightarrow q$ is true when both have the same value.
De Morgan: $\sim(p\land q)\equiv\sim p\lor\sim q$ and $\sim(p\lor q)\equiv\sim p\land\sim q$.
Negation of a conditional: $\sim(p\to q)\equiv p\land\sim q$.

<mark>$\sim(p\to q)\equiv p\land\sim q$ and De Morgan flips $\land$ and $\lor$.</mark>

Asked: [7 marks] (Dec 2023) Write the negation of: (i) If the determinant of a system of linear equations is zero then either the system has no solution or has an indefinite number of solutions. (ii) Either today is not a Sunday or today is not a Wednesday.

Example. (i) Let $d$ = determinant is zero, $a$ = no solution, $b$ = infinitely many. $d\to(a\lor b)$ negates to $d\land\sim a\land\sim b$: the determinant is zero, and the system has a solution and does not have infinitely many solutions. (ii) $\sim p\lor\sim q$ negates to $p\land q$: today is Sunday and today is Wednesday.

Truth tables

Definition. A truth table lists the truth value of a compound proposition for every assignment of T/F to its variables; $n$ variables need $2^n$ rows.

Key points.

List all rows systematically (TT, TF, FT, FF for two variables; eight rows for three).
Add one column per sub-formula, working from the innermost brackets outwards.
$p\to q$ is F only for $p=T, q=F$; $p\leftrightarrow q$ is T when values agree.
The last column decides: all T is a tautology, all F a contradiction, mixed a contingency.
Two formulas are equivalent if their columns are identical.

Example (order TTT, TTF, TFT, TFF, FTT, FTF, FFT, FFF). Dec 2023 (i) $\sim(p\lor(q\lor r))\Leftrightarrow((p\lor q)\land(p\lor r))$: left side $\sim(p\lor q\lor r)$ = 0,0,0,0,0,0,0,1; right side $(p\lor q)\land(p\lor r)$ = 1,1,1,1,1,0,0,0; biconditional 0,0,0,0,0,1,1,0 (T only for FTF and FFT), hence a contingency. (ii) $(\sim q\Rightarrow\sim p)\Rightarrow(p\Rightarrow q)$: final column all T, a tautology (contrapositive equivalence). Jun 2025 $(p\to q)\to r$: $p\to q$ = 1,1,0,0,1,1,1,1; final column 1,0,1,1,1,0,1,0, mixed, so neither tautology nor contradiction (contingency).

<mark>$n$ variables give $2^n$ rows, and the final column classifies the formula.</mark>

Answer frame. Open with the definition and the row count $2^n$; draw the full table with a column per sub-formula; then state the final column and its class; close with "hence the formula is a tautology/contingency".

Asked: [7 marks] (Dec 2023) Construct the truth table of (i) $\sim(p\lor(q\lor r))\Leftrightarrow((p\lor q)\land(p\lor r))$ (ii) $(\sim q\Rightarrow\sim p)\Rightarrow(p\Rightarrow q)$. Asked: [7 marks] (Jun 2025) With $p$: raining, $q$: carrying umbrella, $r$: stay dry, construct the truth table of $(p\to q)\to r$ and decide whether it is a tautology or contradiction.

Tautologies

Definition. A tautology is a compound proposition that is true for every truth assignment; a contradiction is always false; a contingency is neither.

Key points.

Truth-table method: list all $2^n$ rows and show the final column is all T.
Algebra method: replace $A\to B$ by $\sim A\lor B$, then simplify with De Morgan, distributive and complement laws to T.
Example tautology $p\lor\sim p$, contradiction $p\land\sim p$, contingency $p\to q$.
If $A$ is a tautology then $\sim A$ is a contradiction; $A\leftrightarrow B$ is a tautology exactly when $A\equiv B$.
Famous ones: modus ponens $(p\land(p\to q))\to q$ and Peirce's law $((p\to q)\to p)\to p$.

Example 1 (Nov 2018 (i)). Rows TT, TF, FT, FF: $p\to q$ = T,F,T,T; $p\land(p\to q)$ = T,F,F,F; the conditional with $q$ = T,T,T,T, so it is a tautology. (ii) $p\to q$ and $\sim p\lor q$ have the same column T,F,T,T, so the biconditional is T in all four rows.

Example 2 (May 2019). $(p\lor\sim q)\land(\sim p\lor\sim q)\equiv\sim q\lor(p\land\sim p)\equiv\sim q$, then $\sim q\lor q\equiv T$. Table check: final column T,T,T,T.

Example 3 (Nov 2022). $A=P\to(Q\to R)\equiv\sim P\lor\sim Q\lor R$. $B=(P\to Q)\to(P\to R)\equiv(P\land\sim Q)\lor\sim P\lor R\equiv\sim P\lor\sim Q\lor R$ (since $(P\land\sim Q)\lor\sim P\equiv\sim P\lor\sim Q$). So $A\to B\equiv\sim A\lor A\equiv T$.

Example 4 (Jun 2020). $p\Rightarrow q$: F at $p=T,q=F$, not a tautology. $(p\Rightarrow q)\Rightarrow p$: F at $p=F,q=F$, not a tautology. $((p\Rightarrow q)\Rightarrow p)\Rightarrow p$: T,T,T,T, a tautology (Peirce's law).

<mark>A tautology is a compound proposition that is true for every assignment of truth values to its variables.</mark>

Answer frame. Open with the definition; draw the truth table with columns for each sub-formula (or state the algebra chain, one law per line); develop points 1-2 first, then the worked case; close with "the final column is all T, hence a tautology".

Pitfall: For "prove by laws" write the law used at each line; a table is accepted only if every row is shown.

Asked: [14 marks] (Jun 2020) Which of $p\Rightarrow q$, $(p\Rightarrow q)\Rightarrow p$, $((p\Rightarrow q)\Rightarrow p)\Rightarrow p$ are tautologies? Explain tautology and justify with truth tables. (OR part is a recurrence, Unit 5: roots 2, 5 give $a_r=2\cdot5^r-2\cdot2^r$.) Asked: [7 marks] (Nov 2018) Show that $(p\land(p\to q))\to q$ and $(p\to q)\leftrightarrow(\neg p\lor q)$ are tautologies. Asked: [7 marks] (May 2019, Jun 2020) Prove $(p\lor\sim q)\land(\sim p\lor\sim q)\lor q$ is a tautology. Asked: [7 marks] (Nov 2022) Prove $(P\to(Q\to R))\to((P\to Q)\to(P\to R))$ is a tautology by laws of logic. Asked: [7 marks] (Jun 2023) Show that $((p\lor q)\land\neg p)\to q$ is a tautology. Asked: [7 marks] (Jun 2024) (i) Prove $p\land q\Rightarrow q\lor p$ is a tautology. (ii) Show $(p\lor q)\land\sim p\land\sim q$ is a contradiction. Answer: (i) $\sim(p\land q)\lor(q\lor p)\equiv(\sim p\lor\sim q)\lor(p\lor q)\equiv T$. (ii) $\equiv(p\lor q)\land\sim(p\lor q)\equiv F$. Asked: [7 marks] (Dec 2025) Construct the truth table of $(p\to q)\leftrightarrow(\neg p\lor q)$ and show it is a tautology. Asked: [7 marks] (Nov 2022) Explain tautologies, contradiction and contingencies with suitable examples.

Contradictions

Definition. A contradiction is a compound proposition that is false for every truth assignment.

Key points.

Standard examples are $p\land\sim p$ and $(p\lor q)\land\sim(p\lor q)$.
The negation of a tautology is a contradiction and vice versa.
To prove one, build the truth table (all F) or simplify to F using the complement law.

<mark>A contradiction is a compound proposition that is false for every assignment.</mark>

Algebra of Proposition

Definition. The algebra of propositions is the set of equivalence laws used to simplify compound propositions.

Key points.

Idempotent $p\lor p\equiv p$; identity $p\lor F\equiv p$; domination $p\lor T\equiv T$; commutative, associative, distributive.
Complement: $p\lor\sim p\equiv T$, $p\land\sim p\equiv F$; double negation $\sim\sim p\equiv p$; absorption $p\lor(p\land q)\equiv p$.
De Morgan and $p\to q\equiv\sim p\lor q\equiv\sim q\to\sim p$.

<mark>Every law has a dual obtained by swapping $\land/\lor$ and T/F.</mark>

Logical implications

Definition. $A$ logically implies $B$ ($A\Rightarrow B$) when $A\to B$ is a tautology; an argument with premises $P_1,\dots,P_n$ and conclusion $C$ is valid if $(P_1\land\dots\land P_n)\to C$ is a tautology. A rule of inference is a valid argument form.

Formula (rules of inference).

Rule	Form
Modus Ponens	$p,\ p\to q\vdash q$
Modus Tollens	$\neg q,\ p\to q\vdash\neg p$
Hypothetical Syllogism	$p\to q,\ q\to r\vdash p\to r$
Disjunctive Syllogism	$p\lor q,\ \neg p\vdash q$
Addition	$p\vdash p\lor q$
Simplification	$p\land q\vdash p$
Conjunction	$p,\ q\vdash p\land q$
Resolution	$p\lor q,\ \neg p\lor r\vdash q\lor r$

Key points.

An argument is valid if no assignment makes all premises true and the conclusion false.
Denying the antecedent ($p\to q,\ \sim p\vdash\sim q$) and affirming the consequent are fallacies.
Conditional proof: to prove $R\to S$, assume $R$ as an extra premise and derive $S$.
Proof by contradiction: add $\neg C$ as a premise and derive a contradiction.

Example 1 (Dec 2024). $p$: races fixed, $r$: trade declines, $s$: police happy. Premises $p\to r$, $r\to s$, $\neg s$; conclusion $\neg p$. (1) $r\to s$, (2) $\neg s$, so $\neg r$ by modus tollens. (3) $p\to r$ and $\neg r$ give $\neg p$ by modus tollens. Valid.

Example 2 (Nov 2019). (1) $R$ assumed. (2) $\neg R\lor P$ gives $P$ (disjunctive syllogism). (3) $P\to(Q\to S)$ gives $Q\to S$ (modus ponens). (4) $Q$ given, so $S$. (5) Discharge: $R\to S$.

Example 3 (Nov 2018). Assume $\neg(\neg Q\to S)\equiv\neg Q\land\neg S$. $P\to Q$ and $\neg Q$ give $\neg P$; $P\lor R$ gives $R$; $\neg R\lor S$ gives $S$; contradiction with $\neg S$, so valid.

Example 4 (Jun 2020). Hypothetical syllogism: if $p\to q$ and $q\to r$ are T then $p\to r$ is T, since $p=T$ forces $q=T$ then $r=T$. The only row with $p\to r$ false is $p=T,r=F$; it makes $p\to q$ or $q\to r$ false. Valid. Rain argument: $p\to q,\ \sim p\therefore\sim q$ fails at $p=F,q=T$ (premises true, conclusion false): invalid, denying the antecedent.

<mark>An argument is valid when the conjunction of its premises implies the conclusion, that is, when the conditional is a tautology.</mark>

Answer frame. Rules question: open with "a rule of inference is a valid argument form", list all eight rules with symbolic form, close with one example. Argument question: symbolise with a key, list premises, number each step with its rule, close with "hence the argument is valid".

Pitfall: If you take the first premise as $(p\land q)\to r$, modus tollens gives only $\neg(p\land q)$, not $\neg p$; use the reading $p\to r$ to reach the stated conclusion.

Asked: [7 marks] (Dec 2024, Jun 2024) Explain various rules of inference for propositional logic. Asked: [7 marks] (Nov 2018) Establish the validity of $[(P\to Q)\land(\neg R\lor S)\land(P\lor R)]\to[\neg Q\to S]$ using contradiction. Asked: [7 marks] (Nov 2019) Show that $R\to S$ follows from $P\to(Q\to S)$, $\neg R\lor P$ and $Q$. Asked: [7 marks] (Jun 2020) Show that the rule of hypothetical syllogism is valid. Asked: [7 marks] (Jun 2020) Test the validity: if it rains, Ram will be sick; it did not rain; therefore Ram was not sick. Asked: [7 marks] (Dec 2024) Prove the validity: if the races are fixed so the casinos are crooked, then the tourist trade will decline; if the tourist trade decreases, the police will be happy; the police are never happy; therefore the races are not fixed.

Logical equivalence

Definition. $A\equiv B$ when $A\leftrightarrow B$ is a tautology, that is, both have identical truth tables.

Key points.

Prove by equal truth-table columns or by a chain of laws.
As printed, $\neg(p\land q)$ (column F,T,T,T) and $\neg p\lor q$ (column T,F,T,T) differ, so say so; the intended pair is $\neg p\lor\neg q$ with column F,T,T,T, which matches, proving De Morgan.

<mark>Two propositions are logically equivalent when they have identical truth tables.</mark>

Asked: [7 marks] (Dec 2023) Show that $\neg(p\land q)$ and $\neg p\lor q$ are logically equivalent.

Predicates

Definition. A predicate is a statement containing variables, such as $P(x)$: "$x>3$", that becomes a proposition when the variables get values or are quantified.

Key points.

$P(x)$ has a domain (universe) for $x$.
A predicate with $n$ variables is $n$-place, such as $G(x,y)$.

<mark>A predicate becomes a proposition when values are assigned or quantifiers are applied.</mark>

Normal forms

Definition. DNF is a sum (OR) of product terms; CNF is a product (AND) of sum terms. PDNF is a sum of minterms (every variable in each term); PCNF is a product of maxterms.

Key points.

A minterm is an AND of all variables, each plain or negated; a maxterm is an OR of all variables.
PDNF collects rows where the formula is T; PCNF collects rows where it is F.
Minterm $m_i$ has variable plain for bit 1; maxterm $M_i$ has variable plain for bit 0 (with $P$ as the most significant bit).
Minterm indices and maxterm indices are complementary, so PDNF follows from PCNF and vice versa.
Algebra method: remove $\to,\leftrightarrow$, push negations in, distribute, and add missing variables using $x\equiv x\land(y\lor\sim y)$.
A contradiction has no minterms; a tautology has all $2^n$ minterms.

Steps (equivalences). $p\to q\equiv\sim p\lor q$; $p\leftrightarrow q\equiv(p\land q)\lor(\sim p\land\sim q)$; expand; drop terms with $x\land\sim x$.

Example 1 (Nov 2019, Dec 2020). $(\sim P\to R)\equiv P\lor R$; $(Q\leftrightarrow P)\equiv(P\land Q)\lor(\sim P\land\sim Q)$. Product: $(P\land Q\land(P\lor R))\lor(\sim P\land\sim Q\land R)$ gives $(P\land Q\land R)\lor(P\land Q\land\sim R)\lor(\sim P\land\sim Q\land R)$.

$$\text{PDNF}=m_1\lor m_6\lor m_7=(\sim P\land\sim Q\land R)\lor(P\land Q\land\sim R)\lor(P\land Q\land R)$$

$$\text{PCNF}=M_0M_2M_3M_4M_5=(P\lor Q\lor R)(P\lor\sim Q\lor R)(P\lor\sim Q\lor\sim R)(\sim P\lor Q\lor R)(\sim P\lor Q\lor\sim R)$$

Example 2 (May 2019). $\sim(p\lor q)\leftrightarrow(p\land q)$ is T for $(p,q)=(F,T)$ and $(T,F)$ only, so PDNF $=(\sim p\land q)\lor(p\land\sim q)$.

Example 3 (Nov 2022, Dec 2023). $(Q\lor P)(Q\lor R)(\sim(P\lor R)\lor\sim Q)$ is F for indices 0,1,3,4,6,7, so PCNF $=M_0M_1M_3M_4M_6M_7$. Remaining minterms $m_2,m_5$: PDNF $=(\sim P\land Q\land\sim R)\lor(P\land\sim Q\land R)$.

Example 4 (CNF). (i) $p\land(p\Rightarrow q)\equiv p\land(\sim p\lor q)$. (ii) $\sim p\Rightarrow[r\land(p\Rightarrow q)]\equiv p\lor(r\land(\sim p\lor q))\equiv p\lor r$.

<mark>PDNF is the sum of minterms of the rows where the formula is true; PCNF is the product of maxterms of the rows where it is false.</mark>

Answer frame. Open with the definition of principal form; write the formula in $\lor,\land,\sim$ using equivalences, show each expansion, list indices, and write the answer; close by stating the other form from the complementary index set.

Asked: [7 marks] (Nov 2019, Dec 2020) Obtain PCNF and PDNF of $(\neg P\to R)\land(Q\leftrightarrow P)$ using equivalences. Asked: [7 marks] (May 2019) Obtain the PDNF of $\sim(p\lor q)\leftrightarrow(p\land q)$. Asked: [7 marks] (Nov 2022, Dec 2023) Find PDNF by constructing its PCNF of $(Q\lor P)\land(Q\lor R)\land(\sim(P\lor R)\lor\sim Q)$; obtain the CNF of (i) $p\land(p\Rightarrow q)$ (ii) $\sim p\Rightarrow[r\land(p\Rightarrow q)]$.

Universal and existential quantifiers

Definition. A predicate $P(x)$ is made a proposition by quantifiers. $\forall x\,P(x)$ ("for all $x$") is true when $P(x)$ holds for every $x$ in the domain; $\exists x\,P(x)$ ("there exists $x$") is true when $P(x)$ holds for at least one $x$.

Key points.

A predicate is a statement with variables that becomes a proposition when values are assigned, for example $P(x)$: $x>3$.
$\forall$ is false if a single counterexample exists; $\exists$ is false only if no element satisfies $P$.
Example: $\forall x\,(x^2\ge0)$ is true over reals; $\exists x\,(x+2=5)$ is true ($x=3$).
Truth depends on the domain: $\exists x\,(x^2=2)$ is true over reals, false over integers.
Negation: $\neg\forall x\,P(x)\equiv\exists x\,\neg P(x)$ and $\neg\exists x\,P(x)\equiv\forall x\,\neg P(x)$.
Use $\forall$ with $\to$ and $\exists$ with $\land$: "all students study" is $\forall x(S(x)\to D(x))$, "some student studies" is $\exists x(S(x)\land D(x))$.

Example (Dec 2025). $S(x)$: $x$ is a student, $D(x)$: $x$ studies Discrete Mathematics. Statement: $\forall x\,(S(x)\to D(x))$. Negation: $\exists x\,(S(x)\land\neg D(x))$, that is, there exists a student who does not study Discrete Mathematics.

Example (Jun 2023). "No one has more than three grandmothers" means no person $y$ has four distinct grandmothers:

$$\forall y\,\neg\exists x_1\exists x_2\exists x_3\exists x_4\,\big(\bigwedge_{i<j}x_i\ne x_j\land G(x_1,y)\land G(x_2,y)\land G(x_3,y)\land G(x_4,y)\big)$$

<mark>$\forall$ means true for every element of the domain, $\exists$ means true for at least one, and negation swaps them.</mark>

Answer frame. Open with the predicate definition; define $\forall$ then $\exists$ with a symbolic and an English example each; add negation rules and domain remark; close with the translation asked.

Asked: [7 marks] (Nov 2018, Jun 2025) Explain universal and existential quantifiers with example. Asked: [7 marks] (Jun 2023) Express "No one has more than three grandmothers" using $G(x,y)$ and quantifiers. Asked: [7 marks] (Jun 2025) What are predicates in propositional logic? Define universal and existential quantifiers with examples. Asked: [7 marks] (Dec 2025) Convert "Every student studies Discrete Mathematics" into predicate logic and write its negation.

Introduction to finite state machine

Definition. A finite state machine with output is $M=(Q,\Sigma,\Delta,\delta,\lambda,q_0)$.

Key points.

$Q$ is the finite set of states, $\Sigma$ the input alphabet, $\Delta$ the output alphabet.
$\delta:Q\times\Sigma\to Q$ is the next-state function and $\lambda$ the output function ($Q\times\Sigma\to\Delta$ for Mealy, $Q\to\Delta$ for Moore); $q_0$ is the start state.
Example (Mealy, parity of 1s): $Q=\{E,O\}$, $\Sigma=\Delta=\{0,1\}$, $q_0=E$.

State	Input 0	Input 1
E (even)	E / 0	O / 1
O (odd)	O / 1	E / 0

<figure class="ds-fig" style="margin:1.4rem 0;overflow-x:auto"><svg xmlns="http://www.w3.org/2000/svg" id="dsfig-u3-01" viewBox="0 0 338 80" width="338" height="80" role="img" aria-label="Mealy machine, E = even number of 1s so far, O = odd. Loops: E on 0/0, O on 0/1."><style>#dsfig-u3-01 .e{stroke:#454C5A;stroke-width:1.4;fill:none}#dsfig-u3-01 .e.hi{stroke:#2340B8;stroke-width:2.6}#dsfig-u3-01 .n{fill:#FFFFFF;stroke:#16181D;stroke-width:1.4}#dsfig-u3-01 .n.hi{fill:#E3E9FC;stroke:#2340B8;stroke-width:2.2}#dsfig-u3-01 .n.rb-b{fill:#16181D;stroke:#16181D}#dsfig-u3-01 .n.rb-r{fill:#BD3227;stroke:#BD3227}#dsfig-u3-01 text{font-family:"JetBrains Mono",ui-monospace,Menlo,Consolas,monospace;font-size:13px}#dsfig-u3-01 .t{fill:#16181D;font-weight:500}#dsfig-u3-01 .t.inv{fill:#FFFFFF;font-weight:700}#dsfig-u3-01 .kd{stroke:#16181D;stroke-width:1.2}#dsfig-u3-01 .dot{fill:#16181D}#dsfig-u3-01 .ann{fill:#2340B8;font-size:11px;font-weight:700}#dsfig-u3-01 .lbl{fill:#6F7787;font-family:system-ui,-apple-system,sans-serif;font-size:12px;font-weight:700}#dsfig-u3-01 .ptr{fill:#2340B8;font-size:12px;font-weight:700}#dsfig-u3-01 .ah{fill:#454C5A}#dsfig-u3-01 .ah.hi{fill:#2340B8}#dsfig-u3-01 .wl rect{fill:#FFFFFF;stroke:#DCE0E7}#dsfig-u3-01 .wl .t{font-size:12px;font-weight:700}#dsfig-u3-01 .wl.hi rect{fill:#2340B8;stroke:#2340B8}#dsfig-u3-01 .wl.hi .t{fill:#FFFFFF}html.dark #dsfig-u3-01 .e{stroke:#B1B7C3}html.dark #dsfig-u3-01 .e.hi{stroke:#8FA3FF}html.dark #dsfig-u3-01 .n{fill:#161920;stroke:#E6E8ED}html.dark #dsfig-u3-01 .n.hi{fill:#1E2748;stroke:#8FA3FF}html.dark #dsfig-u3-01 .n.rb-b{fill:#E6E8ED;stroke:#E6E8ED}html.dark #dsfig-u3-01 .n.rb-r{fill:#FF7E71;stroke:#FF7E71}html.dark #dsfig-u3-01 .t{fill:#E6E8ED}html.dark #dsfig-u3-01 .t.inv{fill:#0F1115}html.dark #dsfig-u3-01 .kd{stroke:#E6E8ED}html.dark #dsfig-u3-01 .dot{fill:#E6E8ED}html.dark #dsfig-u3-01 .ann{fill:#8FA3FF}html.dark #dsfig-u3-01 .lbl{fill:#858D9C}html.dark #dsfig-u3-01 .ptr{fill:#8FA3FF}html.dark #dsfig-u3-01 .ah{fill:#B1B7C3}html.dark #dsfig-u3-01 .ah.hi{fill:#8FA3FF}html.dark #dsfig-u3-01 .wl rect{fill:#161920;stroke:#2A2E37}html.dark #dsfig-u3-01 .wl.hi rect{fill:#8FA3FF;stroke:#8FA3FF}html.dark #dsfig-u3-01 .wl.hi .t{fill:#0F1115}</style><defs><marker id="ah3" viewBox="0 0 10 10" refX="9" refY="5" markerWidth="7" markerHeight="7" orient="auto-start-reverse"><path class="ah" d="M0,1 L9,5 L0,9 z"/></marker><marker id="ahh3" viewBox="0 0 10 10" refX="9" refY="5" markerWidth="7" markerHeight="7" orient="auto-start-reverse"><path class="ah hi" d="M0,1 L9,5 L0,9 z"/></marker></defs><path class="e" d="M58.4,44.6 Q169,72 277.6,45.1" marker-end="url(#ah3)"/><path class="e" d="M279.6,35.4 Q169,8 60.4,34.9" marker-end="url(#ah3)"/><g class="wl"><rect x="151.7" y="49.4" width="33.6" height="18" rx="9"/><text class="t" x="168.5" y="58.4" dy=".35em" text-anchor="middle">1/1</text></g><g class="wl"><rect x="152.7" y="12.6" width="33.6" height="18" rx="9"/><text class="t" x="169.5" y="21.6" dy=".35em" text-anchor="middle">1/0</text></g><circle class="n" cx="40" cy="40" r="18"/><text class="t" x="40" y="40" dy=".35em" text-anchor="middle">E</text><circle class="n" cx="298" cy="40" r="18"/><text class="t" x="298" y="40" dy=".35em" text-anchor="middle">O</text></svg><figcaption style="font-size:.82em;opacity:.72;margin-top:.45rem">Mealy machine, E = even number of 1s so far, O = odd. Loops: E on 0/0, O on 0/1.</figcaption></figure>

<mark>A finite state machine is the 6-tuple $(Q,\Sigma,\Delta,\delta,\lambda,q_0)$.</mark>

Asked: [7 marks] (Jun 2023) Discuss the 6 tuple notation of finite state machine $M$ with an example.

Finite state machines as models of physical system equivalence machines

Definition. Physical systems with finitely many configurations, such as vending machines, traffic lights and elevators, are modelled by FSMs, with states as configurations and inputs as events.

Key points.

Two machines are equivalent if they give the same output for every input string.
A machine with equivalent (indistinguishable) states can be reduced to a minimal machine by merging them.

<mark>Equivalent machines produce identical outputs for every input string.</mark>

Finite state machines as language recognizers

Definition. A finite state automaton (recognizer) is $M=(Q,\Sigma,\delta,q_0,F)$: states $Q$, input alphabet $\Sigma$, transition function $\delta$, start state $q_0$ and set of accepting (final) states $F\subseteq Q$. It has no output; it only accepts or rejects.

Key points.

The machine reads the input string one symbol at a time, moving by $\delta$ from $q_0$.
A string is accepted if the machine ends in a state of $F$; otherwise it is rejected.
The language $L(M)$ is the set of all accepted strings.
In the diagram the start state has an incoming arrow and accepting states are double circles.
Each state remembers a piece of history, and so a finite machine recognises only regular languages.

Design (strings ending in 01). States: $A$ = no useful suffix (start), $B$ = last symbol 0, $C$ = ends in 01 (accepting).

State	on 0	on 1
A (start)	B	A
B	B	C
C (final)	B	A

<figure class="ds-fig" style="margin:1.4rem 0;overflow-x:auto"><svg xmlns="http://www.w3.org/2000/svg" id="dsfig-u3-02" viewBox="0 0 510 80" width="510" height="80" role="img" aria-label="A = start, B = last symbol 0, C = accepting (string ends in 01). Loops: A on 1, B on 0."><style>#dsfig-u3-02 .e{stroke:#454C5A;stroke-width:1.4;fill:none}#dsfig-u3-02 .e.hi{stroke:#2340B8;stroke-width:2.6}#dsfig-u3-02 .n{fill:#FFFFFF;stroke:#16181D;stroke-width:1.4}#dsfig-u3-02 .n.hi{fill:#E3E9FC;stroke:#2340B8;stroke-width:2.2}#dsfig-u3-02 .n.rb-b{fill:#16181D;stroke:#16181D}#dsfig-u3-02 .n.rb-r{fill:#BD3227;stroke:#BD3227}#dsfig-u3-02 text{font-family:"JetBrains Mono",ui-monospace,Menlo,Consolas,monospace;font-size:13px}#dsfig-u3-02 .t{fill:#16181D;font-weight:500}#dsfig-u3-02 .t.inv{fill:#FFFFFF;font-weight:700}#dsfig-u3-02 .kd{stroke:#16181D;stroke-width:1.2}#dsfig-u3-02 .dot{fill:#16181D}#dsfig-u3-02 .ann{fill:#2340B8;font-size:11px;font-weight:700}#dsfig-u3-02 .lbl{fill:#6F7787;font-family:system-ui,-apple-system,sans-serif;font-size:12px;font-weight:700}#dsfig-u3-02 .ptr{fill:#2340B8;font-size:12px;font-weight:700}#dsfig-u3-02 .ah{fill:#454C5A}#dsfig-u3-02 .ah.hi{fill:#2340B8}#dsfig-u3-02 .wl rect{fill:#FFFFFF;stroke:#DCE0E7}#dsfig-u3-02 .wl .t{font-size:12px;font-weight:700}#dsfig-u3-02 .wl.hi rect{fill:#2340B8;stroke:#2340B8}#dsfig-u3-02 .wl.hi .t{fill:#FFFFFF}html.dark #dsfig-u3-02 .e{stroke:#B1B7C3}html.dark #dsfig-u3-02 .e.hi{stroke:#8FA3FF}html.dark #dsfig-u3-02 .n{fill:#161920;stroke:#E6E8ED}html.dark #dsfig-u3-02 .n.hi{fill:#1E2748;stroke:#8FA3FF}html.dark #dsfig-u3-02 .n.rb-b{fill:#E6E8ED;stroke:#E6E8ED}html.dark #dsfig-u3-02 .n.rb-r{fill:#FF7E71;stroke:#FF7E71}html.dark #dsfig-u3-02 .t{fill:#E6E8ED}html.dark #dsfig-u3-02 .t.inv{fill:#0F1115}html.dark #dsfig-u3-02 .kd{stroke:#E6E8ED}html.dark #dsfig-u3-02 .dot{fill:#E6E8ED}html.dark #dsfig-u3-02 .ann{fill:#8FA3FF}html.dark #dsfig-u3-02 .lbl{fill:#858D9C}html.dark #dsfig-u3-02 .ptr{fill:#8FA3FF}html.dark #dsfig-u3-02 .ah{fill:#B1B7C3}html.dark #dsfig-u3-02 .ah.hi{fill:#8FA3FF}html.dark #dsfig-u3-02 .wl rect{fill:#161920;stroke:#2A2E37}html.dark #dsfig-u3-02 .wl.hi rect{fill:#8FA3FF;stroke:#8FA3FF}html.dark #dsfig-u3-02 .wl.hi .t{fill:#0F1115}</style><defs><marker id="ah4" viewBox="0 0 10 10" refX="9" refY="5" markerWidth="7" markerHeight="7" orient="auto-start-reverse"><path class="ah" d="M0,1 L9,5 L0,9 z"/></marker><marker id="ahh4" viewBox="0 0 10 10" refX="9" refY="5" markerWidth="7" markerHeight="7" orient="auto-start-reverse"><path class="ah hi" d="M0,1 L9,5 L0,9 z"/></marker></defs><path class="e" d="M59,40 L234,40" marker-end="url(#ah4)"/><path class="e" d="M273.2,45.4 Q362.5,72 449.9,46" marker-end="url(#ah4)"/><path class="e" d="M451.8,34.6 Q362.5,8 275.1,34" marker-end="url(#ah4)"/><path class="e" d="M451,40 L61,40" marker-end="url(#ah4)"/><g class="wl"><rect x="137.9" y="31" width="19.2" height="18" rx="9"/><text class="t" x="147.5" y="40" dy=".35em" text-anchor="middle">0</text></g><g class="wl"><rect x="352.4" y="49.9" width="19.2" height="18" rx="9"/><text class="t" x="362" y="58.9" dy=".35em" text-anchor="middle">1</text></g><g class="wl"><rect x="353.4" y="12.1" width="19.2" height="18" rx="9"/><text class="t" x="363" y="21.1" dy=".35em" text-anchor="middle">0</text></g><g class="wl"><rect x="245.4" y="31" width="19.2" height="18" rx="9"/><text class="t" x="255" y="40" dy=".35em" text-anchor="middle">1</text></g><circle class="n" cx="40" cy="40" r="18"/><text class="t" x="40" y="40" dy=".35em" text-anchor="middle">A</text><circle class="n" cx="255" cy="40" r="18"/><text class="t" x="255" y="40" dy=".35em" text-anchor="middle">B</text><circle class="n" cx="470" cy="40" r="18"/><text class="t" x="470" y="40" dy=".35em" text-anchor="middle">C</text></svg><figcaption style="font-size:.82em;opacity:.72;margin-top:.45rem">A = start, B = last symbol 0, C = accepting (string ends in 01). Loops: A on 1, B on 0.</figcaption></figure>

Test: 1101 goes A,A,A,B,C accepted; 0110 goes A,B,C,A,B rejected.

<mark>A string is accepted by a finite state machine if reading it from the start state ends in an accepting state.</mark>

Answer frame. Open with the 5-tuple definition; draw the transition diagram with start arrow and double-circled final state; explain acceptance (points 1-3); design question: name the states by the suffix remembered, give the table and test two strings; close with "L(M) is the set of strings ending in a final state".

Asked: [14 marks] (Jun 2025, Dec 2025) Write short notes on (any four): (i) Finite state machines as language recognizers (ii) Binomial theorem (iii) Permutation group (iv) Partial ordering relation (v) Countable and uncountable sets. Asked: [7 marks] (Dec 2025) Design a finite state machine that accepts all binary strings ending with 01.

Last-minute revision

$2^n$ rows for $n$ variables; $p\to q$ is F only at $p=T,q=F$.
Tautology always T, contradiction always F, contingency mixed.
$p\to q\equiv\sim p\lor q\equiv\sim q\to\sim p$; $\sim(p\to q)\equiv p\land\sim q$.
De Morgan: $\sim(p\land q)\equiv\sim p\lor\sim q$.
Modus ponens $p,p\to q\vdash q$; modus tollens $\neg q,p\to q\vdash\neg p$.
Peirce's law $((p\to q)\to p)\to p$ is a tautology.
PDNF = sum of minterms (T rows); PCNF = product of maxterms (F rows).
$\neg\forall x P\equiv\exists x\neg P$; $\neg\exists x P\equiv\forall x\neg P$.
Mealy machine 6-tuple $(Q,\Sigma,\Delta,\delta,\lambda,q_0)$; recognizer 5-tuple $(Q,\Sigma,\delta,q_0,F)$.

Memory hooks

PDNF = True rows, minterms, OR of ANDs; PCNF = False rows, maxterms, AND of ORs.
$\forall$ is an upside-down A (All); $\exists$ is a backwards E (Exists).
FSM design: name each state by what it remembers.

Coverage checklist

Proposition: definition (no past questions).
First order logic: definition (no past questions).
Basic logical operation: negation questions (Dec 2023).
truth tables: Dec 2023, Jun 2025.
tautologies: Nov 2018, May 2019, Jun 2020 (two), Nov 2022 (two), Jun 2023, Jun 2024, Dec 2025.
Contradictions: Jun 2024 (ii) (with tautologies), Nov 2022 (with tautologies).
Algebra of Proposition: laws (no past questions).
logical implications: Nov 2018, Nov 2019, Jun 2020 (two), Jun 2024, Dec 2024 (two).
logical equivalence: Dec 2023.
predicates: Jun 2025 (with quantifiers).
Normal Forms: May 2019, Nov 2019, Dec 2020, Nov 2022, Dec 2023.
Universal and existential quantifiers: Nov 2018, Jun 2023, Jun 2025 (two), Dec 2025.
Introduction to finite state machine: Jun 2023.
Finite state machines as models of physical system equivalence machines: no past questions.
Finite state machines as language recognizers: Jun 2025, Dec 2025 (two).

Account

Discrete Structure (CS-302) - Unit 3 Short Notes

How unit 3 is examined

Proposition

First order logic

Basic logical operation

Truth tables

Tautologies

Contradictions

Algebra of Proposition

Logical implications

Logical equivalence

Predicates

Normal forms

Universal and existential quantifiers

Introduction to finite state machine

Finite state machines as models of physical system equivalence machines

Finite state machines as language recognizers

Last-minute revision

Memory hooks

Coverage checklist