Introduction to 1st Order Predicate Logic in Logical Thinking
Explore the limitations of propositional logic and the enhanced expressive power of 1st order predicate logic (PL1). Understand how PL1 allows for analyzing the structure of atomic propositions and proving arguments that depend on these structures. Through examples and valid argument schemata, delve into the complexities of relations between individuals and properties. Prepare to learn formal language, valid argument schemata, and advanced inference methods in the upcoming lessons.
Download Presentation
Please find below an Image/Link to download the presentation.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author. Download presentation by click this link. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
Presentation Transcript
1storder predicate logic Introduction to Logical Thinking, Lesson 5 Course Guarantor: Marek Men k Author of the slides: Marie Du 1
Language of the 1storder predicate logic (PL1) We have seen that the language of propositional logic (PL) has a lot of shortcomings; which is not to say that PL is not valuable. Just opposite, it is the basic logical system contained in other more expressive systems. Yet, the language of PL logic is rather poor in its expressive power. It makes it possible to compose propositions into molecular ones, but we cannot analyse the structure of atomic propositions. When evaluating or proving logical validity of an argument or a proposition, atomic propositions contribute only by its truth value. Hence, in PL we can prove only those arguments the validity of which does not depend on the structure of atomic propositions. Propositional logic = algebra of truth values. 2
Language of the 1storder predicate logic (PL1) Example of an obviously valid argument that cannot be proved in PL: All monkeys like bananas. Judy is a monkey. Judy likes bananas. From the point of view of PL, premises and conclusion are atomic propositions, p, q, r. But the PL argument p, q | r is not valid; at the valuation p=1, q=1 a r=0 the premises are true and conclusion false. Yet the argument is valid because assuming that Judy does not like bananas contradicts the premises. If Judy is a monkey and doesn t like bananas, then the first premise that all the monkeys like bananas cannot be true. 3
Language of the 1storder predicate logic (PL1) The argument has a valid schema: All P are Q. a is a P. a is a Q. If we substitute for the symbol P the property of being a monkey, for the symbol Q the property of liking bananas, and for the symbol a the individual Judy, we obtain the above valid argument. Similarly we can apply another valid schema: All P are Q. b is not a Q. b is not a P. Leaving interpretation of the symbols P and Q as above, and substituting for b individual Barty, we obtain another valid argument that is not provable in PL: All monkeys like bananas. Barty does not like bananas. Barty is not a monkey. 4
Language of the 1storder predicate logic (PL1) The structure of propositions can be more complex. Not only properties can be ascribed to individuals, but also relations between them. Consider, for instance, these assumptions: Everybody who likes George, cooperates with Milan. Milan is not in good friends with anybody who is a friend of Luke. Petr cooperates only with the friends of Charles. What follows from these assumption? For instance, that if Petr likes George, then Milan is a friend of Charles, and if Charles is a friend of Luke, then Petr does not like George. Yet, inferring these conclusions from our premises is not so trivial as above. Hence, we need to introduce a formal language, prove valid argument schemata and learn some more sophisticated methods of inferring consequences and proving the validity. This we are going to do in the rest of this course. 5
Language of the 1storder predicate logic (PL1) We need to talk about properties of the objects of interest (individuals) and about relations between them. To this end, we introduce predicate symbols. In addition, we need to refer to the individuals about whom we want to talk and assign them properties or relations. To this end, we introduce terms. Some claims are true for all or only some individuals. To this end we introduce quantifiers, namely (general) and (existential). Example: x [M(x) B(x)] M(j) B(j) Gloss. The formula x [M(x) B(x)] is read like this: for all ( ) individuals x it holds that if x has the property M (i.e. M(x)), then it has also the property B (i.e. B(x)). The formulas M(j) and B(j) mean that the individual j has the property M and B, respectively. 6
Language of the 1storder predicate logic (PL1) Some monkeys like bananas x [M(x) B(x)] The symbol x an individual variable. It refers to any element (individual) of the domain of interest (universe of discourse), namely depending on valuation v. In one valuation it can refer to the individual Judy and in another to Barty. Variables are atomic terms that refer to individuals. Mind! In propositional logic we deal with truth-value variables p, q, r, that stand for propositions, and refer to their truth values. However, in the 1st order predicate logic, we deal with individual variables that refer to the elements of the domain of interest; hence by their evaluation we obtain individuals. The symbols , are quantifiers, namely general ( ) and existential ( ). Roughly, their meaning is this. In order a formula x (F) or x (F) be true, the formula F must be true for some or all (respectively) individuals referred to by the variable x. 7
Language of the 1storder predicate logic The symbols O and B are predicates. In these formulas they represent properties of individuals. Predicate symbols can also represent relations between individuals. Example. x [L(x,g) C(x,m)] y [F(y,l) F(m,y)] z [C(p,z) F(z,c)] The symbols x, y, z are variables, the symbols L, C, F are predicate symbols. In the intended interpretation of the above example, the represent the relations Like, Cooperate, Friend, respectively. In addition, we have got here another kind of terms referring to individuals, namely constants: g, m, l, p a c. Constants rigorously refer to just one individual, independently of a valuation. In our intended interpretation, they refer to George, Milan, Luke, Petr and Charles. However, in another interpretation they can refer, e.g., to the numbers 1, 2, 3, 4, 5. 8
Definition of the PL1 language I) Alphabet consists of these symbols: a) Logical symbols Individual variables x, y, z,... (can be with subscripts) Symbols for connectives: , , , , Quantifiers , b) Special symbols Predicate symbols: P, Q, R, ... (can be with superscripts denoting arity) Functional symbols: f, g, h, ... (can be with superscripts denoting arity) c) Auxiliary symbols: (,), [,],{,} Arity is the number of arguments; By applying functional symbols to arguments, i.e. terms, we create molecular terms, e.g. f(a,b). For instance, if we interpret f as the adding function and constants a, b as the numbers 2, 3, we obtain application of the function + to the numbers 2, 3, i.e., +(2,3), or 2+3 in the infix mathematical notation. Then the term denotes the number 5. 9
Definition of the PL1 language II) Grammar that generates a) terms Each variable symbol is an atomic term If t1, , tn(n 0) are terms and f is n-ary functional symbol, then f(t1, ,tn) is a term; for n = 0 we have a ulary functional symbol, i.e. a constant, denoted a, b, c, ; for n > 0 we have a molecular term. Only expressions due to i) and ii) are terms b) formulas If P is an n-ary predicate symbol and t1, , tnare terms, then P(t1, ,tn) is an atomic formula If A is a formula, then A is a molecular formula If A and B are formulas, then (A B), (A B), (A B), (A B) are molecular formulas If x is a variable and A a formula, then x A and x A are molecular formulas Only expressions due to i) vi) are formulas 10
PL1 language; comments 1) In PL1 language, the only type of variables are individual variables that can be bound by quantifiers. (In the language of PL2 there are also predicate variables.) 2) Notational conventions for omitting parentheses: The outermost parentheses can be omitted. Parentheses can be omitted due to the following priority of symbols: ( , ), , , , , . In case the priority does not decide, we evaluate the formula from left to right. Since conjunction and disjunction are associative and commutative, parentheses are not necessary here. Anyway, similarly as in PL, we do not recommend to overuse priority conventions; It is better to insert parentheses whenever the structure of a formula might not be clear. 11
PL1 language; examples The following sequences of symbols are well-formed formulas: P(a), P(f(x),y) atomic formulas P(a) Q(x,y) R(a,x) conjunction of atomic formulas, parentheses omitted x y [P(a) Q(x,y) R(a,x)] parentheses here mark the scope of quantifiers Variable that occurs in the scope of a quantifier is bound. Bound variables behace in another way than free variables. Hence, we define: 12
Free and bound variables; definition Definice (free and bound variables) The occurrence of a variable x in a formula A is bound, if it occurs in a sub- formula of A that is of the form x B(x) or x B(x). Variable x is bound in a formula A, if x has in A a bound occurrence. The occurrence of a variable x in a formula A that is not bound is free. Variable x is free in a formula A, if x has in A a free occurrence. A formula is closed, if it does not contain any free variable. A formula that does contain at least one free variable is open. Note. Variable x can have both free and bound occurrences in a formula A. Anyway, we prefer to work with formulas with clear variables. They are the formulas in which all the occurrences of one and the same variable are either free or bound. 13
Free and bound variables; examples x [P(x) Q(a,y)] The variable x is bound in this formula, whereas the variable y is free. The formula is open. xP(x) Q(a,x) The first occurrence of x is bound, the second is free. The formula is open, and it is not a formula with clear variables. The second occurrence of x is actually another variable. Thus it would be more plausible to write this formula in a clear way, for instance as xP(x) Q(a,y) x y [P(x) Q(a,y)] The variable x is bound by general quantifier, the variable y is bound by existential quantifier. The formula is closed and it is the formula with clear variables. 14
Substitution We know that free variables denote any element of the universe, while terms without free variables a certain definite element of the universe. Hence, we can substitute only terms for free variables. Since free variables differ from bound ones, the substitution must not turn any variable occurring in the term as free to a bound one. Hence, we must protect substitution from the collision of variables. Let A(t/x) be formula that is obtained from A by the substitution of term t for the variable x. In order the substitution be correct, the term t must be substitutable for the variable x in the formula A. There are two rules for a correct substitution. 15
Correct substitution; two rules 1. Term t can be substituted only for all the free occurrences of the variable x in the formula A; hence, we replace all the free occurrences of the variable x by the term t in A. 2. Nofree variable occurring in the term t can become bound by the substitution t/x. Example. Let A(x) be P(x) yQ(x, y) and let term t be f(y). The substitution A(f(y)/x) yields the formula P(f(y)) yQ(f(y), y). We can see that the second occurrence of the variable y is bound.Such a substitution is incorrect. Hence, the term f(y) is not substitutable for x in the formula A. 16
Formalization in the PL1 language Expressions of a natural language that denote properties of individuals or relations between them are replaced by predicate symbols P, Q, R, etc. Expressions that denote functional mappings are replaced by functional symbols f, g, h, etc. Expressions like all , everybody , nobody , none are translated by the qeneral quantifier Expressions like somebody , some , something , there are , exists are translated by the existential quantifier . The other rules that we stated for the formalization in propositional logic are valid as well, as the PL1 language is an extension of the PL language. 17
Formalization in the PL1 language A natural language sentence that we want to formalize in PL1 should often be reformulated in an equivalent way, i.e., in such a way that the truth conditions of sentences remain the same. It is also useful to find more such equivalent formulations, and then check that the resulting formulas are, indeed, equivalent (have the same models). Now we will make it only intuitively. Later we will also learn some useful equivalent transformations of formulas. Example. Only employees use the lift (is equivalent) If somebody is not an employee, then they do not use the lift There is nobody who would use the lift and were not an employee x [L(x) E(x)] x [ E(x) L(x)] x [L(x) E(x)] The first equivalence is due to transposition of implication; the second is application of de Morgan law. 18
Formalization in the PL1 language Example. Some prime numbers are even There is an x such that Prime(x) and Even(x) x [P(x) E(x)] Another equivalent formulation: It is not true that no prime is even x [P(x) E(x)] (checking) x [P(x) S(x)] x [ P(x) S(x)] x [P(x) S(x)] We can see that our formalization is correct, as all the formulas we obtained are equivalent; In the last line we again applied de Morgan law. 19
De Morgan laws (for negating quantified formulas) If it is not true that all x satisfy the condition specified by the formula A, i.e. x (A), then some x do not satisfy this condition, i.e. x (A), and vice versa: x (A) x (A) If it is not true that some x satisfy the condition specified by the formula A, i.e. x (A), then no x satisfies this condition, i.e. x (A), and vice versa: x (A) x (A) Mind! The last formula x (A) is read as No x is A . If we read it as All x are not A , it would have different meaning. It would mean Not all x are A , hence Some x are not A . 20
De Morgan laws Recall de Morgan laws in propositional logic for negation of conjunction and disjunction. If it is not true that A and B, i.e. (A B), then non-A or non-B, i.e. ( A B), and vice versa. (A B) ( A B) If it is not true that A and B, i.e. (A B), then neither-A, nor-B, i.e. ( A B), and vice versa. (A B) ( A B) 21
Formalization in the PL1 language Example. No prime number greater than 2 is even For all x it holds that if (Prime(x) and Greater x than 2), then notEven(x) x [(P(x) G(x,2)) E(x)] Equivalently: It is not true that some prime numbers greater than 2 are even x [(P(x) G(x,2)) E(x)] (check) x [(P(x) G(x,2)) E(x)] x [ (P(x) G(x,2)) E(x)] x [(P(x) G(x,2)) E(x)] In the last line, we have applied an important law of propositional logic that should be remembered: ( A B) (A B) Check this law by a truth table. 22
The sense of quantifiers Imagine that we work with a finite universe of discourse, i.e. the set {a1, a2, , an}. Then the statement that the condition F is valid for all the elements of discourse, i.e. x F(x), is equivalent to the statement that the condition is valid for a1 and a2 and, , an. Hence, that the formula F(a1) F(a2) F(an) is true. Similarly, the statement that the condition F is valid for some elements of discourse, i.e. x F(x), is equivalent to the statement that this condition is valid for a1 or a2or, , an, i.e. that the formula F(a1) F(a2) F(an) is true. But if the universe is infinite (for instance the set of natural numbers {0,1,2, , }), then it is impossible to write an infinite conjunction or disjunction. Hence, to this end we use quantifiers. General quantifier can be viewed as the generalization of conjunction and existential quantifier as a generalization of disjunction for an infinite number of elements. Schematically: x F(x) F(a1) F(a2) F(an) x F(x) F(a1) F(a2) F(an) 23
The sense of quantifiers Now the sense of de Morgan laws should also be clear. Again schematically, as an infinite conjunction or disjunction are not well- formed formulas: x F(x) (F(a1) F(a2) F(an) ) ( F(a1) F(a2) F(an) ) x F(x) x F(x) (F(a1) F(a2) F(an) ) ( F(a1) F(a2) F(an) ) x F(x) 24
Important tenets of formalization Sentences of the type Some P are Q analyse as x [P(x) Q(x)] Sentences of the type All P jare Q analyse as x [P(x) Q(x)]. Schema: x - , x - 25
Checking the correctness of analysis; negation Some students (S) have a job (H) There is an x such that x is a student and x has a job x [S(x) H(x)] It is not true that some students have a job No student has a job It holds for all x that if x is a student then x doesn t have a job x [S(x) H(x)] x [S(x) H(x)] x [ S(x) H(x)] x [S(x) H(x)] All students (S) have a job (H) It holds for all x that if x is a student then x has a job x [S(x) H(x)] It is not true that all students have a job Some students don t have a job x [S(x) H(x)] x [S(x) H(x)] x [ S(x) H(x)] x [S(x) H(x)] 26
