Discrete Structures: Comprehensive Lecture 6–25 Notes

Predicate Logic (First-Order Logic)

• Predicate / Propositional Function
  • Declarative statement with ≥ 1 variable; notation: $P(x),Q(x),R(x)$.
  • Returns $T$ or $F$ once all variables receive specific values.
  • Example: P(x)=x<5;\ P(1)=T;\ P(10)=F.
• Need for Predicates
  • Propositional Logic insufficient for statements like “Every CS computer is protected” or “Some students have brown hair.”
  • Predicate Logic adds quantification over domains (universes of discourse).
• Truth Testing
  • Statement categories in slides: proposition? $10+4=14$ → Yes; $x+2=5$ → No (open); quantified versions vary by quantifier.

Quantifiers

• Universal Quantifier $\forall xP(x)$ (“for all x”).
  • False iff a counter-example exists.
  • Conjunction view: $\forall x\;P(x)\equiv P(x<em>1)\land … \land P(x</em>n)$ for finite domains.
  • Provide domain every time!
• Existential Quantifier $\exists xP(x)$ (“there exists x”).
  • True if at least one element satisfies $P$.
  • Disjunction view: $\exists x\;P(x)\equiv P(x<em>1)\lor … \lor P(x</em>n)$.
  • Truth/falsehood reversed relative to universal.
• Uniqueness Quantifier $\exists !xP(x)$ (“exactly one x”).
• Restricted Domains
  • Notation $\forall x<0\; x^2>0$ means $\forall x[(x<0)\to(x^2>0)]$.
  • Existential restriction \exists z>0\; z^2=2 ≡ \exists z[(z>0)\land(z^2=2)].

Binding & Scope

• Bound variable: inside scope of a quantifier or assigned value.
• Free variable: not bound → expression not a proposition.
• Scope examples illustrated with nested quantifiers; ensure no free variables.

Translation Examples

• “Every student in this class has studied calculus” (domain = people): $\forall x[S(x)\to C(x)]$.
• Russian/C++ examples: $\exists x(R(x)\land\neg C(x))$, $\forall x(R(x)\lor C(x))$ etc.

Negating Quantified Statements

• De Morgan for quantifiers: $\neg\forall xP(x)\equiv\exists x\neg P(x)$; $\neg\exists xP(x)\equiv\forall x\neg P(x)$.
• Practical phrasing: negate universal by claiming “some counterexample,” negate existential by asserting “none.”

Rules of Inference (Propositional)

• Modus Ponens $(p\land(p\to q))\to q$.
• Modus Tollens $(\neg q\land(p\to q))\to\neg p$.
• Addition, Simplification, Conjunction, Disjunctive Syllogism, Hypothetical Syllogism, Resolution — each supplied with tautology form.
• Arguments = premises + conclusion; validity when $(p<em>1\land…\land p</em>n)\to q$ is tautology.

Quantified Inference Rules

• Universal / Existential Instantiation & Generalisation.
• Universal Modus Ponens: $\forall x(P\to Q),\;P(a)\Rightarrow Q(a)$.
• Universal Modus Tollens: $\forall x(P\to Q),\;\neg Q(a)\Rightarrow\neg P(a)$.

Set Theory Essentials

• Set, Element ($a\in A$), empty set $\varnothing$, singleton, power set $\mathcal P(S)$ with $|\mathcal P(S)|=2^{|S|}$.
• Subset $A\subseteq B\iff\forall x(x\in A\to x\in B)$; proper subset $A\subset B$ requires inequality.
• Cardinality; finite vs infinite; examples.
• Cartesian Product $A\times B$ (order matters); $|A\times B|=|A||B|$.
• Operations: union, intersection, difference, complement with identities & De Morgan.
• Inclusion–Exclusion (2 sets) $|A\cup B|=|A|+|B|-|A\cap B|$; general forms listed.
• Quantifiers w/ Sets notation $\forall x\in S\;P(x)$, truth sets.

Functions

