Compound propositions

Subsection 1.1.2 Compound propositions

Using logical operators, we will be able to use existing propositions to create compound propositions. . .

Definition 1.1.2.1.

Let \(p\) be a proposition. The negation of \(p\) , denoted \(\lnot p\) , is the proposition “It is not the case that \(p\text{.}\)” It is read as “Not \(p\)” and has the opposite truth value from \(p\text{.}\)

🔗

Figure 1.1.2.2 gives the truth table for negation. If \(p\) is true, then \(\lnot p\) is false. If \(p\) is false, then \(\lnot p\) is true.

🔗

\begin{equation*} \begin{array}{|*{1}{c|}|*{1}{c|}} \hline p\amp \lnot p\\ \hline \true \amp \false \\ \false \amp \true \\ \hline \end{array} \end{equation*}

🔗

Figure 1.1.2.2. Truth table for negation (not \(p\) ).

🔗

Example 1.1.2.3.

Let \(p\) be the proposition “\(2 + 3 = 5\)”. The negation \(\lnot p\) is the proposition “It is not the case that \(2 + 3 = 5\) .” More directly, \(\lnot p\) can be expressed as “\(2 + 3 \neq 5\) .” The original proposition \(p\) is true, so the negation is false.

🔗

Example 1.1.2.4. Negation of a false proposition.

Let \(q\) be the proposition “\(2^3 = 5\text{.}\)” The negation \(\lnot q\) is the proposition “It is not the case that \(2^3 = 5\) .” More directly, \(\lnot p\) can be expressed as “\(2^3 \neq 5\) .” The original proposition is false, so the negation is true.

🔗

Definition 1.1.2.5.

Let \(p\) and \(q\) be propositions. The conjunction of \(p\) and \(q\text{,}\) denoted \(p\land q\) is the proposition “\(p\) and \(q\text{.}\)” It is true when \(p\) and \(q\) are both true and false otherwise.

🔗

The conjunction is often referred to as and . Figure 1.1.2.6 gives the truth table for conjunction. If \(p\) is true and \(q\) is true, then \(p\land q\) is true. If \(p\) or \(q\) are false (including the case where both \(p\) and \(q\) are false), then the conjunction \(p\land q\) is false.

🔗

\begin{equation*} \begin{array}{|*{2}{c|}|*{1}{c|}} \hline p\amp q\amp p\land q\\ \hline \true \amp \true \amp \true \\ \true \amp \false \amp \false \\ \false \amp \true \amp \false \\ \false \amp \false \amp \false \\ \hline \end{array} \end{equation*}

🔗

Figure 1.1.2.6. Truth table for conjunction ( \(p\) and \(q\)).

🔗

Example 1.1.2.7. Conjunction is true.

Let \(p\) be the proposition “\(1 + 2 = 3\text{,}\)” and let \(q\) be the proposition “\(3 + 4 = 7\) .”

🔗

Since \(p\) and \(q\) are both true, the conjunction \(p\land q\) is true. The conjunction \(p\land q\) can be expressed as “\(1 + 2 = 3\) and \(3 + 4 = 7\text{.}\)”

🔗

Example 1.1.2.8. Conjuction is false.

Let \(p\) be the proposition “\(5 \lt 3\)” and let \(q\) be the proposition “\(4 = 7\) .” Both \(p\) and \(q\) are false.

🔗

The conjunction \(p\land q\) is false. The conjunction \(p\land q\) can be expressed as “\(5 \lt 3\) and \(4 = 7\text{.}\)”

🔗

Example 1.1.2.9. Conjunction is true.

Let \(p\) be the proposition “\(5 \lt 5\)” and let \(q\) be the proposition “\(10 = 5 \cdot 2\) .”

🔗

The conjunction \(p\land q\) is false because \(p\) is false. The fact that \(q\) is true is not enough to make the conjunction true. The conjunction \(p\land q \) can be expressed as “\(5 \lt 5\) and \(10 = 5 \cdot 2\text{.}\)”

🔗

Example 1.1.2.10. Alice and Bob are tall.

Let \(a\) be the propositions “Alice is tall,” and let \(b\) be “Bob is tall.”

🔗

The conjunction \(a\land b\) of \(a\) and \(b\) is the proposition “Alice is tall, and Bob is tall.” More directly, \(a\land b\) can be expressed as “Alice and Bob are tall.” The conjunction \(a\land b\) is true if Alice and Bob are both tall; it is false if either one is not tall.

🔗

Definition 1.1.2.11.

Let \(p\) and \(q\) be propositions. The disjunction of \(p\) and \(q\text{,}\) denoted \(p\lor q\) , is the proposition “\(p\) or \(q\text{.}\)” It is false when \(p\) and \(q\) are both false and true otherwise.

🔗

