Section 5: Sentences of QL
- Page ID
- 1054
\( \newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } \)
\( \newcommand{\vecd}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}} \)
\( \newcommand{\id}{\mathrm{id}}\) \( \newcommand{\Span}{\mathrm{span}}\)
( \newcommand{\kernel}{\mathrm{null}\,}\) \( \newcommand{\range}{\mathrm{range}\,}\)
\( \newcommand{\RealPart}{\mathrm{Re}}\) \( \newcommand{\ImaginaryPart}{\mathrm{Im}}\)
\( \newcommand{\Argument}{\mathrm{Arg}}\) \( \newcommand{\norm}[1]{\| #1 \|}\)
\( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\)
\( \newcommand{\Span}{\mathrm{span}}\)
\( \newcommand{\id}{\mathrm{id}}\)
\( \newcommand{\Span}{\mathrm{span}}\)
\( \newcommand{\kernel}{\mathrm{null}\,}\)
\( \newcommand{\range}{\mathrm{range}\,}\)
\( \newcommand{\RealPart}{\mathrm{Re}}\)
\( \newcommand{\ImaginaryPart}{\mathrm{Im}}\)
\( \newcommand{\Argument}{\mathrm{Arg}}\)
\( \newcommand{\norm}[1]{\| #1 \|}\)
\( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\)
\( \newcommand{\Span}{\mathrm{span}}\) \( \newcommand{\AA}{\unicode[.8,0]{x212B}}\)
\( \newcommand{\vectorA}[1]{\vec{#1}} % arrow\)
\( \newcommand{\vectorAt}[1]{\vec{\text{#1}}} % arrow\)
\( \newcommand{\vectorB}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } \)
\( \newcommand{\vectorC}[1]{\textbf{#1}} \)
\( \newcommand{\vectorD}[1]{\overrightarrow{#1}} \)
\( \newcommand{\vectorDt}[1]{\overrightarrow{\text{#1}}} \)
\( \newcommand{\vectE}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash{\mathbf {#1}}}} \)
\( \newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } \)
\( \newcommand{\vecd}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}} \)
\(\newcommand{\avec}{\mathbf a}\) \(\newcommand{\bvec}{\mathbf b}\) \(\newcommand{\cvec}{\mathbf c}\) \(\newcommand{\dvec}{\mathbf d}\) \(\newcommand{\dtil}{\widetilde{\mathbf d}}\) \(\newcommand{\evec}{\mathbf e}\) \(\newcommand{\fvec}{\mathbf f}\) \(\newcommand{\nvec}{\mathbf n}\) \(\newcommand{\pvec}{\mathbf p}\) \(\newcommand{\qvec}{\mathbf q}\) \(\newcommand{\svec}{\mathbf s}\) \(\newcommand{\tvec}{\mathbf t}\) \(\newcommand{\uvec}{\mathbf u}\) \(\newcommand{\vvec}{\mathbf v}\) \(\newcommand{\wvec}{\mathbf w}\) \(\newcommand{\xvec}{\mathbf x}\) \(\newcommand{\yvec}{\mathbf y}\) \(\newcommand{\zvec}{\mathbf z}\) \(\newcommand{\rvec}{\mathbf r}\) \(\newcommand{\mvec}{\mathbf m}\) \(\newcommand{\zerovec}{\mathbf 0}\) \(\newcommand{\onevec}{\mathbf 1}\) \(\newcommand{\real}{\mathbb R}\) \(\newcommand{\twovec}[2]{\left[\begin{array}{r}#1 \\ #2 \end{array}\right]}\) \(\newcommand{\ctwovec}[2]{\left[\begin{array}{c}#1 \\ #2 \end{array}\right]}\) \(\newcommand{\threevec}[3]{\left[\begin{array}{r}#1 \\ #2 \\ #3 \end{array}\right]}\) \(\newcommand{\cthreevec}[3]{\left[\begin{array}{c}#1 \\ #2 \\ #3 \end{array}\right]}\) \(\newcommand{\fourvec}[4]{\left[\begin{array}{r}#1 \\ #2 \\ #3 \\ #4 \end{array}\right]}\) \(\newcommand{\cfourvec}[4]{\left[\begin{array}{c}#1 \\ #2 \\ #3 \\ #4 \end{array}\right]}\) \(\newcommand{\fivevec}[5]{\left[\begin{array}{r}#1 \\ #2 \\ #3 \\ #4 \\ #5 \\ \end{array}\right]}\) \(\newcommand{\cfivevec}[5]{\left[\begin{array}{c}#1 \\ #2 \\ #3 \\ #4 \\ #5 \\ \end{array}\right]}\) \(\newcommand{\mattwo}[4]{\left[\begin{array}{rr}#1 \amp #2 \\ #3 \amp #4 \\ \end{array}\right]}\) \(\newcommand{\laspan}[1]{\text{Span}\{#1\}}\) \(\newcommand{\bcal}{\cal B}\) \(\newcommand{\ccal}{\cal C}\) \(\newcommand{\scal}{\cal S}\) \(\newcommand{\wcal}{\cal W}\) \(\newcommand{\ecal}{\cal E}\) \(\newcommand{\coords}[2]{\left\{#1\right\}_{#2}}\) \(\newcommand{\gray}[1]{\color{gray}{#1}}\) \(\newcommand{\lgray}[1]{\color{lightgray}{#1}}\) \(\newcommand{\rank}{\operatorname{rank}}\) \(\newcommand{\row}{\text{Row}}\) \(\newcommand{\col}{\text{Col}}\) \(\renewcommand{\row}{\text{Row}}\) \(\newcommand{\nul}{\text{Nul}}\) \(\newcommand{\var}{\text{Var}}\) \(\newcommand{\corr}{\text{corr}}\) \(\newcommand{\len}[1]{\left|#1\right|}\) \(\newcommand{\bbar}{\overline{\bvec}}\) \(\newcommand{\bhat}{\widehat{\bvec}}\) \(\newcommand{\bperp}{\bvec^\perp}\) \(\newcommand{\xhat}{\widehat{\xvec}}\) \(\newcommand{\vhat}{\widehat{\vvec}}\) \(\newcommand{\uhat}{\widehat{\uvec}}\) \(\newcommand{\what}{\widehat{\wvec}}\) \(\newcommand{\Sighat}{\widehat{\Sigma}}\) \(\newcommand{\lt}{<}\) \(\newcommand{\gt}{>}\) \(\newcommand{\amp}{&}\) \(\definecolor{fillinmathshade}{gray}{0.9}\)In this section, we provide a formal definition for a well-formed formula (wff) and sentence of QL.
Expressions
There are six kinds of symbols in QL:
predicates with subscripts, as needed |
\(A\),\(B\),\(C\),...,\(Z\) \(A\)1,\(B\)1,\(Z\)1,\(A\)2,\(A\)25,\(J\)375,... |
constants with subscripts, as needed |
\(a\),\(b\),\(c\),...,\(w\) \(a\)1,\(w\)4,\(h\)7,\(m\)32,... |
variables with subscripts, as needed |
\(x\),\(y\),\(z\) \(x\)1,\(y\)1,\(z\)1,\(x\)2,... |
connectives | ¬,&,∨,→,↔ |
parentheses | ( , ) |
quantifiers | ∀,∃ |
We define an expression of Ql as any string of symbols of QL. Take any of the symbols of QL and write them down, in any order, and you have an expression.
Well-formed formulae
By definition, a term of ql is either a constant or a variable.
An atomic formula of ql is an n-place predicate followed by n terms.
Just as we did for SL, we will give a recursive definition for a wff of QL. In fact, most of the definition will look like the definition of for a wff of SL: Every atomic formula is a wff, and you can build new wffs by applying the sentential connectives.
We could just add a rule for each of the quantifiers and be done with it. For instance: If \(\mathcal{A}\) is a wff, then ∀x\(\mathcal{A}\) and ∃x\(\mathcal{A}\) are wffs. However, this would allow for bizarre sentences like ∀x∃xDx and ∀xDw. What could these possibly mean? We could adopt some interpretation of such sentences, but instead we will write the definition of a wff so that such abominations do not even count as well-formed.
In order for ∀x\(\mathcal{A}\) to be a wff, \(\mathcal{A}\) must contain the variable x and must not already contain an x-quantifier. ∀xDw will not count as a wff because ‘x’ does not occur in Dw, and ∀x∃xDx will not count as a wff because ∃xDx contains an x-quantifier
1. Every atomic formula is a wff.
2. If \(\mathcal{A}\) is a wff, then ¬\(\mathcal{A}\) is a wff.
3. If \(\mathcal{A}\) and \(\mathcal{B}\) are wffs, then (\(\mathcal{A}\) & \(\mathcal{B}\)), is a wff.
4. If \(\mathcal{A}\) and \(\mathcal{B}\) are wffs, (\(\mathcal{A}\)∨\(\mathcal{B}\)) is a wff.
5. If \(\mathcal{A}\) and \(\mathcal{B}\) are wffs, then (\(\mathcal{A}\) →\(\mathcal{B}\)) is a wff.
6. If \(\mathcal{A}\) and \(\mathcal{B}\) are wffs, then (\(\mathcal{A}\) ↔ \(\mathcal{B}\)) is a wff.
7. If \(\mathcal{A}\) is a wff, \(\mathcal{x}\) is a variable, \(\mathcal{A}\) contains at least one occurrence of \(\mathcal{x}\), and \(\mathcal{A}\) contains no \(\mathcal{x}\)-quantifiers, then ∀\(\mathcal{x}\)\(\mathcal{A}\) is a wff.
8. If \(\mathcal{A}\) is a wff, \(\mathcal{x}\) is a variable, \(\mathcal{A}\) contains at least one occurrence of \(\mathcal{x}\), and \(\mathcal{A}\) contains no \(\mathcal{x}\)-quantifiers, then ∃\(\mathcal{x}\)\(\mathcal{A}\) is a wff.
9. All and only wffs of QL can be generated by applications of these rules.
Notice that the ‘\(\mathcal{x}\)’ that appears in the definition above is not the variable \(x\). It is a meta-variable that stands in for any variable of QL. So ∀\(xAx\) is a wff, but so are ∀\(yAy\), ∀\(zAz\), ∀\(x\)4\(Ax\)4, and ∀\(z\)9\(Az\)9.
We can now give a formal definition for scope: The scope of a quantifier is the subformula for which the quantifier is the main logical operator.
Sentences
A sentence is something that can be either true or false. In SL, every wff was a sentence. This will not be the case in QL. Consider the following symbolization key:
UD: people
Lxy: \(x\) loves \(y\)
b: Boris
Consider the expression \(Lzz\). It is an atomic forumula: a two-place predicate followed by two terms. All atomic formula are wffs, so \(Lzz\) is a wff. Does it mean anything? You might think that it means that \(z\) loves himself, in the same way that \(Lbb\) means that Boris loves himself. Yet \(z\) is a variable; it does not name some person the way a constant would. The wff \(Lzz\) does not tell us how to interpret \(z\). Does it mean everyone? anyone? someone? If we had a \(z\)-quantifier, it would tell us how to interpret \(z\). For instance, ∃\(zLzz\) would mean that someone loves themselves.
Some formal languages treat a wff like \(Lzz\) as implicitly having a universal quantifier in front. We will not do this for QL. If you mean to say that everyone loves themself, then you need to write the quantifier: ∀\(zLzz\) In order to make sense of a variable, we need a quantifier to tell us how to interpret that variable. The scope of an \(x\)-quantifier, for instance, is the part of the formula where the quantifier tells how to interpret \(x\).
In order to be precise about this, we define a bound variable to be an occurrence of a variable \(\mathcal{x}\) that is within the scope of an \(\mathcal{x}\)-quantifier. A free variable is an occurance of a variable that is not bound.
For example, consider the wff ∀\(x\)(\(Ex\)∨\(Dy\)) → ∃\(z\)(\(Ex\) → \(Lzx\)). The scope of the universal quantifier ∀\(x\) is (\(Ex\)∨\(Dy\)), so the first \(x\) is bound by the universal quantifier but the second and third \(x\)s are free. There is not \(y\)-quantifier, so the \(y\) is free. The scope of the existential quantifier ∃\(z\) is (\(Ex\) → \(Lzx\)), so both occurrences of \(z\) are bound by it.
We define a sentence of QL as a wff of QL that contains no free variables.
Notational conventions
We will adopt the same notational conventions that we did for SL (p. 30.) First, we may leave off the outermost parentheses of a formula. Second, we will use square brackets ‘[’ and ‘]’ in place of parentheses to increase the readability of formulae. Third, we will leave out parentheses between each pair of conjuncts when writing long series of conjunctions. Fourth, we will leave out parentheses between each pair of disjuncts when writing long series of disjunctions.