4. Predicate logic Flashcards
Translate ‘john walks’ in predicate logic
Wj
What is the existential quantifiër in predicate logic? Give an example
existential quantifiër: ∃
Some boy walks: ∃x(Bx ∧ W x)
What is the universal quantifiër in predicate logic? Give an example
universal quantifiër: ∀
Every boy walks: ∀x(Bx → W x)
Which predicate is bounded by ∀ in the expression: ∀x(Ax →Bx)
Only A
Which predicate is bounded by ∃ in the expression: ∃x(Ax ∧ Bx).
Only A
Predicate logic expression for symmetry
∀x∀y(Rxy → Ryx)
Predicate logic expression for transitivity
∀x∀z∀y((Rxy ∧ Ryz) → Rxz)
Predicate logic expression for linearity
∀x∀y(Rxy ∨ x = y ∨ Ryx)
When is a predicate logic formula open?
When there is at least one variable occurens which is free (not bound)
What is a close predicate logic formula and what else is it called?
When there are no free occurences of a variable, also called a sentence
When is a quantifiër vacuous?
If the quantifiër ranges over an empty domain.
i.e. ∀x∃yRxx
Give an example of substitution without quantifiër
Change variable Rxx if the substitution has ‘x substituted by y’ to Ryy
Give an example of substitution with quantifiër
(∀yRxx) if x is substituted by y it changes to (∀yRyy)
What is are ‘Alphabetic variants’, give an example
If the quantification patterns are the same, but with differ in the variables they quantifiy over.
i.e. ∀xRxx and ∀yRyy
∀x∃yRxy and ∀z∃xRzx
When is a predicate logical formule P called ‘logically valid’?
If P is true in every model under ever assignment, |= ϕ
When are two predicate formulas (p and q) logically equivalent?
If P ↔ Q is valid
Describe predicate logic ‘valid consequence’
If q follows from p so that p |= q and q is never false if p is true.
How do you specify the number of instances in a predicat logical formula?
exlemation mark followed by ^2 i.e. ∃!^n x
How do we say: p follows from q ?
q |= p
Does this hold ∀x∀y(Rxy → Ryx), Rab |= Rba ?
yes, we can pick a and b again in the conclusion
Describe the ‘Universal Generalization’ rule
From ϕ infer ∀xϕ. Condition: x does not occur free in any premise which has been used in the proof of ϕ.
Describe: soundness
Every theorem of predicate logic is valid
Describe: Completeness
Every valid formula is a provable theorem
Describe identity in predicate logic
Also called equality, use = and /=
How to say: there is exactly one object with property P (no exlamation)
∃x (P x ∧ ∀y (P y → y = x))
Describe: Function symbols
f, for example if f is the father function, f(x) gives the father of x
Describe predicate logic Models.
M = (D, I)
D: The domain of objects
I: The interpretation function for objects from domain D
The only interesting valid inference between 2-quantifier combinations
∃x∀yϕ implies ∀y∃xϕ.
Does ∀ distributes over V ?
No, we know ∀x(Gx ∨ Bx) = ∀xGx ∨ ∀xBx doesn’t hold.
Valid inference of ∀x∀yϕ
∀x∀yϕ ↔ ∀y∀xϕ
Valid inference of ∃x∀yϕ
∃x∀yϕ implies ∀y∃xϕ
Equivalence of: ¬∀x(Ax → Bx)
∃x¬(Ax → Bx) and ∃x(Ax ∧ ¬Bx)
Equivalence of: ∀x(Ax → ¬Bx)
¬∃x¬(Ax → ¬Bx), and ¬∃x(Ax ∧ Bx).
Parafrase: Not all A are B
Some A are not B
Parafrase: All A are not B
there are no A that are also B
