PREDICATE LOGIC

Predicate Logic

• Predicate logic is an extension of propositional logic, allowing for more complex conditions to be formulated.
• It introduces predicates, which are expressions that depend on variables, and quantifiers, which specify how many objects in the domain of discourse satisfy a formula.

Basic Concepts

• A quantifier is an operator in predicate logic that specifies how many objects in the domain of discourse satisfy a formula.
• There are two types of quantifiers: universal quantifier (∀) and existential quantifier (∃).
• The universal quantifier (∀) means "for all," and the existential quantifier (∃) means "there exists."
• Predicates can be used to describe membership in a set, assign a value to a variable, or describe a relationship between variables.

Syntax and Semantics

• The syntax of predicate logic is defined by a set of rules that specify how formulas can be constructed.
• The semantics of predicate logic is defined by an interpretation, which consists of a domain of discourse, a function that assigns values to variables, and a function that assigns truth values to predicates.

Transformation Rules

• Predicate logic supports laws analogous to those in propositional logic.
• There are rules for the transformation of quantifiers, including negation, commutative, transposition, and merge laws.
• These laws can be used to transform formulas into different forms, but the rules are not always reversible.

Normal Forms

• A formula can be transformed into different normal forms, such as negation normal form (NNF), conjunctive normal form (CNF), and disjunctive normal form (DNF).
• Normal forms are not unique, and a formula can be transformed into multiple normal forms.

Resolution in Predicate Logic

• The resolution rule can be used to transform two clauses into a new clause, but it is more complex than in propositional logic.
• Unification is required to apply resolution in predicate logic, which involves finding a substitution that makes the literals in the two clauses identical.

Completeness and Incompleteness

• A calculus is sound if it derives only true formulas, and complete if it can derive all true formulas.
• David Hilbert's program aimed to develop a sound and complete calculus for mathematics.
• Kurt Gödel proved that predicate logic is complete, but also showed that any sufficiently powerful formal system is either incomplete or inconsistent.

Key Figures

• Bertrand Russell: a British mathematician, logician, and philosopher who published foundational work in logic.
• Kurt Gödel: an Austrian mathematician and logician who is famous for his incompleteness theorems.
• John Alan Robinson: a British philosopher and logician who is known for his work on resolution.### Gödel's Incompleteness Theorems
• Gödel's First Incompleteness Theorem: Any formal system that includes predicate logic and certain basic properties of arithmetic is either inconsistent or incomplete.
• This means that a formal system that is consistent contains tautologies that cannot be proved.
• Gödel's Second Incompleteness Theorem: Any consistent formal system that includes predicate logic and certain basic properties of arithmetic cannot prove its own consistency.

Implications of Gödel's Theorems

• There is no consistent and complete formal system that can serve as a basis for mathematics.
• Every attempt to define such a formal system will be unsuccessful since there will always be formulas that are true but cannot be proved.
• Gödel's theorems show that there is no algorithm that can determine the truth or falsehood of a statement in a formal system.

Goldbach's Conjecture

• Goldbach's conjecture states that every even integer n > 2 can be written as the sum of two prime numbers.
• Although no counterexample has been found, the conjecture remains unproven.

Diagonalization

• Gödel used diagonalization to prove his incompleteness theorems.
• Diagonalization is a technique to enumerate all possible formulas of a formal system.
• Gödel showed that a system cannot be consistent and complete at the same time.

Logic Programming with Prolog

• Prolog is a programming language based on a subset of predicate logic.
• Prolog is used for logic programming and is particularly well-suited for recursive computations.
• Prolog programs consist of facts and rules.

Prolog Syntax

• Every entry (fact, rule, and request) must be completed with a period and a line break.
• Comments are encapsulated in %.
• Variables start with an uppercase letter, while constants start with a lowercase letter.
• Predicates start with a lowercase letter and have the number of arguments specified.

Closed-World Assumption

• The closed-world assumption assumes that everything that is not true or cannot be derived from true statements is false.

Recursion

• Recursion requires the definition of a base case and a function or recursive step that reduces all successive cases towards the base case.
• Predicates can be defined recursively.

Search in Prolog

