Graduate
  1. Real Analysis  1.1. Set Theory and Logic  1.1.1. Sets and Operations  1.1.2. Relations and Functions  1.1.3. Logic and Quantifiers  1.1.4. Cardinality of Sets  1.2. Metric Spaces  1.2.1. Open and Closed Sets  1.2.2. Convergence of Sequences  1.2.3. Continuous Functions in Metric Spaces  1.2.4. Compactness and Completeness in Metric Spaces in Real Analysis  1.3. Sequence and Series  1.3.1. Convergence of Sequences  1.3.2. Infinite Series  1.3.3. Uniform Convergence  1.3.4. Power Series  1.4. Differentiation  1.4.1. Mean Value Theorems  1.4.2. Taylor Series  1.4.3. Functions of Several Variables  1.4.4. Partial Derivatives  1.5. Integration  1.5.1. Riemann and Lebesgue Integration  1.5.2. Improper Integrals  1.5.3. Measure Theory  1.5.4. Fubini’s Theorem  1.6. Functional Analysis  1.6.1. Banach Spaces  1.6.2. Hilbert Spaces  1.6.3. Operators on Spaces  1.6.4. Spectral Theory
  2. Abstract Algebra  2.1. Groups  2.1.1. Definitions and Examples in Groups in Abstract Algebra  2.1.2. Group Homomorphisms  2.1.3. Normal Subgroups  2.1.4. Sylow Theorems  2.2. Rings and Fields  2.2.1. Ideals and Factor Rings  2.2.2. Field Extensions  2.2.3. Galois Theory  2.2.4. Polynomial Rings  2.3. Modules  2.3.1. Module Homomorphisms  2.3.2. Free Modules  2.3.3. Tensor Products  2.3.4. Exact Sequences  2.4. Linear Algebra  2.4.1. Vector Spaces  2.4.2. Eigenvalues and Eigenvectors  2.4.3. Inner Product Spaces  2.4.4. Diagonalization
  3. Topology  3.1. General Topology  3.1.1. Open and Closed Sets  3.1.2. Compactness and Connectedness  3.1.3. Continuous Maps  3.1.4. Separation Axioms  3.2. Algebraic Topology  3.2.1. Fundamental Groups  3.2.2. Homotopy and Homology  3.2.3. Simplicial Complexes  3.2.4. Exact Sequences in Homology  3.3. Differential Topology  3.3.1. Manifolds  3.3.2. Smooth Functions  3.3.3. Tangent and Cotangent Spaces  3.3.4. Vector Bundles
  4. Differential Equations  4.1. Ordinary Differential Equations  4.1.1. First-Order Equations  4.1.2. Second-Order Linear Equations  4.1.3. Systems of Differential Equations  4.1.4. Stability Analysis  4.2. Partial Differential Equations  4.2.1. Classification of PDEs  4.2.2. Fourier Series  4.2.3. Green's Functions  4.2.4. Method of Characteristics  4.3. Dynamical Systems  4.3.1. Stability Theory  4.3.2. Limit Cycles  4.3.3. Chaos Theory  4.3.4. Bifurcation Theory
  5. Probability and Statistics  5.1. Probability Theory  5.1.1. Random Variables  5.1.2. Probability Distributions  5.1.3. Law of Large Numbers  5.1.4. Central Limit Theorem  5.2. Statistical Inference  5.2.1. Hypothesis Testing  5.2.2. Confidence Intervals  5.2.3. Bayesian Methods  5.2.4. Maximum Likelihood Estimation  5.3. Stochastic Processes  5.3.1. Markov Chains  5.3.2. Brownian Motion  5.3.3. Poisson Processes  5.3.4. Martingales
  6. Numerical Analysis  6.1. Numerical Solutions of Equations  6.1.1. Root Finding  6.1.2. Iterative Methods  6.1.3. Convergence Analysis  6.1.4. Error Bounds in Numerical Solutions of Equations  6.2. Numerical Linear Algebra  6.2.1. Matrix Factorizations  6.2.2. Eigenvalue Computations  6.2.3. Sparse Matrices  6.2.4. Preconditioning Techniques  6.3. Numerical Integration and Differentiation  6.3.1. Quadrature Methods  6.3.2. Finite Differences  6.3.3. Error Analysis in Numerical Integration and Differentiation  6.3.4. Adaptive Methods
  7. Complex Analysis  7.1. Complex Numbers  7.1.1. Polar Form  7.1.2. Complex Conjugates  7.1.3. Exponential Form  7.1.4. Roots of Unity  7.2. Analytic Functions  7.2.1. Cauchy-Riemann Equations  7.2.2. Power Series  7.2.3. Conformal Mappings  7.2.4. Harmonic Functions  7.3. Integration in the Complex Plane  7.3.1. Cauchy’s Theorem  7.3.2. Residue Theorem  7.3.3. Contour Integration  7.3.4. Integral Transforms
  8. Mathematical Logic and Foundations  8.1. Propositional Logic  8.1.1. Truth Tables  8.1.2. Logical Equivalences  8.1.3. Proof Techniques in Propositional Logic  8.1.4. Resolution  8.2. Predicate Logic  8.2.1. Quantifiers in Predicate Logic  8.2.2. Formal Systems in Predicate Logic  8.2.3. Completeness and Soundness  8.2.4. Model Theory  8.3. Set Theory  8.3.1. Cardinality and Ordinality  8.3.2. Axiomatic Systems  8.3.3. Zermelo-Fraenkel Set Theory  8.3.4. Forcing
  9. Optimization  9.1. Linear Programming  9.1.1. Simplex Method  9.1.2. Duality in Linear Programming  9.1.3. Sensitivity Analysis  9.1.4. Interior Point Methods  9.2. Nonlinear Programming  9.2.1. Gradient Descent  9.2.2. Lagrange Multipliers  9.2.3. Convex Optimization  9.2.4. Quadratic Programming  9.3. Combinatorial Optimization  9.3.1. Graph Algorithms  9.3.2. Integer Programming  9.3.3. Network Flows  9.3.4. Approximation Algorithms
  10. Discrete Mathematics  10.1. Graph Theory  10.1.1. Graph Representations  10.1.2. Planarity and Coloring  10.1.3. Shortest Path Algorithms  10.1.4. Network Flows  10.2. Combinatorics  10.2.1. Permutations and Combinations  10.2.2. Generating Functions  10.2.3. Recurrence Relations  10.2.4. Inclusion-Exclusion Principle  10.3. Cryptography  10.3.1. Number Theory Applications in Cryptography  10.3.2. Symmetric and Asymmetric Cryptography  10.3.3. RSA and Elliptic Curve Cryptography  10.3.4. Post-Quantum Cryptography

