[discrete mathematics review series] II. First order logic (predicate logic)

1. First order logic ( Predicate logic );
Individual words : An individual that exists alone , Can be specific , Abstract . As a man , draw , thought …
The predicate : Express the nature or relationship between the two, e.g … It's programmers A Than B high
Individual items : A word denoting a specific or particular individual
Individual variables : A word that refers to an individual in general
Individual domain : The value range of the individual variable , May be limited , Or infinite Such as the set of natural numbers
Total individual domain : The individual domain consists of everything in the universe
Predicate constant : The predicate of a specific property or relationship
Predicate variables : An abstract or generalized predicate
x Have the quality of F : Write it down as F(x)
x,y Have a relationship L: Write it down as L(x,y)
Element number : The number of individual words contained in the predicate is called .
contain n(n≥1) The predicate of each body word is called n Meta predicate . A unary predicate is one that expresses the nature of a body word .
When n≥2 when ,n The meta predicate represents the relationship between individual words
0 Meta predicate : Predicates without individual variables , Is to change individual predicate variable into individual predicate constant

2. Full name quantifier :

3. There are quantifiers :

example :

M（x）：x Is the person , Predicate for attribute

3. The symbolic alphabet of first-order logic

4. term :

5. Atomic formula : set up R(x1,x2,…xn) Is arbitrary n Meta predicate ,t1,t2,…, tn It's a , said R(t1,t2,…,tn).
The resultant formula ( Predicate formula ): Abbreviation formula

6. Guide variables : The resultant formula ∀xA and ∃xA Medium x
Jurisdiction : The resultant formula ∀xA and ∃xA Medium A
Constraints appear : In the scope x All the things that happened (x Constrained by the corresponding quantifier guiding variables )
Free to appear :A The occurrence of other variables that are not constraints in （ Variables that are not bound by quantifiers ）
example ：

Closed form formula ( Closed form ): If formula A There is no free individual variable in （ There are no unconstrained items ）

8. explain I: Generally speaking, it means that the uncertain items ( Elements , function , The predicate ) All assignment

Problem solving skills : Just bring in all the conditions
assignment : Given an explanation I, Assign an element in the individual field to each freely occurring individual variable in the formula
example

9. Logical efficient ( Yongzhen style ): set up A Is a predicate formula , If A True under any interpretation and any assignment under that interpretation
Paradoxical ( Permanent falsehood ):, If A False under any interpretation and any assignment under that interpretation
Satisfiability : If there is at least one interpretation and an assignment under that interpretation makes A It's true

11. Equivalent formula : set up A、B Are two formulas in first-order logic , if A<-→B Is a logically efficient form , Write it down as A<=>B
Important theorem :

notes :A(x) Is an arbitrary formula with free occurrence , and B It does not contain x The free emergence of

The toe in paradigm ： It refers to the whole quantifier or existential quantifier in front of the predicate formula
example :

notes : The purpose of changing names is to remove some constraints unrelated to a quantifier, such as （2） topic , Easy access to toe in （ quantifiers ）, If you can move forward directly, you don't need to change the yuan , Otherwise, you need to
Of course, the pre bundle normal form of predicate formula is not unique , such as （3） You can change your name before you bring it up , The result is also right
12. ending :
Socrates' syllogism “ All men die . Socrates is a man . So Socrates is going to die