First Order Logic

Question 1

4 Logical symbols

Answer 1

• Punctuation: parentheses and commas: ( and ) and ,
• Connectives: ∧, ∨, ¬, →
• Quantifiers: ∃, ∀
• Variables: an infinite supply of these, usually written x, y etc and sometimes x₁, x₂, etc.

Question 2

3 Non-logical symbols

Answer 2

• Constant symbols
• Relation symbols
• Proposition symbols

Question 3

Terms

Answer 3

Terms are linguistic entities that can refer to individual things.

Don’t confuse terms with formulas, which can have truth values.

Question 4

3 Rules for building terms

Answer 4

• Every variable is a term.
• Every constant symbol is a term.
• Nothing else is a term.

Question 5

Formulas

Answer 5

Things in the language that can have truth values.

Don’t confuse formulas with terms, which can refer to individual things.

Question 6

5 Rules for formulas

Answer 6

• Every propositional symbol is a formula
• If P is a predicate symbol of arity n≥1 and t₁, …, tₙ are terms, then P(t₁, …, tₙ) is a formula.
• If ɑ and β are formulas, then these are formulas:
  
  • ¬ɑ
  • (ɑ ∨ β)
  • (ɑ ∧ β)
• If x is a variable and ɑ is a formula, then ∀x ɑ and ∃x ɑ are formulas.
• Nothing else is a formula.

Question 7

4 Items required to specify an interpretation

Answer 7

• Give a non-empty set, D, called the domain.
• For each constant symbol, give the element of D for it.
• For each n-ary relation symbol, give an n-ary relation on D.
• For each propositional symbol, give a truth value.

Question 8

The domain

Answer 8

There is no restriction on what the elements of D are:

• They can be abstract (numbers, symbols, mathematical structures such as sets.
• They can be physical concrete things in the real world.
• They can be concepts used in the world (e.g. time)

Question 9

3 Properties of equality (binary relation)

Answer 9

• Reflexive
• Transitive
• Symmetric

Question 10

Valuation

Answer 10

Given an interpretation I with a domain D, a valuation means a function that gives an element of D for each variable.

Question 11

Free variables

Answer 11

A variable which is not quantified in an explicit way

Question 12

Bound variables

Answer 12

A variable which is associated to a quantifier.

Question 13

Formal definition of interpretation

Answer 13

Given a first order language, L, an interpretation for L is a pair (D, I) where:
- D is a non-empty set, called the domain, and
- I is a function which:
- to each constant symbol c of L assigns an element I(c) ∈ D
- to each n-ary predicate symbol P, ( n > 0 ), assigns an n-ary relation I(P) ⊆ D^n,
- to each propositional constant q, assigns a truth value I(q).

Sometimes I is called a structure.

Question 14

Formal definition of a valuation

Answer 14

Given a structure (D, I) for a language L, a valuation is a function from the set of all variables to D.

Given a valuation V, a variable x and d ∈ D, we define the valuation V[ x → d ] to be the same as V for every variable other than x, and x gets sent to d.

V[ x → d ] (u) =
V(u) if u is not x.
d if u is x

Question 15

Definition of truth

Answer 15

For a structure A = (D, I) and a valuation v and a formula φ, the notation

A, V ⊧ φ

will mean that φ is true in the structure A under the valuation V.

Question 16

Sentence

Answer 16

A formula with no free variables.