3.1: Statements, Connectives, and Quantifiers
- Page ID
- 52960
\( \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}}} \)
A statement in logic is a declarative sentence that is either true or false. We represent statements by lowercase letters such as p, q, or r.
Examples of statements:
- Guillermo has the flu.
- Either George Washington or Abraham Lincoln was the first president of the United States
- If Paul eats pizza, then Paul will drink soda.
Examples of Non-statements:
- Go clean your room. (This is not declaring a truth or false)
- Why are you here? (This is a question)
- This sentence is false. (This is a paradox. It cannot be either true or false. If we assume that this sentence is true, then we must conclude that it is false. If we assume that it is false, then we must conclude that it is true.)
It is possible to form new statements from existing statements by connecting the statements with words such as “and” and “or” or by negating the statement.
A connective on a statement is a word or combination of words that combines one or more statements to make a new mathematical statement.
A compound statement is a statement that contains one or more connectives. Because these connectives are used so frequently in logic, we give them names and use special symbols to represent them.
A negation expresses the word "not" and uses the symbol \(\sim\): not \(p\) is notated \(\sim p\)
A conjunction expresses the word "and" between two statements and uses the symbol \(\wedge\): \( p\) and \(q\) is notated \(p \wedge q\)
A disjunction expresses the word "or" between two statements and uses the symbol \(\vee\): \(p\) or \(q\) is notated \(p \vee q\)
A conditional statement is of the form "If ... then ..." and uses the symbol \(\rightarrow\): If \(p\), then \(q\) is notated \(p \rightarrow q\)
A biconditional statement expresses "if and only if" between two statements and uses the symbol \(\leftrightarrow\): \(p\) if and only if \(q\) is notated \(p \leftrightarrow q\)
You can remember the first two symbols by relating them to the shapes for the union and intersection. \(A \wedge B\) would be the elements that exist in both sets, in \(A \cap B\). Likewise, \(A \vee B\) would be the elements that exist in either set, in \(A \cup B\). When we are working with sets, we use the rounded version of the symbols; when we are working with statements, we use the pointy version.
Translate each statement into symbolic notation. Let \(P\) represent "I like Pepsi" and let \(C\) represent "I like Coke."
- I like Pepsi or I like Coke.
- I like Pepsi and I like Coke.
- I do not like Pepsi.
- It is not the case that I like Pepsi or Coke.
- I like Pepsi and I do not like Coke.
Solution
- \(P \vee C\)
- \(P \wedge C\)
- \(\sim P\)
- \(\sim(P \vee C)\)
- \(P \wedge \sim C\)
As you can see, we can use parentheses to organize more complicated statements.
Translate “We have carrots or we will not make soup” into symbols. Let \(C\) represent “we have carrots” and let \(S\) represent “we will make soup”.
- Answer
-
\(C \vee \sim S\)
A universal quantifier states that an entire set of things share a characteristic. (all, every, or none)
An existential quantifier states that a set contains at least one element. (some, many, or at least one)
Something interesting happens when we negate – or state the opposite of – a quantified statement.
Suppose your friend says “Everybody cheats on their taxes.” What is the minimum amount of evidence you would need to prove your friend wrong?
To show that it is not true that everybody cheats on their taxes, all you need is one person who does not cheat on their taxes. It would be perfectly fine to produce more people who do not cheat, but one counterexample is all you need.
It is important to note that you do not need to show that absolutely nobody cheats on their taxes.
Suppose your friend says “One of these six cartons of milk is leaking.” What is the minimum amount of evidence you would need to prove your friend wrong?
Solution
In this case, you would need to check all six cartons and show that none of them is leaking. You cannot disprove your friend’s statement by checking only one of the cartons.
When we negate a statement with a universal quantifier, we get a statement with an existential quantifier, and vice-versa.
The negation of “all A are B” is “at least one A is not B”.
The negation of “no A are B” is “at least one A is B”.
The negation of “at least one A is B” is “no A are B”.
The negation of “at least one A is not B” is “all A are B”.
“Somebody brought a flashlight.” Write the negation of this statement.
The negation is “Nobody brought a flashlight.”
“There are no prime numbers that are even.” Write the negation of this statement.
The negation is “At least one prime number is even.”
Write the negation of “All Icelandic children learn English in school.”
- Answer
-
At least one Icelandic child did not learn English in school.