The disjunction is often referred to as or . Figure 1.1.2.12 gives the truth table for disjunction. If at least one of \(p\) or \(q\) is true, then the disjunction \(p\lor q\) is true. If \(p\) and \(q\) are both false, then \(p\lor q\) is false.

🔗

\begin{equation*} \begin{array}{|*{2}{c|}|*{1}{c|}} \hline p\amp q\amp p\lor q\\ \hline \true \amp \true \amp \true \\ \true \amp \false \amp \true \\ \false \amp \true \amp \true \\ \false \amp \false \amp \false \\ \hline \end{array} \end{equation*}

🔗

Figure 1.1.2.12. Truth table for disjunction ( \(p\) or \(q\)).

🔗

A disjunction is true if at least one of the propositions is true.

🔗

Example 1.1.2.13. Squares and triangles.

Let \(s\) be the proposition “Squares have four sides,” and let \(t\) be “Triangles have five sides.”

🔗

The disjunction \(s\lor t\) of \(s\) and \(t\) is the proposition “Squares have four sides, or triangles have five sides.” The disjunction is true because squares have four sides. It does not matter that triangles don’t have five sides. Disjunctions are only false when both propositions being combined are false.

🔗

The disjunction of two true propositions is true.

🔗

Example 1.1.2.14. Greensboro and Japan.

Let \(g\) be the proposition “I live in Greensboro,” and let \(j\) be the proposition “I was born in Japan.” Then \(g\) and \(j\) are both true. The disjunction \(g\lor j\) is true and can be expressed as “I live in Greensboro, or I was born in Japan.”.

🔗

The only way the disjunction of two propositions is false is if both propositions are false.

🔗

Example 1.1.2.15. Mascot and motto.

Let \(s\) be the proposition “UNCG’s mascot is Rudy the Rodeo Clown,” and let \(m\) be the the proposition “The UNCG motto is Sleep.” The disjunction can be expressed as \(s\lor m =\) “UNCG’s mascot is Rudy the Rodeo Clown and motto is Sleep.” Since the mascot is Spiro the Spartan and the motto is Service, both \(s\) and \(m\) are false. Thus the disjunction \(s\lor m\) is also false.

🔗

Definition 1.1.2.16.

Let \(p\) and \(q\) be propositions. The exclusive disjunction of \(p\) and \(q\text{,}\) denoted \(p\lxor q\) , is the proposition “\(p\) or \(q\) but not both.” It is true when exactly one of \(p\) or \(q\) is true and false otherwise.

🔗

The exclusive disjunction is often referred to as exclusive or or xor. Figure 1.1.2.17 gives the truth table for exclusive disjunction.

🔗

The exclusive disjunction of one true proposition and one false proposition is true.

🔗

\begin{equation*} \begin{array}{|*{2}{c|}|*{1}{c|}} \hline p\amp q\amp p\lxor q\\ \hline \true \amp \true \amp \false \\ \true \amp \false \amp \true \\ \false \amp \true \amp \true \\ \false \amp \false \amp \false \\ \hline \end{array} \end{equation*}

🔗

Figure 1.1.2.17. Truth table for exclusive disjunction ( \(p\) xor \(q\)).

🔗

Example 1.1.2.18. Ostrich and beaver.

Let \(o\) be the statement “An ostrich is a bird,” and let \(b\) be the statement “A beaver is a bird.”

🔗

The exclusive disjunction is \(o\lxor b\) is “An ostrich is a bird, or a beaver is a bird but not both.”. The exclusive disjunction is true, because an ostrich is a bird and a beaver is not a bird.

🔗

The exclusive disjunction of two false propositions is false.

🔗

Example 1.1.2.19. False xor False.

The exclusive disjunction of “Dogs are reptiles,” and “Snakes are mammals,” is “Dogs are reptiles or snakes are mammals, but not both.” The exclusive disjunction is false, because dogs are not reptiles, and snakes are not mammals. Exclusive disjunctions are true when exactly one of the propositions being combined is true.

🔗

The exclusive disjunction of two true propositions is false.

🔗

Example 1.1.2.20. True xor True.

The exclusive disjunction of “Dogs are mammals,” and “Snakes are reptiles,” is “Dogs are mammals or snakes are reptiles, but not both.” The exclusive disjunction is false, because dogs are mammals and snakes are reptiles. Exclusive disjunctions are true when exactly one of the propositions being combined is true.

🔗

Definition 1.1.2.21.

Let \(p\) and \(q\) be propositions. The conditional of \(p\) and \(q\text{,}\) denoted \(p \implies q\) , is the proposition “if \(p\) then \(q\) .” It is false when \(p\) is true and \(q\) is false and true otherwise. In the conditional \(p \implies q\) , \(p\) is called the hypothesis and \(q\) is called the conclusion .

