- Last updated
- Save as PDF
- Page ID
- 54769
\( \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}}} \)
Summary of Logic Notation
Be sure to review this notation summary since these terms will be used throughout this unit.
The notation for logic operations has been gradually introduced as our study proceeds. Here is a summary:
∊ element of, x ∊ Y, x is an element of Set Y
∉ not an element of, x ∉ Y, x is not an element of Set Y
∧ and, conjunction, p ∧ q, p and q
∨ or, disjunction, p ∨ q, p or q
ᆨ not, ᆨp, not p; sometimes you will see the letter with a line over it, other times, you may see a preceding minus sign
⟶ conditional implication, p ⟶ q, if p then q
↔ biconditional implication, p ↔ q, p if and only if q
Truth Tables and Propositions Generated by a Set
What is in a set and what is not in a set leads to some interesting ways of analyzing truth or falsehood. In this section we use 0 for false (no) and 1 for true (yes). One can also speak in terms of "do-not" or "do", "do not perform this action" or "do this action". It is a matter of interpretation, an interpretation that must be established and remain consistent. We can write equations to express these ideas so that many factors can be considered and operated upon in a standard way. This section starts you down that path.
3.2 Truth Tables and Propositions Generated by a Set
3.2.1 Truth Tables
Consider the compound proposition \(c= (p \wedge q) \vee(\negq \wedge r)\), wherep,q, andrare propositions. This is an example of a proposition generated byp,q, andr. We will define this terminology later in the section. Since each of the three simple propositions has two possible truth values, it follows that there are eight different combinations of truth values that determine a value forc. These values can be obtained from a truth table forc. To construct the truth table, we buildcfromp,q, andrand from the logical operators. The result is the truth table below. Strictly speaking, the first three columns and the last column make up the truth table forc. The other columns are work space needed to build up toc.
Note that the first three columns of the truth table are an enumeration of the eight three-digit binary integers. This standardizes the order in which the cases are listed. In general, ifcis generated bynsimple propositions, then the truth table forcwill have \(2^n\) rows with the firstncolumns being an enumeration of thendigit binary integers. In our example, we can see at a glance that for exactly four of the eight cases,cwill be true. For example, ifpandrare true andqis false (the sixth case), thencis true.
LetSbe any set of propositions. We will give two definitions of a proposition generated by S. The first is a bit imprecise but should be clear. The second definition is called arecursive definition. If you find it confusing, use the first definition and return to the second later.
3.2.2 Propositions Generated by a Set
Definition 3.2.2: Proposition Generated by a Set.
LetSbe any set of propositions. A proposition generated bySis any valid combination of propositions inSwith conjunction, disjunction, and negation. Or, to be more precise,
- If \(p \epsilon \text{ } S\), thenpis a proposition generated byS, and
- Ifxandyare propositions generated byS, then so are (x), \(\neg x\), \( x \vee y\), and \( x \wedge y\).
Note: We have not included the conditional and biconditional in the definition because they can both be generated from conjunction, disjunction, andnegation, as we will see later.
IfSis a finite set, then we may use slightly different terminology. For example, if \(S =\{p,q,r\}\), we might say that a proposition is generated byp,q,andrinstead of from \(\{p,q,r\}\).
It is customary to use the following hierarchy for interpreting propositions,with parentheses overriding this order:
- First: Negation
- Second: Conjunction
- Third: Disjunction
- Fourth: The conditional operation
- Fifth: The biconditional operation
Within any level of the hierarchy, work from left to right. Using these rules, \(p \wedge q \vee r\) is taken to mean \((p \wedge q) \vee r\). These precedence rules are universal andare exactly those used by computer languages to interpret logical expressions.
Example 3.2.3: Examples of the Hierarchy of Logical Operations
Afew shortened expressions and their fully parenthesized versions:
- \(p \wedge q \wedge r\) is \((p \wedge q) \wedge r\).
- \(\neg p \vee \neg r\) is \((\neg p) \vee (\neg r)\).
- \(\neg \neg p\) is \(\neg(\neg p)\).
- \(p \leftrightarrow q \wedge r \to s\) is \(p \leftrightarrow ((q \wedge r) \to s)\)
A proposition generated by a setSneed not include each element ofSin its expression. For example, \(\neg q \wedge r\) is a proposition generated byp, q, andr.
