Propositional formula
Undergraduate (logic)
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
Examples
-
$p \land \neg q$
Undergraduate
$p \land \neg q$ is a propositional formula because its truth depends on the truth values of $p$ and $q$.
Non-examples
Things that may be mistaken for examples.
-
“$7$ is prime”
High school
“$7$ is prime” is not a propositional formula, because it has no propositional variables.
-
“$x > 3$”
High school
“$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”
Undergraduate
“$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$
Undergraduate
$\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$
Graduate
$\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$.
Distinctions involving this term
- Proposition vs. propositional formula: In logic, statements are combined with logical connectives such as “and” ($\land$), “or” ($\lor$), and “not” ($\neg$). A proposition is a particular statement that is true or false, such as “$7$ is prime.” A propositional formula is a pattern, such as $p \land \neg q$, built from propositional variables that stand for propositions, and the formula has a truth value only once each variable is assigned a truth value. Substituting a proposition for each variable in a propositional formula gives a proposition.
- 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.