🔗

The conditional is often referred to as if then. Figure 1.1.2.28 gives the truth table for the conditional.

🔗

Example 1.1.2.22. True conditional.

The conditional of “\(5^2 =10\)” and “\(3 \cdot 4 = 12\)” is “if \(5^2 =10\) , then \(3 \cdot 4 = 12\text{.}\)” The conditional is true because the the hypothesis is false. Similarly, the conditional “if \(5^2 =10\) , then \(3 \cdot 4 = 13\text{,}\)” is also true.

🔗

Example 1.1.2.23. False conditional.

The conditional “if \(3 \cdot 4 = 12\) , then \(5^2 =10\text{,}\)” is false because the the hypothesis is true, but the conclusion is false.

🔗

Definition 1.1.2.24.

Let \(p\) and \(q\) be propositions. The biconditional of \(p\) and \(q\text{,}\) denoted \(p \iff q\) , is the proposition “\(p\) if and only if \(q\) .” In other words, \(p \iff q\) is the proposition \((p \implies q)\land (q \implies p)\text{.}\) It is true when \(p\) and \(q\) have the same truth values and false otherwise.

🔗

The biconditional is often referred to as if and only if or iff . Figure 1.1.2.28 gives the truth table for the conditional.

🔗

The biconditional \(p \iff q\) is true when \(p\) and \(q\) are both true.

🔗

Example 1.1.2.25. True iff True.

The biconditional “\(2 + 4 = 6\) if and only if \(2 \cdot 4 = 8\text{.}\)” is true because both component propositions are true. Biconditionals are true exactly when the component propositions have the same truth value.

🔗

The biconditional \(p \iff q\) is also true when \(p\) and \(q\) are both false.

🔗

Example 1.1.2.26. False iff False.

The biconditional “\(2 + 4 = 7\) if and only if \(2 \cdot 4 = 9\)” is is true because both component propositions are false. Biconditionals are true exactly when the component propositions have the same truth value.

🔗

The biconditional \(p \iff q\) is false when \(p\) is true and \(q\) is false, or when \(p\) is false and \(q\) is true.

🔗

Example 1.1.2.27. False iff True.

The biconditional “\(1 = 2\) if and only if \(3 = 3\)” is false, because “\(1 = 2\)” is false and “\(3=3\)” is true.

🔗

\begin{equation*} \begin{array}{|*{2}{c|}|*{1}{c|}} \hline p\amp q\amp p \implies q\\ \hline \true \amp \true \amp \true \\ \true \amp \false \amp \false \\ \false \amp \true \amp \true \\ \false \amp \false \amp \true \\ \hline \end{array} \end{equation*}

🔗

Figure 1.1.2.28. Truth table for conditional (if \(p\) then \(q\)).

🔗

\begin{equation*} \begin{array}{|*{2}{c|}|*{1}{c|}} \hline p\amp q\amp p \iff q\\ \hline \true \amp \true \amp \true \\ \true \amp \false \amp \false \\ \false \amp \true \amp \false \\ \false \amp \false \amp \true \\ \hline \end{array} \end{equation*}

🔗

Figure 1.1.2.29. Truth tables for biconditional ( \(p\) if and only if \(q\)).

🔗

Example 1.1.2.30. Singing in a store.

Suppose \(p\) be the proposition “I’m in a store,” and let \(q\) be the proposition “I’m singing.” Then we have the following.

\(\lnot p\) is “I’m not in a store.”
🔗

🔗
\(p\land q\) is “I’m in a store, and I’m singing.”
🔗

🔗
\(p\lor q\) is “I’m in a store, or I’m singing.”
🔗

🔗
\(p\lxor q\) is “I’m in a store, or I’m singing but not both.”
🔗

🔗
\(p \implies q\) is “If I’m in a store, then I’m singing.”
🔗

🔗
\(p \iff q\) is “I’m in a store if and only if I’m singing.”
🔗

🔗

🔗

Example 1.1.2.31. Swimming with sharks.

Let \(p\) be the proposition “Swimming is allowed,” and let \(q\) be the proposition “Sharks have been spotted.”

“Swimming is not allowed,” can be written symbolically as \(\lnot p\) .
🔗

🔗
“Sharks have been spotted, but swimming is allowed,” can be written as \(q\land p\) . Note that “but” has been converted logically to “and” in this context. We will see more trickiness of the English language in Subsection 1.1.6.
🔗

🔗
“If sharks have not been spotted, then swimming is allowed,” can be written as \(\lnot q \implies p\) .
🔗

🔗

🔗

Figure 1.1.2.32. *Formal Logic* by Randal Munroe (`https://xkcd.com/1033/`. Note that this implies you should NOT honk solely because I stopped for a pedestrian and you’re behind me.
🔗

🔗

Prev Top Next