- Last updated
- Save as PDF
- Page ID
- 4799
\( \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}}\)
We can make a new statement from other statements; we call these compound propositions or compound statements.
Example \(\PageIndex{1}\):
- It is not the case that all birds can fly. (This is the negation of the statement all birds can fly).
- \(1+1=2\) and "All birds can fly". (Here the connector "and" was used to create a new statement).
Note the following four basic ways to start with one or more propositions and use them to make a more elaborate compound statement. If \(p\) and \(q\) are statements
then here are four compound statements made from them:
- \(\neg p \), Not \(p\) (i.e. the negation of \(p\)),
- \( p \wedge q,\, p\, \textit{and}\, q\),
- \(p\vee q, \,p \,\textit{or} \,q\) and
- \(p \rightarrow q,\: \textit{If} \; p \, \textit{then}\, q.\)
Example \(\PageIndex{2}\):
If \(p =\) "You eat your supper tonight" and \(q = \) "You get desert". Then
- Not \(p \) is "You don't eat your supper tonight".
- \(p\, \textit{and}\, q\) is "You eat your supper tonight and you get desert".
- \( p \,\textit{or} \,q\) is "You eat your supper tonight or you get desert".
- \(\textit{If} \; p \, \textit{then}\, q\) is "If you eat your supper tonight then you get dessert."
In English, we know these four propositions don't say the same thing. In logic, this is also the case, but we can make that clear by displaying the truth value possibilities. It is common to use a table to capture the possibilities for truth values of compound statements. We call such a table a truth table. Below are the possibilities: the first is the least profound. It says that a statement p is either true or false.
| \(p\) |
|---|
| \(T\) |
| \(F\) |
Negation
Truth tables are more useful in describing the possible truth values for various compound propositions. Consider the following truth table:
| \(p\) | \(\neg p\) |
|---|---|
| \(T\) | \(F\) |
| \(F\) | \(T\) |
The table above describes the truth value possibilities for the statements \(p\) and \(\neg p\), or "not p". As you can see, if \(p\) is true then \(\neg p\) is false and if \(p\) is false, the negation (i.e. not p) is true. \(\neg\) is the mathematical notation used to mean "not."
Example \(\PageIndex{3}\):
Consider the statement \(p\): \(1 + 1 = 3\).
Statement \(p\) can either be true or false, not both.
\(\neg p\) is "not \(p\)," or the negation of statement \(p\).
\(\neg p\) is \(1 + 1 \ne 3\).
You can see that the negation of a proposition affects only the proposition itself, not any other assumptions.
Conjunction
Conjunction statements use two or more propositions. If two or more simple propositions are involved the truth table gets bigger. Below is the truth table for "and," otherwise known as a conjunction. When is an and statement true? As the truth table indicates, only when both of the component propositions are true is the compound conjunction statement true:
| \(p\) | \(q\) | \(p \wedge q\) |
|---|---|---|
| \(T\) | \(T\) | \(T\) |
| \(T\) | \(F\) | \(F\) |
| \(F\) | \(T\) | \(F\) |
| \(F\) | \(F\) | \(F\) |
Example \(\PageIndex{4}\):
Consider statements \(p:= \,1 + 1 = 2\) and \(q:=\,2 < 5\).
Note that, \(p \wedge q\) is true only if both \(p\) and \(q\) are both true.
Since statements \(p\) and \(q\) are both true, \(p \wedge q\) is true.
Disjunction
Disjunction statements are compound statements made up of two or more statements and are true when one of the component propositions is true. They are called "Or Statements." In English, "or" is used in two ways:
- If a person is looking for a house with 4 bedrooms or a short commute, a real estate agent might present houses with either 4 bedrooms or a short commute or both 4 bedrooms and a short commute. This is called an inclusive or.
- If a person is asked whether they would like a co*ke or a Pepsi, they are expected to choose between the two options. This is an exclusive or: "both" is not an acceptable case.
In logic, we use inclusive or statements
| \(p\) | \(q\) | \(p \vee q\) |
|---|---|---|
| \(T\) | \(T\) | \(T\) |
| \(T\) | \(F\) | \(T\) |
| \(F\) | \(T\) | \(T\) |
| \(F\) | \(F\) | \(F\) |
The \(p \) or \( q\) proposition is only false if both component propositions \(p \) and \( q\) are false.
Example \(\PageIndex{5}\):
Consider the statement \(2 \leq -3\)
The statement reads "2 is less than or equal to -3", or "\(2 < -3 \vee 2 = -3\)" and can be broken into two component propositions:
- Proposition \(p\): \(2 < -3\) (False)
- Proposition \(q\): \(2 = -3\) (False)
Because propositions \(p\) and \(q\) are both false, the statement is false.
Example \(\PageIndex{6}\):
Consider the statement \(2 \leq 5\)
The statement's two component propositions are:
- Proposition \(p\): \(2 < 5\) (True)
- Proposition \(q\): \(2 = 5\) (False)
Since proposition \(p\) is true, the statement is true.
Conditional Statements
Consider the "if p then q" proposition. This is a conditional statement. Read the statements below. If these statements are made, in which instance is one lying (i.e. when is the overall statement false)?
Suppose, at suppertime, your mother makes the statement “If you eat your broccoli then you’ll get dessert.” Under what conditions could you say your mother is lying?
- If you eat your broccoli but don't get dessert, she lied!
- If you eat your broccoli and get dessert, she told the truth.
- If you don’t eat your broccoli and you don’t get dessert she told you the truth.
- If you don’t eat your broccoli but you do get dessert we still think she told the truth. After all, she only outlined one condition that was supposed to get you desert, she didn’t say that was the only way you could earn dessert. Maybe you had cauliflower instead.
Note that the order in which the cases are presented in the truth table is irrelevant. The cases themselves are important information, not their order relative to each other.
| \(p\) | \(q\) | \(p \to q\) |
|---|---|---|
| \(T\) | \(F\) | \(F\) |
| \(T\) | \(T\) | \(T\) |
| \(F\) | \(F\) | \(T\) |
| \(F\) | \(T\) | \(T\) |
It is important to notice that, if the first proposition is false, the conditional statement is true by default. A conditional statement is defined as being true unless a true hypothesis leads to a false conclusion.
Example \(\PageIndex{7}\):
Consider the statement "If a closed figure has four sides, then it is a square." This is a false statement - why?
We can prove it using a counter-example: we draw a four-sided figure that is not a square. So there!
Example \(\PageIndex{8}\):
Consider the statement "If \(2 = 3\), then \(5 = 2\)"
Since \(2 \ne 3\), it does not matter if \(5 = 2\) is true or not, the conditional statement as a whole is true.
The converse of a conditional statement
Let P be a statement if p then q. Then the converse of P is if q then p.
Example \(\PageIndex{9}\):
Consider the statement Q, "If a closed figure has four sides, then it is a square."
Then the converse of Q is "If it is a square then it is a closed figure with four sides".
The contrapositive of a Conditional Statement
Let P be a statement if p then q. Then the contrapositive of P is if \(\neg q\) then \(\neg p.\)
Example \(\PageIndex{10}\):
Consider the statement Q, "If a closed figure has four sides, then it is a square."
Then the converse of Q is "If it is not a square then it is not a closed figure with four sides".
Bi-Conditional Statements
Bi-conditional statements are conditional statements which depend on both component propositions. They read "p if and only if q" and are denoted \(p \leftrightarrow q\) or "p iff q", which is logically equivalent to \((p \to q) \wedge (q \to p)\). These compound statements are true if both component propositions are true or both are false:
| \(p\) | \(q\) | \(p \leftrightarrow q\) |
|---|---|---|
| \(T\) | \(T\) | \(T\) |
| \(T\) | \(F\) | \(F\) |
| \(F\) | \(T\) | \(F\) |
| \(F\) | \(F\) | \(T\) |
Example \(\PageIndex{11}\):
Consider the statement: "Two lines are perpendicular if and only if they intersect to form a right angle."
The component propositions are:
- \(p\): Two lines are perpendicular
- \(q\): [The lines] intersect to form a right angle
Logically, we can see that if two lines are perpendicular, then they must intersect to form a right angle. Also, we can see that if two lines form a right angle, then they are perpendicular.
If two lines are not perpendicular, then they cannot form a right angle. Conversely, if two lines do not form a right angle, they cannot be perpendicular. This is why, if both propositions in a biconditional statement are false, the statement itself is true!
Logically Equivalent Statements
Once we know the basic statement types and their truth tables, we can derive the truth tables of more elaborate compound statements. Below is the truth table for the proposition, not p or (p and q). First, we calculate the truth values for not p, then p and q and finally, we use these two columns of truth values to figure out the truth values for not p or (p and q).
| \(p\) | \(q\) | \(\neg p\) | \(p \wedge q\) | \(\neg p \vee (p \wedge q)\) |
|---|---|---|---|---|
| \(T\) | \(T\) | \(F\) | \(T\) | \(T\) |
| \(T\) | \(F\) | \(F\) | \(F\) | \(F\) |
| \(F\) | \(T\) | \(T\) | \(F\) | \(T\) |
| \(F\) | \(F\) | \(T\) | \(F\) | \(T\) |
So the proposition "not p or (p and q)" is only false if p is true and q is false. Does this seem familiar?
"If p then q" is only false if p is true and q is false as well.
| \(p\) | \(q\) | \(p \to q\) |
|---|---|---|
| \(T\) | \(T\) | \(T\) |
| \(T\) | \(F\) | \(F\) |
| \(F\) | \(T\) | \(T\) |
| \(F\) | \(F\) | \(T\) |
This has some significance in logic because if two propositions have the same truth table they are in a logical sense equal to each other – and we say that they are logically equivalent. So: \(\neg p \vee (p \wedge q) \equiv p \to q\), or "Not p or (p and q) is equivalent to if p then q."
Example \(\PageIndex{12}\):
Prove or disprove: for any mathematical statements \(p,q\) and \(r,\, p\to(q \vee r)\) is logically equivalent to \(\neg r \to ( p \to q).\)
| \(p\) | \(q\) | \(r\) | \(q \vee r\) | \(p \to (q \vee r)\) | \(\neg r\) | \(p \to q\) | \(\neg r \to (p \to q)\) |
|---|---|---|---|---|---|---|---|
| T | T | T | T | T | F | T | T |
| T | T | F | T | T | T | T | T |
| T | F | T | T | T | F | F | T |
| T | F | F | F | F | T | F | F |
| F | T | T | T | T | F | T | T |
| F | T | F | T | T | T | T | T |
| F | F | T | T | T | F | T | T |
| F | F | F | F | T | T | T | T |
Hence, \(p\to(q \vee r)\) is logically equivalent to \(\neg r \to ( p \to q).\)
Tautologies and Contradictions
There are two cases in which compound statements can be made that result in either always true or always false. These are called tautologies and contradictions, respectively. Let's consider a tautology first, and then a contradiction:
Example \(\PageIndex{13}\):
Consider the statement "\((2 = 3) \vee (2 \ne 3)\)":
There are two component propositions:
- \(p\): \(2 = 3\)
- \(\neg p\): \(2 \ne 3\)
Clearly, this statement is a tautology.
Let's make a truth table for general case \(p \vee (\neg p)\):
| \(p\) | \(\neg p\) | \(p \vee (\neg p)\) |
|---|---|---|
| \(T\) | \(F\) | \(T\) |
| \(F\) | \(T\) | \(T\) |
As you can see, no matter what we do, this statement is always true. It is a tautology. Careful! This is not to say that this statement makes logical sense in English, but rather that, using logical mathematics, this statement is always true.
Example \(\PageIndex{14}\):
Consider the statement "2 is even \(\wedge\) 2 is odd"
There are two component propositions:
- \(p\): 2 is even
- \(\neg p\): 2 is odd
Clearly, this statement is a contradiction.
Let's make a truth table for general case \(p \wedge (\neg p)\):
| \(p\) | \(\neg p\) | \(p \wedge (\neg p)\) |
|---|---|---|
| \(T\) | \(F\) | \(F\) |
| \(F\) | \(T\) | \(F\) |
As you can see again, no matter what we do, this statement will always be false. It is a contradiction. These make more sense in English: 2 cannot be both even and odd, after all! Still, what matters is what we decide using logical mathematics.
Summary:
| Operation | Notation | Summary of truth values |
| Negation | \(\neg p\) | The opposite truth value of p |
| Conjunction | \(p \wedge q\) | True only when both p and q are true |
| Disjunction | \(p \vee q\) | False only when both p and q are false |
| Conditional | \(p \to q\) | False only when p is true and q is false |
| Biconditional | \(p\leftrightarrow q\) | True only when both p and q are true or both are false |
Notations & Definitions:
- Negation: \(\neg\) or "not"
- Conjunction: \(\wedge\) or "and"
- Disjunction: \(\vee\) or "or"
- Conditional: \(\to\) or "implies" or "if/then"
- Bi-Conditional: \(\leftrightarrow\) or "if and only if" or "iff"
- Counter-example: An example that disproves a mathematical proposition or statement.
- Logically Equivalent: \(\equiv\) Two propositions that have the same truth table result.
- Tautology: A statement that is always true, and a truth table yields only true results.
- Contradiction: A statement which is always false, and a truth table yields only false results.