• Prolog searches for a variable assignment (the most general unifier) for which the request is identical to a fact in the knowledge base or can be traced back to such a fact.
• The procedure used by Prolog for processing a request involves searching for a unifier and then traversing the tree of potential solutions using a depth-first approach with backtracking.

Predicate Logic

• An extension of propositional logic, allowing for more complex conditions to be formulated.
• Introduces predicates, which are expressions that depend on variables, and quantifiers, which specify how many objects in the domain of discourse satisfy a formula.

Basic Concepts

• Quantifiers: universal quantifier (∀) and existential quantifier (∃).
• The universal quantifier (∀) means "for all," and the existential quantifier (∃) means "there exists."
• Predicates can be used to describe membership in a set, assign a value to a variable, or describe a relationship between variables.

Syntax and Semantics

• Syntax defined by a set of rules that specify how formulas can be constructed.
• Semantics defined by an interpretation, which consists of a domain of discourse, a function that assigns values to variables, and a function that assigns truth values to predicates.

Transformation Rules

• Laws analogous to those in propositional logic.
• Rules for the transformation of quantifiers, including negation, commutative, transposition, and merge laws.
• These laws can be used to transform formulas into different forms, but the rules are not always reversible.

Normal Forms

• A formula can be transformed into different normal forms, such as negation normal form (NNF), conjunctive normal form (CNF), and disjunctive normal form (DNF).
• Normal forms are not unique, and a formula can be transformed into multiple normal forms.

Resolution in Predicate Logic

• The resolution rule can be used to transform two clauses into a new clause, but it is more complex than in propositional logic.
• Unification is required to apply resolution in predicate logic, which involves finding a substitution that makes the literals in the two clauses identical.

Completeness and Incompleteness

• A calculus is sound if it derives only true formulas, and complete if it can derive all true formulas.
• David Hilbert's program aimed to develop a sound and complete calculus for mathematics.
• Kurt Gödel proved that predicate logic is complete, but also showed that any sufficiently powerful formal system is either incomplete or inconsistent.

Key Figures

• Bertrand Russell: a British mathematician, logician, and philosopher who published foundational work in logic.
• Kurt Gödel: an Austrian mathematician and logician who is famous for his incompleteness theorems.
• John Alan Robinson: a British philosopher and logician who is known for his work on resolution.

Gödel's Incompleteness Theorems

• Gödel's First Incompleteness Theorem: Any formal system that includes predicate logic and certain basic properties of arithmetic is either inconsistent or incomplete.
• Gödel's Second Incompleteness Theorem: Any consistent formal system that includes predicate logic and certain basic properties of arithmetic cannot prove its own consistency.

Implications of Gödel's Theorems

• There is no consistent and complete formal system that can serve as a basis for mathematics.
• Every attempt to define such a formal system will be unsuccessful since there will always be formulas that are true but cannot be proved.
• Gödel's theorems show that there is no algorithm that can determine the truth or falsehood of a statement in a formal system.

Goldbach's Conjecture

• Goldbach's conjecture states that every even integer n > 2 can be written as the sum of two prime numbers.
• Although no counterexample has been found, the conjecture remains unproven.

Diagonalization

• Gödel used diagonalization to prove his incompleteness theorems.
• Diagonalization is a technique to enumerate all possible formulas of a formal system.

Logic Programming with Prolog

• Prolog is a programming language based on a subset of predicate logic.
• Prolog is used for logic programming and is particularly well-suited for recursive computations.
• Prolog programs consist of facts and rules.

Prolog Syntax

• Every entry (fact, rule, and request) must be completed with a period and a line break.
• Comments are encapsulated in %.
• Variables start with an uppercase letter, while constants start with a lowercase letter.
• Predicates start with a lowercase letter and have the number of arguments specified.

Closed-World Assumption

• The closed-world assumption assumes that everything that is not true or cannot be derived from true statements is false.

Recursion

• Recursion requires the definition of a base case and a function or recursive step that reduces all successive cases towards the base case.
• Predicates can be defined recursively.

Search in Prolog

• Prolog searches for a variable assignment (the most general unifier) for which the request is identical to a fact in the knowledge base or can be traced back to such a fact.
• The procedure used by Prolog for processing a request involves searching for a unifier and then traversing the tree of potential solutions using a depth-first approach with backtracking.