Logic and Proof Techniques in Computation

Introduction

Section 1: Propositional Logic

1.1 Basic Concepts

• Propositions: A proposition is a declarative statement that is either true or false.
  • Example: “It is raining.” (True or False)
• Logical Connectives: These are operators used to combine propositions.
  • Conjunction ($\wedge$): “AND” operator.
    • Example: $P\wedge Q$ (True if both $P$ and $Q$ are true)
  • Disjunction ($\vee$): “OR” operator.
    • Example: $P\vee Q$ (True if either $P$ or $Q$ is true)
  • Negation ($\neg$): “NOT” operator.
    • Example: $\neg P$ (True if $P$ is false)
  • Implication ($⟹$): “IF…THEN…” operator.
    • Example: $P⟹Q$ (False only if $P$ is true and $Q$ is false)
  • Biconditional ($⟺$): “IF AND ONLY IF” operator.
    • Example: $P⟺Q$ (True if $P$ and $Q$ have the same truth value)

1.2 Truth Tables

• Example Truth Table for $P\wedge Q$:

  $P$	$Q$	$P\wedge Q$
  T	T	T
  T	F	F
  F	T	F
  F	F	F

Section 2: Predicate Logic

2.1 Basic Concepts

• Predicates: A predicate is a statement that contains variables and becomes a proposition when specific values are substituted for the variables.
  • Example: $P(x)$: “x is a prime number.”
• Quantifiers:
  • Universal Quantifier ($\forall$): “For all” or “For every.”
    • Example: $\forall x\in \mathbb{N},P(x)$ (All natural numbers are prime – False)
  • Existential Quantifier ($\exists$): “There exists.”
    • Example: $\exists x\in \mathbb{N},P(x)$ (There exists a natural number that is prime – True)

2.2 Scope and Binding

• Example:
  • $\forall x(P(x)⟹Q(x)\; )$
  • Here, $x$ is bound to the universal quantifier within the scope of the implication.

Section 3: Proof Techniques

3.1 Direct Proof

• Example: Prove that the sum of two even integers is even.
  • Let $a$ and $b$ be even integers.
  • Then $a=2m$ and $b=2n$ for some integers $m$ and $n$.
  • $a+b=2m+2n=2(m+n)$, which is even.

3.2 Indirect Proof (Proof by Contradiction)

1. Example: Prove that \(\sqrt{2}\) is irrational.
   • Assume \(\sqrt{2}\) is rational, so \(\sqrt{2} = \frac{p}{q}\) where \(p\) and \(q\) are coprime integers.
   • Squaring both sides: \(2 = \frac{p^2}{q^2}\) \(\Rightarrow\) \(2q^2 = p^2\).
   • This implies \(p^2\) is even, so \(p\) is even. Let \(p = 2k\).
   • Substituting back: \(2q^2 = (2k)^2 = 4k^2\) \(\Rightarrow\) \(q^2 = 2k^2\).
   • This implies \(p^2\) is even, so \(p\) is even. Let \(p = 2k\).
   • But this contradicts the assumption that \(p\) and \(q\) are coprime.
   • Therefore, \(\sqrt{2}\) is irrational.

3.3 Mathematical Induction

• Base Case: Show the statement is true for the initial value (usually $n=1$).
• Inductive Step: Assume the statement is true for $n=k$ (inductive hypothesis), and prove it for $n=k+1$.
• Example: Prove that the sum of the first $n$ natural numbers is \(\frac{n(n+1)}{2}\).
  • Base Case: For $n=1$, the sum is $1=\; \backslash (\backslash frac\{1(1+1)\}\{2\}\backslash )$  ​= 1. True.
  • Inductive Step: Assume the formula holds for $n=k$, i.e., $1+2+\cdots +k=\; \backslash (\backslash frac\{k(k+1)\}\{2\}\backslash )$.
  • For $n=k+1$:
    • 1+2+⋯+k + (k+1) = \(\frac{k(k+1)}{2}\)​ + (k+1)
    • = \(\frac{k(k+1)+2(k+1)}{2}\)​ = \(\frac{(k+1)(k+2)}{2}\)
    • This matches the formula for $n=k+1$.
  • Therefore, by induction, the formula holds for all natural numbers.

Section 4: Applications in TOC

• Algorithm Correctness: Proving that an algorithm produces the correct output for all valid inputs.
• Complexity Analysis: Establishing the time and space complexity of algorithms using logical reasoning.
• Automata Theory: Defining the behavior of automata using logical conditions and transitions.

Note to the Reader