Created: 2025-12-15 12:48 by Thom
Predicate logic, this is also one of the topics covered in the course Formal Reasoning at Radboud University, reader can be found here. Instead of understanding the truth of a sentence, you write sentences in a formal way. And again you use dictionaries like in propositional logic. Example ` AA w in W [ ( EE x in ( M uu W) L(w,x) ) -> H(w) ]``^^ AA m in M [ ( EE x in (M uu W) L(x,m) ) -> H(m) ] ` In this example there are several new items, like `AA` which is for all and `EE` which is there exists. `in` is membership in a set. And `uu` is the union of two sets. Relations and constants In propositional logic there were propositional atoms, like R for it is Raining and such, but if you want to have something as Sharon is Happy with SH you might also want Maud, Jonan, Pien etc. this will become very cumbersome to add. This is why predicate logic uses predicates, these then get applied onto subjects. Instead of writing SH for Shanon is Happy we can write it like H(s), now more subjects can be used, H(m), H(j), H(p) etc. etc. Subjects (more constants) need to be in a certain domain, this is indicated with the `in` sign. Example `s in W` and `j in M`. Using a predicate like H (x is happy) we also like to have binary predicates like L (x loves y). Using an `^^` symbol is very useful here, because this can in a sentence show what character is meant. It makes explicit the ambiguities that often occur in the English (or any other natural) language. The language Predicate logic is built up from the following items [1]: 1. Variables, usually `x, y, x_1, y_1` etc. 2. Individual constants, like a, b, c or s, j and p. 3. Domains, M, W, E. 4. Relation symbols, usually with a fixed arity `P^1, P^2, T^2` and so on. 5. The atoms, or atomic formulas which are as follow, `P^1(t), R^2(t,y)`. t and y here are variables or individuals. 6. Formulas, - Every atomic formula is a formula - If f and g are formulas, then so are `(f ^^ g)`, `(f vv g)`, `(f -> g)`, `(f harr g)`, `not f`. - f f is a formula, and x is a variable, and D is a domain, then `(AA x in D f )` and `(EE x in D f )` are also formulas, made with the quantifiers ‘` AA `’ and ‘` EE `’. `AA` and `EE` both bind stronger than all other connectives. For this course the convention is to write `AA x in D [ f ]`. One thing that is not very obvious is that if you have a quantifier not all connectives can be used, for `AA` you use `->` and for `EE` you use `^^`, to give an example from Huth and Ryan, `not ( AA x ( B(x) -> F(x) ) )` and `EE x ( B(x) ^^ not F(x))`. These two formula's say the same thing, but with `AA` you can't use `^^` and with `EE` thus not `->`. Freek and Engelbert make this even less obvious by writing these sentence more like, `not (AA x in B [ F(x) ])` and `EE x in B [ not F(x) ]`. Determining truth When is a formula true? This depends on the structure and interpretation of the `cancel("computer programs")` model that is used. Interpretation is given by a dictionary which states, 1. Which sets are referred to by the domain symbols. 2. which subjects are referred to by the names (and to which domain sets these belong). 3. and which predicates and relations are referred to by the predicate and relation symbols. What are structures? These are things from the 'real' world. Where you map them to a domain, constant, predicates and relations. Domain is like all humans in a lecture hall, a predicate can be is more than 20 years old, relations are maybe who they're sitting next to and constants can be students itself, like Thom. We can then define models like this, a model is a pair (M, I) where M is a structure and I an interpretation. To denote if a formula f is true under some model we do, `(M,I) |== f`. This pair can also include subscript numbers, `(M_7, I_6)` etc. and if there isn't a specific structure this can also be done: `((NN, lt), I_7) |== f`. When no model is given `|== f`, f here is then valid or logically true in any structure and interpretation. But we omit `|==`. Suppose f and g are two formulas of predicate logic. We say that g follows from f, denoted as `f |== g`, when `|== f -> g`. Which means that in every situation in which f is true, g is true as well. But there is more, `f -= g`, `|== f harr g` are all the same. Predicate logic with equality How would you formalise this "Sharon is intelligent; there is a man who pays attention to nobody else."? To make this possible equality has to be added, now you can write something like this "`I(s) ^^ EE x in M [ A(x,s) ^^ AA w in W [ A(x,w) -> w = s]]`". The definition is as follows, if x and y are variables, and a and b are constants, then `(x = y)`, `(x = a)`, `(a = x)`, and `(a = b)` are formulas as well. Equality here binds stronger than the quantifiers, and connectives. Inequality is not needed because you can say something like `not (a = b)`. Counting is very easy now with equality such as having one object, two objects etc. `N(s) ^^ AA x in H [N(x) -> x = s]` now translates to "Only Sharon is nice", because she is the only human being that is nice and that human being is Sharon. Logical laws These are not directly mentioned in the Formal Reasoning course notes, but are very useful to know. Law of negation is first, `not EE x in D [ P(x) ] iff AA x in D [ not P(x) ] `. Universal generalisation law, if P(a) is true for any arbitrary a, then `AA x in D [ P(x) ]` is true. And existential generalisation is if `EE x in D [ P(x) ]` is true, then we can assume P(a) for some specific a. Applications There are a lot of use cases with predicate logic, mostly in AI. But also a lot of CS topics. Mathematics Formalising proofs is probably the biggest use case of predicate logic. And naturally also set theory. Computer Science SQL uses predicate logic for querying databases, where predicates filter data based on conditions. Then for AI, predicate logic is used in knowledge representation and reasoning systems to model facts and rules. Predicate logic is also used for software verification but modal logic is much more useful for this. Engineering Predicate logic can be applied in designing systems that require precise specifications and conditions. [1] A grammar is also defined like this, Individual := Variable | Name Variable := `x, y, z, x_1, y_1, z_1, ...` Name := `a, b, c, d, e, ...` Domain := `D, E, ...` Atom := `P^1(`Individual`)` | `R^2(`Individual,Individual`)` | `T^3(`Individual,Individual,Individual`)` | `...` Formula := Atom | `not `Formula | `(`Formula` -> `Formula`)` | `(`Formula` ^^ `Formula`)` | `(`Formula` vv `Formula`)` | `(`Formula` harr `Formula`)` | `(AA `Variable` in `Domain Formula`)` | `(EE `Variable` in `Domain Formula`)`