index.md (1461B)
1 +++ 2 title = 'Predicate Logic' 3 +++ 4 # Predicate Logic 5 ## Atomic formulas 6 7 role of propositional vars p,q,r is taken over by atomic formulas with objects and predicates 8 9 C(j) 10 11 - C is a unary predicate symbol 12 - can mean e.g. Jane (j) is clever (C) 13 14 K(a,b) 15 16 - K is a binary predicate symbol 17 - can mean e.g. A knows B 18 - A and B are objects a and b 19 20 ## Quantifiers 21 ∃x C(x) — somebody is clever 22 23 ∀x C(x) — everybody is clever 24 25 same priority level as for ¬ 26 27 ## Models 28 if L(r,j) means Robert loves Jane, it holds in M1 but not M2 29 30  31 32 meaning/truth value of a formula from predicate logic depends on underlying model M, consisting of: 33 34 - set A of elements 35 - interpretation of constants (r, j) 36 - interpretation of predicate symbols (L, C, K) 37 38 ∀x ϕ is true in M if true for *every* element in A 39 40 ∃x ϕ is true in M if true for *some* element in A 41 42 for each e ∈ A, ϕ [x := e] is true in M 43 44 ## Semantic entailment 45 for formula ϕ, M ⊨ ϕ means that ϕ is true in M 46 47 - tautology — true in all models 48 - contradiction — false in all models 49 - contingent — true in some model, false in another 50 - satisfiable — true in some model 51 52 ## Semantic equivalence 53 1. if for all models M, M ⊨ ϕ ⟷ M ⊨ Ψ 54 2. then ϕ ≡ Ψ 55 56 also, given that “nobody is perfect”, this holds: 57 > ¬∃x P(x) ≡ ∀x ¬P(x) 58 59 ## Alpha conversion 60 you can rename bound variables like in lambda calc 61 > ∀x C(x) ≡ ∀y C(y)