Skip to main content
Mathematics LibreTexts

3.3: Formulas

  • Page ID
    99064
    • Bob Dumas and John E. McCarthy
    • University of Washington and Washington University in St. Louis
    \( \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}}\)

    Loosely speaking, a formula is a mathematical expression with variables. Corresponding to each variable, \(x_{i}\), appearing in a formula is a universe, \(U_{i}\), from which that variable may be substituted.

    DEFINITION. Open formula An open mathematical formula in variables \(x_{1}, \ldots, x_{n}\) is a mathematical expression in which substitution of the \(x_{i}(1 \leq i \leq n)\) by specific elements from \(U_{i}\) yields a mathematical statement.

    EXAMPLE 3.8. Consider the formula, \[x^{2}+y^{2}=z^{2}\] in variables \(x, y\) and \(z\), all with universe \(\mathbb{N}\). Any substitution of the variables with natural numbers results in a statement. For instance, \[3^{2}+4^{2}=5^{2}\] or \[1^{2}+1^{2}=2^{2} .\] Of course, statements can be true or false, so some substitutions yield true statements, while others will yield false statements.

    In discussing a general formula in \(n\) variables, we may use the notation \(P\left(x_{1}, \ldots, x_{n}\right)\). For \(1 \leq i \leq n\), let \(U_{i}\) be the universe of the variable \(x_{i}\), and \(a_{i} \in U_{i}\). The statement that results from the substitution of \(a_{i}\) for \(x_{i}, 1 \leq i \leq n\), is written \(P\left(a_{1}, \ldots, a_{n}\right)\).

    If \(P\left(x_{1}, \ldots, x_{n}\right)\) is a formula in variables \(x_{1}, \ldots, x_{n}\), and for \(1 \leq i \leq\) \(n, U_{i}\) is the universe of \(x_{i}\), then we may think of \(\left(x_{1}, \ldots, x_{n}\right)\) as a single variable with universe \(U=\prod_{1 \leq i \leq n} U_{i}\).

    Formulas can fulfill many purposes in mathematics:

    (1) Characterize relationships between quantities

    (2) Define computations (3) Define sets

    (4) Define functions.

    EXAMPLE 3.9. Consider an open formula, \(P(x, y)\), in two variables, \[x^{2}+y^{2}=1,\] with universe \(\mathbb{R}^{2}\). That is, the universe of \(x\) is \(\mathbb{R}\) and the universe of \(y\) is \(\mathbb{R}\). One way to think of \(P(x, y)\) is as a means to partition \(\mathbb{R}^{2}\) into two sets:

    (1) the subset of the Cartesian Plane for which the equation is true, namely the unit circle;

    (2) the subset of the Cartesian Plane for which the equation is false, the complement of the unit circle in \(\mathbb{R}^{2}\).

    DEFINITION. Characteristic set, \(\chi_{P}\) Let \(P(x)\) be a formula, and \(U\) the universe of the variable \(x\). The subset of \(U\) for which the formula \(P\) holds is written \(\chi_{P}\). The set \(\chi_{P}\) is called the characteristic set of \(P(x)\).

    So, \[\chi_{\neg P}=U \backslash \chi_{P} .\]

    3.3.1. Formulas and Propositional Connectives.

    Propositional logic is easily extended to formulas. Let \(P(x)\) and \(Q(x)\) be formulas in the variable \(x\), with universe \(U\). Let \[R(x)=P(x) \wedge Q(x) .\] Then the characteristic set of \(R(x)\) is given by \[\chi_{R}=\{a \in U \mid T(P(a) \wedge Q(a))=1\}\] Hence \[\chi_{R}=\chi_{P} \cap \chi_{Q} .\] The propositional connective \(\wedge\) is strongly associated with the set operation \(\cap\). Similarly \(\vee\) may be associated with \(\cup, \neg\) with complement (in \(U\) ), and \(\Rightarrow\) with \(\subseteq\).


    This page titled 3.3: Formulas is shared under a CC BY 4.0 license and was authored, remixed, and/or curated by Bob Dumas and John E. McCarthy via source content that was edited to the style and standards of the LibreTexts platform; a detailed edit history is available upon request.

    • Was this article helpful?