Graduate → Mathematical Logic and Foundations → Propositional Logic ↓


Proof Techniques in Propositional Logic


In the field of mathematical logic, proof techniques are methods applied by mathematicians to demonstrate the truth of propositions. Propositional logic involves statements that can be true or false, often called "propositions." Understanding the various proof techniques is important for analyzing logical arguments and formulating new arguments. This text discusses in depth the major proof techniques used in propositional logic, providing text-based and visual examples for clarity.

1. Direct evidence

Direct proof is a direct way of establishing that a given proposition is true. It involves a logical sequence of statements from an assumed true premise to a conclusion.

Consider proving if A, then B

phase:

  1. Suppose that A is true.
  2. Use logical reasoning to show that B must also be true.

Example:

Prove: If n is an even number, then n 2 is even.

evidence:

  1. Let n be even. Then n = 2k for some integer k.
  2. So n 2 = (2k) 2 = 4k 2.
  3. Note that 4k 2 = 2(2k 2 ), which is divisible by 2, so even.
  4. Therefore, n 2 is even.
Assume that n is even prove n² even

2. Indirect proof (proof by contradiction)

Indirect proof, or proof by contradiction, involves assuming that the statement you want to prove is false, then showing that this assumption leads to a contradiction.

Suppose that proving ¬A ⇒ false makes A true.

