First Order Language Flashcards
What are the terms of L?
- All constant symbols
- All variables
- n-ary function symbols
What are the formulas of L?
- t_1≈t_2
- Rt_1…t_n where R is an n-ary relation symbol
- ¬φ if φ is a formula
- (φ_1→φ_2) if φ_1 and φ_2 are formulas
- ∀xφ is a formula if φ is a formula
Which of the formulas are atomic?
- t_1≈t_2
- Rt_1…t_n where R is an n-ary relation symbol
What are the components of a model?
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
What is an assignment β?
β a/x (y) = β(y) if y≠x
β a/x (y) = a if y=x
What is an interpretation?
A model and assignment pair I=(A,β)
What are the interpretations for the terms of L?
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 ))
What are the interpretations for the formulas?
- If φ=t_1≈t_n, then I⊨t_1≈t_n⟺I(t_1 )=I(t_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
- If φ=¬φ, then I⊨¬φ⟺I⊭φ
- If φ=(ψ_1→ψ_2 ), then I⊭(ψ_1→ψ_2 )⟺I⊨ψ_1 and I⊭ψ_2
- If φ=∀xψ, then I⊨∀xψ ⟺ for all a∈A, I a/x⊨ψ
- I⊨(φ∧ψ) ⟺I⊨ φ and I⊨ψ
- I⊨(φ∨ψ) ⟺I⊨ φ or I⊨ψ
- I⊨(φ↔ψ) ⟺I⊨ φ ⟺I⊨ψ
- I⊨ ∃x φ ⟺ there exists a∈A such that I a/x⊨φ
What is the sub formula for φ=∀xψ?
sub(φ) = {φ} ∪ sub(ψ).
What does ∃x φ abbreviate?
¬ ∀x ¬φ
What is the language of arithmetic?
L_ar={+,∙,0,1,<}
Domain: Q,N,Z,R
What are the variables of the formula φ = ∀x ψ?
var(φ) = var(ψ)
If φ = ∀x ψ, what is free(φ)?
free(φ) = free(ψ) \ {x}.
What are bounded variables?
The variables that occur next to the quantifier.
What is a sentence?
a formula that has no free variables.
What type of formula is complete?
Sentences
How can formulas be true in models?
a formula can be true, false, or neither true nor false
How can sentences be true in models?
only true or false
If β(x)=β ̃(x) for all x∈free(φ), then what?
(A,β) ⊨ φ ⟺ (A,β ̃) ⊨ φ.
If β and β ̃ are assignments on A that agree on all variables occurring in t, then what?
(A,β)(t) = (A,β ̃)(t).
What is the notation for divides in the language of arithmetic?
r|s (abbreviates ∃x_i r·x_i ≈ s)
Define Logical Consequence
φ is a logical consequence of Γ if for every interpretation I such that I ⊨ γ for all γ∈Γ, then I ⊨ φ.
Define logically valid
If I ⊨ φ for all interpretations (∅⊨φ), then ⊨φ.
Define truth equivalent
For every interpretation I of L, either both I ⊨ φ and I ⊨ ψ or both I ⊭ φ and I ⊭ ψ
Define satisfiable
Γ is satisfiable if there exists an interpretation I such that I ⊨ Γ.
If γ is a tautology in propositional logic, then?
γ^* is a logically valid first order formula
What is a first order tautology?
If φ=γ^* for a tautology γ and formula φ, then φ is a first order tautology.
How do you substitute terms for variables?
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
How do you substitute formulas for variables?
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 = φ.
Define substitutable.
If φ t/x creates no new bound occurrence for t, then t is substitutable for x in φ.
Define part 1 of the substitution lemma
For any terms s and t, any variable x, and any interpretation I of L, I(s t/x)=I I(t)/x(s)
Define part 2 of the substitution lemma
I ⊨ φ t/x iff I I(t)/x ⊨ φ
If t is substitutable for x in φ, then what is logically valid?
(∀xφ→φ t/x)
For any variable x, φ is logically valid if and only if what is logically valid?
∀x φ
φ is logically valid if what is logically valid?
∃x φ for any variable x
φ and ψ are truth equivalent if and only if what?
(φ ↔ ψ) is logically valid.
What is prenex normal form?
a formula that has the form Q_1 y_1…Q_n y_n ψ where Q_i∈{∀,∃}, ψ is quantifier free, and n≥0.
Convert the following formulas to prenex normal form.
¬Qxφ
(ψ→Qxφ) and (Qxφ→ψ)
y is substitutable for x in φ: Qxφ
¬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.
Convert the following formulas to prenex normal form.
(Qxφ ∧ ψ)
(ψ ∧ Qxφ)
(Qxφ ∨ ψ)
(ψ ∨ Qxφ)
(Qxφ ∧ ψ) ⊨=|Qx(φ ∧ ψ)
(ψ ∧ Qxφ) ⊨=|Qx(ψ ∧ φ)
(Qxφ ∨ ψ) ⊨=|Qx(φ ∨ ψ)
(ψ ∨ Qxφ) ⊨=|Qx(ψ ∨ φ)
Every first order formula is truth equivalent to a formula in prenex normal form with what?
The same free variables.
Define the quantifier number of φ for the following:
φ is atomic
φ = ¬ψ
φ = (ψ → γ)
φ = ∀xψ
If φ is atomic, qn(φ) = 0.
If φ = ¬ψ, then qn(φ) = qn(ψ).
If φ = (ψ → γ), then qn(φ) = qn(ψ)+qn(γ).
If φ = ∀xψ, then qn(φ) = qn(ψ)+1.
If φ is an L-formula with qn(φ) ≤ n, then there is an L-formula ψ in prenex normal form with qn(φ) = ?, free(φ) = ? and φ ⊨=|?
qn(φ) = qn(ψ), free(φ) = free(ψ) and φ⊨=|ψ.
