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)P(x),Q(x),R(x).
    • Returns TT or FF once all variables receive specific values.
    • Example: P(x)=x<5; P(1)=T; P(10)=FP(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=1410+4=14 → Yes; x+2=5x+2=5 → No (open); quantified versions vary by quantifier.

Quantifiers

  • Universal Quantifier ∀xP(x)\forall xP(x) (“for all x”).
    • False iff a counter-example exists.
    • Conjunction view: ∀x  P(x)≡P(x<em>1)∧…∧P(x</em>n)\forall x\;P(x)\equiv P(x<em>1)\land … \land P(x</em>n) for finite domains.
    • Provide domain every time!
  • Existential Quantifier ∃xP(x)\exists xP(x) (“there exists x”).
    • True if at least one element satisfies PP.
    • Disjunction view: ∃x  P(x)≡P(x<em>1)∨…∨P(x</em>n)\exists x\;P(x)\equiv P(x<em>1)\lor … \lor P(x</em>n).
    • Truth/falsehood reversed relative to universal.
  • Uniqueness Quantifier ∃!xP(x)\exists !xP(x) (“exactly one x”).
  • Restricted Domains
    • Notation ∀x<0  x2>0\forall x<0\; x^2>0 means ∀x[(x<0)→(x2>0)]\forall x[(x<0)\to(x^2>0)].
    • Existential restriction ∃z>0  z2=2\exists z>0\; z^2=2 ≡ ∃z[(z>0)∧(z2=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): ∀x[S(x)→C(x)]\forall x[S(x)\to C(x)].
  • Russian/C++ examples: ∃x(R(x)∧¬C(x))\exists x(R(x)\land\neg C(x)), ∀x(R(x)∨C(x))\forall x(R(x)\lor C(x)) etc.

Negating Quantified Statements

  • De Morgan for quantifiers: ¬∀xP(x)≡∃x¬P(x)\neg\forall xP(x)\equiv\exists x\neg P(x); ¬∃xP(x)≡∀x¬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∧(p→q))→q(p\land(p\to q))\to q.
  • Modus Tollens (¬q∧(p→q))→¬p(\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∧…∧p</em>n)→q(p<em>1\land…\land p</em>n)\to q is tautology.

Quantified Inference Rules

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

Set Theory Essentials

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

Functions

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

Relations

  • Binary relation R⊆A×BR\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∘RS\circ R).
  • Powers R2=R∘RR^2=R\circ R etc.

Counting Principles

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

Recursion

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

Sequences & Series

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

Graph Theory

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

Trees

  • Tree: connected acyclic simple undirected graph.
    • ∣E∣=∣V∣−1|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 vv.
  • m-ary & binary trees; full m-ary (all internal vertices have exactly mm children); balanced if leaves at heights hh or h−1h-1.
  • Levels & Height: root level 00; 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).