Skip to main content
\(\newcommand{\identity}{\mathrm{id}} \newcommand{\notdivide}{{\not{\mid}}} \newcommand{\notsubset}{\not\subset} \newcommand{\lcm}{\operatorname{lcm}} \newcommand{\gf}{\operatorname{GF}} \newcommand{\inn}{\operatorname{Inn}} \newcommand{\aut}{\operatorname{Aut}} \newcommand{\Hom}{\operatorname{Hom}} \newcommand{\cis}{\operatorname{cis}} \newcommand{\chr}{\operatorname{char}} \newcommand{\Null}{\operatorname{Null}} \renewcommand{\vec}[1]{\mathbf{#1}} \newcommand{\lt}{<} \newcommand{\gt}{>} \newcommand{\amp}{&} \)

## Read the Online Textbook for the full content.

## Section 3.2 Truth Tables and Propositions Generated by a Set

### Subsection 3.2.1 Truth Tables

Consider the compound proposition \(c= (p \land q)\lor (\neg q \land r)\text{,}\) where \(p\text{,}\) \(q\text{,}\) and \(r\) are propositions.

- Example of a proposition generated by \(p\text{,}\) \(q\text{,}\) and \(r\text{.}\)
- We will define this terminology later in the section.
- Each of \(p, q, r\) has two possible truth values, it follows that there are 23=8 different combinations of truth values that determine a value for \(c\text{.}\)
- These values can be obtained from a truth table for \(c\text{.}\)
- To construct the truth table, we build \(c\) from \(p\text{,}\) \(q\text{,}\) and \(r\) and 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 for \(c\text{.}\)
- The other columns are work space needed to build up to \(c\text{.}\)

Table 3.2.1. Truth Table for \(c= (p \land q)\lor (\neg q \land r)\)

\(p\) | \(q\) | \(r\) | \(p\land q\) | \(\neg q\) | \(\neg q\land r\) | \((p\land q)\lor (\neg q\land r)\)
0 | 0 | 0 | 0 | 1 | 0 | 0
0 | 0 | 1 | 0 | 1 | 1 | 1
0 | 1 | 0 | 0 | 0 | 0 | 0
0 | 1 | 1 | 0 | 0 | 0 | 0
1 | 0 | 0 | 0 | 1 | 0 | 0
1 | 0 | 1 | 0 | 1 | 1 | 1
1 | 1 | 0 | 1 | 0 | 0 | 1
1 | 1 | 1 | 1 | 0 | 0 | 1

- The first 3 columns of the truth table are an enumeration of the eight three-digit binary integers.
- Standard order in which the cases are listed.
- In general, if \(c\) is generated by \(n\) simple propositions, then the truth table for \(c\) will have \(2^n\) rows with the first \(n\) columns being an enumeration of the \(n\) digit binary integers.
- In our example, we can see that for exactly four of the eight cases, \(c\) will be true. For example, if \(p\) and \(r\) are true and \(q\) is false (the sixth case), then \(c\) is true.

Let \(S\) be 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 a recursive definition.

### Subsection 3.2.2 Propositions Generated by a Set

#### Definition 3.2.2. Proposition Generated by a Set.

Let \(S\) be any set of propositions. A proposition generated by \(S\) is any valid combination of propositions in \(S\) with conjunction, disjunction, and negation. Or, to be more precise,

1. If \(p \in S\text{,}\) then \(p\) is a proposition generated by \(S\text{,}\) and

2. If \(x\) and \(y\) are propositions generated by \(S\text{,}\) then so are \((x)\text{,}\) \(\neg x\text{,}\) \(x\lor y\) , and \(x\land y\text{.}\)

Note: We have not included the conditional and biconditional in the definition because they can both be generated from conjunction, disjunction, and negation, as we will see later.

If \(S\) is a finite set, then we may use slightly different terminology. For example, if \(S = \{p, q, r\}\text{,}\) we might say that a proposition is generated by \(p, q\text{,}\) and \(r\) instead of from \(\{p, q, r\}\text{.}\)

## Operator Precedence

Use the following hierarchy (order) for interpreting propositions, with parentheses overriding it:

- 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 \land q \lor r\) is taken to mean \((p \land q)\lor r\text{.}\)

These precedence rules are universal, and are exactly those used by computer languages to interpret logical expressions.

#### Example 3.2.3. Examples of the Hierarchy of Logical Operations.

A few shortened expressions and their fully parenthesized versions:

1. \(p \land q \land r\) is \((p \land q) \land r\text{.}\)

2. \(\neg p \lor \neg r\) is \((\neg p) \lor (\neg r)\text{.}\)

3. \(\neg \neg p\) is \(\neg (\neg p)\text{.}\)

4. \(p \leftrightarrow q\land r\rightarrow s \) is \(p \leftrightarrow ((q\land r)\rightarrow s)\text{.}\)

A proposition generated by a set \(S\) need not include each element of \(S\) in its expression. For example, \(\neg q \land r\) is a proposition generated by \(p, q\text{,}\) and \(r\text{.}\)

### Exercises 3.2.3 Exercises

#### 1.

Construct the truth tables of:

1. \(\displaystyle p\lor p\)

2. \(\displaystyle p\land (\neg p)\)

3. \(\displaystyle p\lor (\neg p)\)

4. \(\displaystyle p \land p\)

Answer.

1. \(\displaystyle \begin{array}{cc} p & p\lor p \\ \hline 0 & 0 \\ 1 & 1 \\ \end{array}\)

2. \(\displaystyle \begin{array}{ccc} p & \neg p & p\land (\neg p) \\ \hline 0 & 1 & 0 \\ 1 & 0 & 0 \\ \end{array}\)

3. \(\displaystyle \begin{array}{ccc} p & \neg p & p\lor (\neg p) \\ \hline 0 & 1 & 1 \\ 1 & 0 & 1 \\ \end{array}\)

4. \(\displaystyle \begin{array}{cc} p & p\land p \\ \hline 0 & 0 \\ 1 & 1 \\ \end{array}\)

#### 2.

Construct the truth tables of:

1. \(\displaystyle \neg (p\land q )\)

2. \(\displaystyle p \land (\neg q)\)

3. \(\displaystyle (p \land q)\land r\)

4. \(\displaystyle (p \land q) \lor (q \land r)\lor (r \land p)\)

5. \(\displaystyle \text{ }\neg p\lor \neg q\)

6. \(\displaystyle p \lor q \lor r \lor s\)

#### 3.

Rewrite the following with as few extraneous parentheses as possible:

1. \(\displaystyle (\neg ((p) \land (r))) \lor (s)\)

2. \(\displaystyle ((p) \lor (q)) \land ((r) \lor (q))\)

Answer.

1. \(\displaystyle \neg (p\land r) \lor s\)

2. \(\displaystyle (p\lor q) \land (r\lor q)\)

#### 4.

In what order are the operations in the following propositions performed?

1. \(\displaystyle p \lor \neg q \lor r\land \neg p\)

2. \(\displaystyle p \land \neg q \land r \land \neg p\)

#### 5.

Determine the number of rows in the truth table of a proposition containing four variables \(p, q, r, \textrm{ and } s\text{.}\)

Answer.

\(2^4 = 16\) rows.

#### 6.

If there are 45 lines on a sheet of paper, and you want to reserve one line for each line in a truth table, how large could \(\lvert S\rvert \) be if you can write truth tables of propositions generated by \(S\) on the sheet of paper?