Variables and Quantifiers for First-order models -artificial intelligence:
So what do sentences containing variables mean? In other words, how does first order model select whether such a sentence is false ortrue? The first step is to ensure that the sentence does not contain any unrestricted variables, variables which are not bound by (associated with) a quantifier. Firmly speaking, a first-order expression is not a sentence unless all the variables are bound. However, we typically assume that if a variable is not explicitly bound then actually it is implicitly commonly quantified.
Next we look for the outermost quantifier in our sentence. If it is X then we consider the truth of the sentence for each value X could take. When the outermost quantifier is X we have to search only a single possible value of X. To make it more formal we may use a concept of substitution. Here {X\t} is a substitution that replaces all occurrences of variable X with a term representing an object t:
- X. A is true if and only if A.{X\t} for all t in Δ
- X. A is true if and only if A.{X\t} for at least one t in Δ
Repeating this for all the quantifiers we get a set of ground formulae which we have to check to see if the original sentence is true or false. Unluckily, we haven't specificed that our domain Δ is finite for an example, it may contain the natural numbers - so there may be a infinite number of sentences to check for a given model! There may be also be an infinite number of models .So even though we have a right definition of model, and so a proper semantics for first-order logic, so we cannot rely on having a finite number of models as we did when drawing propositional truth tables.