The fundamental building block of mathematics that we will be exploring in this course is logical statements/propositions. This section explores what they are and introduces operations that we do with them.
SubsectionThe Basics
Definition1.1.1.Logical Propositions.
A logical proposition or logical statement is a sentence which is either true or false, but not both.
This is not a statement. Although it is my opinion that chocolate cupcakes are the best, it is not something that is true or false -- it depends.
This is a mathematical statement. “One minus three is four.” is a false statement.
This is a statement. It’s false, since Topeka is the capitol.
This is a question; it’s not a statement.
This isn’t a statement either. The mathematical operation “Add one to two” does not have a truth value, it’s just an instruction.
The last example raises an important distinction: not everything that looks like math is a logical statement. A question you might ask yourself is “what is the result?” If I wrote “1 + 2”, the result is a number. You’d say it’s 3. If I wrote “1 - 3 = 4”, you’d say, “No, that’s false!” The result is a truth value.
Definition1.1.3.Logical Negation.
Let \(p\) be a logical proposition. The negation of \(p\text{,}\) denoted by \(\neg p\) has the opposite truth value of \(p\text{.}\)
We can negate a statement like “1- 3 = 4”. It’s negation is “\(1-3 \ne 4\)”. We can’t negate something that isn’t a statement -- Asking the opposite of “1+3” is meaningless.
Example1.1.4.
What are the logical negations of each of the following?
Let \(p\) and \(q\) be propositions. The conjunction of \(p\) and \(q\text{,}\) denoted \(p \wedge q\text{,}\) is the proposition “\(p\) and \(q\)”.
The disjunction of \(p\) and \(q\text{,}\) denoted \(p \vee q\text{,}\) is the proposition “\(p\) or \(q\) (or both)”.
The logical disjunction is an “inclusive or”. On the other hand, we define the “exclusive or” of \(p\) and \(q\) to be the proposition “\(p\) or \(q\) but not both”. We won’t be using it in Discrete 1, so we won’t give it a special symbol.
Definition1.1.6.Conditional Statements.
Let \(p\) and \(q\) be propositions. The conditional statement is the compound proposition “if \(p\) then \(q\)”. The conditional is denoted by \(p \to q\text{.}\)
We call \(p\) the hypothesis or antecedent or premise, and \(q\) is the conclusion or consequence.
Example1.1.7.
Write the following as a simple English expression, letting \(p\) be the statement “it rains” and \(q\) be the statement “I complain about the weather”.
\(\displaystyle p\to q\)
\(\displaystyle p \vee q\)
\(\displaystyle q \to p\)
\(\displaystyle \neg q \to \neg p \)
What is the logical negation of \(p \to q\) in simple English?
Let \(p\) and \(q\) be propositions. The biconditional of \(p\) and \(q\text{,}\) is the statement “\(p\) if and only if \(q\)”, denoted \(p \leftrightarrow q\text{.}\)
Other ways to phrase an “if and only if” statement:
\(p\) iff \(q\text{.}\)
\(p\) is necessary and sufficient for \(q\text{.}\)
If \(p\) then \(q\) and conversely.
Just as with arithmetic operations (\(+, -, \times, \div\)) on numbers, we need to define an order of operations so that compound propositions can be understood without grouping symbols. Though for clarity, we will generally write grouping symbols.
Operator
Precedence
\(\neg\)
highest
\(\wedge, \vee \)
next, from left to right
\(\to, \leftrightarrow \)
lowest, left to right
For example:
\begin{align*}
\amp\neg p \vee q \wedge r \to p \wedge q\\
\amp\equiv \left(\left(\left(\neg p\right)\vee q\right) \wedge r\right) \to \left(p \wedge q \right)
\end{align*}
SubsectionTruth Tables for Logical Connectives
Truth tables allow us to uniquely determine the truth value of a compound proposition, based on the truth values of the simple statements from which it is made. Below are the truth tables for conjunction \(\wedge\text{,}\) disjunction \(\lor\text{,}\) conditional \(\to\text{,}\) biconditional \(\leftrightarrow\text{,}\) exclusive or \(\oplus\text{,}\) and negation \(\neg\text{.}\)
\(p\)
\(q\)
\(p\wedge q\)
T
T
T
T
F
F
F
T
F
F
F
F
\(p\)
\(q\)
\(p\vee q\)
T
T
T
T
F
T
F
T
T
F
F
F
\(p\)
\(q\)
\(p\to q\)
T
T
T
T
F
F
F
T
T
F
F
T
\(p\)
\(q\)
\(p\leftrightarrow q\)
T
T
T
T
F
F
F
T
F
F
F
T
\(p\)
\(\neg p\)
T
F
F
T
Example1.1.11.
Construct a truth table for each of the following statements:
The objects that are logical propositions in mathematics are bool Boolean datatypes in computer science. For example, the clause 5 <= 3 will evaluate to False. This corresponds to the proposition \(p:=\)“5 \(\le\) 3”\(\equiv F\text{.}\)
In C-like syntax:
Logical and, \(p \land q\text{,}\) is in code p && q
Logical or, \(p \lor q\text{,}\) is in code p || q
Logical negation, \(\neg p\text{,}\) is the code !p
The conditional is an if...then statement
So a block of code such as:
if (collision == 1 && object==sword && !blocking){
// hit by a sword, take damage
health--;
}
corresponds to a logical statement of the form \((p \land q \land \neg r) \to s\text{.}\) Note that health--; isn’t a statement. It’s an operation to decrement the health; it isn’t true or false.
ExercisesExercises
1.
Construct a truth table for the compound statement \(((p \to q) \land \neg p) \to \neg q\)
Make a truth table for the statement \(\neg p \wedge (q \to p)\text{.}\) What can you conclude about \(p\) and \(q\) if you know the statement is true?
Converse: “If I bring an umbrella then it rains today.”. Inverse: “If it doesn’t rain today then I won’t bring an umbrella.” Contrapositive: “If I won’t bring an umbrella, then it isn’t raining today”.
The conditional “Whenever I drive my car, I do not use my phone” is “If I drive my car, then I don’t use my phone.” Now find the other statements.
The conditional “When I stay up too late, it’s necessary that I sleep until noon” is “If I stay up too late, then it’s necessary that I sleep until noon.” Now find the other statements.
7.
A classic example is that we’re on the island of knights and knaves. Knights always tell the truth. Knaves always lie.
What happens if A is a knight and is telling the truth? What happens if A is lying? Which scenarios are impossible? What must the answer be?
9.
This is a favorite of my daughter. You encounter a guard standing at a fork in the road. It is not known whether the guard is a knight or a knave, that is, that they will (always) tell the truth or (always) lie. One of the paths leads to great treasure, the other leads to a violent and scary death. You are allowed to ask one and only one question to the guard.
What can you ask the guard in order to ensure you go on the path towards the treasure?