4. First-Order Logic

Question 1

Whats the definition of a well formed term for first-order logic?

Answer 1

The smallest set such that

• variable v in V is a term
• if f in F has arity n and t1, … tn are terms, so is f(t1, …, tn)

Where:

• V is a countably infinite set of variables
• F is a finite/countably infinite set of function letters each with an arity

Question 2

What is a constant in first order logic?

Answer 2

A function with an arity of zero

Question 3

What is the definition for a wff in first-order logic?

Answer 3

The smallest set such that

• if A in P has arity n and t1, …, tn are terms then A(t1, …, tn) is a wff
• if P and Q are wff, so are ¬P, P ∨ Q, P ∧ Q, P → Q, P ↔ Q
• if P is a wff, so are ∃x. P and ∀x. P for any x in V

where P is a countable infinite set of predicates each with an arity

Question 4

Whats the binding strength or ∀, ∃?

Answer 4

Weaker than any of the propositional connectives

Question 5

What is a bound variable (FOL)?

Answer 5

A variable x in formula P is bound if its within the scope of a quantifier

Question 6

What is a free variable (FOL)?

Answer 6

A variable that is not bound

Question 7

What does P[s/x] mean?

Answer 7

The formula obtained by substituting s for all free occurrences of x in P

Question 8

How can a relation r(x, y) be represented as a function in FOL?

Answer 8

f_r(x) = {y | r(x, y)}