Overview
In discrete mathematics, let R() be any n-ary predicate of Γ, and t1, t2,..., tn are any n items of any F, then R(t1 ,t2,...tn) is the atomic formula of Γ. Usually, an atomic formula is composed of several predicate symbols and terms. Constant symbols are the simplest terms used to represent objects or entities in the domain. It can be actual objects, concepts or things with names, and variable symbols are also Item, it does not have to involve which entity it is. Well-formed formulas in logical systems are usually defined recursively by identifying all valid atomic formulas and giving rules for formulating formulas from two atomic formulas. Formulas made from atomic formulas are compound formulas.
For example, there are the following formula construction rules in propositional logic:
Any propositional variable p is a well-formed atomic formula.
Given any formula A, deny that ¬A ("not A") is a well-formed formula.
Given any two formulas A and B, the conjunction A∧B ("A and B") is a well-formed formula.
Given any two formulas A and B, the disjunction A∨B ("A or B") is a well-formed formula.
Given any two formulas A and B, implication A⇒B ("A implies B") is a well-formed formula.
So, we can construct arbitrarily complex compound formulas, for example, from simple atomic formulas p, q and r and our construction rules ((p∧¬(q⇒r)))∨ ¬p).
Predicate logic
Introduction
You can often see statements containing variables in mathematical assertions, computer programs, and system specifications, such as the statement "x is greater than 3 ", the predicate is "greater than 3", the predicate indicates a property of the subject of the sentence.
Predicate logic is a kind of logic model, it is the most accurate way to express thinking and reasoning so far, and it is the most widely used way of expressing knowledge. The basic components of predicate logic are predicate symbols, variable symbols, and constant symbols, separated by parentheses, square brackets, curly brackets, and commas to indicate the relationship within the domain. It can also be called first-order logic. Predicate logic is also divided into classic predicate logic and non-classical predicate logic. The latter includes non-classical propositional logic as a subsystem. Classical first-order predicate logic is the basic part of predicate logic. The first complete predicate logic system was established by G. Frege in 1879. K. Gödel and others systematically studied the meta-logic problems of predicate logic and proved important theorems.
In predicate logic, you should pay attention to the following points when using quantifiers:
(1) In different individual domains, the form of proposition symbolization may be different, and the truth value of the proposition may also be Will change.
(2) When considering the symbolization of propositions, if the individual domain is not explained, the total individual domain shall be used.
(3) When multiple quantifiers appear, the order of them cannot be reversed at will, otherwise the meaning of the proposition may be changed.
The predicate formula is just a symbol string, meaningless, but we give this symbol string an explanation, make it have a truth value, it becomes a proposition. The so-called explanation is to make each variable in the formula correspond to the elements in the individual domain.
In predicate logic, proposition symbolization must specify the individual domain, and it is considered as the total individual domain without special instructions. In general, use the universal quantifier ", use ® after the characteristic predicate; use the existence quantifier $, use Ù after the characteristic predicate;
Axiom system
A universally valid formula for predicate logic In a certain sense, they are all logical laws. In order to study these laws systematically, we need to consider them as a whole and include them in a system. Predicate calculus or first-order predicate calculus is such a system. Predicate calculus is a formal system established by the axiomatization and formalization of predicate logic. According to different selections of the initial symbols, axioms and deformation rules that are the starting point of the calculus, different predicate calculus systems can be established. There is a symbol = in the initial symbol , Known as the first-order predicate calculus with equal words, equal words = is a predicate constant; the system without equal words is called (first-order) predicate calculus. The basic elements that constitute a predicate logic axiom system are: initial Symbols, formation rules, axioms and deformation rules, etc. This can be explained from a system F without equal words. The initial symbols of F include individual variables, predicate variables, connectives and quantifiers, and technical symbols. The lowercase Latin letters of individual variable symbols are: x,y,z,x1,y1,z1,x2,...; the predicate variable symbols are uppercase Latin letters, namely: F,G,H,F1,G1,.... In principle, for each n≥1, n-ary predicate variables should be listed separately, such as: F1, G1, H1,...; F2, G2, H2,...; etc. However, omit the superscript 1, 2,...,n, there will be no confusion in practice. The connective and quantifier symbols are: 塡, →, 凬; technical symbols are brackets (,) and commas. The formation rules stipulate what symbol sequence or combination of symbols is The well-formed formula in F. The well-formed formula is meaningful after explanation. The language used to describe and discuss the F system, that is, the symbols of the metalanguage are: lowercase Greek letters α, α1, …, αn, δ represent arbitrary individual variables ; Fn represents any n-ary predicate variable; capital Latin letters X, Y represent any sequence of symbols. These symbols are called grammatical variables. There are four rules for the formation of F: ①If fn is an n-ary predicate variable, α1,…,αn are individual variables, then fn(α1,…,αn) is a combined formula;
②If X is a combined formula, then X is a combined formula. If X, Y are A well-formed formula, then (X→Y) is a well-formed formula;
③If X is a well-formed formula and α is an individual variable, then (凬α)X is a well-formed formula;
④The only suitable formulas for the above ①～③ are well-formed formulas. Well-formed formulas are abbreviated as formulas. Use letters A, B, and C to represent arbitrary formulas. A, B, and C are also grammatical variables and belong to the metalanguage.
Well-formed formula
The propositional formula is the object of propositional logic discussion, and any number of compound propositions can be formed by the use of connectives from the propositional variables, such as P∧Q, P∧Q∨R, P→Q, etc. The question is whether they all have meaning? The proposition P,P∧Q,P→Q with only one connective is of course meaningful. The proposition P∧Q∨R composed of two connectives is at least unclear. Should we make P∧Q first and then do ∨ to R, or do Q∨R first and then do ∧ to P? P∧Q has the same problem. . It is easy to solve the order of operations. You can use parentheses like elementary algebra. Parentheses are often used in logical operations to distinguish the order of operations. In this way, all the symbols of propositional logic are composed of propositional variables, propositional connectives and parentheses. The further problem is to establish a general principle in order to generate all legal propositional formulas, and to be able to identify what kind of symbol strings are legal.
In formal logic, the proof is a WFF sequence with specific properties, and the final WFF in the sequence is to be proved.
The definition of a well-formed formula (abbreviated as Wff):
1. A simple proposition is a well-formed formula.
2. If A is a well-formed formula, then A is also a well-formed formula.
3. If A and B are well-formed formulas, then (A∧B), (A∨B), (A→B) and (AB) are well-formed formulas.
4. It is a well-formed formula if and only if the symbol string composed of 1.2.3 is used for a limited number of times.
This definition gives the general principle of establishing a well-formed formula, and also the principle of identifying whether a string of symbols is a well-formed formula.
This is the definition of recursion (induction). In the definition, the concept to be defined is used. For example, in 2 and 3, the well-formed formula to be defined appears. Secondly, the definition specifies the initial situation. For example, 1 indicates that the known simple proposition is a well-formed formula.
Condition 4 explains what is not a well-formed formula, but 1, 2, and 3 cannot explain this.
According to the definition, if a formula is judged whether it is a well-formed formula, it must be freed and returned to a simple proposition before it can be judged.
(P∧Q),(P→(P∧Q)),
((((P→Q)∧(Q→R))(P→R)) They are all well-formed formulas. And P∨Q∨,((P→Q)→(∧Q)),(P→Q is not a well-formed formula, meaningless, we will not discuss it.
In actual use, in order to reduce the circle The number of brackets can introduce some conventions, such as the way to specify the priority of conjunctions, which can be arranged in the order of, ∨, ∧, →, and multiple identical conjunctions are given priority from left to right. In this way , When writing a well-formed formula, you can omit part or all of the parentheses. Usually the method of omitting part of the parentheses and retaining part of the parentheses is used, so that the choice will bring convenience to the reading of the formula. For example,
(P→( Q∨R)) can be written as P→(Q∨R) or P→Q∨R.
(P→(P→R)) can be written as P→(P→R).
Only combined formulas are discussed in propositional calculus. For convenience, combined formulas are called formulas.