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 ↓


Resolution


Resolution is a fundamental rule of inference used in propositional logic and automated theorem proving. It plays an important role in logic programming and forms the basis of the programming language Prolog. The technique is based on the principle of refutation, where one proves the impossibility of a proposition by assuming its negation and obtaining a contradiction. In propositional logic, resolution is used to derive a conclusion by resolving a set of clauses.

Basics of propositional logic

In propositional logic, we deal with propositions, which are statements that can be true or false. These propositions are represented by propositional variables such as p, q, r, etc. Combined propositions are formed using logical connectives such as AND (∧), OR (∨), NOT (¬), IMPLIES (→), and EQUIVALENT (↔).

A literal is either a propositional variable or the negation of a propositional variable. A clause is a disjunction of a literal. For example, the clause (p ∨ ¬q ∨ r) contains the literals p, ¬q, and r.

The central concept in solution is the solution rule, which allows us to deduce a new clause from two existing clauses that contain complementary literals. Complementary literals are pairs, such as p and ¬p, that are negations of each other.

Resolution rules

The solution rule can be formally expressed as follows:

C1: (A ∨ X)
C2: (¬x ∨ b)
,
Answer: (A ∨ B)

Here, C1 and C2 are clauses containing letters x and ¬x, respectively. The clause (A ∨ B) is the result of solving these two clauses on the letter x.

Consider the following example:

C1: (p ∨ q)
C2: (¬q ∨ r)
,
Res: (P ∨ R)

In this case, the literal q in C1 and ¬q in C2 are complemented. The solution result is (p ∨ r).

Conjunctive normal form (CNF)

To use the solution effectively, propositions must be converted into a specific form known as conjunctive normal form (CNF). A formula is in CNF if it is a conjunction of one or more clauses, where each clause is a disjunction of literals.

Converting a logical formula to CNF involves a series of equivalence transformations:

  • Eliminate implications and equivalences using logical equivalences such as: 
            p → q ≡ ¬p ∨ q
        p ↔ q ≡ (p → q) ∧ (q → p)
  • Move the NOTs inwards using De Morgan's laws and double negation: 
            ¬(p ∧ q) ≡ ¬p ∨ ¬q
        ¬(p ∨ q) ≡ ¬p ∧ ¬q
        ¬¬P ≡ P
  • Distribute the OR over the AND, making sure that all clauses become disjunctions of literal terms.

Example of conversion to CNF

Consider the formula: 

 (P → Q) → (Q → R)

Step 1: Eliminate the implications: 

 ¬(¬p∨q) ∨ (¬q∨r)

Step 2: Apply De Morgan's Laws: 

 (p ∧ ¬q) ∨ (¬q ∨ r)

Step 3: Deliver: 

 (p ∨¬q) ∧ (p ∨r)

Now, the formula is in CNF.

Example of a solution in propositional logic

Let us consider an example of how resolution can be used to solve a logic problem:

The following statements are given:

  1. If it is raining, then the ground is wet. (R → W)
  2. If the ground is wet, the sky is cloudy. (W → C)
  3. There are no clouds in the sky. (¬C)

Prove that it is not raining. (¬R)

Represent each statement in CNF:

  • ¬R ∨ W (derived from R → W)
  • ¬W ∨ C (derived from W → C)
  • ¬C

To prove ¬R, add the negation of the conclusion as an assumption and resolve the contradiction:

Add R to the set.

Solution:

1. R
2.¬R ∨ W
3. ¬W ∨ C
4. ¬C

Solve (1) R and (2) ¬R ∨ W: 

 5. W
Solve (5) W and (3) ¬W ∨ C: 
 6. C
(6) C contradicts (4) ¬C. Therefore, assumption R must be false, so ¬R is true.

Properties of resolution

Resolution has several important properties that make it a powerful tool in automated theorem proving:

  • Soundness: If a clause emerges from the solution rule, then that clause is logically implied by the initial set of clauses.
  • Completeness: If a set of clauses is unsatisfiable (that is, they cannot all be true at the same time), then the solution can reflect that unsatisfiability.
  • Refutation completeness: If a contradiction can be derived from a set of clauses, then the solution will eventually find it.

Complexity and limitations

Although resolution is a powerful technique, it is important to note its limitations:

  • Exponential growth: The space of possible segments can grow exponentially in size, making solutions computationally expensive for large problems.
  • Restricted to CNF: Since the solution works on CNF, any problem must be transformed into this form, which can sometimes involve a large number of clauses.

Visual representation of resolution

To make the solution more clear, let's look at a simple diagrammatic representation. Consider these sentences:

A (A ∨ B) ¬B
(A ∨ B) ¬B A

The solution step A combines (A ∨ B) and (¬B) to make a conjecture.

Solution strategies

In practice, a number of strategies and optimizations are employed to efficiently use the solution. These strategies aim to control the order and method in which clauses are solved, often based on heuristics or specific algorithms.

  • Unit solution: This involves prioritizing single letter blocks, known as unit blocks, in order to simplify and rapidly reduce the size of the problem.
  • Input resolution: ensures that resolution is performed between a segment of the original set and a newly derived segment, thereby reducing complexity.
  • Set of support strategy: focuses on reducing the search space by solving clauses only within a specified subset, often used in interactive theorem proving.

Applications in computer science

Resolution is widely used in computer science disciplines, particularly in areas such as artificial intelligence and logic programming. Its main applications include:

  • Automated theorem proving: As a primary technique in proof systems and automated reasoning tools, solution proving helps verify the validity of logical statements.
  • Logic programming: Solution theory is the basis of languages such as Prolog, where logical relations are resolved to form computation questions.
  • Satisfiability solvers: Modern SAT solvers apply solution-based strategies to determine whether a propositional formula can be satisfied.

Conclusion

Resolution in propositional logic is a robust and compelling method for logical reasoning. By leveraging the power of inference through the resolution rule, it provides a systematic approach to proving the validity or contradiction of statements expressed in propositional logic. While its application in real-world scenarios can be computationally intensive, its theoretical basis holds immense value for understanding logical systems and developing practical, automated tools in computer science.

Solution inference provides great insight into the logical structure of problems, making it possible to construct efficient algorithms for tackling complex logical reasoning tasks, and it remains an important area of study in mathematics and computer science.


Graduate → 8.1.4


U
username
0%
completed in Graduate

← Prev (8.1.3)
Proof Techniques in Propositional Logic
Next (8.2) →
Predicate Logic

Comments 



Resolution

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