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.
Definitions
A proposition is a statement that is either true or false.
Examples
-
“$7$ is prime”
“$7$ is prime” is a proposition because it is true.
-
$\exists x \, (x^2 = 2)$
: True if $x$ ranges over $\reals$; false if $x$ ranges over the rational numbers
$\exists x \, (x^2 = 2)$ expresses a proposition only once the set that $x$ ranges over is chosen: over $\reals$, the number $\sqrt{2}$ satisfies $x^2 = 2$, and over the rational numbers, no number does.
-
“$7$ is prime and $4$ is not prime”
“$7$ is prime and $4$ is not prime” is a proposition, because the statement is true: $7$ is prime, and $4$ is not prime.
-
$\forall x \, (x^2 \geq 0)$, with $x$ ranging over $\reals$
With $x$ ranging over $\reals$, $\forall x \, (x^2 \geq 0)$ is a proposition, because it is true.
Non-examples
-
“$x > 3$”
“$x > 3$” is not a proposition, because it is not true or false until $x$ is given.
-
$p \land \neg q$
$p \land \neg q$ is not a proposition, because it is not true or false by itself—the truth value depends on the truth values of $p$ and $q$.
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 | proposition | propositional formula | Why |
|---|---|---|---|
| “$7$ is prime” | ✓ | ✗ | |
| $p \land \neg q$ | ✗ | ✓ | |
| “$7$ is prime and $4$ is not prime” | ✓ | ✗ | Substituting “$7$ is prime” for $p$ and “$4$ is prime” for $q$ in the formula $p \land \neg q$ gives the proposition “$7$ is prime and $4$ is not prime,” which is true. |
Missing example: p_lor_neg_p | |||
Notes
- A propositional formula plays the same role for propositions that an algebraic expression such as $x + 1$ plays for numbers: the formula has a value only once its variables have values.