Sentence vs. propositional formula
Formal logic has formulas at two levels: propositional logic (zeroth-order logic), whose variables stand for whole statements, and first-order logic, whose variables stand for objects such as numbers. A sentence is a formula of first-order logic in which a quantifier, such as “for all” ($\forall$) or “there exists” ($\exists$), binds every variable, and the sentence is true or false once its symbols are interpreted, for example as statements about real numbers. A propositional formula is a formula of propositional logic, built from propositional variables with logical connectives such as $\land$ and $\neg$, and the formula is true or false once each variable is assigned a truth value.
Definitions
Consider a formula of first-order logic, such as $\forall x \, (x^2 \geq 0)$ or $x > 3$. The formula is a sentence if it has no free variables: every variable in it is bound by a quantifier.
Examples
-
$\exists x \, (x^2 = 2)$
$\exists x \, (x^2 = 2)$ is a sentence, because the quantifier $\exists x$ binds the only variable $x$.
-
$\forall x \, (x^2 \geq 0)$, with $x$ ranging over $\reals$
$\forall x \, (x^2 \geq 0)$ is a sentence, because the quantifier binds its only variable $x$.
-
The first-order sentence $\forall x \, (x^2 \geq 0) \land \neg \exists x \, (x^2 < 0)$, whose propositional form is $p \land \neg q$
$\forall x \, (x^2 \geq 0) \land \neg \exists x \, (x^2 < 0)$ is a sentence, because the quantifiers $\forall x$ and $\exists x$ bind every occurrence of $x$.
Non-examples
-
“$7$ is prime”
“$7$ is prime” is not a sentence of first-order logic, because “$7$ is prime” is written in English, not as a string of symbols of a formal language.
-
“$x > 3$”
“$x > 3$” is not a sentence, because $x$ is a free variable.
-
$\exists y \, (y > x)$
$\exists y \, (y > x)$ is not a sentence, although $\exists y \, (y > x)$ has a quantifier: the quantifier binds $y$, but $x$ is free, so the truth of $\exists y \, (y > x)$ depends on the value of $x$ (for example, if $x$ and $y$ range over the natural numbers, then the formula is true for every $x$, and if $x$ and $y$ range over $\setdef{1, 2, 3}$, then the formula is false for $x = 3$).
-
$p \land \neg q$
$p \land \neg q$ is not a sentence of first-order logic, because the variables $p$ and $q$ stand for whole statements, not for objects such as numbers, and $p \land \neg q$ has no quantifiers; a sentence such as $\forall x \, (x^2 \geq 0)$ has variables that stand for objects, and a quantifier binds each of those variables.
Properties
- Once its symbols are interpreted in a structure (such as $\reals$ with its usual operations), a sentence is true or false, so it expresses a proposition.
- A formula with free variables, such as $x > 3$, expresses a predicate. Quantifying every free variable turns it into a sentence.
A propositional formula is an expression built from propositional variables $p, q, r, \dots$ using logical connectives such as $\neg$, $\land$, $\lor$, and $\implies$. It has a truth value only once each variable is assigned true or false.
Examples
-
$p \land \neg q$
$p \land \neg q$ is a propositional formula because its truth depends on the truth values of $p$ and $q$.
Non-examples
-
“$7$ is prime”
“$7$ is prime” is not a propositional formula, because it has no propositional variables.
-
“$x > 3$”
“$x > 3$” is not a propositional formula, because its variable $x$ stands for a number, not for a proposition.
-
“$7$ is prime and $4$ is not prime”
“$7$ is prime and $4$ is not prime” is not a propositional formula, because the statement contains no propositional variables; the statement is one instance of the formula $p \land \neg q$.
-
$\forall x \, (x^2 \geq 0)$, with $x$ ranging over $\reals$
$\forall x \, (x^2 \geq 0)$ is not a propositional formula, because the formula uses the quantifier $\forall$, which propositional logic does not have.
-
The first-order sentence $\forall x \, (x^2 \geq 0) \land \neg \exists x \, (x^2 < 0)$, whose propositional form is $p \land \neg q$
$\forall x \, (x^2 \geq 0) \land \neg \exists x \, (x^2 < 0)$ is not a propositional formula, because its parts are quantified statements about numbers, not propositional variables; replacing $\forall x \, (x^2 \geq 0)$ by $p$ and $\exists x \, (x^2 < 0)$ by $q$ gives the propositional formula $p \land \neg q$.
Examples
| Example | sentence | propositional formula | Why |
|---|---|---|---|
| $\forall x \, (x^2 \geq 0)$, with $x$ ranging over $\reals$ | ✓ | ✗ | |
| $p \land \neg q$ | ✗ | ✓ | |
| The first-order sentence $\forall x \, (x^2 \geq 0) \land \neg \exists x \, (x^2 < 0)$, whose propositional form is $p \land \neg q$ | ✓ | ✗ | The sentence $\forall x \, (x^2 \geq 0) \land \neg \exists x \, (x^2 < 0)$ has the propositional form $p \land \neg q$: the propositional formula records only how the statements are combined, and the sentence also says what the statements are about. |
| “$x > 3$” | ✗ | ✗ | “$x > 3$” is neither a sentence nor a propositional formula: “$x > 3$” is a formula of first-order logic, but its variable $x$ is free, and $x$ stands for a number, not a proposition. |
Notes
- The truth of a propositional formula depends on a truth assignment to its variables, and the truth of a sentence depends on an interpretation of its symbols, such as the set the variables range over.
- Some books call every propositional formula without variables a “sentence” of propositional logic; this page uses “sentence” in the first-order sense.