4. Predicate logic

Question 1

Translate ‘john walks’ in predicate logic

Answer 1

Wj

Question 2

What is the existential quantifiër in predicate logic? Give an example

Answer 2

existential quantifiër: ∃
Some boy walks: ∃x(Bx ∧ W x)

Question 3

What is the universal quantifiër in predicate logic? Give an example

Answer 3

universal quantifiër: ∀
Every boy walks: ∀x(Bx → W x)

Question 4

Which predicate is bounded by ∀ in the expression: ∀x(Ax →Bx)

Answer 4

Only A

Question 5

Which predicate is bounded by ∃ in the expression: ∃x(Ax ∧ Bx).

Answer 5

Only A

Question 6

Predicate logic expression for symmetry

Answer 6

∀x∀y(Rxy → Ryx)

Question 7

Predicate logic expression for transitivity

Answer 7

∀x∀z∀y((Rxy ∧ Ryz) → Rxz)

Question 8

Predicate logic expression for linearity

Answer 8

∀x∀y(Rxy ∨ x = y ∨ Ryx)

Question 9

When is a predicate logic formula open?

Answer 9

When there is at least one variable occurens which is free (not bound)

Question 10

What is a close predicate logic formula and what else is it called?

Answer 10

When there are no free occurences of a variable, also called a sentence

Question 11

When is a quantifiër vacuous?

Answer 11

If the quantifiër ranges over an empty domain.
i.e. ∀x∃yRxx

Question 12

Give an example of substitution without quantifiër

Answer 12

Change variable Rxx if the substitution has ‘x substituted by y’ to Ryy

Question 13

Give an example of substitution with quantifiër

Answer 13

(∀yRxx) if x is substituted by y it changes to (∀yRyy)

Question 14

What is are ‘Alphabetic variants’, give an example

Answer 14

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

Question 15

When is a predicate logical formule P called ‘logically valid’?

Answer 15

If P is true in every model under ever assignment, |= ϕ

Question 16

When are two predicate formulas (p and q) logically equivalent?

Answer 16

If P ↔ Q is valid

Question 17

Describe predicate logic ‘valid consequence’

Answer 17

If q follows from p so that p |= q and q is never false if p is true.

Question 18

How do you specify the number of instances in a predicat logical formula?

Answer 18

exlemation mark followed by ^2 i.e. ∃!^n x

Question 19

How do we say: p follows from q ?

Answer 19

q |= p

Question 20

Does this hold ∀x∀y(Rxy → Ryx), Rab |= Rba ?

Answer 20

yes, we can pick a and b again in the conclusion

Question 21

Describe the ‘Universal Generalization’ rule

Answer 21

From ϕ infer ∀xϕ. Condition: x does not occur free in any premise which has been used in the proof of ϕ.

Question 22

Describe: soundness

Answer 22

Every theorem of predicate logic is valid

Question 23

Describe: Completeness

Answer 23

Every valid formula is a provable theorem

Question 24

Describe identity in predicate logic

Answer 24

Also called equality, use = and /=

Question 25

How to say: there is exactly one object with property P (no exlamation)

Answer 25

∃x (P x ∧ ∀y (P y → y = x))

Question 26

Describe: Function symbols

Answer 26

f, for example if f is the father function, f(x) gives the father of x

Question 27

Describe predicate logic Models.

Answer 27

M = (D, I)
D: The domain of objects
I: The interpretation function for objects from domain D

Question 28

The only interesting valid inference between 2-quantifier combinations

Answer 28

∃x∀yϕ implies ∀y∃xϕ.

Question 29

Does ∀ distributes over V ?

Answer 29

No, we know ∀x(Gx ∨ Bx) = ∀xGx ∨ ∀xBx doesn’t hold.

Question 30

Valid inference of ∀x∀yϕ

Answer 30

∀x∀yϕ ↔ ∀y∀xϕ

Question 31

Valid inference of ∃x∀yϕ

Answer 31

∃x∀yϕ implies ∀y∃xϕ

Question 32

Equivalence of: ¬∀x(Ax → Bx)

Answer 32

∃x¬(Ax → Bx) and ∃x(Ax ∧ ¬Bx)

Question 33

Equivalence of: ∀x(Ax → ¬Bx)

Answer 33

¬∃x¬(Ax → ¬Bx), and ¬∃x(Ax ∧ Bx).

Question 34

Parafrase: Not all A are B

Answer 34

Some A are not B

Question 35

Parafrase: All A are not B

Answer 35

there are no A that are also B