Understanding First-Order Predicate Logic in Computer Science Education
Exploring the concepts of first-order predicate logic in computer science, this content delves into the formal language, grammar, and logical form of arguments. It covers the importance of moving beyond propositional logic, introduces valid schemata, and illustrates the structure of atomic and composed formulas. Through examples and visual aids, it illustrates how FOL expands the capabilities of logical reasoning.
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.
E N D
Presentation Transcript
Department of Computer Science, Faculty of Electrical Engineering and Computer Science, VSB - Technical University of Ostrava 1st-order Predicate Logic (FOL) 1
Simple arguments, where propositional logic does not suffice All monkeys like bananas. Judy is a monkey. Judy likes bananas. From the viewpoint of Propositional Logic (PL) the above are simple (atomic) sentences: p, q, r, and p, q does not entail r. All students are clever Charles is not clever Charles is not a student What are the valid schemata of these arguments? 2
Logical form (scheme) of an argument The schemata of the arguments above remind valid schemata of PL: p q, p |= q (modus ponens) or p q, q |= p (modus tollens) But, in PL we cannot refine the analyses of simple sentences. Let us reformulate them: 1. Every individual, if it is a Monkey, then it likes Bananas 2. Judy is an individual with the property of being a Monkey 3. Judy is an individual that likes Bananas x [M(x) B(x)], M(J) |= B(J), where x is an individual variable, M, B are predicate symbols, J is a functional symbol It is again a schema: For M, B, J we can substitute other properties and individual, respectively. For instance, man for M, mortal for B and Charles for J. M, B, J are here only symbols which stand for properties and individuals 3
Formal language of FOL (first-order predicate logic) Alphabet Logical symbols individual variables: x, y, z, ... Symbols for truth-connectives: , , , , Symbols for quantifiers: , Special symbols Predicate: Pn, Qn, ... n arity = number of arguments -- -- Functional: fn, gn, hn, ... Auxiliary symbols: (, ), [, ], {, }, ... 4
Formal language of FOL Grammar terms: each symbol for a variable x, y, ... is a term if t1, ,tn(n 0) are terms and if f is an n-ary functional symbol, then the expression f(t1, ,tn) is a term; If n = 0, then we talk about individual constant (denoted a, b, c, ) only expressions due to i. and ii. are terms i. ii. iii. 5
Formal language of FOL Grammar atomic formulas: If P is an n-ary predicate symbol and if t1, ,tnare terms, then P(t1, ,tn) is an atomic formula (composed) formulas: each atomic formula is a formula if A is a formula, then A is a formula if A and B are formulas, then (A B), (A B), (A B), (A B) are formulas if x is a variable and A a formula, then x A and x A are formulas 6
Formal language of FOL 1st-order Example: Leibniz s definition of identity: If two individuals have all the properties identical, then it is one and the same individual P [ P(x) = P(y)] (x = y) here we need a 2nd-order language, because we quantify over properties We can quantify only over individual variables We cannot quantify over properties or functions 7
Example: the language of arithmetic We need special functional symbols: 0-ary symbol: 0 (the constant zero) constant is a 0-ary functional symbol unary symbol: s (the successor function) binary symbols: + and (functions of adding and multiplying) Examples of terms (using infix notation for + and ): 0, s(x), s(s(x)), (x + y) s(s(0)), etc. Formulas are, e.g.: (= is here a special predicate symbol): s(0) = (0 x) + s(0), x (y = x z), x [(x = y) y (x = s(y))] 8
Transforming natural language into the language of FOL all , every , none , nobody , any , ... somebody , something , some , there is , ... A sentence often needs to be reformulated (in an equivalent way) No student is retired (For any student it holds that he is not retired): x [S(x) R(x)] But: Not all students are retired (It is not true that any student is retired): x [S(x) R(x)] x [S(x) R(x)] 9
Transforming natural language into the language of FOL An auxiliary rule: + , + (almost always) x [P(x) Q(x)] x [P(x) Q(x)] It is not true that all P s are Q s Some P s are not Q s x [P(x) Q(x)] x [P(x) Q(x)] It is not true that some P s are Q s No P is a Q de Morgan laws in FOL 10
Transforming natural language into the language of FOL The lift is used only by employees x [L(x) E(x)] All employees use the lift x [E(x) L(x)] Mary likes only the winners: Hence, for all individuals it holds that if Mary likes him then he must be a winner: x [L(m, x) W(x)], to like is a binary relation, not a property !!! 11
Transforming natural language into the language of FOL Everybody loves somebody sometimes x y t L(x, y, t) Everybody loves somebody sometimes but Hitler doesn t like anybody x y t L(x, y, t) z L (h, z) Everybody loves nobody ambiguous Nobody loves anybody ambiguous; Everybody dislikes anybody: x y L (x, y) x y L (x, y) 12
Introduction: valid arguments x y P(x, y, t) x Q(y, x) Formula with clear variables: each variable has only free occurrences, or only bound occurrences; each quantifier has its own variables . bound, free free, bound For instance, the above formula does not have clear variables: x in the second conjunct is another variable than the x in the first conjunct, similarly for y. Clear formula: x y P(x, y, t) z Q(u, z) 13
Substitution of terms for variables A(x/t) arises from A by a correct (i.e., collisionless) substitution of a termt for the variablex. There are two rules for a correct substitution: We can substitute a term t only for free occurrences of a variable x in a formula A, and we have to substitute for all the free occurrences. No individual variable that occurrs in the term t can become bound in A (in such a case the term t is not substitutable for x in the formula A). 14
Substitution, example A(x): P(x) y Q(x, y), term t = f(y) After executing the substitution A(x/f(y)), we obtain: P(f(y)) y Q(f(y), y). The term f(y) is not substitutable for x in A We d change the sense of the formula 15
Semantics of FOL P(x) y Q(x, y) is this formula true? A non-reasonable question; For, we do not know what the symbols P, Q mean, what they stand for. They are only symbols which can stand for any predicate (property). P(x) P(x) is this formula true? YES, it is; and it is always so, in all the circumstances. It is necessarily true. 16
Semantics of FOL x P(x, f(x)) x P(x , f(x)) 1) What do they talk about; we have to choose the universe of discourse: any non-empty set U 2) What does the symbol P denote; it is binary, with two arguments; it has to denote a binary relation R U U 3) What does the symbol f denote; it is an unary, one-argument symbol; it has to denote a function F U U, denoted F: U U we have to specify first, how to understand these formulas: 17
Semantics of FOL A: x P(x, f(x)) we have to specify B: x P(x , f(x)) how to understand these formulas: 1) Let U = N (the set of natural numbers) 2) let P denote the relation < (i.e., the set of pairs, where the first element is strictly less than the second one: { 0,1 , 0,2 , , 1,2 , }) 3) Let f denote the function second power x2, i.e., the set of pairs where the second element is the power of the first one: { 0,0 , 1,1 , 2,4 , , 5,25 , } Now we can evaluate the truth values of the formulas A, B 18
Semantics of FOL A: x P(x, f(x)) B: x P(x , f(x)) We evaluate from the inside : First evaluate the term f(x). Each term denotes an element of the universe. Which one? It depends on the valuation e of the variable x. Let e(x) = 0, then f(x) = x2 = 0. Let e(x) = 1, then f(x) = x2 = 1, Let e(x) = 2, then f(x) = x2 = 4, etc. Now by evaluating P(x , f(x)) we have to obtain a truth value: e(x) = 0, 0 is not < 0 False e(x) = 1, 1 is not < 1 False, e(x) = 2, 2 is < 4 True. 19
Semantics of FOL A: x P(x, f(x)) B: x P(x , f(x)) The formula P(x , f(x)) is in the given interpretation True for some valuations of the variable x, and False for other valuations. The meaning of x ( x): the formula is true for all (some) valuations of x Formula A: False in our interpretation I: | IA Formula B: True in the interpretation I: |=IB 20
Model of a formula, interpretation A: x P(x, f(x)) B: x P(x , f(x)) We have found an interpretation I in which the formula B is true. The Interpretation structure N, <, x2 satisfies the formula B; it is a model of the formula B. How to adjust the interpretation in order it were a model of the formula A? There are infinitely many possibilities, infinitely many models. For instance: N, <, x+1 , {N/{0,1}, <, x2 , N, , x2 , All the models of the formula A are also models of the formula B ( what holds for all, it holds also for some ) 21
Model of a formula, interpretation C: x P(x, f(y))what are the models of this formula (with a free variable y)? Let us again 1. choose a Universe U = N 2. to the symbol P assign a relation: 3. to the symbol f assign a function: x2 Is the structure IS = N, , power a model of the formula C? In order it were so, the formula C would have to be true in IS for all the valuations of the variable y. Hence the formula P(x, f(y)) would have to be true for all valuations of x and y. But it is not so, for instance, if e(x) = 5, e(y) = 2, then 5 is not 22 22
Model of a formula, interpretation C: x P(x, f(y)) what are the models of this formula (with a free variable y)? The structure N, , x2 is not a model of formula C. A (trivial) model is, e.g., N, N N, x2 . The whole Cartesian product N N, i.e. the set of all the pairs of natural numbers, is also a relation over N. Or, the structure N, , F , where F is the function, mapping N N, such that F associates all the natural numbers with the number 0. 23