• Definition: assignment $f:A\to B$, domain, codomain, range (image set).
• One-to-one (injective): $f(a)=f(b)\Rightarrow a=b$.
• Onto (surjective): $\forall b\in B\;\exists a\in A\,f(a)=b$.
• Bijective: both above ⇒ invertible; inverse $f^{-1}$ satisfies $f^{-1}(f(a))=a$.
• Arithmetic on functions: $(f!+!g)(x)=f(x)+g(x)$ etc.
• Composition $(f\circ g)(x)=f(g(x))$, generally non-commutative.
• Special functions: floor $\lfloor x\rfloor$, ceiling $\lceil x\rceil$, factorial $n!$, identity.

Relations

• Binary relation $R\subseteq A\times B$; on one set ⇒ relation on A.
• Properties:
  • Reflexive, Irreflexive
  • Symmetric, Anti-symmetric
  • Transitive.
• Equivalence relation = reflexive + symmetric + transitive.
• Partial order = reflexive + anti-symmetric + transitive (implied).
• Representations: ordered-pair lists, adjacency matrices, directed graphs, incidence matrices.
• Operations on relations (union, intersection, complement, composition $S\circ R$).
• Powers $R^2=R\circ R$ etc.

Counting Principles

• Product Rule: procedure with consecutive tasks ⇒ $n<em>1n</em>2…n_k$ ways.
• Sum Rule: mutually exclusive options ⇒ $n<em>1+n</em>2+…$ ways.
• Inclusion–Exclusion handles overlap.
• Examples: telephone numbering, license plates, 3-digit numbers divisible by $5$.

Recursion

• Recursive definitions require (1) basis step (2) recursive step.
  • Factorial: $f(0)=1,\;f(n)=n\,f(n-1)$.
  • Fibonacci: $F(0)=0,\;F(1)=1,\;F(n)=F(n-1)+F(n-2)$.
• Recursive algorithms: factorial, Euclidean GCD, etc.

Sequences & Series

• Sequence = function $a_n$ from $\mathbb N$.
• Arithmetic progression $a,a+d,a+2d,…$ general term $a_n=a+(n-1)d$.
• Geometric progression $a,ar,ar^2,…$ general $a_n=ar^{n-1}$.
• Summation notation $\sum<em>{k=m}^n a</em>k$; properties, index shifts, double sums.
• Useful identities: $\sum_{k=1}^n k=\frac{n(n+1)}2$, $\sum k^2=\frac{n(n+1)(2n+1)}6$, $\sum k^3=\left[\frac{n(n+1)}2\right]^2$.

Graph Theory

• Graphs $G=(V,E)$: simple, multigraph, pseudograph, directed, weighted.
• Special graphs: complete $K<em>n$, cycle $C</em>n$, wheel $W<em>n$, bipartite & complete bipartite $K</em>{m,n}$.
• Degree: $\deg(v)$ (loops count twice); Handshaking Lemma $\sum\deg(v)=2|E|$ ⇒ even number of odd-degree vertices.
• Directed graphs: in-degree $deg^-(v)$, out-degree $deg^+(v)$, totals equal $|E|$.
• Paths / Circuits / Walks distinctions; connectivity; distance matrix, eccentricity, radius, diameter.
• Representations: adjacency list, adjacency matrix $A$, incidence matrix.
• Subgraphs & unions; graph models (social networks, influence, tournaments, intersection graphs).

Trees

• Tree: connected acyclic simple undirected graph.
  • $|E|=|V|-1$ (implicit).
• Forest: acyclic, possibly disconnected.
• Rooted tree: designate root, direct edges away.
  • Parent, child, siblings, ancestors, descendants.
  • Internal vertex vs leaf.
  • Subtree rooted at $v$.
• m-ary & binary trees; full m-ary (all internal vertices have exactly $m$ children); balanced if leaves at heights $h$ or $h-1$.
• Levels & Height: root level $0$; height = max level.
• Ordered rooted tree: children ordered L→R; enables traversals.
• Traversals (recursive):
  • Preorder (Root-Left-Right).
  • Inorder (Left-Root-Right) — yields infix expressions for binary trees.
  • Postorder (Left-Right-Root).
• Binary Search Tree (BST): in-order traversal gives sorted order; each node key > all in left subtree & < all in right.
• Expression Trees: internal vertices = operators, leaves = operands; prefix/pre-order (Polish), inorder (infix), postfix/post-order (Reverse Polish).