First Order Language

Question 1

What are the terms of L?

Answer 1

1. All constant symbols
2. All variables
3. n-ary function symbols

Question 2

What are the formulas of L?

Answer 2

1. t_1≈t_2
2. Rt_1…t_n where R is an n-ary relation symbol
3. ¬φ if φ is a formula
4. (φ_1→φ_2) if φ_1 and φ_2 are formulas
5. ∀xφ is a formula if φ is a formula

Question 3

Which of the formulas are atomic?

Answer 3

1. t_1≈t_2
2. Rt_1…t_n where R is an n-ary relation symbol

Question 4

What are the components of a model?

Answer 4

Domain of A (a non-empty set)

For every n-ary relation symbol, R^A⊆A^n

For every n-ary function symbol: A^n→A

For every constant symbol, an element c^A∈A

Question 5

What is an assignment β?

Answer 5

β a/x (y) = β(y) if y≠x
β a/x (y) = a if y=x

Question 6

What is an interpretation?

Answer 6

A model and assignment pair I=(A,β)

Question 7

What are the interpretations for the terms of L?

Answer 7

If c is constant: I(c)=c^A
If x is a first order variable: I(x)=β(x)
If f is an n-ary function symbol: I(ft_1…t_n )=f^A (I(t_1 ),…,I(t_n ))

Question 8

What are the interpretations for the formulas?

Answer 8

1. If φ=t_1≈t_n, then I⊨t_1≈t_n⟺I(t_1 )=I(t_2)
2. If φ=Rt_1…t_n where R is a relation symbol, then I⊨Rt_1…t_n⟺(I(t_1 ),…,I(t_n ))∈R^A
3. If φ=¬φ, then I⊨¬φ⟺I⊭φ
4. If φ=(ψ_1→ψ_2 ), then I⊭(ψ_1→ψ_2 )⟺I⊨ψ_1 and I⊭ψ_2
5. If φ=∀xψ, then I⊨∀xψ ⟺ for all a∈A, I a/x⊨ψ
6. I⊨(φ∧ψ) ⟺I⊨ φ and I⊨ψ
7. I⊨(φ∨ψ) ⟺I⊨ φ or I⊨ψ
8. I⊨(φ↔ψ) ⟺I⊨ φ ⟺I⊨ψ
9. I⊨ ∃x φ ⟺ there exists a∈A such that I a/x⊨φ

Question 9

What is the sub formula for φ=∀xψ?

Answer 9

sub(φ) = {φ} ∪ sub(ψ).

Question 10

What does ∃x φ abbreviate?

Answer 10

¬ ∀x ¬φ

Question 11

What is the language of arithmetic?

Answer 11

L_ar={+,∙,0,1,<}
Domain: Q,N,Z,R

Question 12

What are the variables of the formula φ = ∀x ψ?

Answer 12

var(φ) = var(ψ)

Question 13

If φ = ∀x ψ, what is free(φ)?

Answer 13

free(φ) = free(ψ) \ {x}.

Question 14

What are bounded variables?

Answer 14

The variables that occur next to the quantifier.

Question 15

What is a sentence?

Answer 15

a formula that has no free variables.

Question 16

What type of formula is complete?

Answer 16

Sentences

Question 17

How can formulas be true in models?

Answer 17

a formula can be true, false, or neither true nor false

Question 18

How can sentences be true in models?

Answer 18

only true or false

Question 19

If β(x)=β ̃(x) for all x∈free(φ), then what?

Answer 19

(A,β) ⊨ φ ⟺ (A,β ̃) ⊨ φ.

Question 20

If β and β ̃ are assignments on A that agree on all variables occurring in t, then what?

Answer 20

(A,β)(t) = (A,β ̃)(t).

Question 21

What is the notation for divides in the language of arithmetic?

Answer 21

r|s (abbreviates ∃x_i r·x_i ≈ s)

Question 22

Define Logical Consequence

Answer 22

φ is a logical consequence of Γ if for every interpretation I such that I ⊨ γ for all γ∈Γ, then I ⊨ φ.

Question 23

Define logically valid

Answer 23

If I ⊨ φ for all interpretations (∅⊨φ), then ⊨φ.

Question 24

Define truth equivalent

Answer 24

For every interpretation I of L, either both I ⊨ φ and I ⊨ ψ or both I ⊭ φ and I ⊭ ψ

Question 25

