Difference between revisions of "Semantics of formulas (FOL)"

Revision as of 07:50, 11 September 2016

Definition

Given a first order language, $\mathscr{L}$ and a model, $(\mathbf{M},\sigma)$ also, the semantics of a formula, $A\in\mathscr{L}_F$, which we denote by $A_{\mathbf{M}[\sigma]}$, is defined inductively as follows^[1]:

See here for semantics of terms and here for logical connectives, which are denoted $\mathbf{B}_*$ for $*\in\{\neg,\vee,\wedge,\rightarrow,\leftrightarrow\}$

1. For an $n$-ary predicate symbol, $P$ and terms, $t_1,\ldots,t_n\in\mathscr{L}_T$ the semantics are: $(Pt_1\cdots t_n)_{\mathbf{M}[\sigma]}:=P_\mathbf{M}((t_1)_{\mathbf{M}[\sigma]},\ldots,(t_n)_{\mathbf{M}[\sigma]})$, recall $P_\mathbf{M}$ denotes $I(P)$ where $I$ is an interpretation.
2. For terms then $t_1,t_2\in\mathscr{L}_T$, $(t_1\doteq t_2)_{\mathbf{M}[\sigma]}:=\left\{\begin{array}{lr}T & \text{if } (t_1)_{\mathbf{M}[\sigma]}=(t_2)_{\mathbf{M}[\sigma]}\\ F & \text{otherwise}\end{array}\right.$, recall $T$ and $F$ are truth values
3. For a formula, $A\in\mathscr{L}_F$ then: $(\neg A)_{\mathbf{M}[\sigma]}:=\mathbf{B}_\neg(A_{\mathbf{M}[\sigma]})$
4. For formulas, $A,B\in\mathscr{L}_F$ then: $(A\vee B)_{\mathbf{M}[\sigma]}:=B_\vee(A_{\mathbf{M}[\sigma]},B_{\mathbf{M}[\sigma]})$
5. For formulas, $A,B\in\mathscr{L}_F$ then: $(A\wedge B)_{\mathbf{M}[\sigma]}:=B_\wedge(A_{\mathbf{M}[\sigma]},B_{\mathbf{M}[\sigma]})$
6. For formulas, $A,B\in\mathscr{L}_F$ then: $(A\rightarrow B)_{\mathbf{M}[\sigma]}:=B_\rightarrow(A_{\mathbf{M}[\sigma]},B_{\mathbf{M}[\sigma]})$
7. For formulas, $A,B\in\mathscr{L}_F$ then: $(A\leftrightarrow B)_{\mathbf{M}[\sigma]}:=B_\leftrightarrow(A_{\mathbf{M}[\sigma]},B_{\mathbf{M}[\sigma]})$
8. For a formula, $A\in\mathscr{L}_F$ and a variable symbol, $x\in V$ then: $(\forall xA)_{\mathbf{M}[\sigma]}:=\left\{\begin{array}{lr}T & \text{if for every }a\in M,\ A_{\mathbf{M}[\sigma[x:=a]]}=T\text{ holds}\\ F & \text{otherwise}\end{array}\right.$
9. For a formula, $A\in\mathscr{L}_F$ and a variable symbol, $x\in V$ then: $(\exists xA)_{\mathbf{M}[\sigma]}:=\left\{\begin{array}{lr} T & \text{if there exists an }a\in M\text{ such that }A_{\mathbf{M}[\sigma[x:=a]]}=T\text{ holds} \\ F & \text{otherwise}\end{array}\right.$

See next

• Satisfiable formula
• Valid formula (AKA: tautology)
• Satisfiability and validity of formulas and sets of formulas - an overview of the above

References

1. Jump up ↑ Mathematical Logic - Foundations for Information Science - Wei Li

Template:Formal logic navbox