phase:

  1. Suppose A is false.
  2. Show that this assumption leads to a logical contradiction.
  3. Conclude that A must be true.

Example:

Prove: There is no greatest integer.

evidence:

  1. For the sake of contradiction suppose that there is a largest integer called N
  2. Consider N + 1 Clearly, N + 1 > N.
  3. This contradicts the assumption that N is the largest integer.
  4. So our assumption is wrong. So there is no largest integer.
Let ¬A contraindications

3. Proof by counterbalancing

Proof by counterexample consists in proving that if not B, then not A is a way of showing if A, then B.

Example:

Prove: If n 2 is even, then n is even.

evidence:

  1. Conversely, we will prove: if n is odd, then n 2 is odd.
  2. Let n be odd. Then n = 2k + 1 for some integer k.
  3. So n 2 = (2k + 1) 2 = 4k 2 + 4k + 1.
  4. Note that 4k 2 + 4k + 1 is odd since it is of the form 2m + 1.
  5. Thus, if n is odd, n 2 is odd.
  6. Therefore, by converse, if n 2 is even, n is even.
Assume that n is odd Prove that n² is odd

4. Proof by induction

Mathematical induction is a powerful technique used to prove statements about the natural numbers. It consists of two main components: the base case and the inductive step.

phase:

  1. Base case: Verify the statement for an initial value (often n=0 or n=1).
  2. Inductive step: Assume the statement is true for an arbitrary case n=k, and show that it is also true for n=k+1.

Example:

Prove: For all natural numbers n , 1 + 2 + ldots + n = frac{n(n + 1)}{2}.

evidence:

  1. Base case: For n=1, the left side is 1 and the right side frac{1(1+1)}{2} = 1 The base case is valid.
  2. Inductive step: Assume that for n=k the truth is:
    1 + 2 + ldots + k = frac{k(k+1)}{2}
  3. Prove that for n=k+1:
    1 + 2 + ldots + k + (k+1) = frac{k(k+1)}{2} + (k+1)
  4. Rewriting,
    frac{k(k+1)}{2} + (k+1) = frac{k(k+1) + 2(k+1)}{2} = frac{(k+1)(k+2)}{2}
  5. Thus, the formula is true for n=k+1.
  6. By induction, the formula is valid for all natural numbers n.
Base Case Inductive Phase n = k n = k+1

5. Evidence from exhaustion

Proof by exhaustion, or case analysis, is a technique in which a statement is proved by including all possible cases.

phase:

  1. Divide the proposal into a limited number of cases.
  2. Prove that the proposition is true for each case separately.

Example:

Prove: Every integer from 1 to 4 is less than 5.

evidence:

  1. Case 1: n = 1 , then 1 < 5.
  2. Case 2: n = 2 , then 2 < 5.
  3. Case 3: n = 3 , then 3 < 5.
  4. Case 4: n = 4 , then 4 < 5.
Case 1 Case 2 Case 3 Case 4

6. Proof by counterexample

Proof by counterexample is the technique of proving a universal statement false by providing a single counterexample.

Example:

Disprove: All prime numbers are odd.

Counterexample:

  • 2 is a prime number but it is not odd.
2 is even

Conclusion

Understanding and using proof techniques in propositional logic is an essential skill in mathematical logic and foundations. Mastering these techniques provides the tools needed to efficiently analyze and construct logical arguments. From direct and indirect proofs to mathematical induction and proof by counterexample, each method offers unique insights and approaches to solving logical problems. Practicing these techniques with diverse examples helps build a strong foundation for advanced topics in mathematics.


Graduate → 8.1.3


U
username
0%
completed in Graduate

← Prev (8.1.2)
Logical Equivalences
Next (8.1.4) →
Resolution

Comments 



Proof Techniques in Propositional Logic

https://www.buddymath.com/g/8.1.3?bmal=en