Define satisfiable

Answer 25

Γ is satisfiable if there exists an interpretation I such that I ⊨ Γ.

Question 26

If γ is a tautology in propositional logic, then?

Answer 26

γ^* is a logically valid first order formula

Question 27

What is a first order tautology?

Answer 27

If φ=γ^* for a tautology γ and formula φ, then φ is a first order tautology.

Question 28

How do you substitute terms for variables?

Answer 28

If s is a constant symbol, then s t/x= s
If s is a variable and y≠x, then s t/x=s
If s is a variable and y=x, then s t/x=t
If f is a function symbol, then s t/x=fs1 t/x…sn t/x

Question 29

How do you substitute formulas for variables?

Answer 29

If φ = s_1≈s_2, then φ t/x = s_t t/x ≈ s_2 t/x
If φ = R is an n-ary relation symbol then, φ t/x = Rs_1 t/x ··· s_n t/x
If φ = ¬φ_1, then φ t/x = ¬[φ_1 t/x]
If φ = (φ_1→ φ_2), then φ t/x=(φ_1 t/x→φ_2 t/x).
If φ = ∀yφ_1 where y≠x, then φ t/x = ∀y [φ_1 t/x].
If φ = ∀xφ_1 where y=x, then φ t/x = φ.

Question 30

Define substitutable.

Answer 30

If φ t/x creates no new bound occurrence for t, then t is substitutable for x in φ.

Question 31

Define part 1 of the substitution lemma

Answer 31

For any terms s and t, any variable x, and any interpretation I of L, I(s t/x)=I I(t)/x(s)

Question 32

Define part 2 of the substitution lemma

Answer 32

I ⊨ φ t/x iff I I(t)/x ⊨ φ

Question 33

If t is substitutable for x in φ, then what is logically valid?

Answer 33

(∀xφ→φ t/x)

Question 34

For any variable x, φ is logically valid if and only if what is logically valid?

Answer 34

∀x φ

Question 35

φ is logically valid if what is logically valid?

Answer 35

∃x φ for any variable x

Question 36

φ and ψ are truth equivalent if and only if what?

Answer 36

(φ ↔ ψ) is logically valid.

Question 37

What is prenex normal form?

Answer 37

a formula that has the form Q_1 y_1…Q_n y_n ψ where Q_i∈{∀,∃}, ψ is quantifier free, and n≥0.

Question 38

Convert the following formulas to prenex normal form.
¬Qxφ
(ψ→Qxφ) and (Qxφ→ψ)
y is substitutable for x in φ: Qxφ

Answer 38

¬Qxφ ⊨=| Q ̅x¬φ.
If x ∉ free(ψ), then (ψ→Qxφ) ⊨=|Qx(ψ→φ) and (Qxφ→ψ) ⊨=|Q ̅x(φ→ψ).
If y ∉ free(φ) and y is substitutable for x in φ, then Qxφ ⊨=|Qyφ y/x.

Question 39

Convert the following formulas to prenex normal form.
(Qxφ ∧ ψ)
(ψ ∧ Qxφ)
(Qxφ ∨ ψ)
(ψ ∨ Qxφ)

Answer 39

(Qxφ ∧ ψ) ⊨=|Qx(φ ∧ ψ)
(ψ ∧ Qxφ) ⊨=|Qx(ψ ∧ φ)
(Qxφ ∨ ψ) ⊨=|Qx(φ ∨ ψ)
(ψ ∨ Qxφ) ⊨=|Qx(ψ ∨ φ)

Question 40

Every first order formula is truth equivalent to a formula in prenex normal form with what?

Answer 40

The same free variables.

Question 41

Define the quantifier number of φ for the following:
φ is atomic
φ = ¬ψ
φ = (ψ → γ)
φ = ∀xψ

Answer 41

If φ is atomic, qn(φ) = 0.
If φ = ¬ψ, then qn(φ) = qn(ψ).
If φ = (ψ → γ), then qn(φ) = qn(ψ)+qn(γ).
If φ = ∀xψ, then qn(φ) = qn(ψ)+1.

Question 42

If φ is an L-formula with qn(φ) ≤ n, then there is an L-formula ψ in prenex normal form with qn(φ) = ?, free(φ) = ? and φ ⊨=|?

Answer 42

qn(φ) = qn(ψ), free(φ) = free(ψ) and φ⊨=|ψ.