3_0_3A_Prelude_to_Symbolic_Logic_and_Proofs
> 来源: LibreTexts
> 原页: https://math.libretexts.org/Bookshelves/Combinatorics_and_Discrete_Mathematics/Discrete_Mathematics_(Levin)/3%3A_Symbolic_Logic_and_Proofs/3.0%3A_Prelude_to_Symbolic_Logic_and_Proofs
Skip to main content
\\ \def\d{\displaystyle}\\
\\ \newcommand{\f}$$1$${\mathfrak \#1}\\
\\ \newcommand{\s}$$1$${\mathscr \#1}\\
\\ \def\N{\mathbb N}\\
\\ \def\B{\mathbf{B}}\\
\\ \def\circleA{(-.5,0) circle (1)}\\
\\ \def\Z{\mathbb Z}\\
\\ \def\circleAlabel{(-1.5,.6) node$$above$${\$A\$}}\\
\\ \def\Q{\mathbb Q}\\
\\ \def\circleB{(.5,0) circle (1)}\\
\\ \def\R{\mathbb R}\\
\\ \def\circleBlabel{(1.5,.6) node$$above$${\$B\$}}\\
\\ \def\C{\mathbb C}\\
\\ \def\circleC{(0,-1) circle (1)}\\
\\ \def\F{\mathbb F}\\
\\ \def\circleClabel{(.5,-2) node$$right$${\$C\$}}\\
\\ \def\A{\mathbb A}\\
\\ \def\twosetbox{(-2,-1.5) rectangle (2,1.5)}\\
\\ \def\X{\mathbb X}\\
\\ \def\threesetbox{(-2,-2.5) rectangle (2,1.5)}\\
\\ \def\E{\mathbb E}\\
\\ \def\O{\mathbb O}\\
\\ \def\U{\mathcal U}\\
\\ \def\pow{\mathcal P}\\
\\ \def\inv{^{-1}}\\
\\ \def\nrml{\triangleleft}\\
\\ \def\st{:}\\
\\ \def\\{\widetilde}\\
\\ \def\rem{\mathcal R}\\
\\ \def\sigalg{\$\sigma\$-algebra }\\
\\ \def\Gal{\mbox{Gal}}\\
\\ \def\iff{\leftrightarrow}\\
\\ \def\Iff{\Leftrightarrow}\\
\\ \def\land{\wedge}\\
\\ \def\And{\bigwedge}\\
\\ \def\entry{\entry}\\
\\ \def\AAnd{\d\bigwedge\mkern-18mu\bigwedge}\\
\\ \def\Vee{\bigvee}\\
\\ \def\VVee{\d\Vee\mkern-18mu\Vee}\\
\\ \def\imp{\rightarrow}\\
\\ \def\Imp{\Rightarrow}\\
\\ \def\Fi{\Leftarrow}\\
\\ \def\var{\mbox{var}}\\
\\ \def\Th{\mbox{Th}}\\
\\ \def\entry{\entry}\\
\\ \def\sat{\mbox{Sat}}\\
\\ \def\con{\mbox{Con}}\\
\\ \def\iffmodels{\bmodels\models}\\
\\ \def\dbland{\bigwedge \\\\\bigwedge}\\
\\ \def\dom{\mbox{dom}}\\
\\ \def\rng{\mbox{range}}\\
\\ \def\isom{\cong}\\
\\\DeclareMathOperator{\wgt}{wgt}\\
\\ \newcommand{\vtx}$$2$${node$$fill,circle,inner sep=0pt, minimum size=4pt,label=#1:#2$${}}\\
\\ \newcommand{\va}$$1$${\vtx{above}{#1}}\\
\\ \newcommand{\vb}$$1$${\vtx{below}{#1}}\\
\\ \newcommand{\vr}$$1$${\vtx{right}{#1}}\\
\\ \newcommand{\vl}$$1$${\vtx{left}{#1}}\\
\\ \renewcommand{\v}{\vtx{above}{}}\\
\\ \def\circleA{(-.5,0) circle (1)}\\
\\ \def\circleAlabel{(-1.5,.6) node$$above$${\$A\$}}\\
\\ \def\circleB{(.5,0) circle (1)}\\
\\ \def\circleBlabel{(1.5,.6) node$$above$${\$B\$}}\\
\\ \def\circleC{(0,-1) circle (1)}\\
\\ \def\circleClabel{(.5,-2) node$$right$${\$C\$}}\\
\\ \def\twosetbox{(-2,-1.4) rectangle (2,1.4)}\\
\\ \def\threesetbox{(-2.5,-2.4) rectangle (2.5,1.4)}\\
\\ \def\ansfilename{practice-answers}\\
\\ \def\shadowprops{ {fill=black!50,shadow xshift=0.5ex,shadow yshift=0.5ex,path fading={circle with fuzzy edge 10 percent}} }\\
\\ \renewcommand{\bar}{\overline}\\
\\ \newcommand{\card}$$1$${\left\| \#1 \right\|}\\
\\ \newcommand{\twoline}$$2$${\begin{pmatrix}#1 \\ \#2 \end{pmatrix}}\\
\\ \newcommand{\lt}{<}\\
\\ \newcommand{\gt}{>}\\
\\ \newcommand{\amp}{&}\\
\\ \newcommand{\hexbox}$$3$${
\def\x{-cos{30}\*\r\*#1+cos{30}\*#2\*\r\*2}
\def\y{-\r\*#1-sin{30}\*\r\*#1}
\draw (\x,\y) +(90:\r) -- +(30:\r) -- +(-30:\r) -- +(-90:\r) -- +(-150:\r) -- +(150:\r) -- cycle;
\draw (\x,\y) node{#3};
}\\
\\\renewcommand{\bar}{\overline}\\
\\\newcommand{\card}$$1$${\left\| \#1 \right\|}\\
\\\newcommand{\twoline}$$2$${\begin{pmatrix}#1 \\ \#2 \end{pmatrix}}\\
\\\newcommand{\lt}{\<}\\
\\\newcommand{\gt}{\>}\\
\\\newcommand{\amp}{&}\\
Logic is the study of consequence. Given a few mathematical statements or facts, we would like to be able to draw some conclusions. For example, if I told you that a particular real-valued function was continuous on the interval \\$$0,1$$\text{,}\\ and \\f(0) = -1\\ and \\f(1) = 5\text{,}\\ can we conclude that there is some point between \\$$0,1$$\\ where the graph of the function crosses the \\x\\-axis? Yes, we can, thanks to the Intermediate Value Theorem from Calculus. Can we conclude that there is exactly one point? No. Whenever we find an “answer” in math, we really have a (perhaps hidden) argument. Mathematics is really about proving general statements (like the Intermediate Value Theorem), and this too is done via an argument, usually called a proof. We start with some given conditions, the *premises* of our argument, and from these we find a consequence of interest, our *conclusion*.
The problem is, as you no doubt know from arguing with friends, not all arguments are *good* arguments. A “bad” argument is one in which the conclusion does not follow from the premises, i.e., the conclusion is not a consequence of the premises. Logic is the study of what makes an argument good or bad. In other words, logic aims to determine in which cases a conclusion is, or is not, a consequence of a set of premises.
By the way, “argument” is actually a technical term in math (and philosophy, another discipline which studies logic):
Definition: Arguments
An argument is a set of statements, one of which is called the conclusion and the rest of which are called premises . An argument is said to be valid if the conclusion must be true whenever the premises are all true. An argument is invalid if it is not valid; it is possible for all the premises to be true and the conclusion to be false.
For example, consider the following two arguments:
| | |
|----------------|-----------------------------------------------------------|
| | If Edith eats her vegetables, then she can have a cookie. |
| | Edith eats her vegetables. |
| \\\therefore\\ | Edith gets a cookie. |
| | |
|----------------|------------------------------------------------------------|
| | Florence must eat her vegetables in order to get a cookie. |
| | Florence eats her vegetables. |
| \\\therefore\\ | Florence gets a cookie. |
(The symbol “\\\therefore\\” means “therefore”)
Are these arguments valid? Hopefully you agree that the first one is but the second one is not. Logic tells us why by analyzing the structure of the statements in the argument. Notice the two arguments above look almost identical. Edith and Florence both eat their vegetables. In both cases there is a connection between the eating of vegetables and cookies. But we claim that it is valid to conclude that Edith gets a cookie, but not that Florence does. The difference must be in the connection between eating vegetables and getting cookies. We need to be skilled at reading and comprehending these sentences. Do the two sentences mean the same thing? Unfortunately, in everyday language we are often sloppy, and you might be tempted to say they are equivalent. But notice that just because Florence *must* eat her vegetables, we have not said that doing so would be *enough* (she might also need to clean her room, for example). In everyday (non-mathematical) practice, you might be tempted to say this “other direction” is implied. In mathematics, we never get that luxury.
Before proceeding, it might be a good idea to quickly review Section 0.2 where we first encountered statements and the various forms they can take. The goal now is to see what mathematical tools we can develop to better analyze these, and then to see how this helps read and write proofs
---
3_1_3A_Propositional_Logic
> 来源: LibreTexts
> 原页: https://math.libretexts.org/Bookshelves/Combinatorics_and_Discrete_Mathematics/Discrete_Mathematics_(Levin)/3%3A_Symbolic_Logic_and_Proofs/3.1%3A_Propositional_Logic
Skip to main content
\\ \def\d{\displaystyle}\\
\\ \newcommand{\f}$$1$${\mathfrak \#1}\\
\\ \newcommand{\s}$$1$${\mathscr \#1}\\
\\ \def\N{\mathbb N}\\
\\ \def\B{\mathbf{B}}\\
\\ \def\circleA{(-.5,0) circle (1)}\\
\\ \def\Z{\mathbb Z}\\
\\ \def\circleAlabel{(-1.5,.6) node$$above$${\$A\$}}\\
\\ \def\Q{\mathbb Q}\\
\\ \def\circleB{(.5,0) circle (1)}\\
\\ \def\R{\mathbb R}\\
\\ \def\circleBlabel{(1.5,.6) node$$above$${\$B\$}}\\
\\ \def\C{\mathbb C}\\
\\ \def\circleC{(0,-1) circle (1)}\\
\\ \def\F{\mathbb F}\\
\\ \def\circleClabel{(.5,-2) node$$right$${\$C\$}}\\
\\ \def\A{\mathbb A}\\
\\ \def\twosetbox{(-2,-1.5) rectangle (2,1.5)}\\
\\ \def\X{\mathbb X}\\
\\ \def\threesetbox{(-2,-2.5) rectangle (2,1.5)}\\
\\ \def\E{\mathbb E}\\
\\ \def\O{\mathbb O}\\
\\ \def\U{\mathcal U}\\
\\ \def\pow{\mathcal P}\\
\\ \def\inv{^{-1}}\\
\\ \def\nrml{\triangleleft}\\
\\ \def\st{:}\\
\\ \def\\{\widetilde}\\
\\ \def\rem{\mathcal R}\\
\\ \def\sigalg{\$\sigma\$-algebra }\\
\\ \def\Gal{\mbox{Gal}}\\
\\ \def\iff{\leftrightarrow}\\
\\ \def\Iff{\Leftrightarrow}\\
\\ \def\land{\wedge}\\
\\ \def\And{\bigwedge}\\
\\ \def\entry{\entry}\\
\\ \def\AAnd{\d\bigwedge\mkern-18mu\bigwedge}\\
\\ \def\Vee{\bigvee}\\
\\ \def\VVee{\d\Vee\mkern-18mu\Vee}\\
\\ \def\imp{\rightarrow}\\
\\ \def\Imp{\Rightarrow}\\
\\ \def\Fi{\Leftarrow}\\
\\ \def\var{\mbox{var}}\\
\\ \def\Th{\mbox{Th}}\\
\\ \def\entry{\entry}\\
\\ \def\sat{\mbox{Sat}}\\
\\ \def\con{\mbox{Con}}\\
\\ \def\iffmodels{\bmodels\models}\\
\\ \def\dbland{\bigwedge \\\\\bigwedge}\\
\\ \def\dom{\mbox{dom}}\\
\\ \def\rng{\mbox{range}}\\
\\ \def\isom{\cong}\\
\\\DeclareMathOperator{\wgt}{wgt}\\
\\ \newcommand{\vtx}$$2$${node$$fill,circle,inner sep=0pt, minimum size=4pt,label=#1:#2$${}}\\
\\ \newcommand{\va}$$1$${\vtx{above}{#1}}\\
\\ \newcommand{\vb}$$1$${\vtx{below}{#1}}\\
\\ \newcommand{\vr}$$1$${\vtx{right}{#1}}\\
\\ \newcommand{\vl}$$1$${\vtx{left}{#1}}\\
\\ \renewcommand{\v}{\vtx{above}{}}\\
\\ \def\circleA{(-.5,0) circle (1)}\\
\\ \def\circleAlabel{(-1.5,.6) node$$above$${\$A\$}}\\
\\ \def\circleB{(.5,0) circle (1)}\\
\\ \def\circleBlabel{(1.5,.6) node$$above$${\$B\$}}\\
\\ \def\circleC{(0,-1) circle (1)}\\
\\ \def\circleClabel{(.5,-2) node$$right$${\$C\$}}\\
\\ \def\twosetbox{(-2,-1.4) rectangle (2,1.4)}\\
\\ \def\threesetbox{(-2.5,-2.4) rectangle (2.5,1.4)}\\
\\ \def\ansfilename{practice-answers}\\
\\ \def\shadowprops{ {fill=black!50,shadow xshift=0.5ex,shadow yshift=0.5ex,path fading={circle with fuzzy edge 10 percent}} }\\
\\ \renewcommand{\bar}{\overline}\\
\\ \newcommand{\card}$$1$${\left\| \#1 \right\|}\\
\\ \newcommand{\twoline}$$2$${\begin{pmatrix}#1 \\ \#2 \end{pmatrix}}\\
\\ \newcommand{\lt}{<}\\
\\ \newcommand{\gt}{>}\\
\\ \newcommand{\amp}{&}\\
\\ \newcommand{\hexbox}$$3$${
\def\x{-cos{30}\*\r\*#1+cos{30}\*#2\*\r\*2}
\def\y{-\r\*#1-sin{30}\*\r\*#1}
\draw (\x,\y) +(90:\r) -- +(30:\r) -- +(-30:\r) -- +(-90:\r) -- +(-150:\r) -- +(150:\r) -- cycle;
\draw (\x,\y) node{#3};
}\\
\\\renewcommand{\bar}{\overline}\\
\\\newcommand{\card}$$1$${\left\| \#1 \right\|}\\
\\\newcommand{\twoline}$$2$${\begin{pmatrix}#1 \\ \#2 \end{pmatrix}}\\
\\\newcommand{\lt}{\<}\\
\\\newcommand{\gt}{\>}\\
\\\newcommand{\amp}{&}\\
Investigate!
You stumble upon two trolls playing Stratego®. They tell you:
Troll 1: If we are cousins, then we are both knaves.
Troll 2: We are cousins or we are both knaves.
Could both trolls be knights? Recall that all trolls are either always-truth-telling knights or always-lying knaves.
A proposition is simply a statement. Propositional logic studies the ways statements can interact with each other. It is important to remember that propositional logic does not really care about the content of the statements. For example, in terms of propositional logic, the claims, “if the moon is made of cheese then basketballs are round,” and “if spiders have eight legs then Sam walks with a limp” are exactly the same. They are both implications: statements of the form, \\P \imp Q\text{.}\\
Truth Tables
Here's a question about playing Monopoly:
If you get more doubles than any other player then you will lose, or if you lose then you must have bought the most properties.
True or false? We will answer this question, and won't need to know anything about Monopoly. Instead we will look at the logical *form* of the statement.
We need to decide when the statement \$P \imp Q) \vee (Q \imp R)\\ is true. Using the definitions of the connectives in Section 0.2, we see that for this to be true, either \\P \imp Q\\ must be true or \\Q \imp R\\ must be true (or both). Those are true if either \\P\\ is false or \\Q\\ is true (in the first case) and \\Q\\ is false or \\R\\ is true (in the second case). So—yeah, it gets kind of messy. Luckily, we can make a chart to keep track of all the possibilities. Enter truth tables . The idea is this: on each row, we list a possible combination of T's and F's (for true and false) for each of the sentential variables, and then mark down whether the statement in question is true or false in that case. We do this for every possible combination of T's and F's. Then we can clearly see in which cases the statement is true or false. For complicated statements, we will first fill in values for each part of the statement, as a way of breaking up our task into smaller, more manageable pieces.
Since the truth value of a statement is completely determined by the truth values of its parts and how they are connected, all you really need to know is the truth tables for each of the logical connectives. Here they are:
| \\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\imp Q\\ |
|-------|-------|-------------|
| T | T | T |
| T | F | F |
| F | T | T |
| F | F | T |
| \\P\\ | \\Q\\ | \\P\iff Q\\ |
|-------|-------|-------------|
| T | T | T |
| T | F | F |
| F | T | F |
| F | F | T |
The truth table for negation looks like this:
| \\P\\ | \\\neg P\\ |
|-------|------------|
| T | F |
| F | T |
None of these truth tables should come as a surprise; they are all just restating the definitions of the connectives. Let's try another one.
Example \\\PageIndex{1}\\
Make a truth table for the statement \\\neg P \vee Q\text{.}\\
Solution
Note that this statement is not \\\neg(P \vee Q)\text{,}\\ the negation belongs to \\P\\ alone. Here is the truth table:
| \\P\\ | \\Q\\ | \\\neg P\\ | \\\neg P \vee Q\\ |
|-------|-------|------------|-------------------|
| T | T | F | T |
| T | F | F | F |
| F | T | T | T |
| F | F | T | T |
We added a column for \\\neg P\\ to make filling out the last column easier. The entries in the \\\neg P\\ column were determined by the entries in the \\P\\ column. Then to fill in the final column, look only at the column for \\Q\\ and the column for \\\neg P\\ and use the rule for \\\vee\text{.}\\
Now let's answer our question about monopoly:
Example \\\PageIndex{2}\\
Analyze the statement, “if you get more doubles than any other player you will lose, or that if you lose you must have bought the most properties,” using truth tables.
Solution
Represent the statement in symbols as \$P \imp Q) \vee (Q \imp R)\text{,}\\ where \\P\\ is the statement “you get more doubles than any other player,” \\Q\\ is the statement “you will lose,” and \\R\\ is the statement “you must have bought the most properties.” Now make a truth table.
The truth table needs to contain 8 rows in order to account for every possible combination of truth and falsity among the three statements. Here is the full truth table:
| \\P\\ | \\Q\\ | \\R\\ | \\P \imp Q\\ | \\Q \imp R\\ | \$P \imp Q) \vee (Q \imp R)\\ |
|-------|-------|-------|--------------|--------------|--------------------------------|
| T | T | T | T | T | T |
| T | T | F | T | F | T |
| T | F | T | F | T | T |
| T | F | F | F | T | T |
| F | T | T | T | T | T |
| F | T | F | T | F | T |
| F | F | T | T | T | T |
| F | F | F | T | T | T |
The first three columns are simply a systematic listing of all possible combinations of T and F for the three statements (do you see how you would list the 16 possible combinations for four statements?). The next two columns are determined by the values of \\P\text{,}\\ \\Q\text{,}\\ and \\R\\ and the definition of implication. Then, the last column is determined by the values in the previous two columns and the definition of \\\vee\text{.}\\ It is this final column we care about.
Notice that in each of the eight possible cases, the statement in question is true. So our statement about monopoly is true (regardless of how many properties you own, how many doubles you roll, or whether you win or lose).
The statement about monopoly is an example of a tautology , a statement which is true on the basis of its logical form alone. Tautologies are always true but they don't tell us much about the world. No knowledge about monopoly was required to determine that the statement was true. In fact, it is equally true that “If the moon is made of cheese, then Elvis is still alive, or if Elvis is still alive, then unicorns have 5 legs.”
Logical Equivalence
You might have noticed that the final column in the truth table from \\\neg P \vee Q\\ is identical to the final column in the truth table for \\P \imp Q\text{:}\\
| \\P\\ | \\Q\\ | \\P \imp Q\\ | \\\neg P \vee Q\\ |
|-------|-------|--------------|-------------------|
| T | T | T | T |
| T | F | F | F |
| F | T | T | T |
| F | F | T | T |
This says that no matter what \\P\\ and \\Q\\ are, the statements \\\neg P \vee Q\\ and \\P \imp Q\\ either both true or both false. We therefore say these statements are logically equivalent .
Logical Equivalence
Two (molecular) statements \\P\\ and \\Q\\ are logically equivalent provided \\P\\ is true precisely when \\Q\\ is true. That is, \\P\\ and \\Q\\ have the same truth value under any assignment of truth values to their atomic parts.
To verify that two statements are logically equivalent, you can make a truth table for each and check whether the columns for the two statements are identical.
Recognizing two statements as logically equivalent can be very helpful. Rephrasing a mathematical statement can often lends insight into what it is saying, or how to prove or refute it. Using truth tables we can systematically verify that two statements are indeed logically equivalent.
Example \\\PageIndex{3}\\
Are the statements, “it will not rain or snow” and “it will not rain and it will not snow” logically equivalent?
Solution
We want to know whether \\\neg(P \vee Q)\\ is logically equivalent to \\\neg P \wedge \neg Q\text{.}\\ Make a truth table which includes both statements:
| \\P\\ | \\Q\\ | \\\neg(P \vee Q)\\ | \\\neg P \wedge \neg Q\\ |
|-------|-------|--------------------|--------------------------|
| T | T | F | F |
| T | F | F | F |
| F | T | F | F |
| F | F | T | T |
Since in every row the truth values for the two statements are equal, the two statements are logically equivalent.
Notice that this example gives us a way to “distribute” a negation over a disjunction (an “or”). We have a similar rule for distributing over conjunctions (“and”s):
De Morgan's Laws
\begin{equation\*} \neg(P \wedge Q) \text{ is logically equivalent to } \neg P \vee \neg Q. \end{equation\*} \begin{equation\*} \neg(P \vee Q) \text{ is logically equivalent to } \neg P \wedge \neg Q. \end{equation\*}
This suggests there might be a sort of “algebra” you could apply to statements (okay, there is: it is called *Boolean algebra*) to transform one statement into another. We can start collecting useful examples of logical equivalence, and apply them in succession to a statement, instead of writing out a complicated truth table. We will probably also want a way to deal with double negation:
Double Negation
\begin{equation\*} \neg \neg P \mbox{ is logically equivalent to } P. \end{equation\*}
Example: “It is not the case that \\c\\ is not odd” means “\\c\\ is odd.”
Let's see how we can apply the equivalences we have encountered so far.
Example \\\PageIndex{4}\\
Prove that the statements \\\neg(P \imp Q)\\ and \\P\wedge \neg Q\\ are logically equivalent without using truth tables.
Solution
We want to start with one of the statements, and transform it into the other through a sequence of logically equivalent statements. Start with \\\neg(P \imp Q)\text{.}\\ We can rewrite the implication as a disjunction this is logically equivalent to
\begin{equation\*} \neg(\neg P \vee Q). \end{equation\*}
Now apply DeMorgan's law to get
\begin{equation\*} \neg\neg P \wedge \neg Q. \end{equation\*}
Finally, use double negation to arrive at \\P \wedge \neg Q\\
Notice that the above example illustrates that the negation of an implication is NOT an implication: it is a conjunction!
To verify that two statements are logically equivalent, you can use truth tables or a sequence of logically equivalent replacements. The truth table method, although cumbersome, has the advantage that it can verify that two statements are NOT logically equivalent.
Example \\\PageIndex{5}\\
Are the statements \$P \vee Q) \imp R\\ and \$P \imp R) \vee (Q \imp R)\\ logically equivalent?
Solution
Note that while we could start rewriting these statements with logically equivalent replacements in the hopes of transforming one into another, we will never be sure that our failure is due to their lack of logical equivalence rather than our lack of imagination. So instead, let's make a truth table:
| \\P\\ | \\Q\\ | \\R\\ | \$P\vee Q) \imp R\\ | \$P\imp R) \vee (Q \imp R)\\ |
|-------|-------|-------|----------------------|-------------------------------|
| T | T | T | T | T |
| T | T | F | F | F |
| T | F | T | T | T |
| T | F | F | F | T |
| F | T | T | T | T |
| F | T | F | F | T |
| F | F | T | T | T |
| F | F | F | T | T |
Look at the fourth (or sixth) row. In this case, \$P \imp R) \vee (Q \imp R)\\ is true, but \$P \vee Q) \imp R\\ is false. Therefore the statements are not logically equivalent.
While we don't have logical equivalence, it is the case that whenever \$P \vee Q) \imp R\\ is true, so is \$P \imp R) \vee (Q \imp R)\text{.}\\ This tells us that we can *deduce* \$P \imp R) \vee (Q \imp R)\\ from \$P \vee Q) \imp R\text{,}\\ just not the reverse direction.
Deductions
Investigate!
Holmes owns two suits: one black and one tweed. He always wears either a tweed suit or sandals. Whenever he wears his tweed suit and a purple shirt, he chooses to not wear a tie. He never wears the tweed suit unless he is also wearing either a purple shirt or sandals. Whenever he wears sandals, he also wears a purple shirt. Yesterday, Holmes wore a bow tie. What else did he wear?
Earlier we claimed that the following was a valid argument:
If Edith eats her vegetables, then she can have a cookie. Edith ate her vegetables. Therefore Edith gets a cookie.
How do we know this is valid? Let's look at the form of the statements. Let \\P\\ denote “Edith eats her vegetables” and \\Q\\ denote “Edith can have a cookie.” The logical form of the argument is then:
| | |
|----------------|--------------|
| | \\P \imp Q\\ |
| | \\P\\ |
| \\\therefore\\ | \\Q\\ |
This is an example of a deduction rule , an argument form which is always valid. This one is a particularly famous rule called *modus ponens*. Are you convinced that it is a valid deduction rule? If not, consider the following truth table:
| \\P\\ | \\Q\\ | \\P\imp Q\\ |
|-------|-------|-------------|
| T | T | T |
| T | F | F |
| F | T | T |
| F | F | T |
This is just the truth table for \\P \imp Q\text{,}\\ but what matters here is that all the lines in the deduction rule have their own column in the truth table. Remember that an argument is valid provided the conclusion must be true given that the premises are true. The premises in this case are \\P \imp Q\\ and \\P\text{.}\\ Which *rows* of the truth table correspond to both of these being true? \\P\\ is true in the first two rows, and of those, only the first row has \\P \imp Q\\ true as well. And lo-and-behold, in this one case, \\Q\\ is also true. So if \\P\imp Q\\ and \\P\\ are both true, we see that \\Q\\ must be true as well.
Here are a few more examples.
Example \\\PageIndex{6}\\
Show that
| | |
|----------------|-------------------|
| | \\P \imp Q\\ |
| | \\\neg P \imp Q\\ |
| \\\therefore\\ | \\Q\\ |
is a valid deduction rule.
Solution
We make a truth table which contains all the lines of the argument form:
| \\P\\ | \\Q\\ | \\P\imp Q\\ | \\\neg P\\ | \\\neg P \imp Q\\ |
|-------|-------|-------------|------------|-------------------|
| T | T | T | F | T |
| T | F | F | F | T |
| F | T | T | T | T |
| F | F | T | T | F |
(we include a column for \\\neg P\\ just as a step to help getting the column for \\\neg P \imp Q\$.
Now look at all the rows for which both \\P \imp Q\\ and \\\neg P \imp Q\\ are true. This happens only in rows 1 and 3. Hey! In those rows \\Q\\ is true as well, so the argument form is valid (it is a valid deduction rule).
Example \\\PageIndex{7}\\
Decide whether
| | |
|----------------|--------------|
| | \\P \imp R\\ |
| | \\Q \imp R\\ |
| | \\R\\ |
| \\\therefore\\ | \\P \vee Q\\ |
is a valid deduction rule.
Solution
Let's make a truth table containing all four statements.
| \\P\\ | \\Q\\ | \\R\\ | \\P \imp R\\ | \\Q \imp R\\ | \\P \vee Q\\ |
|-------|-------|-------|--------------|--------------|--------------|
| T | T | T | T | T | T |
| T | T | F | F | F | T |
| T | F | T | T | T | T |
| T | F | F | F | T | T |
| F | T | T | T | T | T |
| F | T | F | T | F | T |
| F | F | T | T | T | F |
| F | F | F | T | T | F |
Look at the second to last row. Here all three premises of the argument are true, but the conclusion is false. Thus this is not a valid deduction rule.
While we have the truth table in front of us, look at rows 1 and 5. These are the only rows in which all of the statements statements \\P \imp R\text{,}\\ \\Q \imp R\text{,}\\ and \\P\vee Q\\ are true. It also happens that \\R\\ is true in these rows as well. Thus we have discovered a new deduction rule we know *is* valid:
| | |
|----------------|--------------|
| | \\P \imp R\\ |
| | \\Q \imp R\\ |
| | \\P \vee Q\\ |
| \\\therefore\\ | \\R\\ |
Beyond Propositions
As we saw in Section 0.2, not every statement can be analyzed using logical connectives alone. For example, we might want to work with the statement:
All primes greater than 2 are odd.
To write this statement symbolically, we must use quantifiers. We can translate as follows:
\begin{equation\*} \forall x ((P(x) \wedge x \gt 2) \imp O(x)). \end{equation\*}
In this case, we are using \\P(x)\\ to denote “\\x\\ is prime” and \\O(x)\\ to denote “\\x\\ is odd.” These are not propositions, since their truth value depends on the input \\x\text{.}\\ Better to think of \\P\\ and \\O\\ as denoting *properties* of their input. The technical term for these is predicates and when we study them in logic, we need to use predicate logic .
It is important to stress that predicate logic *extends* propositional logic (much in the way quantum mechanics extends classical mechanics). You will notice that our statement above still used the (propositional) logical connectives. Everything that we learned about logical equivalence and deductions still applies. However, predicate logic allows us to analyze statements at a higher resolution, digging down into the individual propositions \\P\text{,}\\ \\Q\text{,}\\ etc.
A full treatment of predicate logic is beyond the scope of this text. One reason is that there is no systematic procedure for deciding whether two statements in predicate logic are logically equivalent (i.e., there is no analogue to truth tables here). Rather, we end with a couple of examples of logical equivalence and deduction, to pique your interest.
Example \\\PageIndex{8}\\
Suppose we claim that there is no smallest number. We can translate this into symbols as
\begin{equation\*} \neg \exists x \forall y (x \le y) \end{equation\*}
(literally, “it is not true that there is a number \\x\\ such that for all numbers \\y\text{,}\\ \\x\\ is less than or equal to \\y\\”).
However, we know how negation interacts with quantifiers: we can pass a negation over a quantifier by switching the quantifier type (between universal and existential). So the statement above should be *logically equivalent* to
\begin{equation\*} \forall x \exists y (y \lt x). \end{equation\*}
Notice that \\y \lt x\\ is the negation of \\x \le y\text{.}\\ This literally says, “for every number \\x\\ there is a number \\y\\ which is smaller than \\x\text{.}\\” We see that this is another way to make our original claim
Example \\\PageIndex{9}\\
Can you switch the order of quantifiers? For example, consider the two statements:
\begin{equation\*} \forall x \exists y P(x,y) \qquad \mathrm{ and } \qquad \exists y \forall x P(x,y). \end{equation\*}
Are these logically equivalent?
Solution
These statements are NOT logically equivalent. To see this, we should provide an interpretation of the predicate \\P(x,y)\\ which makes one of the statements true and the other false.
Let \\P(x,y)\\ be the predicate \\x \lt y\text{.}\\ It is true, in the natural numbers, that for all \\x\\ there is some \\y\\ greater than it (since there are infinitely many numbers). However, there is not a natural number \\y\\ which is greater than every number \\x\text{.}\\ Thus it is possible for \\\forall x \exists y P(x,y)\\ to be true while \\\exists y \forall x P(x,y)\\ is false.
We cannot do the reverse of this though. If there is some \\y\\ for which every \\x\\ satisfies \\P(x,y)\text{,}\\ then certainly for every \\x\\ there is some \\y\\ which satisfies \\P(x,y)\text{.}\\ The first is saying we can find one \\y\\ that works for every \\x\text{.}\\ The second allows different \\y\\'s to work for different \\x\\'s, but there is nothing preventing us from using the same \\y\\ that work for every \\x\text{.}\\ In other words, while we don't have logical equivalence between the two statements, we do have a valid deduction rule:
| | |
|----------------|--------------------------------|
| | \\\exists y \forall x P(x,y)\\ |
| \\\therefore\\ | \\\forall x \exists y P(x,y)\\ |
Put yet another way, this says that the single statement
\begin{equation\*} \exists y \forall x P(x,y) \imp \forall x \exists y P(x,y) \end{equation\*}
is always true. This is sort of like a tautology, although we reserve that term for necessary truths in propositional logic. A statement in predicate logic that is necessarily true gets the more prestigious designation of a law of logic (or sometimes logically valid , but that is less fun).
---
3_2_3A_Proofs
> 来源: LibreTexts
> 原页: https://math.libretexts.org/Bookshelves/Combinatorics_and_Discrete_Mathematics/Discrete_Mathematics_(Levin)/3%3A_Symbolic_Logic_and_Proofs/3.2%3A_Proofs
Skip to main content
\\ \def\d{\displaystyle}\\
\\ \newcommand{\f}$$1$${\mathfrak \#1}\\
\\ \newcommand{\s}$$1$${\mathscr \#1}\\
\\ \def\N{\mathbb N}\\
\\ \def\B{\mathbf{B}}\\
\\ \def\circleA{(-.5,0) circle (1)}\\
\\ \def\Z{\mathbb Z}\\
\\ \def\circleAlabel{(-1.5,.6) node$$above$${\$A\$}}\\
\\ \def\Q{\mathbb Q}\\
\\ \def\circleB{(.5,0) circle (1)}\\
\\ \def\R{\mathbb R}\\
\\ \def\circleBlabel{(1.5,.6) node$$above$${\$B\$}}\\
\\ \def\C{\mathbb C}\\
\\ \def\circleC{(0,-1) circle (1)}\\
\\ \def\F{\mathbb F}\\
\\ \def\circleClabel{(.5,-2) node$$right$${\$C\$}}\\
\\ \def\A{\mathbb A}\\
\\ \def\twosetbox{(-2,-1.5) rectangle (2,1.5)}\\
\\ \def\X{\mathbb X}\\
\\ \def\threesetbox{(-2,-2.5) rectangle (2,1.5)}\\
\\ \def\E{\mathbb E}\\
\\ \def\O{\mathbb O}\\
\\ \def\U{\mathcal U}\\
\\ \def\pow{\mathcal P}\\
\\ \def\inv{^{-1}}\\
\\ \def\nrml{\triangleleft}\\
\\ \def\st{:}\\
\\ \def\\{\widetilde}\\
\\ \def\rem{\mathcal R}\\
\\ \def\sigalg{\$\sigma\$-algebra }\\
\\ \def\Gal{\mbox{Gal}}\\
\\ \def\iff{\leftrightarrow}\\
\\ \def\Iff{\Leftrightarrow}\\
\\ \def\land{\wedge}\\
\\ \def\And{\bigwedge}\\
\\ \def\entry{\entry}\\
\\ \def\AAnd{\d\bigwedge\mkern-18mu\bigwedge}\\
\\ \def\Vee{\bigvee}\\
\\ \def\VVee{\d\Vee\mkern-18mu\Vee}\\
\\ \def\imp{\rightarrow}\\
\\ \def\Imp{\Rightarrow}\\
\\ \def\Fi{\Leftarrow}\\
\\ \def\var{\mbox{var}}\\
\\ \def\Th{\mbox{Th}}\\
\\ \def\entry{\entry}\\
\\ \def\sat{\mbox{Sat}}\\
\\ \def\con{\mbox{Con}}\\
\\ \def\iffmodels{\bmodels\models}\\
\\ \def\dbland{\bigwedge \\\\\bigwedge}\\
\\ \def\dom{\mbox{dom}}\\
\\ \def\rng{\mbox{range}}\\
\\ \def\isom{\cong}\\
\\\DeclareMathOperator{\wgt}{wgt}\\
\\ \newcommand{\vtx}$$2$${node$$fill,circle,inner sep=0pt, minimum size=4pt,label=#1:#2$${}}\\
\\ \newcommand{\va}$$1$${\vtx{above}{#1}}\\
\\ \newcommand{\vb}$$1$${\vtx{below}{#1}}\\
\\ \newcommand{\vr}$$1$${\vtx{right}{#1}}\\
\\ \newcommand{\vl}$$1$${\vtx{left}{#1}}\\
\\ \renewcommand{\v}{\vtx{above}{}}\\
\\ \def\circleA{(-.5,0) circle (1)}\\
\\ \def\circleAlabel{(-1.5,.6) node$$above$${\$A\$}}\\
\\ \def\circleB{(.5,0) circle (1)}\\
\\ \def\circleBlabel{(1.5,.6) node$$above$${\$B\$}}\\
\\ \def\circleC{(0,-1) circle (1)}\\
\\ \def\circleClabel{(.5,-2) node$$right$${\$C\$}}\\
\\ \def\twosetbox{(-2,-1.4) rectangle (2,1.4)}\\
\\ \def\threesetbox{(-2.5,-2.4) rectangle (2.5,1.4)}\\
\\ \def\ansfilename{practice-answers}\\
\\ \def\shadowprops{ {fill=black!50,shadow xshift=0.5ex,shadow yshift=0.5ex,path fading={circle with fuzzy edge 10 percent}} }\\
\\ \renewcommand{\bar}{\overline}\\
\\ \newcommand{\card}$$1$${\left\| \#1 \right\|}\\
\\ \newcommand{\twoline}$$2$${\begin{pmatrix}#1 \\ \#2 \end{pmatrix}}\\
\\ \newcommand{\lt}{<}\\
\\ \newcommand{\gt}{>}\\
\\ \newcommand{\amp}{&}\\
\\ \newcommand{\hexbox}$$3$${
\def\x{-cos{30}\*\r\*#1+cos{30}\*#2\*\r\*2}
\def\y{-\r\*#1-sin{30}\*\r\*#1}
\draw (\x,\y) +(90:\r) -- +(30:\r) -- +(-30:\r) -- +(-90:\r) -- +(-150:\r) -- +(150:\r) -- cycle;
\draw (\x,\y) node{#3};
}\\
\\\renewcommand{\bar}{\overline}\\
\\\newcommand{\card}$$1$${\left\| \#1 \right\|}\\
\\\newcommand{\twoline}$$2$${\begin{pmatrix}#1 \\ \#2 \end{pmatrix}}\\
\\\newcommand{\lt}{\<}\\
\\\newcommand{\gt}{\>}\\
\\\newcommand{\amp}{&}\\
Investigate!
Decide which of the following are valid proofs of the following statement:
If \\a b\\ is an even number, then \\a\\ or \\b\\ is even.
1. Suppose \\a\\ and \\b\\ are odd. That is, \\a=2k+1\\ and \\b=2m+1\\ for some integers \\k\\ and \\m\text{.}\\ Then \begin{align\*} ab & =(2k+1)(2m+1)\\ & =4km+2k+2m+1\\ & =2(2km+k+m)+1. \end{align\*}
Therefore \\ab\\ is odd.
2. Assume that \\a\\ or \\b\\ is even - say it is \\a\\ (the case where \\b\\ is even will be identical). That is, \\a=2k\\ for some integer \\k\text{.}\\ Then \begin{align\*} ab & =(2k)b\\ & =2(kb). \end{align\*}
Thus \\ab\\ is even.
3. Suppose that \\ab\\ is even but \\a\\ and \\b\\ are both odd. Namely, \\ab = 2n\text{,}\\ \\a=2k+1\\ and \\b=2j+1\\ for some integers \\n\text{,}\\ \\k\text{,}\\ and \\j\text{.}\\ Then \begin{align\*} 2n & =(2k+1)(2j+1)\\ 2n & =4kj+2k+2j+1\\ n & = 2kj+k+j+\frac{1}{2}. \end{align\*}
But since \\2kj+k+j\\ is an integer, this says that the integer \\n\\ is equal to a non-integer, which is impossible.
4. Let \\ab\\ be an even number, say \\ab=2n\text{,}\\ and \\a\\ be an odd number, say \\a=2k+1\text{.}\\ \begin{align\*} ab & =(2k+1)b\\ 2n & =2kb+b\\ 2n-2kb& =b\\ 2(n-kb)& =b. \end{align\*}
Therefore \\b\\ must be even.
Anyone who doesn't believe there is creativity in mathematics clearly has not tried to write proofs. Finding a way to convince the world that a particular statement is necessarily true is a mighty undertaking and can often be quite challenging. There is not a guaranteed path to success in the search for proofs. For example, in the summer of 1742, a German mathematician by the name of Christian Goldbach wondered whether every even integer greater than 2 could be written as the sum of two primes. Centuries later, we still don't have a proof of this apparent fact (computers have checked that “Goldbach's Conjecture” holds for all numbers less than \\4\times 10^{18}\text{,}\\ which leaves only infinitely many more numbers to check).
Writing proofs is a bit of an art. Like any art, to be truly great at it, you need some sort of inspiration, as well as some foundational technique. Just as musicians can learn proper fingering, and painters can learn the proper way to hold a brush, we can look at the proper way to construct arguments. A good place to start might be to study a classic.
Theorem \\\PageIndex{1}\\
There are infinitely many primes.
Proof
Suppose this were not the case. That is, suppose there are only finitely many primes. Then there must be a last, largest prime, call it \\p\text{.}\\ Consider the number
\begin{equation\*} N = p! + 1 = (p \cdot (p-1) \cdot \cdots 3\cdot 2 \cdot 1) + 1. \end{equation\*}
Now \\N\\ is certainly larger than \\p\text{.}\\ Also, \\N\\ is not divisible by any number less than or equal to \\p\text{,}\\ since every number less than or equal to \\p\\ divides \\p!\text{.}\\ Thus the prime factorization of \\N\\ contains prime numbers (possibly just \\N\\ itself) all greater than \\p\text{.}\\ So \\p\\ is not the largest prime, a contradiction. Therefore there are infinitely many primes.
\\\square\\
This proof is an example of a *proof by contradiction*, one of the standard styles of mathematical proof. First and foremost, the proof is an argument. It contains sequence of statements, the last being the *conclusion* which follows from the previous statements. The argument is valid so the conclusion must be true if the premises are true. Let's go through the proof line by line.
1. Suppose there are only finitely many primes. *$$this is a premise. Note the use of “suppose.”$$*
2. There must be a largest prime, call it \\p\text{.}\\ *$$follows from line 1, by the definition of “finitely many.”$$*
3. Let \\N = p! + 1\text{.}\\ *$$basically just notation, although this is the inspired part of the proof; looking at \\p! + 1\\ is the key insight.$$*
4. \\N\\ is larger than \\p\text{.}\\ *$$by the definition of \\p!\\$$*
5. \\N\\ is not divisible by any number less than or equal to \\p\text{.}\\ *$$by definition, \\p!\\ is divisible by each number less than or equal to \\p\text{,}\\ so \\p! + 1\\ is not.$$*
6. The prime factorization of \\N\\ contains prime numbers greater than \\p\text{.}\\ *$$since \\N\\ is divisible by each prime number in the prime factorization of \\N\text{,}\\ and by line 5.$$*
7. Therefore \\p\\ is not the largest prime. *$$by line 6, \\N\\ is divisible by a prime larger than \\p\text{.}\\$$*
8. This is a contradiction. *$$from line 2 and line 7: the largest prime is \\p\\ and there is a prime larger than \\p\text{.}\\$$*
9. Therefore there are infinitely many primes. *$$from line 1 and line 8: our only premise lead to a contradiction, so the premise is false.$$*
We should say a bit more about the last line. Up through line 8, we have a valid argument with the premise “there are only finitely many primes” and the conclusion “there is a prime larger than the largest prime.” This is a valid argument as each line follows from previous lines. So if the premises are true, then the conclusion *must* be true. However, the conclusion is NOT true. The only way out: the premise must be false.
The sort of line-by-line analysis we did above is a great way to really understand what is going on. Whenever you come across a proof in a textbook, you really should make sure you understand what each line is saying and why it is true. Additionally, it is equally important to understand the overall structure of the proof. This is where using tools from logic is helpful. Luckily there are a relatively small number of standard proof styles that keep showing up again and again. Being familiar with these can help understand proof, as well as give ideas of how to write your own.
Direct Proof
The simplest (from a logic perspective) style of proof is a direct proof . Often all that is required to prove something is a systematic explanation of what everything means. Direct proofs are especially useful when proving implications. The general format to prove \\P \imp Q\\ is this:
> Assume \\P\text{.}\\ Explain, explain, …, explain. Therefore \\Q\text{.}\\
Often we want to prove universal statements, perhaps of the form \\\forall x (P(x) \imp Q(x))\text{.}\\ Again, we will want to assume \\P(x)\\ is true and deduce \\Q(x)\text{.}\\ But what about the \\x\text{?}\\ We want this to work for *all* \\x\text{.}\\ We accomplish this by fixing \\x\\ to be an arbitrary element (of the sort we are interested in).
Here are a few examples. First, we will set up the proof structure for a direct proof, then fill in the details.
Example \\\PageIndex{1}\\
Prove: For all integers \\n\text{,}\\ if \\n\\ is even, then \\n^2\\ is even.
Solution
The format of the proof with be this: Let \\n\\ be an arbitrary integer. Assume that \\n\\ is even. Explain explain explain. Therefore \\n^2\\ is even.
To fill in the details, we will basically just explain what it means for \\n\\ to be even, and then see what that means for \\n^2\text{.}\\ Here is a complete proof.
Proof
Let \\n\\ be an arbitrary integer. Suppose \\n\\ is even. Then \\n = 2k\\ for some integer \\k\text{.}\\ Now \\n^2 = (2k)^2 = 4k^2 = 2(2k^2)\text{.}\\ Since \\2k^2\\ is an integer, \\n^2\\ is even.
\\\square\\
Example \\\PageIndex{2}\\
Prove: For all integers \\a\text{,}\\ \\b\text{,}\\ and \\c\text{,}\\ if \\a\|b\\ and \\b\|c\\ then \\a\|c\text{.}\\ Here \\x\|y\text{,}\\ read “\\x\\ divides \\y\\” means that \\y\\ is a multiple of \\x\\ (so \\x\\ will divide into \\y\\ without remainder).
Solution
Even before we know what the divides symbol means, we can set up a direct proof for this statement. It will go something like this: Let \\a\text{,}\\ \\b\text{,}\\ and \\c\\ be arbitrary integers. Assume that \\a\|b\\ and \\b\|c\text{.}\\ Dot dot dot. Therefore \\a\|c\text{.}\\
How do we connect the dots? We say what our hypothesis (\\a\|b\\ and \\b\|c\$ really means and why this gives us what the conclusion (\\a\|c\$ really means. Another way to say that \\a\|b\\ is to say that \\b = ka\\ for some integer \\k\\ (that is, that \\b\\ is a multiple of \\a\$. What are we going for? That \\c = la\text{,}\\ for some integer \\l\\ (because we want \\c\\ to be a multiple of \\a\$. Here is the complete proof.
Proof
Let \\a\text{,}\\ \\b\text{,}\\ and \\c\\ be integers. Assume that \\a\|b\\ and \\b\|c\text{.}\\ In other words, \\b\\ is a multiple of \\a\\ and \\c\\ is a multiple of \\b\text{.}\\ So there are integers \\k\\ and \\j\\ such that \\b = ka\\ and \\c = jb\text{.}\\ Combining these (through substitution) we get that \\c = jka\text{.}\\ But \\jk\\ is an integer, so this says that \\c\\ is a multiple of \\a\text{.}\\ Therefore \\a\|c\text{.}\\
\\\square\\
Proof by Contrapositive
Recall that an implication \\P \imp Q\\ is logically equivalent to its contrapositive \\\neg Q \imp \neg P\text{.}\\ There are plenty of examples of statements which are hard to prove directly, but whose contrapositive can easily be proved directly. This is all that proof by contrapositive does. It gives a direct proof of the contrapositive of the implication. This is enough because the contrapositive is logically equivalent to the original implication.
The skeleton of the proof of \\P \imp Q\\ by contrapositive will always look roughly like this:
Assume \\\neg Q\text{.}\\ Explain, explain, … explain. Therefore \\\neg P\text{.}\\
As before, if there are variables and quantifiers, we set them to be arbitrary elements of our domain. Here are a couple examples:
Example \\\PageIndex{3}\\
Is the statement “for all integers \\n\text{,}\\ if \\n^2\\ is even, then \\n\\ is even” true?
Solution
This is the converse of the statement we proved above using a direct proof. From trying a few examples, this statement definitely appears this is true. So let's prove it.
A direct proof of this statement would require fixing an arbitrary \\n\\ and assuming that \\n^2\\ is even. But it is not at all clear how this would allow us to conclude anything about \\n\text{.}\\ Just because \\n^2 = 2k\\ does not in itself suggest how we could write \\n\\ as a multiple of 2.
Try something else: write the contrapositive of the statement. We get, for all integers \\n\text{,}\\ if \\n\\ is odd then \\n^2\\ is odd. This looks much more promising. Our proof will look something like this:
Let \\n\\ be an arbitrary integer. Suppose that \\n\\ is not even. This means that …. In other words …. But this is the same as saying …. Therefore \\n^2\\ is not even.
Now we fill in the details:
Proof
We will prove the contrapositive. Let \\n\\ be an arbitrary integer. Suppose that \\n\\ is not even, and thus odd. Then \\n= 2k+1\\ for some integer \\k\text{.}\\ Now \\n^2 = (2k+1)^2 = 4k^2 + 4k + 1 = 2(2k^2 + 2k) + 1\text{.}\\ Since \\2k^2 + 2k\\ is an integer, we see that \\n^2\\ is odd and therefore not even.
\\\square\\
Example \\\PageIndex{4}\\
Prove: for all integers \\a\\ and \\b\text{,}\\ if \\a + b\\ is odd, then \\a\\ is odd or \\b\\ is odd.
Solution
The problem with trying a direct proof is that it will be hard to separate \\a\\ and \\b\\ from knowing something about \\a+b\text{.}\\ On the other hand, if we know something about \\a\\ and \\b\\ separately, then combining them might give us information about \\a+b\text{.}\\ The contrapositive of the statement we are trying to prove is: for all integers \\a\\ and \\b\text{,}\\ if \\a\\ and \\b\\ are even, then \\a+b\\ is even. Thus our proof will have the following format:
Let \\a\\ and \\b\\ be integers. Assume that \\a\\ and \\b\\ are both even. la la la. Therefore \\a+b\\ is even.
Here is a complete proof:
Proof
Let \\a\\ and \\b\\ be integers. Assume that \\a\\ and \\b\\ are even. Then \\a = 2k\\ and \\b = 2l\\ for some integers \\k\\ and \\l\text{.}\\ Now \\a + b = 2k + 2l = 2(k+1)\text{.}\\ Since \\k + l\\ is an integer, we see that \\a + b\\ is even, completing the proof.
Note that our assumption that \\a\\ and \\b\\ are even is really the negation of \\a\\ or \\b\\ is odd. We used De Morgan's law here.
We have seen how to prove some statements in the form of implications: either directly or by contrapositive. Some statements are not written as implications to begin with.
\\\square\\
Example \\\PageIndex{5}\\
Consider the statement, for every prime number \\p\text{,}\\ either \\p = 2\\ or \\p\\ is odd. We can rephrase this: for every prime number \\p\text{,}\\ if \\p \ne 2\text{,}\\ then \\p\\ is odd. Now try to prove it.
Solution
Proof
Let \\p\\ be an arbitrary prime number. Assume \\p\\ is not odd. So \\p\\ is divisible by 2. Since \\p\\ is prime, it must have exactly two divisors, and it has 2 as a divisor, so \\p\\ must be divisible by only 1 and 2. Therefore \\p = 2\text{.}\\ This completes the proof (by contrapositive).
\\\square\\
Proof by Contradiction
There might be statements which really cannot be rephrased as implications. For example, “\\\sqrt 2\\ is irrational.” In this case, it is hard to know where to start. What can we assume? Well, say we want to prove the statement \\P\text{.}\\ What if we could prove that \\\neg P \imp Q\\ where \\Q\\ was false? If this implication is true, and \\Q\\ is false, what can we say about \\\neg P\text{?}\\ It must be false as well, which makes \\P\\ true!
This is why proof by contradiction works. If we can prove that \\\neg P\\ leads to a contradiction, then the only conclusion is that \\\neg P\\ is false, so \\P\\ is true. That's what we wanted to prove. In other words, if it is impossible for \\P\\ to be false, \\P\\ must be true.
Here are a couple examples of proofs by contradiction:
Example \\\PageIndex{6}\\
Prove that \\\sqrt{2}\\ is irrational.
Solution
Proof
Suppose not. Then \\\sqrt 2\\ is equal to a fraction \\\frac{a}{b}\text{.}\\ Without loss of generality, assume \\\frac{a}{b}\\ is in lowest terms (otherwise reduce the fraction). So,
\begin{equation\*} 2 = \frac{a^2}{b^2} \end{equation\*} \begin{equation\*} 2b^2 = a^2 \end{equation\*}
Thus \\a^2\\ is even, and as such \\a\\ is even. So \\a = 2k\\ for some integer \\k\text{,}\\ and \\a^2 = 4k^2\text{.}\\ We then have,
\begin{equation\*} 2b^2 = 4k^2 \end{equation\*} \begin{equation\*} b^2 = 2k^2 \end{equation\*}
Thus \\b^2\\ is even, and as such \\b\\ is even. Since \\a\\ is also even, we see that \\\frac{a}{b}\\ is not in lowest terms, a contradiction. Thus \\\sqrt 2\\ is irrational.
\\\square\\
Example \\\PageIndex{7}\\
Prove: There are no integers \\x\\ and \\y\\ such that \\x^2 = 4y + 2\text{.}\\
Solution
Proof
We proceed by contradiction. So suppose there *are* integers \\x\\ and \\y\\ such that \\x^2 = 4y + 2 = 2(2y + 1)\text{.}\\ So \\x^2\\ is even. We have seen that this implies that \\x\\ is even. So \\x = 2k\\ for some integer \\k\text{.}\\ Then \\x^2 = 4k^2\text{.}\\ This in turn gives \\2k^2 = (2y + 1)\text{.}\\ But \\2k^2\\ is even, and \\2y + 1\\ is odd, so these cannot be equal. Thus we have a contradiction, so there must not be any integers \\x\\ and \\y\\ such that \\x^2 = 4y + 2\text{.}\\
\\\square\\
Example \\\PageIndex{8}\\
The Pigeonhole Principle: If more than \\n\\ pigeons fly into \\n\\ pigeon holes, then at least one pigeon hole will contain at least two pigeons. Prove this!
Solution
Proof
Suppose, contrary to stipulation, that each of the pigeon holes contain at most one pigeon. Then at most, there will be \\n\\ pigeons. But we assumed that there are more than \\n\\ pigeons, so this is impossible. Thus there must be a pigeonhole with more than one pigeon.
While we phrased this proof as a proof by contradiction, we could have also used a proof by contrapositive since our contradiction was simply the negation of the hypothesis. Sometimes this will happen, in which case you can use either style of proof. There are examples however where the contradiction occurs “far away” from the original statement.
\\\square\\
Proof by (counter) Example
It is almost NEVER okay to prove a statement with just an example. Certainly none of the statements proved above can be proved through an example. This is because in each of those cases we are trying to prove that something holds of all integers. We claim that \\n^2\\ being even implies that \\n\\ is even, *no matter what integer* \\n\\ we pick. Showing that this works for \\n = 4\\ is not even close to enough.
This cannot be stressed enough. If you are trying to prove a statement of the form \\\forall x P(x)\text{,}\\ you absolutely CANNOT prove this with an example. 1
However, existential statements can be proven this way. If we want to prove that there is an integer \\n\\ such that \\n^2-n+41\\ is not prime, all we need to do is find one. This might seem like a silly thing to want to prove until you try a few values for \\n\text{.}\\
| | | | | | | | |
|------------------|-----|-----|-----|-----|-----|-----|-----|
| \\n\\ | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
| \\n^2 - n + 41\\ | 41 | 43 | 47 | 53 | 61 | 71 | 83 |
So far we have gotten only primes. You might be tempted to conjecture, “For all positive integers \\n\text{,}\\ the number \\n^2 - n + 41\\ is prime.” If you wanted to prove this, you would need to use a direct proof, a proof by contrapositive, or another style of proof, but certainly it is not enough to give even 7 examples. In fact, we can prove this conjecture is *false* by proving its negation: “There is a positive integer \\n\\ such that \\n^2 - n + 41\\ is not prime.” Since this is an existential statement, it suffices to show that there does indeed exist such a number.
In fact, we can quickly see that \\n = 41\\ will give \\41^2\\ which is certainly not prime. You might say that this is a counterexample to the conjecture that \\n^2 - n + 41\\ is always prime. Since so many statements in mathematics are universal, making their negations existential, we can often prove that a statement is false (if it is) by providing a counterexample.
Example \\\PageIndex{9}\\
Above we proved, “for all integers \\a\\ and \\b\text{,}\\ if \\a+b\\ is odd, then \\a\\ is odd or \\b\\ is odd.” Is the converse true?
Solution
The converse is the statement, “for all integers \\a\\ and \\b\text{,}\\ if \\a\\ is odd or \\b\\ is odd, then \\a + b\\ is odd.” This is false! How do we prove it is false? We need to prove the negation of the converse. Let's look at the symbols. The converse is
\begin{equation\*} \forall a \forall b ((O(a) \vee O(b)) \imp O(a+b)). \end{equation\*}
We want to prove the negation:
\begin{equation\*} \neg \forall a \forall b ((O(a) \vee O(b)) \imp O(a+b)). \end{equation\*}
Simplify using the rules from the previous sections:
\begin{equation\*} \exists a \exists b ((O(a) \vee O(b)) \wedge \neg O(a+b)). \end{equation\*}
As the negation passed by the quantifiers, they changed from \\\forall\\ to \\\exists\text{.}\\ We then needed to take the negation of an implication, which is equivalent to asserting the if part and not the then part.
Now we know what to do. To prove that the converse is false we need to find two integers \\a\\ and \\b\\ so that \\a\\ is odd or \\b\\ is odd, but \\a+b\\ is not odd (so even). That's easy: 1 and 3. (remember, “or” means one or the other or both). Both of these are odd, but \\1+3 = 4\\ is not odd.
\\\square\\
Proof by Cases
We could go on and on and on about different proof styles (we haven't even mentioned induction or combinatorial proofs here), but instead we will end with one final useful technique: proof by cases. The idea is to prove that \\P\\ is true by proving that \\Q \imp P\\ and \\\neg Q \imp P\\ for some statement \\Q\text{.}\\ So no matter what, whether or not \\Q\\ is true, we know that \\P\\ is true. In fact, we could generalize this. Suppose we want to prove \\P\text{.}\\ We know that at least one of the statements \\Q_1, Q_2, \ldots, Q_n\\ are true. If we can show that \\Q_1 \imp P\\ and \\Q_2 \imp P\\ and so on all the way to \\Q_n \imp P\text{,}\\ then we can conclude \\P\text{.}\\ The key thing is that we want to be sure that one of our cases (the \\Q_i\\'s) must be true no matter what.
If that last paragraph was confusing, perhaps an example will make things better.
Example \\\PageIndex{10}\\
Prove: For any integer \\n\text{,}\\ the number \$n^3 -n)\\ is even.
Solution
It is hard to know where to start this, because we don't know much of anything about \\n\text{.}\\ We might be able to prove that \\n^3 - n\\ is even if we knew that \\n\\ was even. In fact, we could probably prove that \\n^3-n\\ was even if \\n\\ was odd. But since \\n\\ must either be even or odd, this will be enough. Here's the proof.
Proof
We consider two cases: if \\n\\ is even or if \\n\\ is odd.
Case 1: \\n\\ is even. Then \\n = 2k\\ for some integer \\k\text{.}\\ This gives
\begin{align\*} n^3 - n & = 8k^3 - 2k\\ & = 2(4k^2 - k), \end{align\*}
and since \\4k^2 - k\\ is an integer, this says that \\n^3-n\\ is even.
Case 2: \\n\\ is odd. Then \\n = 2k+1\\ for some integer \\k\text{.}\\ This gives
\begin{align\*} n^3 - n & = (2k+1)^3 - (2k+1)\\ & = 8k^3 + 6k^2 + 6k + 1 - 2k - 1\\ & = 2(4k^3 + 3k^2 + 2k), \end{align\*}
and since \\4k^3 + 3k^2 + 2k\\ is an integer, we see that \\n^3 - n\\ is even again.
Since \\n^3 - n\\ is even in both exhaustive cases, we see that \\n^3 - n\\ is indeed always even.
\![$$(https://math.libretexts.org/images/image-54.svg)
------------------------------------------------------------------------
1This is not to say that looking at examples is a waste of time. Doing so will often give you an idea of how to write a proof. But the examples do not belong in the proof.
---
3_E_3A_Symbolic_Logic_and_Proofs__Exercises_
> 来源: LibreTexts
> 原页: https://math.libretexts.org/Bookshelves/Combinatorics_and_Discrete_Mathematics/Discrete_Mathematics_(Levin)/3%3A_Symbolic_Logic_and_Proofs/3.E%3A_Symbolic_Logic_and_Proofs_(Exercises)
Skip to main content
\\ \def\d{\displaystyle}\\
\\ \newcommand{\f}$$1$${\mathfrak \#1}\\
\\ \newcommand{\s}$$1$${\mathscr \#1}\\
\\ \def\N{\mathbb N}\\
\\ \def\B{\mathbf{B}}\\
\\ \def\circleA{(-.5,0) circle (1)}\\
\\ \def\Z{\mathbb Z}\\
\\ \def\circleAlabel{(-1.5,.6) node$$above$${\$A\$}}\\
\\ \def\Q{\mathbb Q}\\
\\ \def\circleB{(.5,0) circle (1)}\\
\\ \def\R{\mathbb R}\\
\\ \def\circleBlabel{(1.5,.6) node$$above$${\$B\$}}\\
\\ \def\C{\mathbb C}\\
\\ \def\circleC{(0,-1) circle (1)}\\
\\ \def\F{\mathbb F}\\
\\ \def\circleClabel{(.5,-2) node$$right$${\$C\$}}\\
\\ \def\A{\mathbb A}\\
\\ \def\twosetbox{(-2,-1.5) rectangle (2,1.5)}\\
\\ \def\X{\mathbb X}\\
\\ \def\threesetbox{(-2,-2.5) rectangle (2,1.5)}\\
\\ \def\E{\mathbb E}\\
\\ \def\O{\mathbb O}\\
\\ \def\U{\mathcal U}\\
\\ \def\pow{\mathcal P}\\
\\ \def\inv{^{-1}}\\
\\ \def\nrml{\triangleleft}\\
\\ \def\st{:}\\
\\ \def\\{\widetilde}\\
\\ \def\rem{\mathcal R}\\
\\ \def\sigalg{\$\sigma\$-algebra }\\
\\ \def\Gal{\mbox{Gal}}\\
\\ \def\iff{\leftrightarrow}\\
\\ \def\Iff{\Leftrightarrow}\\
\\ \def\land{\wedge}\\
\\ \def\And{\bigwedge}\\
\\ \def\entry{\entry}\\
\\ \def\AAnd{\d\bigwedge\mkern-18mu\bigwedge}\\
\\ \def\Vee{\bigvee}\\
\\ \def\VVee{\d\Vee\mkern-18mu\Vee}\\
\\ \def\imp{\rightarrow}\\
\\ \def\Imp{\Rightarrow}\\
\\ \def\Fi{\Leftarrow}\\
\\ \def\var{\mbox{var}}\\
\\ \def\Th{\mbox{Th}}\\
\\ \def\entry{\entry}\\
\\ \def\sat{\mbox{Sat}}\\
\\ \def\con{\mbox{Con}}\\
\\ \def\iffmodels{\bmodels\models}\\
\\ \def\dbland{\bigwedge \\\\\bigwedge}\\
\\ \def\dom{\mbox{dom}}\\
\\ \def\rng{\mbox{range}}\\
\\ \def\isom{\cong}\\
\\\DeclareMathOperator{\wgt}{wgt}\\
\\ \newcommand{\vtx}$$2$${node$$fill,circle,inner sep=0pt, minimum size=4pt,label=#1:#2$${}}\\
\\ \newcommand{\va}$$1$${\vtx{above}{#1}}\\
\\ \newcommand{\vb}$$1$${\vtx{below}{#1}}\\
\\ \newcommand{\vr}$$1$${\vtx{right}{#1}}\\
\\ \newcommand{\vl}$$1$${\vtx{left}{#1}}\\
\\ \renewcommand{\v}{\vtx{above}{}}\\
\\ \def\circleA{(-.5,0) circle (1)}\\
\\ \def\circleAlabel{(-1.5,.6) node$$above$${\$A\$}}\\
\\ \def\circleB{(.5,0) circle (1)}\\
\\ \def\circleBlabel{(1.5,.6) node$$above$${\$B\$}}\\
\\ \def\circleC{(0,-1) circle (1)}\\
\\ \def\circleClabel{(.5,-2) node$$right$${\$C\$}}\\
\\ \def\twosetbox{(-2,-1.4) rectangle (2,1.4)}\\
\\ \def\threesetbox{(-2.5,-2.4) rectangle (2.5,1.4)}\\
\\ \def\ansfilename{practice-answers}\\
\\ \def\shadowprops{ {fill=black!50,shadow xshift=0.5ex,shadow yshift=0.5ex,path fading={circle with fuzzy edge 10 percent}} }\\
\\ \renewcommand{\bar}{\overline}\\
\\ \newcommand{\card}$$1$${\left\| \#1 \right\|}\\
\\ \newcommand{\twoline}$$2$${\begin{pmatrix}#1 \\ \#2 \end{pmatrix}}\\
\\ \newcommand{\lt}{<}\\
\\ \newcommand{\gt}{>}\\
\\ \newcommand{\amp}{&}\\
\\ \newcommand{\hexbox}$$3$${
\def\x{-cos{30}\*\r\*#1+cos{30}\*#2\*\r\*2}
\def\y{-\r\*#1-sin{30}\*\r\*#1}
\draw (\x,\y) +(90:\r) -- +(30:\r) -- +(-30:\r) -- +(-90:\r) -- +(-150:\r) -- +(150:\r) -- cycle;
\draw (\x,\y) node{#3};
}\\
\\\renewcommand{\bar}{\overline}\\
\\\newcommand{\card}$$1$${\left\| \#1 \right\|}\\
\\\newcommand{\twoline}$$2$${\begin{pmatrix}#1 \\ \#2 \end{pmatrix}}\\
\\\newcommand{\lt}{\<}\\
\\\newcommand{\gt}{\>}\\
\\\newcommand{\amp}{&}\\
3.1: Propositional Logic
1
Consider the statement about a party, “If it's your birthday or there will be cake, then there will be cake.”
1. Translate the above statement into symbols. Clearly state which statement is \\P\\ and which is \\Q\text{.}\\
2. Make a truth table for the statement.
3. Assuming the statement is true, what (if anything) can you conclude if there will be cake?
4. Assuming the statement is true, what (if anything) can you conclude if there will not be cake?
5. Suppose you found out that the statement was a lie. What can you conclude?
Solution
1. \\P\text{:}\\ it's your birthday; \\Q\text{:}\\ there will be cake. \$P \vee Q) \imp Q\\
2. Hint: you should get three T's and one F.
3. Only that there will be cake.
4. It's NOT your birthday!
5. It's your birthday, but the cake is a lie.
2
Make a truth table for the statement \$P \vee Q) \imp (P \wedge Q)\text{.}\\
Solution
| \\P\\ | \\Q\\ | \$P \vee Q) \imp (P \wedge Q)\\ |
|-------|-------|----------------------------------|
| T | T | T |
| T | F | F |
| F | T | F |
| F | F | T |
3
Make a truth table for the statement \\\neg P \wedge (Q \imp P)\text{.}\\ What can you conclude about \\P\\ and \\Q\\ if you know the statement is true?
Solution
| \\P\\ | \\Q\\ | \\\neg P \wedge (Q \imp P)\\ |
|-------|-------|------------------------------|
| T | T | F |
| T | F | F |
| F | T | F |
| F | F | T |
If the statement is true, then both \\P\\ and \\Q\\ are false.
4
Make a truth table for the statement \\\neg P \imp (Q \wedge R)\text{.}\\
Hint
Like above, only now you will need 8 rows instead of just 4.
5
Determine whether the following two statements are logically equivalent: \\\neg(P \imp Q)\\ and \\P \wedge \neg Q\text{.}\\ Explain how you know you are correct.
Solution
Make a truth table for each and compare. The statements are logically equivalent.
6
Are the statements \\P \imp (Q\vee R)\\ and \$P \imp Q) \vee (P \imp R)\\ logically equivalent?
7
Simplify the following statements (so that negation only appears right before variables).
1. \\\neg(P \imp \neg Q)\text{.}\\
2. \$\neg P \vee \neg Q) \imp \neg (\neg Q \wedge R)\text{.}\\
3. \\\neg((P \imp \neg Q) \vee \neg (R \wedge \neg R))\text{.}\\
4. It is false that if Sam is not a man then Chris is a woman, and that Chris is not a woman.
Answer
1. \\P \wedge Q\text{.}\\
2. \$\neg P \vee \neg R) \imp (Q \vee \neg R)\\ or, replacing the implication with a disjunction first: \$P \wedge Q) \vee (Q \vee \neg R)\text{.}\\
3. \$P \wedge Q) \wedge (R \wedge \neg R)\text{.}\\ This is necessarily false, so it is also equivalent to \\P \wedge \neg P\text{.}\\
4. Either Sam is a woman and Chris is a man, or Chris is a woman.
8
Use De Morgan's Laws, and any other logical equivalence facts you know to simplify the following statements. Show all your steps. Your final statements should have negations only appear directly next to the sentence variables or predicates (\\P\text{,}\\ \\Q\text{,}\\ \\E(x)\text{,}\\ etc.), and no double negations. It would be a good idea to use only conjunctions, disjunctions, and negations.
1. \\\neg((\neg P \wedge Q) \vee \neg(R \vee \neg S))\text{.}\\
2. \\\neg((\neg P \imp \neg Q) \wedge (\neg Q \imp R))\\ (careful with the implications).
9
Tommy Flanagan was telling you what he ate yesterday afternoon. He tells you, “I had either popcorn or raisins. Also, if I had cucumber sandwiches, then I had soda. But I didn't drink soda or tea.” Of course you know that Tommy is the world's worst liar, and everything he says is false. What did Tommy eat?
Justify your answer by writing all of Tommy's statements using sentence variables (\\P, Q, R, S, T\$, taking their negations, and using these to deduce what Tommy actually ate.
10
Determine if the following deduction rule is valid:
| | |
|----------------|--------------|
| | \\P \vee Q\\ |
| | \\\neg P\\ |
| \\\therefore\\ | \\Q\\ |
Solution
The deduction rule is valid. To see this, make a truth table which contains \\P \vee Q\\ and \\\neg P\\ (and \\P\\ and \\Q\\ of course). Look at the truth value of \\Q\\ in each of the rows that have \\P \vee Q\\ and \\\neg P\\ true.
11
Determine if the following is a valid deduction rule:
| | |
|----------------|-----------------------|
| | \\P \imp (Q \vee R)\\ |
| | \\\neg(P \imp Q)\\ |
| \\\therefore\\ | \\R\\ |
12
Determine if the following is a valid deduction rule:
| | |
|----------------|-------------------------|
| | \$P \wedge Q) \imp R\\ |
| | \\\neg P \vee \neg Q\\ |
| \\\therefore\\ | \\\neg R\\ |
13
Can you chain implications together? That is, if \\P \imp Q\\ and \\Q \imp R\text{,}\\ does that means the \\P \imp R\text{?}\\ Can you chain more implications together? Let's find out:
1. Prove that the following is a valid deduction rule:
| | |
|----------------|--------------|
| | \\P \imp Q\\ |
| | \\Q \imp R\\ |
| \\\therefore\\ | \\P \imp R\\ |
2. Prove that the following is a valid deduction rule for any \\n \ge 2\text{:}\\
| | |
|----------------|--------------------------|
| | \\P_1 \imp P_2\\ |
| | \\P_2 \imp P_3\\ |
| | \\\vdots\\ |
| | \\P\_{n-1} \imp P_n\\ |
| \\\therefore\\ | \\P_1 \imp P_n\text{.}\\ |
I suggest you don't go through the trouble of writing out a \\2^n\\ row truth table. Instead, you should use part (a) and mathematical induction.
14
We can also simplify statements in predicate logic using our rules for passing negations over quantifiers, and then applying propositional logical equivalence to the “inside” propositional part. Simplify the statements below (so negation appears only directly next to predicates).
1. \\\neg \exists x \forall y (\neg O(x) \vee E(y))\text{.}\\
2. \\\neg \forall x \neg \forall y \neg(x \lt y \wedge \exists z (x \lt z \vee y \lt z))\text{.}\\
3. There is a number \\n\\ for which no other number is either less \\n\\ than or equal to \\n\text{.}\\
4. It is false that for every number \\n\\ there are two other numbers which \\n\\ is between.
Solution
1. \\\forall x \exists y (O(x) \wedge \neg E(y))\text{.}\\
2. \\\exists x \forall y (x \ge y \vee \forall z (x \ge z \wedge y \ge z))\text{.}\\
3. There is a number \\n\\ for which every other number is strictly greater than \\n\text{.}\\
4. There is a number \\n\\ which is not between any other two numbers.
15
Suppose \\P\\ and \\Q\\ are (possibly molecular) propositional statements. Prove that \\P\\ and \\Q\\ are logically equivalent if and only if \\P \iff Q\\ is a tautology.
Hint
What do these concepts mean in terms of truth tables?
16
Suppose \\P_1, P_2, \ldots, P_n\\ and \\Q\\ are (possibly molecular) propositional statements. Suppose further that
| | |
|----------------|------------|
| | \\P_1\\ |
| | \\P_2\\ |
| | \\\vdots\\ |
| | \\P_n\\ |
| \\\therefore\\ | \\Q\\ |
is a valid deduction rule. Prove that the statement
\begin{equation\*} (P_1 \wedge P_2 \wedge \cdots \wedge P_n) \imp Q \end{equation\*}
is a tautology.
3.2: Proofs
1
Consider the statement “for all integers \\a\\ and \\b\text{,}\\ if \\a + b\\ is even, then \\a\\ and \\b\\ are even”
1. Write the contrapositive of the statement.
2. Write the converse of the statement.
3. Write the negation of the statement.
4. Is the original statement true or false? Prove your answer.
5. Is the contrapositive of the original statement true or false? Prove your answer.
6. Is the converse of the original statement true or false? Prove your answer.
7. Is the negation of the original statement true or false? Prove your answer.
Solution
1. For all integers \\a\\ and \\b\text{,}\\ if \\a\\ or \\b\\ is not even, then \\a+b\\ is not even.
2. For all integers \\a\\ and \\b\text{,}\\ if \\a\\ and \\b\\ are even, then \\a+b\\ is even.
3. There are numbers \\a\\ and \\b\\ such that \\a+b\\ is even but \\a\\ and \\b\\ are not both even.
4. False. For example, \\a = 3\\ and \\b = 5\text{.}\\ \\a+b = 8\text{,}\\ but neither \\a\\ nor \\b\\ are even.
5. False, since it is equivalent to the original statement.
6. True. Let \\a\\ and \\b\\ be integers. Assume both are even. Then \\a = 2k\\ and \\b = 2j\\ for some integers \\k\\ and \\j\text{.}\\ But then \\a+b = 2k + 2j = 2(k+j)\\ which is even.
7. True, since the statement is false.
2
Consider the statement: for all integers \\n\text{,}\\ if \\n\\ is even then \\8n\\ is even.
1. Prove the statement. What sort of proof are you using?
2. Is the converse true? Prove or disprove.
Solution
1. Direct proof.
### Proof
Let \\n\\ be an integer. Assume \\n\\ is even. Then \\n = 2k\\ for some integer \\k\text{.}\\ Thus \\8n = 16k = 2(8k)\text{.}\\ Therefore \\8n\\ is even.
2. The converse is false. That is, there is an integer \\n\\ such that \\8n\\ is even but \\n\\ is odd. For example, consider \\n = 3\text{.}\\ Then \\8n = 24\\ which is even but \\n = 3\\ is odd.
3
Your “friend” has shown you a “proof” he wrote to show that \\1 = 3\text{.}\\ Here is the proof:
Proof
I claim that \\1 = 3\text{.}\\ Of course we can do anything to one side of an equation as long as we also do it to the other side. So subtract 2 from both sides. This gives \\-1 = 1\text{.}\\ Now square both sides, to get \\1 = 1\text{.}\\ And we all agree this is true.
What is going on here? Is your friend's argument valid? Is the argument a proof of the claim \\1=3\text{?}\\ Carefully explain using what we know about logic. Hint: What implication follows from the given proof?
4
Suppose you have a collection of 5-cent stamps and 8-cent stamps. We saw earlier that it is possible to make any amount of postage greater than 27 cents using combinations of both these types of stamps. But, let's ask some other questions:
1. What amounts of postage can you make if you only use an even number of both types of stamps? Prove your answer.
2. Suppose you made an even amount of postage. Prove that you used an even number of at least one of the types of stamps.
3. Suppose you made exactly 72 cents of postage. Prove that you used at least 6 of one type of stamp.
5
Suppose that you would like to prove the following implication:
> For all numbers \\n\text{,}\\ if \\n\\ is prime then \\n\\ is solitary.
Write out the beginning and end of the argument if you were to prove the statement,
1. Directly
2. By contrapositive
3. By contradiction
You do not need to provide details for the proofs (since you do not know what solitary means). However, make sure that you provide the first few and last few lines of the proofs so that we can see that logical structure you would follow.
6
Prove that \\\sqrt 3\\ is irrational.
Solution
Proof
Suppose \\\sqrt{3}\\ were rational. Then \\\sqrt{3} = \frac{a}{b}\\ for some integers \\a\\ and \\b \ne 0\text{.}\\ Without loss of generality, assume \\\frac{a}{b}\\ is reduced. Now
\begin{equation\*} 3 = \frac{a^2}{b^2} \end{equation\*} \begin{equation\*} b^2 3 = a^2 \end{equation\*}
So \\a^2\\ is a multiple of 3. This can only happen if \\a\\ is a multiple of 3, so \\a = 3k\\ for some integer \\k\text{.}\\ Then we have
\begin{equation\*} b^2 3 = 9k^2 \end{equation\*} \begin{equation\*} b^2 = 3k^2 \end{equation\*}
So \\b^2\\ is a multiple of 3, making \\b\\ a multiple of 3 as well. But this contradicts our assumption that \\\frac{a}{b}\\ is in lowest terms.
Therefore, \\\sqrt{3}\\ is irrational.
7
Consider the statement: for all integers \\a\\ and \\b\text{,}\\ if \\a\\ is even and \\b\\ is a multiple of 3, then \\ab\\ is a multiple of 6.
1. Prove the statement. What sort of proof are you using?
2. State the converse. Is it true? Prove or disprove.
8
Prove the statement: For all integers \\n\text{,}\\ if \\5n\\ is odd, then \\n\\ is odd. Clearly state the style of proof you are using.
Solution
We will prove the contrapositive: if \\n\\ is even, then \\5n\\ is even.
Proof
Let \\n\\ be an arbitrary integer, and suppose \\n\\ is even. Then \\n = 2k\\ for some integer \\k\text{.}\\ Thus \\5n = 5\cdot 2k = 10k = 2(5k)\text{.}\\ Since \\5k\\ is an integer, we see that \\5n\\ must be even. This completes the proof.
9
Prove the statement: For all integers \\a\text{,}\\ \\b\text{,}\\ and \\c\text{,}\\ if \\a^2 + b^2 = c^2\text{,}\\ then \\a\\ or \\b\\ is even.
10
Prove: \\x=y\\ if and only if \\xy=\dfrac{(x+y)^2}{4}\text{.}\\ Note, you will need to prove two “directions” here: the “if” and the “only if” part.
11
The game TENZI comes with 40 six-sided dice (each numbered 1 to 6). Suppose you roll all 40 dice.
1. Prove that there will be at least seven dice that land on the same number.
2. How many dice would you have to roll before you were guaranteed that some four of them would all match or all be different? Prove your answer.
Solution
1. This is an example of the pigeonhole principle. We can prove it by contrapositive.
### Proof
Suppose that each number only came up 6 or fewer times. So there are at most six 1's, six 2's, and so on. That's a total of 36 dice, so you must not have rolled all 40 dice.
2. We can have 9 dice without any four matching or any four being all different: three 1's, three 2's, three 3's. We will prove that whenever you roll 10 dice, you will always get four matching or all being different.
### Proof
Suppose you roll 10 dice, but that there are NOT four matching rolls. This means at most, there are three of any given value. If we only had three different values, that would be only 9 dice, so there must be 4 different values, giving 4 dice that are all different.
12
Prove that \\\log(7)\\ is irrational.
Solution
We give a proof by contradiction.
Proof
Suppose, contrary to stipulation that \\\log(7)\\ is rational. Then \\\log(7) = \frac{a}{b}\\ with \\a\\ and \\b \ne 0\\ integers. By properties of logarithms, this implies
\begin{equation\*} 7 = 10^{\frac{a}{b}} \end{equation\*}
Equivalently,
\begin{equation\*} 7^b = 10^a \end{equation\*}
But this is impossible as any power of 7 will be odd while any power of 10 will be even. Therefore, \\\log(7)\\ is irrational.
13
Prove that there are no integer solutions to the equation \\x^2 = 4y + 3\text{.}\\
14
Prove that every prime number greater than 3 is either one more or one less than a multiple of 6.
Hint
Prove the contrapositive by cases.
15
For each of the statements below, say what method of proof you should use to prove them. Then say how the proof starts and how it ends. Bonus points for filling in the middle.
1. There are no integers \\x\\ and \\y\\ such that \\x\\ is a prime greater than 5 and \\x = 6y + 3\text{.}\\
2. For all integers \\n\text{,}\\ if \\n\\ is a multiple of 3, then \\n\\ can be written as the sum of consecutive integers.
3. For all integers \\a\\ and \\b\text{,}\\ if \\a^2 + b^2\\ is odd, then \\a\\ or \\b\\ is odd.
Solution
1. Proof by contradiction. Start of proof: Assume, for the sake of contradiction, that there are integers \\x\\ and \\y\\ such that \\x\\ is a prime greater than 5 and \\x = 6y + 3\text{.}\\ End of proof: … this is a contradiction, so there are no such integers.
2. Direct proof. Start of proof: Let \\n\\ be an integer. Assume \\n\\ is a multiple of 3. End of proof: Therefore \\n\\ can be written as the sum of consecutive integers.
3. Proof by contrapositive. Start of proof: Let \\a\\ and \\b\\ be integers. Assume that \\a\\ and \\b\\ are even. End of proof: Therefore \\a^2 + b^2\\ is even.
16
A standard deck of 52 cards consists of 4 suites (hearts, diamonds, spades and clubs) each containing 13 different values (Ace, 2, 3, …, 10, J, Q, K). If you draw some number of cards at random you might or might not have a pair (two cards with the same value) or three cards all of the same suit. However, if you draw enough cards, you will be guaranteed to have these. For each of the following, find the smallest number of cards you would need to draw to be guaranteed having the specified cards. Prove your answers.
1. Three of a kind (for example, three 7's).
2. A flush of five cards (for example, five hearts).
3. Three cards that are either all the same suit or all different suits.
17
Suppose you are at a party with 19 of your closest friends (so including you, there are 20 people there). Explain why there must be least two people at the party who are friends with the same number of people at the party. Assume friendship is always reciprocated.
18
Your friend has given you his list of 115 best Doctor Who episodes (in order of greatness). It turns out that you have seen 60 of them. Prove that there are at least two episodes you have seen that are exactly four episodes apart.
19
Suppose you have an \\n\times n\\ chessboard but your dog has eaten one of the corner squares. Can you still cover the remaining squares with dominoes? What needs to be true about \\n\text{?}\\ Give necessary and sufficient conditions (that is, say exactly which values of \\n\\ work and which do not work). Prove your answers.
\![chessboard1.svg$$(https://math.libretexts.org/@api/deki/files/58989/chessboard1.svg?revision=1&size=bestfit&width=120&height=120)
\![$$(https://math.libretexts.org/images/image-53.svg)
20
What if your \\n\times n\\ chessboard is missing two opposite corners? Prove that no matter what \\n\\ is, you will not be able to cover the remaining squares with dominoes.
\![chessboard2.svg$$(https://math.libretexts.org/@api/deki/files/58991/chessboard2.svg?revision=1&size=bestfit&width=120&height=120)
---
3_S_3A_Symbolic_Logic_and_Proofs__Summary_
> 来源: LibreTexts
> 原页: https://math.libretexts.org/Bookshelves/Combinatorics_and_Discrete_Mathematics/Discrete_Mathematics_(Levin)/3%3A_Symbolic_Logic_and_Proofs/3.S%3A_Symbolic_Logic_and_Proofs_(Summary)
Skip to main content
\\ \def\d{\displaystyle}\\
\\ \newcommand{\f}$$1$${\mathfrak \#1}\\
\\ \newcommand{\s}$$1$${\mathscr \#1}\\
\\ \def\N{\mathbb N}\\
\\ \def\B{\mathbf{B}}\\
\\ \def\circleA{(-.5,0) circle (1)}\\
\\ \def\Z{\mathbb Z}\\
\\ \def\circleAlabel{(-1.5,.6) node$$above$${\$A\$}}\\
\\ \def\Q{\mathbb Q}\\
\\ \def\circleB{(.5,0) circle (1)}\\
\\ \def\R{\mathbb R}\\
\\ \def\circleBlabel{(1.5,.6) node$$above$${\$B\$}}\\
\\ \def\C{\mathbb C}\\
\\ \def\circleC{(0,-1) circle (1)}\\
\\ \def\F{\mathbb F}\\
\\ \def\circleClabel{(.5,-2) node$$right$${\$C\$}}\\
\\ \def\A{\mathbb A}\\
\\ \def\twosetbox{(-2,-1.5) rectangle (2,1.5)}\\
\\ \def\X{\mathbb X}\\
\\ \def\threesetbox{(-2,-2.5) rectangle (2,1.5)}\\
\\ \def\E{\mathbb E}\\
\\ \def\O{\mathbb O}\\
\\ \def\U{\mathcal U}\\
\\ \def\pow{\mathcal P}\\
\\ \def\inv{^{-1}}\\
\\ \def\nrml{\triangleleft}\\
\\ \def\st{:}\\
\\ \def\\{\widetilde}\\
\\ \def\rem{\mathcal R}\\
\\ \def\sigalg{\$\sigma\$-algebra }\\
\\ \def\Gal{\mbox{Gal}}\\
\\ \def\iff{\leftrightarrow}\\
\\ \def\Iff{\Leftrightarrow}\\
\\ \def\land{\wedge}\\
\\ \def\And{\bigwedge}\\
\\ \def\entry{\entry}\\
\\ \def\AAnd{\d\bigwedge\mkern-18mu\bigwedge}\\
\\ \def\Vee{\bigvee}\\
\\ \def\VVee{\d\Vee\mkern-18mu\Vee}\\
\\ \def\imp{\rightarrow}\\
\\ \def\Imp{\Rightarrow}\\
\\ \def\Fi{\Leftarrow}\\
\\ \def\var{\mbox{var}}\\
\\ \def\Th{\mbox{Th}}\\
\\ \def\entry{\entry}\\
\\ \def\sat{\mbox{Sat}}\\
\\ \def\con{\mbox{Con}}\\
\\ \def\iffmodels{\bmodels\models}\\
\\ \def\dbland{\bigwedge \\\\\bigwedge}\\
\\ \def\dom{\mbox{dom}}\\
\\ \def\rng{\mbox{range}}\\
\\ \def\isom{\cong}\\
\\\DeclareMathOperator{\wgt}{wgt}\\
\\ \newcommand{\vtx}$$2$${node$$fill,circle,inner sep=0pt, minimum size=4pt,label=#1:#2$${}}\\
\\ \newcommand{\va}$$1$${\vtx{above}{#1}}\\
\\ \newcommand{\vb}$$1$${\vtx{below}{#1}}\\
\\ \newcommand{\vr}$$1$${\vtx{right}{#1}}\\
\\ \newcommand{\vl}$$1$${\vtx{left}{#1}}\\
\\ \renewcommand{\v}{\vtx{above}{}}\\
\\ \def\circleA{(-.5,0) circle (1)}\\
\\ \def\circleAlabel{(-1.5,.6) node$$above$${\$A\$}}\\
\\ \def\circleB{(.5,0) circle (1)}\\
\\ \def\circleBlabel{(1.5,.6) node$$above$${\$B\$}}\\
\\ \def\circleC{(0,-1) circle (1)}\\
\\ \def\circleClabel{(.5,-2) node$$right$${\$C\$}}\\
\\ \def\twosetbox{(-2,-1.4) rectangle (2,1.4)}\\
\\ \def\threesetbox{(-2.5,-2.4) rectangle (2.5,1.4)}\\
\\ \def\ansfilename{practice-answers}\\
\\ \def\shadowprops{ {fill=black!50,shadow xshift=0.5ex,shadow yshift=0.5ex,path fading={circle with fuzzy edge 10 percent}} }\\
\\ \renewcommand{\bar}{\overline}\\
\\ \newcommand{\card}$$1$${\left\| \#1 \right\|}\\
\\ \newcommand{\twoline}$$2$${\begin{pmatrix}#1 \\ \#2 \end{pmatrix}}\\
\\ \newcommand{\lt}{<}\\
\\ \newcommand{\gt}{>}\\
\\ \newcommand{\amp}{&}\\
\\ \newcommand{\hexbox}$$3$${
\def\x{-cos{30}\*\r\*#1+cos{30}\*#2\*\r\*2}
\def\y{-\r\*#1-sin{30}\*\r\*#1}
\draw (\x,\y) +(90:\r) -- +(30:\r) -- +(-30:\r) -- +(-90:\r) -- +(-150:\r) -- +(150:\r) -- cycle;
\draw (\x,\y) node{#3};
}\\
\\\renewcommand{\bar}{\overline}\\
\\\newcommand{\card}$$1$${\left\| \#1 \right\|}\\
\\\newcommand{\twoline}$$2$${\begin{pmatrix}#1 \\ \#2 \end{pmatrix}}\\
\\\newcommand{\lt}{\<}\\
\\\newcommand{\gt}{\>}\\
\\\newcommand{\amp}{&}\\
We have considered logic both as its own sub-discipline of mathematics, and as a means to help us better understand and write proofs. In either view, we noticed that mathematical statements have a particular logical form, and analyzing that form can help make sense of the statement.
At the most basic level, a statement might combine simpler statements using *logical connectives*. We often make use of variables, and *quantify* over those variables. How to resolve the truth or falsity of a statement based on these connectives and quantifiers is what logic is all about. From this, we can decide whether two statements are logically equivalent or if one or more statements (logically) imply another.
When writing proofs (in any area of mathematics) our goal is to explain why a mathematical statement is true. Thus it is vital that our argument implies the truth of the statement. To be sure of this, we first must know what it means for the statement to be true, as well as ensure that the statements that make up the proof correctly imply the conclusion. A firm understanding of logic is required to check whether a proof is correct.
There is, however, another reason that understanding logic can be helpful. Understanding the logical structure of a statement often gives clues as how to write a proof of the statement.
This is not to say that writing proofs is always straight forward. Consider again the *Goldbach conjecture*:
> Every even number greater than 2 can be written as the sum of two primes.
We are not going to try to prove the statement here, but we can at least say what a proof might look like, based on the logical form of the statement. Perhaps we should write the statement in an equivalent way which better highlights the quantifiers and connectives:
> For all integers \\n\text{,}\\ if \\n\\ is even and greater than 2, then there exists integers \\p\\ and \\q\\ such that \\p\\ and \\q\\ are prime and \\n = p+q\text{.}\\
What would a direct proof look like? Since the statement starts with a universal quantifier, we would start by, “Let \\n\\ be an arbitrary integer.” The rest of the statement is an implication. In a direct proof we assume the “if” part, so the next line would be, “Assume \\n\\ is greater than 2 and is even.” I have no idea what comes next, but eventually, we would need to find two prime numbers \\p\\ and \\q\\ (depending on \\n\$ and explain how we know that \\n = p+q\text{.}\\
Or maybe we try a proof by contradiction. To do this, we first assume the negation of the statement we want to prove. What is the negation? From what we have studied we should be able to see that it is,
> There is an integer \\n\\ such that \\n\\ is even and greater than \\2\text{,}\\ but for all integers \\p\\ and \\q\text{,}\\ either \\p\\ or \\q\\ is not prime or \\n \ne p+q\text{.}\\
Could this statement be true? A proof by contradiction would start by assuming it was and eventually conclude with a contradiction, proving that our assumption of truth was incorrect. And if you can find such a contradiction, you will have proved the most famous open problem in mathematics. Good luck.
Chapter Review
1
Complete a truth table for the statement \\\neg P \imp (Q \wedge R)\text{.}\\
Solution
| \\P\\ | \\Q\\ | \\R\\ | \\\neg P \imp (Q \wedge R)\\ |
|-------|-------|-------|------------------------------|
| T | T | T | T |
| T | T | F | T |
| T | F | T | T |
| T | F | F | T |
| F | T | T | T |
| F | T | F | F |
| F | F | T | F |
| F | F | F | F |
2
Suppose you know that the statement “if Peter is not tall, then Quincy is fat and Robert is skinny” is false. What, if anything, can you conclude about Peter and Robert if you know that Quincy is indeed fat? Explain (you may reference problem \\\PageIndex{1}\$.
Solution
Peter is not tall and Robert is not skinny. You must be in row 6 in the truth table above.
3
Are the statements \\P \imp (Q \vee R)\\ and \$P \imp Q) \vee (P \imp R)\\ logically equivalent? Explain your answer.
Solution
Yes. To see this, make a truth table for each statement and compare.
4
Is the following a valid deduction rule? Explain.
| | |
|----------------|---------------------------------|
| | \\P \imp Q\\ |
| | \\P\imp R\\ |
| \\\therefore\\ | \\P \imp (Q \wedge R)\text{.}\\ |
Solution
Make a truth table that includes all three statements in the argument:
| \\P\\ | \\Q\\ | \\R\\ | \\P \imp Q\\ | \\P \imp R\\ | \\P \imp (Q \wedge R)\\ |
|-------|-------|-------|--------------|--------------|-------------------------|
| T | T | T | T | T | T |
| T | T | F | T | F | F |
| T | F | T | F | T | F |
| T | F | F | F | F | F |
| F | T | T | T | T | T |
| F | T | F | T | T | T |
| F | F | T | T | T | T |
| F | F | F | T | T | T |
Notice that in every row for which both \\P \imp Q\\ and \\P \imp R\\ is true, so is \\P \imp (Q \wedge R)\text{.}\\ Therefore, whenever the premises of the argument are true, so is the conclusion. In other words, the deduction rule is valid.
5
Write the negation, converse and contrapositive for each of the statements below.
1. If the power goes off, then the food will spoil.
2. If the door is closed, then the light is off.
3. \\\forall x (x \lt 1 \imp x^2 \lt 1)\text{.}\\
4. For all natural numbers \\n\text{,}\\ if \\n\\ is prime, then \\n\\ is solitary.
5. For all functions \\f\text{,}\\ if \\f\\ is differentiable, then \\f\\ is continuous.
6. For all integers \\a\\ and \\b\text{,}\\ if \\a\cdot b\\ is even, then \\a\\ and \\b\\ are even.
7. For every integer \\x\\ and every integer \\y\\ there is an integer \\n\\ such that if \\x \> 0\\ then \\nx \> y\text{.}\\
8. For all real numbers \\x\\ and \\y\text{,}\\ if \\xy = 0\\ then \\x = 0\\ or \\y = 0\text{.}\\
9. For every student in Math 228, if they do not understand implications, then they will fail the exam.
Solution
1. Converse: If the food spoils, then the power went off.
Contrapositive: If the food does not spoil, then the power did not go off.
2. Converse: If the light is off then the door is closed.
Contrapositive: If the light is on then the door is open.
3. Converse: \\\forall x( x^2 \lt 1 \imp x \lt 1)\\
Contrapositive: \\\forall x (x^2 \ge 1 \imp x \ge 1)\text{.}\\
4. Converse: For all natural numbers \\n\text{,}\\ if \\n\\ is solitary, then \\n\\ is prime.
Contrapositive: For all natural numbers \\n\text{,}\\ if \\n\\ is not solitary then \\n\\ is not prime.
5. Converse: For all functions \\f\text{,}\\ if \\f\\ is continuous then \\f\\ is differentiable.
Contrapositive: For all functions \\f\text{,}\\ if \\f\\ is not continuous then \\f\\ is not differentiable.
6. Converse: For all integers \\a\\ and \\b\text{,}\\ if \\a\\ and \\b\\ are even then \\ab\\ is even.
Contrapositive: For all integers \\a\\ and \\b\text{,}\\ if \\a\\ or \\b\\ is odd, then \\ab\\ is odd.
7. Converse: For every integer \\x\\ and every integer \\y\\ there is an integer \\n\\ such that if \\nx \> y\\ then \\x \> 0\text{.}\\
Contrapositive: For every integer \\x\\ and every integer \\y\\ there is an integer \\n\\ such that if \\nx \le y\\ then \\x \le 0\text{.}\\
8. Converse: For all real numbers \\x\\ and \\y\text{,}\\ if \\x = 0\\ or \\y = 0\\ then \\xy = 0\\
Contrapositive: For all real numbers \\x\\ and \\y\text{,}\\ if \\x \ne 0\\ and \\y \ne 0\\ then \\xy \ne 0\text{.}\\
9. Converse: For every student in Math 228, if they fail the exam, then they did not understand implications.
Contrapositive: For every student in Math 228, if they pass the exam, then they understood implications.
6
Consider the statement: for all integers \\n\text{,}\\ if \\n\\ is even and \\n \le 7\\ then \\n\\ is negative or \\n \in \\0,2,4,6\\\text{.}\\
1. Is the statement true? Explain why.
2. Write the negation of the statement. Is it true? Explain.
3. State the contrapositive of the statement. Is it true? Explain.
4. State the converse of the statement. Is it true? Explain.
Solution
1. The statement is true. If \\n\\ is an even integer less than or equal to 7, then the only way it could not be negative is if \\n\\ was equal to 0, 2, 4, or 6.
2. There is an integer \\n\\ such that \\n\\ is even and \\n \le 7\\ but \\n\\ is not negative and \\n \not\in \\0,2,4,6\\\text{.}\\ This is false, since the original statement is true.
3. For all integers \\n\text{,}\\ if \\n\\ is not negative and \\n \not\in\\0,2,4,6\\\\ then \\n\\ is odd or \\n \> 7\text{.}\\ This is true, since the contrapositive is equivalent to the original statement (which is true).
4. For all integers \\n\text{,}\\ if \\n\\ is negative or \\n \in \\0,2,4,6\\\\ then \\n\\ is even and \\n \le 7\text{.}\\ This is false. \\n = -3\\ is a counterexample.
7
Consider the statement: \\\forall x (\forall y (x + y = y) \imp \forall z (x\cdot z = 0))\text{.}\\
1. Explain what the statement says in words. Is this statement true? Be sure to state what you are taking the universe of discourse to be.
2. Write the converse of the statement, both in words and in symbols. Is the converse true?
3. Write the contrapositive of the statement, both in words and in symbols. Is the contrapositive true?
4. Write the negation of the statement, both in words and in symbols. Is the negation true?
Solution
1. For any number \\x\text{,}\\ if it is the case that adding any number to \\x\\ gives that number back, then multiplying any number by \\x\\ will give 0. This is true (of the integers or the reals). The “if” part only holds if \\x = 0\text{,}\\ and in that case, anything times \\x\\ will be 0.
2. The converse in words is this: for any number \\x\text{,}\\ if everything times \\x\\ is zero, then everything added to \\x\\ gives itself. Or in symbols: \\\forall x (\forall z (x \cdot z = 0) \imp \forall y (x + y = y))\text{.}\\ The converse is true: the only number which when multiplied by any other number gives 0 is \\x = 0\text{.}\\ And if \\x = 0\text{,}\\ then \\x + y = y\text{.}\\
3. The contrapositive in words is: for any number \\x\text{,}\\ if there is some number which when multiplied by \\x\\ does not give zero, then there is some number which when added to \\x\\ does not give that number. In symbols: \\\forall x (\exists z (x\cdot z \ne 0) \imp \exists y (x + y \ne y))\text{.}\\ We know the contrapositive must be true because the original implication is true.
4. The negation: there is a number \\x\\ such that any number added to \\x\\ gives the number back again, but there is a number you can multiply \\x\\ by and not get 0. In symbols: \\\exists x (\forall y (x + y = y) \wedge \exists z (x \cdot z \ne 0))\text{.}\\ Of course since the original implication is true, the negation is false.
8
Write each of the following statements in the form, “if …, then ….” Careful, some of the statements might be false (which is alright for the purposes of this question).
1. To lose weight, you must exercise.
2. To lose weight, all you need to do is exercise.
3. Every American is patriotic.
4. You are patriotic only if you are American.
5. The set of rational numbers is a subset of the real numbers.
6. A number is prime if it is not even.
7. Either the Broncos will win the Super Bowl, or they won't play in the Super Bowl.
Solution
1. If you have lost weight, then you exercised.
2. If you exercise, then you will lose weight.
3. If you are American, then you are patriotic.
4. If you are patriotic, then you are American.
5. If a number is rational, then it is real.
6. If a number is not even, then it is prime. (Or the contrapositive: if a number is not prime, then it is even.)
7. If the Broncos don't win the Super Bowl, then they didn't play in the Super Bowl. Alternatively, if the Broncos play in the Super Bowl, then they will win the Super Bowl.
9
Simplify the following.
1. \\\neg (\neg (P \wedge \neg Q) \imp \neg(\neg R \vee \neg(P \imp R)))\text{.}\\
2. \\\neg \exists x \neg \forall y \neg \exists z (z = x + y \imp \exists w (x - y = w))\text{.}\\
Solution
1. \$\neg P \vee Q) \wedge (\neg R \vee (P \wedge \neg R))\text{.}\\
2. \\\forall x \forall y \forall z (z = x+y \wedge \forall w (x-y \ne w))\text{.}\\
10
Consider the statement: for all integers \\n\text{,}\\ if \\n\\ is odd, then \\7n\\ is odd.
1. Prove the statement. What sort of proof are you using?
2. Prove the converse. What sort of proof are you using?
Solution
1. Direct proof.
### Proof
Let \\n\\ be an integer. Assume \\n\\ is odd. So \\n = 2k+1\\ for some integer \\k\text{.}\\ Then
\begin{equation\*} 7n = 7(2k+1) = 14k + 7 = 2(7k +3) + 1. \end{equation\*}
Since \\7k + 3\\ is an integer, we see that \\7n\\ is odd.
2. The converse is: for all integers \\n\text{,}\\ if \\7n\\ is odd, then \\n\\ is odd. We will prove this by contrapositive.
### Proof
Let \\n\\ be an integer. Assume \\n\\ is not odd. Then \\n = 2k\\ for some integer \\k\text{.}\\ So \\7n = 14k = 2(7k)\\ which is to say \\7n\\ is even. Therefore \\7n\\ is not odd.
11
Suppose you break your piggy bank and scoop up a handful of 22 coins (pennies, nickels, dimes and quarters).
1. Prove that you must have at least 6 coins of a single denomination.
2. Suppose you have an odd number of pennies. Prove that you must have an odd number of at least one of the other types of coins.
3. How many coins would you need to scoop up to be sure that you either had 4 coins that were all the same or 4 coins that were all different? Prove your answer.
Solution
1. Suppose you only had 5 coins of each denomination. This means you have 5 pennies, 5 nickels, 5 dimes and 5 quarters. This is a total of 20 coins. But you have more than 20 coins, so you must have more than 5 of at least one type.
2. But this says that the number of pennies is also even (it is 2 times an integer). Thus we have established the contrapositive of the statement, “If you have an odd number of pennies then you have an odd number of at least one other coin type.”
3. You need 10 coins. You could have 3 pennies, 3 nickels, and 3 dimes. The 10th coin must either be a quarter, giving you 4 coins that are all different, or else a 4th penny, nickel or dime. To prove this, assume you don't have 4 coins that are all the same or all different. In particular, this says that you only have 3 coin types, and each of those types can only contain 3 coins, for a total of 9 coins, which is less than 10.
12
You come across four trolls playing bridge. They declare:
- Troll 1: All trolls here see at least one knave.
- Troll 2: I see at least one troll that sees only knaves.
- Troll 3: Some trolls are scared of goats.
- Troll 4: All trolls are scared of goats.
Are there any trolls that are not scared of goats? Recall, of course, that all trolls are either knights (who always tell the truth) or knaves (who always lie).
---