2.2: Conjunctions and Disjunctions
- Page ID
- 23236
\( \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}}} \)
\(\newcommand{\avec}{\mathbf a}\) \(\newcommand{\bvec}{\mathbf b}\) \(\newcommand{\cvec}{\mathbf c}\) \(\newcommand{\dvec}{\mathbf d}\) \(\newcommand{\dtil}{\widetilde{\mathbf d}}\) \(\newcommand{\evec}{\mathbf e}\) \(\newcommand{\fvec}{\mathbf f}\) \(\newcommand{\nvec}{\mathbf n}\) \(\newcommand{\pvec}{\mathbf p}\) \(\newcommand{\qvec}{\mathbf q}\) \(\newcommand{\svec}{\mathbf s}\) \(\newcommand{\tvec}{\mathbf t}\) \(\newcommand{\uvec}{\mathbf u}\) \(\newcommand{\vvec}{\mathbf v}\) \(\newcommand{\wvec}{\mathbf w}\) \(\newcommand{\xvec}{\mathbf x}\) \(\newcommand{\yvec}{\mathbf y}\) \(\newcommand{\zvec}{\mathbf z}\) \(\newcommand{\rvec}{\mathbf r}\) \(\newcommand{\mvec}{\mathbf m}\) \(\newcommand{\zerovec}{\mathbf 0}\) \(\newcommand{\onevec}{\mathbf 1}\) \(\newcommand{\real}{\mathbb R}\) \(\newcommand{\twovec}[2]{\left[\begin{array}{r}#1 \\ #2 \end{array}\right]}\) \(\newcommand{\ctwovec}[2]{\left[\begin{array}{c}#1 \\ #2 \end{array}\right]}\) \(\newcommand{\threevec}[3]{\left[\begin{array}{r}#1 \\ #2 \\ #3 \end{array}\right]}\) \(\newcommand{\cthreevec}[3]{\left[\begin{array}{c}#1 \\ #2 \\ #3 \end{array}\right]}\) \(\newcommand{\fourvec}[4]{\left[\begin{array}{r}#1 \\ #2 \\ #3 \\ #4 \end{array}\right]}\) \(\newcommand{\cfourvec}[4]{\left[\begin{array}{c}#1 \\ #2 \\ #3 \\ #4 \end{array}\right]}\) \(\newcommand{\fivevec}[5]{\left[\begin{array}{r}#1 \\ #2 \\ #3 \\ #4 \\ #5 \\ \end{array}\right]}\) \(\newcommand{\cfivevec}[5]{\left[\begin{array}{c}#1 \\ #2 \\ #3 \\ #4 \\ #5 \\ \end{array}\right]}\) \(\newcommand{\mattwo}[4]{\left[\begin{array}{rr}#1 \amp #2 \\ #3 \amp #4 \\ \end{array}\right]}\) \(\newcommand{\laspan}[1]{\text{Span}\{#1\}}\) \(\newcommand{\bcal}{\cal B}\) \(\newcommand{\ccal}{\cal C}\) \(\newcommand{\scal}{\cal S}\) \(\newcommand{\wcal}{\cal W}\) \(\newcommand{\ecal}{\cal E}\) \(\newcommand{\coords}[2]{\left\{#1\right\}_{#2}}\) \(\newcommand{\gray}[1]{\color{gray}{#1}}\) \(\newcommand{\lgray}[1]{\color{lightgray}{#1}}\) \(\newcommand{\rank}{\operatorname{rank}}\) \(\newcommand{\row}{\text{Row}}\) \(\newcommand{\col}{\text{Col}}\) \(\renewcommand{\row}{\text{Row}}\) \(\newcommand{\nul}{\text{Nul}}\) \(\newcommand{\var}{\text{Var}}\) \(\newcommand{\corr}{\text{corr}}\) \(\newcommand{\len}[1]{\left|#1\right|}\) \(\newcommand{\bbar}{\overline{\bvec}}\) \(\newcommand{\bhat}{\widehat{\bvec}}\) \(\newcommand{\bperp}{\bvec^\perp}\) \(\newcommand{\xhat}{\widehat{\xvec}}\) \(\newcommand{\vhat}{\widehat{\vvec}}\) \(\newcommand{\uhat}{\widehat{\uvec}}\) \(\newcommand{\what}{\widehat{\wvec}}\) \(\newcommand{\Sighat}{\widehat{\Sigma}}\) \(\newcommand{\lt}{<}\) \(\newcommand{\gt}{>}\) \(\newcommand{\amp}{&}\) \(\definecolor{fillinmathshade}{gray}{0.9}\)Given two real numbers \(x\) and \(y\), we can form a new number by means of addition, subtraction, multiplication, or division, denoted \(x+y\), \(x-y\), \(x\cdot y\), and \(x/y\), respectively. The symbols \(+\), \(-\), \(\cdot\) , and \(/\) are binary operators because they all work on two operands. In fact, the negative sign in \(-x\) can be regarded as a unary operator that changes the sign of \(x\).
In a similar manner, from one or more logical statements, we can form a compound statement by joining them with logical operators, which are also called logical connectives because they are used to connect logical statements. Obviously, negation is a unary operation.
Since a compound statement is itself a statement, it is either true or false. Therefore, we define a logical operation by describing the truth value of the resulting compound statement. The first two binary operations we shall study are conjunction and disjunction. They perform the “and” and “or” operations, respectively.
AND \(\wedge\) OR \(\vee\)
| name | meaning | notation | truth value |
|---|---|---|---|
| conjunction | \(p\) and \(q\) | \(p \wedge q\) | true if both \(p\) and \(q\) are true, false otherwise |
| disjunction | \(p\) or \(q\) | \(p \vee q\) | false if both \(p\) and \(q\) are false, true otherwise |
Their truth values are summarized in the following truth table:
| \(p\) | \(q\) | \(p\wedge q\) | \(p\vee q\) |
|---|---|---|---|
| T | T | T | T |
| T | F | F | T |
| F | T | F | T |
| F | F | F | F |
Example \(\PageIndex{1} \label{eg:conjdisj-01}\)
Do not use mathematical notations as abbreviation in writing. For example, do not write “\(x \wedge y\) are real numbers” if you want to say “\(x\) and \(y\) are real numbers.”
In fact, the phrase “\(x \wedge y\) are real numbers” is syntactically incorrect. Since \(\wedge\) is a binary logical operator, it is used to connect two logical statements. Here, the “\(x\)” before \(\wedge\) is not a logical statement. Therefore we cannot write “\(x \wedge y\) are real numbers.”
Incidentally, the statement “\(x\) and \(y\) are real numbers” is actually a conjunction. It means “\(x\) is a real number and \(y\) is a real number,” or symbolically, \[(x\in\mathbb{R}) \wedge (y\in\mathbb{R}).\] It is wrong to write “\(x\wedge y\in\mathbb{R}\).” Can you explain why?
hands-on exercise \(\PageIndex{1} \label{he:conjdisj-01}\)
Write “\(x\) and \(y\) are rational” as a conjunction, first in words, then in mathematical symbols.
Example \(\PageIndex{2} \label{eg:conjdisj-02}\)
The statement “New York is the largest state in the United States and New York City is the state capital of New York” is clearly a conjunction. A conjunction of two statements is true only when both statements are true. Since New York is not the largest state in the United States, the conjunction is false.
In general, in a conjunction of two statements, if the first statement is false, no further consideration of the second statement is necessary since we know the conjunction must be false. In computer science, this is referred to as the short circuit evaluation.
Example \(\PageIndex{3} \label{eg:conjdisj-03}\)
The statement “\(\sqrt{30}\) is greater than 6 or \(\sqrt{30}\) is less than 5” can be expressed symbolically as \[\big(\sqrt{30}>6\big) \vee \big(\sqrt{30}<5\big).\] Both statements “\(\sqrt{30}>6\)” and “\(\sqrt{30}<5\)” are false. Hence, their disjunction is also false.
Example \(\PageIndex{4} \label{eg:conjdisj-04}\)
Determine the truth values of the following statements:
- \(\big(\sqrt{30}>5\big) \wedge \big(\sqrt{30}>7\big)\)
- Either \(\big(\sqrt{30}<5\big)\) or \(\big(\sqrt{30}>7\big)\)
- Solution
-
(a) Since \(\sqrt{30}>5\) is true, but \(\sqrt{30}>7\) is false, their conjunction is false.
(b) Since \(\sqrt{30}<5\) is false, and \(\sqrt{30}>7\) is also false, their disjunction is false.
hands-on exercise \(\PageIndex{2} \label{he:conjdisj-02}\)
Determine the truth values of the following statements:
- \(\big(\sqrt{30}<5\big)\) and \(\big(\sqrt{30}>7\big)\).
- \(\big(\sqrt{30}>5\big) \vee \big(\sqrt{30}<7\big)\).
Be sure to show your reasons.
example \(\PageIndex{5} \label{eg:twoleg}\)
What does “\(0 \leq x \leq 1\)” really mean, logically?
- Solution
-
It means the conjunction “\((x \geq 0) \wedge (x \leq 1)\).” Hence, given a real number \(x\), to test whether \(0\leq x\leq 1\), we have to check whether \(x\geq 0\) and \(x\leq 1\).
hands-on exercise \(\PageIndex{3} \label{he:conjdisj-03}\)
Write \(5<x<8\) as a conjunction.
hands-on exercise \(\PageIndex{4} \label{he:conjdisj-04}\)
Many students assume that they can negate “\(0 \leq x \leq 1\)” by reversing the signs. However, neither “\(0\geq x\geq 1\)” nor “\(0 > x > 1\)” is the correct negation. For example, what does “\(0\geq x\geq 1\)” really mean? Actually, the statement “\(0\geq x\geq 1\)” is syntactically correct, and it is always false. Can you explain why?
In the everyday usage of most languages, when we say “\(p\) or \(q\),” we normally mean exclusive or, which means either \(p\) or \(q\) is true, but not both. An example is “I either pass or fail this course,” which really means
Either I pass this course or I fail this course.
Sometimes, as illustrated in the statement
Either you pass this course, or I pass this course.
the connective “or” can be interpreted as an inclusive or. The actual meaning of “or” in human languages depends on the context. In mathematics, however, “or” always means inclusive or.
Logically Equivalent \(\equiv\)
Definition
Two logical formulas \(p\) and \(q\) are said to be logically equivalent, denoted \[p\equiv q,\] if \(p \mbox{ and } q\) have have identical truth values in all cases.
Consider this truth table:
| \(p\) | \(\overline{p}\) | \(\overline{\overline{p}}\) |
|---|---|---|
| T | F | T |
| F | T | F |
Do you see the truth table above shows \(p\equiv\overline{\overline{p}},?\)
Summary and Review
- The conjunction “\(p\) and \(q\)” is denoted “\(p\wedge q\)”. It is true only when both \(p\) and \(q\) are true.
- The disjunction “\(p\) or \(q\)” is denoted “\(p\vee q\)”. It is false only when both \(p\) and \(q\) are false.
- The inequality “\(a<x<b\)” is actually a conjunction, it means “\((a<x) \wedge (x<b)\)”.
- Likewise, the phrase “\(x\) and \(y\) are rational” is also a conjunction, it means “\(x\) is rational and \(y\) is rational.” Symbolically, we can write ”\(x\in\mathbb{Q} \wedge y\in\mathbb{Q}\).”
Exercises \(\PageIndex{}\)
Exercise \(\PageIndex{1} \label{ex:conjdisj-01}\)
Let \(p\), \(q\), and \(r\) represent the following statements:
| \(p\): | Sam had pizza last night. |
| \(q\): | Chris finished her homework. |
| \(r\): | Pat watched the news this morning. |
Write each of these statements in symbolic form:
(a) Sam had pizza last night and Chris finished her homework.
(b) Chris did not finish her homework and Pat watched the news this morning.
(c) Sam did not have pizza last night or Chris did not finish her homework.
(d) Either Chris finished her homework or Pat watched the news this morning, but not both.
- Answer
-
(a) \(p\wedge q\)
(b) \(\overline{q}\wedge r\)
(c) \(\overline{p}\vee \overline{q}\)
(d) \((q\vee r) \wedge \overline{q\wedge r}\)
Exercise \(\PageIndex{2} \label{ex:conjdisj-02}\)
Define the propositional variables \(p\), \(q\), and \(r\) as in Problem 1. Express, in words, the following symbolic statements:
(a) \(p\vee q\)
(b) \(q\wedge r\)
(c) \((p\wedge q)\vee r\)
(d) \(\overline{p}\vee r\)
Exercise \(\PageIndex{3} \label{ex:conjdisj-03}\)
Consider the following statements:
| \(p\): | Niagara Falls is in New York. |
| \(q\): | New York City is the state capital of New York. |
| \(r\): | New York City will have more than 40 inches of snow in 2525. |
The statement \(p\) is true, but the statement \(q\) is false. Represent each of the following statements in symbolic form. What are their truth values if \(r\) is true? What if \(r\) is false?
(a) Niagara Falls is in New York and New York City is the state capital of New York.
(b) Niagara Falls is in New York or New York City is the state capital of New York.
(c) Either Niagara Falls is in New York and New York City is the state capital of New York, or New York City will have more than 40 inches of snow in 2525.
(d) New York City is not the state capital of New York and New York City will have more than 40 inches of snow in 2525.
- Answer
-
(a) \(p\wedge q\); always false regardless of the value of \(r\).
(b) \(p\vee q\); always true regardless of the value of \(r\).
(c) \((p\wedge q)\vee r\); true if \(r\) is true, and false if \(r\) is false.
(d) \(\overline{q}\wedge r\); true if \(r\) is true, and false if \(r\) is false
Exercise \(\PageIndex{4} \label{ex:conjdisj-04}\)
Determine the truth values of these statements:
(a) \((0\in\mathbb{Q}) \wedge (-4\in\mathbb{Z})\)
(b) \((-4\in\mathbb{N}) \vee (3\in2\mathbb{Z})\)
Exercise \(\PageIndex{5} \label{ex:conjdisj-05}\)
Determine the truth values of these statements:
(a) \((-3>-2) \wedge (\sqrt{3}>2)\)
(b) \((4^2-5^2\leq0) \vee (\sqrt{3^2+4^2}=3+4)\)
- Answer
-
(a) false
(b) true
Exercise \(\PageIndex{6} \label{ex:conjdisj-06}\)
Construct the truth tables for the following logic statements:
(a) \(p\wedge\overline{q}\)
(b) \(\overline{p}\vee q\)
(c) \(\overline{p\wedge q}\)
Exercise \(\PageIndex{7} \label{ex:conjdisj-07}\)
Rewrite the following expressions as conjunction:
(a) \(4\leq x\leq 7\)
(b) \(4 < x\leq 7\)
(c) \(4\leq x < 7\)
- Answer
-
(a) \((x\geq 4)\wedge (x\leq 7)\)
(b) \((x >4)\wedge (x\leq 7)\)
(c) \((x\geq 4)\wedge (x < 7)\)
Exercise \(\PageIndex{8} \label{ex:conjdisj-08}\)
In words, the inequality \(0<x<1\) means “\(x\) is between 0 and 1.” Its negation means \(x\) is outside this range. Hence, the negation is “\(x\leq 0\) or \(x\geq1\).” Find the negation of the following inequalities:
(a) \(0\leq x\leq 4\)
(b) \(-2 < x\leq 5\)
(c) \(1.76\leq x<\sqrt{5}\)
Exercise \(\PageIndex{9} \label{ex:conjdisj-09}\)
In volleyball it is important to know which team is serving, because a team scores a point only if that team is serving and wins a volley. If the serving team loses the volley, then the other team gets to serve. Thus, to keep score in a volleyball game between teams \(A\) and \(B\), it may be useful to define propositional variables \(p\) and \(q\), where \(p\) is true if team \(A\) is serving (hence false if team \(B\) is serving); and \(q\) is true if team \(A\) wins the current volley (hence false if team \(B\) wins it).
- Give a formula that is true if team \(A\) scores a point and is false otherwise.
- Give a formula that is true if team \(B\) scores a point and is false otherwise.
- Give a formula that is true if the serving team loses the current volley and is false otherwise.
- Give a formula whose truth value determines whether the serving team will serve again.
Exercise \(\PageIndex{10}\)
Construct the truth tables for the following logic statements:
(a) \(p\wedge\overline{p}\)
(b) \(p\vee\overline{p}\)
(c) \(p\wedge (q \vee r)\)
(d) \((p \wedge q)\vee (q \wedge r)\)
(e) \(p \vee (q \wedge \overline r)\)
Exercise \(\PageIndex{11} \label{ex:conjdisj-11}\)
The exclusive or operation, denoted \(p\veebar q\), means “\(p\) or \(q\), but not both.”
Construct the truth table for \(p\veebar q\).
- Answer
-
\(p\) \(q\) \(p\veebar q\) T T F T F T F T T F F F