Skip to main content
Logo image

Applied Discrete Structures

Al Doerr, Ken Levasseur

Section 3.5 Mathematical Systems and Proofs

Subsection 3.5.1 Mathematical Systems

In this section, we present an overview of what a mathematical system is and how logic plays an important role in one. The axiomatic method that we will use here will not be duplicated with as much formality anywhere else in the book, but we hope an emphasis on how mathematical facts are developed and organized will help to unify the concepts we will present. The system of propositions and logical operators we have developed will serve as a model for our discussion. Roughly, a mathematical system can be defined as follows.

Definition 3.5.1. Mathematical System.

A mathematical system consists of:
  1. A set or universe, \(U\text{.}\)
  2. Definitions: sentences that explain the meaning of concepts that relate to the universe. Any term used in describing the universe itself is said to be undefined. All definitions are given in terms of these undefined concepts of objects.
  3. Axioms: assertions about the properties of the universe and rules for creating and justifying more assertions. These rules always include the system of logic that we have developed to this point.
  4. Theorems: the additional assertions mentioned above.

Example 3.5.2. Euclidean Geometry.

In Euclidean geometry the universe consists of points and lines (two undefined terms). Among the definitions is a definition of parallel lines and among the axioms is the axiom that two distinct parallel lines never meet.

Example 3.5.3. Propositional Calculus.

Propositional calculus is a formal name for the logical system that we’ve been discussing. The universe consists of propositions. The axioms are the truth tables for the logical operators and the key definitions are those of equivalence and implication. We use propositions to describe any other mathematical system; therefore, this is the minimum amount of structure that a mathematical system can have.

Definition 3.5.4. Theorem.

A true proposition derived from the axioms of a mathematical system is called a theorem.
Theorems are normally expressed in terms of a finite number of propositions, \(p_1, p_2, . . . ,p_n\) , called the premises, and a proposition,\(C\text{,}\) called the conclusion. These theorems take the form
\begin{equation*} p_1\land p_2\land \cdots \land p_n\Rightarrow C \end{equation*}
or more informally,
\begin{equation*} p_1, p_2, . . . , \textrm{ and } p_n \textrm{ imply } C \end{equation*}
For a theorem of this type, we say that the premises imply the conclusion. When a theorem is stated, it is assumed that the axioms of the system are true. In addition, any previously proven theorem can be considered an extension of the axioms and can be used in demonstrating that the new theorem is true. When the proof is complete, the new theorem can be used to prove subsequent theorems. A mathematical system can be visualized as an inverted pyramid with the axioms at the base and the theorems expanding out in various directions.
Inverted pyramid of knowledge with the axioms at the narrow bottom, then early theorems at the next level up, and then new theorems in a wider area. Research is above and outside the pyramid.
Figure 3.5.5. The body of knowledge in a mathematical system

Definition 3.5.6. Proof.

A proof of a theorem is a finite sequence of logically valid steps that demonstrate that the premises of a theorem imply its conclusion.
Exactly what constitutes a proof is not always clear. For example, a research mathematician might require only a few steps to prove a theorem to a collegue, but might take an hour to give an effective proof to a class of students. Therefore, what constitutes a proof often depends on the audience. But the audience is not the only factor. One of the most famous theorems in graph theory, The Four-Color Theorem, was proven in 1976, after over a century of effort by many mathematicians. Part of the proof consisted of having a computer check many different graphs for a certain property. Without the aid of the computer, this checking would have taken years. In the eyes of some mathematicians, this proof was considered questionable. Shorter proofs have been developed since 1976 and there is no controversy associated with The Four Color Theorem at this time.

Subsection 3.5.2 Direct Proof

Theoretically, you can prove anything in propositional calculus with truth tables. In fact, the laws of logic stated in Section 3.4 are all theorems. Propositional calculus is one of the few mathematical systems for which any valid sentence can be determined true or false by mechanical means. A program to write truth tables is not too difficult to write; however, what can be done theoretically is not always practical. For example,
\begin{equation*} a, a\to b, b\to c, . . . ,y\to z\Rightarrow z \end{equation*}
is a theorem in propositional calculus. However, suppose that you wrote such a program and you had it write the truth table for
\begin{equation*} (a\land (a\to b)\land ( b\to c)\land \cdots \land (y\to z))\to z \end{equation*}
The truth table will have \(2^{26}\) cases. At one million cases per second, it would take approximately one hour to verify the theorem. Now if you decided to check a similar theorem,
\begin{equation*} p_1,p_1\to p_2,\ldots ,p_{99}\to p_{100}\Rightarrow p_{100} \end{equation*}
you would really have time trouble. There would be \(2^{100} \approx 1.26765\times 10^{30}\) cases to check in the truth table. At one million cases per second it would take approximately \(1.46719\times 10^{19}\) days to check all cases. For most of the remainder of this section, we will discuss an alternate method for proving theorems in propositional calculus. It is the same method that we will use in a less formal way for proofs in other systems. Formal axiomatic methods would be too unwieldy to actually use in later sections. However, none of the theorems in later chapters would be stated if they couldn’t be proven by the axiomatic method.
We will introduce two types of proof here, direct and indirect.

Example 3.5.7. A typical direct proof.

This is a theorem: \(p \rightarrow r, q\rightarrow s,p\lor q\Rightarrow s\lor r\text{.}\) A direct proof of this theorem is:
Table 3.5.8. Direct proof of \(p \rightarrow r, q\rightarrow s,p\lor q\Rightarrow s\lor r\)
Step Proposition Justification
1. \(p \lor q\) Premise
2. \(\neg p \rightarrow q\) (1), conditional rule
3. \(q \rightarrow s\) Premise
4. \(\neg p \rightarrow s\) (2), (3), chain rule
5. \(\neg s \rightarrow p\) (4), contrapositive
6. \(p \rightarrow r\) Premise
7. \(\neg s \rightarrow r\) (5), (6), chain rule
8. \(s \lor r\) (7), conditional rule \(\blacksquare\)
Note that \(\blacksquare\) marks the end of a proof.
Example 3.5.7 illustrates the usual method of formal proof in a formal mathematical system. The rules governing these proofs are:
  1. A proof must end in a finite number of steps.
  2. Each step must be either a premise or a proposition that is implied from previous steps using any valid equivalence or implication.
  3. For a direct proof, the last step must be the conclusion of the theorem. For an indirect proof (see below), the last step must be a contradiction.
  4. Justification Column. The column labeled “justification” is analogous to the comments that appear in most good computer programs. They simply make the proof more readable.

Example 3.5.9. Two proofs of the same theorem.

Here are two direct proofs of \(\neg p \lor q, s\lor p, \neg q \Rightarrow s\text{:}\)
Table 3.5.10. Direct proof of \(\neg p \lor q, s\lor p, \neg q \Rightarrow s\)
1. \(\neg p \lor q\) Premise
2. \(\neg q\) Premise
3. \(\neg p\) Disjunctive simplification, (1), (2)
4. \(s\lor p\) Premise
5. \(s\) Disjunctive simplification, (3), (4). \(\blacksquare\)
You are invited to justify the steps in this second proof:
Table 3.5.11. Alternate proof of \(\neg p \lor q, s\lor p, \neg q \Rightarrow s\)
1. \(\neg p \lor q\)
2. \(\neg q \rightarrow \neg p\)
3. \(s\lor p\)
4. \(p \lor s\)
5. \(\neg p \to s\)
6. \(\neg q \rightarrow s\)
7. \(\neg q\)
8. \(s\) \(\blacksquare\)
The conclusion of a theorem is often a conditional proposition. The condition of the conclusion can be included as a premise in the proof of the theorem. The object of the proof is then to prove the consequence of the conclusion. This rule is justified by the logical law
\begin{equation*} p \rightarrow (h \rightarrow c) \Leftrightarrow (p \land h) \rightarrow c \end{equation*}

Example 3.5.12. Example of a proof with a conditional conclusion.

The following proof of \(p \to (q \rightarrow s), \neg r \lor p, q \Rightarrow r \rightarrow s\) includes \(r\) as a fourth premise. Inference of truth of \(s\) completes the proof.
Table 3.5.13. Proof of a theorem with a conditional conclusion.
1. \(\neg r \lor p\) Premise
2. \(r\) Added premise
3. \(p\) (1), (2), disjunction simplification
4. \(p \rightarrow (q \to s)\) Premise
5. \(q\rightarrow s\) (3), (4), detachment
6. \(q\) Premise
7. \(s\) (5), (6), detachment. \(\blacksquare\)

Subsection 3.5.3 Indirect Proof

Consider a theorem \(P\Rightarrow C\text{,}\) where \(P\) represents \(p_1, p_2, . . . , \textrm{ and } p_n\text{,}\) the premises. The method of indirect proof is based on the equivalence \(P\rightarrow C\Leftrightarrow \neg (P\land \neg C)\text{.}\) In words, this logical law states that if \(P \Rightarrow C\text{,}\) then \(P \land \neg C\) is always false; that is, \(P \land \neg C\) is a contradiction. This means that a valid method of proof is to negate the conclusion of a theorem and add this negation to the premises. If a contradiction can be implied from this set of propositions, the proof is complete. For the proofs in this section, a contradiction will often take the form \(t \land \neg t\text{.}\)
For proofs involving numbers, a contradiction might be \(1 = 0\) or \(0 < 0\text{.}\) Indirect proofs involving sets might conclude with \(x \in \emptyset\) or (\(x \in A\) and \(x \in A^c\)). Indirect proofs are often more convenient than direct proofs in certain situations. Indirect proofs are often called proofs by contradiction.

Example 3.5.14. An Indirect Proof.

Here is an example of an indirect proof of the theorem in Example 3.5.7.
Table 3.5.15. An Indirect proof of \(p \rightarrow r, q\rightarrow s,p\lor q\Rightarrow s\lor r\)
1. \(\neg (s \lor r)\) Negated conclusion
2. \(\neg s \land \neg r\) DeMorgan’s Law, (1)
3. \(\neg s\) Conjunctive simplification, (2)
4. \(q\to s\) Premise
5. \(\neg q\) Indirect reasoning, (3), (4)
6. \(\neg r\) Conjunctive simplification, (2)
7. \(p \rightarrow r\) Premise
8. \(\neg p\) Indirect reasoning, (6), (7)
9. \((\neg p) \land (\neg q)\) Conjunctive, (5), (8)
10. \(\neg (p \lor q)\) DeMorgan’s Law, (9)
11. \(p \lor q\) Premise
12. \(0\) (10), (11) \(\blacksquare\)

Note 3.5.16. Proof Style.

The rules allow you to list the premises of a theorem immediately; however, a proof is much easier to follow if the premises are only listed when they are needed.

Example 3.5.17. Yet Another Indirect Proof.

Here is an indirect proof of \(a \rightarrow b, \neg (b \lor c ) \Rightarrow \neg a\text{.}\)
Table 3.5.18. Indirect proof of \(a \rightarrow b, \neg (b \lor c ) \Rightarrow \neg a\)
1. \(a\) Negation of the conclusion
2. \(a\to b\) Premise
3. \(b\) (1), (2), detachment
4. \(b \lor c\) (3), disjunctive addition
5. \(\neg (b \lor c)\) Premise
6. \(0\) (4), (5) \(\blacksquare\)
As we mentioned at the outset of this section, we are only presenting an overview of what a mathematical system is. For greater detail on axiomatic theories, see Stoll (1961). An excellent description of how propositional calculus plays a part in artificial intelligence is contained in Hofstadter (1980). If you enjoy the challenge of constructing proofs in propositional calculus, you should enjoy the game WFF’N PROOF (1962), by L.E. Allen.

Exercises 3.5.4 Exercises

1.

Prove with truth tables:
  1. \(\displaystyle p\lor q, \neg q\Rightarrow p\)
  2. \(\displaystyle p \rightarrow q, \neg q \Rightarrow \neg p\)
Answer.
  1. \begin{equation*} \begin{array}{cccc} p & q & (p\lor q)\land \neg q & ((p\lor q)\land \neg q)\to p \\ 0 & 0 & 0 & 1 \\ 0 & 1 & 0 & 1 \\ 1 & 0 & 1 & 1 \\ 1 & 1 & 0 & 1 \\ \end{array} \end{equation*}
  2. \begin{equation*} \begin{array}{ccccc} p & q & (p\to q)\land \neg q & \neg p & (p\to q)\land (\neg q) \\ 0 & 0 & 1 & 1 & 1 \\ 0 & 1 & 0 & 1 & 1 \\ 1 & 0 & 0 & 0 & 1 \\ 1 & 1 & 0 & 0 & 1 \\ \end{array} \end{equation*}

2.

Prove with truth tables:
  1. \(\displaystyle q, \neg q\Rightarrow p\)
  2. \(\displaystyle p \rightarrow q \Leftrightarrow \neg p \lor q\)

3.

Give direct and indirect proofs of:
  1. \(a \rightarrow b, c \rightarrow b, d\rightarrow (a \lor c), d\Rightarrow b\text{.}\)
  2. \((p\to q) \land (r\to s), (q\rightarrow t) \land (s \to u), \neg (t \land u), p \rightarrow r \Rightarrow \neg p\text{.}\)
  3. \(p\to (q\to r),\neg s \lor p,q\Rightarrow s\to r\text{.}\)
  4. \(p\rightarrow q, q\rightarrow r, \neg (p \land r), p \lor r \Rightarrow r\text{.}\)
  5. \(\displaystyle \neg q, p\to q, p\lor t \Rightarrow t\)
Answer.
  1. Direct proof:
    1. \(\displaystyle d\to (a\lor c)\)
    2. \(\displaystyle d\)
    3. \(\displaystyle a\lor c\)
    4. \(\displaystyle a\to b\)
    5. \(\displaystyle \neg a \lor b\)
    6. \(\displaystyle c\to b\)
    7. \(\displaystyle \neg c\lor b\)
    8. \(\displaystyle (\neg a\lor b)\land (\neg c\lor b)\)
    9. \(\displaystyle (\neg a\land \neg c) \lor b\)
    10. \(\displaystyle \neg (a\lor c)\lor b\)
    11. \(b\) \(\blacksquare\)
    Indirect proof:
    1. \(\neg b\quad \) Negated conclusion
    2. \(a\to b\quad \) Premise
    3. \(\neg a\quad \) Indirect Reasoning (1), (2)
    4. \(c\to b\quad \) Premise
    5. \(\neg c\quad \) Indirect Reasoning (1), (4)
    6. \((\neg a\land \neg c)\quad \) Conjunctive (3), (5)
    7. \(\neg (a\lor c)\quad \) DeMorgan’s law (6)
    8. \(d\to (a\lor c)\quad \) Premise
    9. \(\neg d\quad \) Indirect Reasoning (7), (8)
    10. \(d\quad \) Premise
    11. \(\mathbb{0} \quad \) (9), (10) \(\quad \blacksquare\)
  2. Direct proof:
    1. \(\displaystyle (p\to q)\land (r\to s)\)
    2. \(\displaystyle p\to q\)
    3. \(\displaystyle (p\to t)\land (s\to u)\)
    4. \(\displaystyle q\to t\)
    5. \(\displaystyle p\to t\)
    6. \(\displaystyle r\to s\)
    7. \(\displaystyle s\to u\)
    8. \(\displaystyle r\to u\)
    9. \(\displaystyle p\to r\)
    10. \(\displaystyle p\to u\)
    11. \(p\to (t\land u)\) Use \((x\to y)\land (x\to z)\Leftrightarrow x\to (y\land z)\)
    12. \(\displaystyle \neg (t\land u)\to \neg p\)
    13. \(\displaystyle \neg (t\land u)\)
    14. \(\neg p\) \(\quad \blacksquare\)
    Indirect proof:
    1. \(\displaystyle p\)
    2. \(\displaystyle p\to q\)
    3. \(\displaystyle q\)
    4. \(\displaystyle q\to t\)
    5. \(\displaystyle t\)
    6. \(\displaystyle \neg (t\land u)\)
    7. \(\displaystyle \neg t\lor \neg u\)
    8. \(\displaystyle \neg u\)
    9. \(\displaystyle s\to u\)
    10. \(\displaystyle \neg s\)
    11. \(\displaystyle r\to s\)
    12. \(\displaystyle \neg r\)
    13. \(\displaystyle p\to r\)
    14. \(\displaystyle r\)
    15. \(0\) \(\quad \blacksquare\)
  3. Direct proof:
    1. \(\neg s\lor p\quad \) Premise
    2. \(s\quad \) Added premise (conditional conclusion)
    3. \(\neg (\neg s)\quad \) Involution (2)
    4. \(p \quad \) Disjunctive simplification (1), (3)
    5. \(p\to (q\to r)\quad \) Premise
    6. \(q\to r\quad \) Detachment (4), (5)
    7. \(q \quad\) Premise
    8. \(r\quad \) Detachment (6), (7) \(\blacksquare\)
    Indirect proof:
    1. \(\neg (s\to r)\quad \) Negated conclusion
    2. \(\neg (\neg s\lor r)\quad \) Conditional equivalence (1)
    3. \(s\land \neg r\quad \) DeMorgan (2)
    4. \(s\quad\) Conjunctive simplification (3)
    5. \(\neg s\lor p\quad \) Premise
    6. \(s\to p\quad\) Conditional equivalence (5)
    7. \(p \quad\) Detachment (4), (6)
    8. \(p\to (q\to r)\quad\) Premise
    9. \(q\to r \quad\) Detachment (7), (8)
    10. \(q\quad \) Premise
    11. \(r\quad\) Detachment (9), (10)
    12. \(\neg r \quad\) Conjunctive simplification (3)
    13. \(0 \quad\) Conjunction (11), (12) \(\blacksquare\)
  4. Direct proof:
    1. \(\displaystyle p\to q\)
    2. \(\displaystyle q\to r\)
    3. \(\displaystyle p\to r\)
    4. \(\displaystyle p\lor r\)
    5. \(\displaystyle \neg p\lor r\)
    6. \(\displaystyle (p\lor r)\land (\neg p\lor r)\)
    7. \(\displaystyle (p\land \neg p)\lor r\)
    8. \(\displaystyle 0\lor r\)
    9. \(r\)\(\blacksquare\)
    Indirect proof:
    1. \(\neg r\) Negated conclusion
    2. \(p\lor r\quad\) Premise
    3. \(p\quad\) (1), (2)
    4. \(p\to q\quad\) Premise
    5. \(q \quad \) Detachment (3), (4)
    6. \(q\to r\quad\) Premise
    7. \(r \quad \)Detachment (5), (6)
    8. \(0 \quad\) (1), (7) \(\blacksquare\)

4.

Give direct and indirect proofs of:
  1. \(p\rightarrow q, \neg r\rightarrow \neg q, \neg r \Rightarrow \neg p\text{.}\)
  2. \(p\rightarrow \neg q, \neg r\rightarrow q, p \Rightarrow r\text{.}\)
  3. \(a \lor b, c \land d, a \rightarrow \neg c \Rightarrow b\text{.}\)

5.

Are the following arguments valid? If they are valid, construct formal proofs; if they aren’t valid, explain why not.
  1. If wages increase, then there will be inflation. The cost of living will not increase if there is no inflation. Wages will increase. Therefore, the cost of living will increase.
  2. If the races are fixed or the casinos are crooked, then the tourist trade will decline. If the tourist trade decreases, then the police will be happy. The police force is never happy. Therefore, the races are not fixed.
Answer.
  1. Let \(W\) stand for “Wages will increase,” \(I\) stand for “there will be inflation,” and \(C\) stand for “cost of living will increase.” Therefore the argument is: \(W\to I,\text{ }\neg I\to \neg C,\text{ }W\Rightarrow C\text{.}\) The argument is invalid. The easiest way to see this is through a truth table, which has one case, the seventh, that this false. Let \(x\) be the conjunction of all premises. \(\begin{array}{ccccccccc} W & I & C & \neg I & \neg C & W\to I & \neg I\to \neg C & x & x\to C \\ \hline 0 & 0 & 0 & 1 & 1 & 1 & 1 & 0 & 1 \\ 0 & 0 & 1 & 1 & 0 & 1 & 0 & 0 & 1 \\ 0 & 1 & 0 & 0 & 1 & 1 & 1 & 0 & 1 \\ 0 & 1 & 1 & 0 & 0 & 1 & 1 & 0 & 1 \\ 1 & 0 & 0 & 1 & 1 & 0 & 1 & 0 & 1 \\ 1 & 0 & 1 & 1 & 0 & 0 & 0 & 0 & 1 \\ 1 & 1 & 0 & 0 & 1 & 1 & 1 & 1 & 0 \\ 1 & 1 & 1 & 0 & 0 & 1 & 1 & 1 & 1 \\ \end{array}\)
  2. Let \(r\) stand for “the races are fixed,” \(c\) stand for “casinos are crooked,” \(t\) stand for “the tourist trade will decline,” and \(p\) stand for “the police will be happy.” Therefore, the argument is:
    \begin{equation*} (r\lor c)\to t, t\to p, \neg p\to \neg r\text{.} \end{equation*}
    The argument is valid. Proof:
    1. \(t\to p\quad \) Premise
    2. \(\neg p\quad \) Premise
    3. \(\neg t\quad \) Indirect Reasoning (1), (2)
    4. \((r\lor c)\to t\quad \) Premise
    5. \(\neg (r\lor c)\quad \) Indirect Reasoning (3), (4)
    6. \((\neg r)\land (\neg c)\quad \) DeMorgan (5)
    7. \(\neg r\quad \) Conjunction simplification \((6)\text{ }\blacksquare\)

6.

My salad contains beets and okra. If my salad contains cottage cheese then it doesn’t contain beets. My salad contains cottage cheese or hummus. Therefore, my salad contains hummus.

7.

Describe how \(p_1,p_1\to p_2,\ldots ,p_{99}\to p_{100}\Rightarrow p_{100}\) could be proved in 199 steps.
Answer.
\(p_1\to p_k\) and \(p_k\to p_{k+1}\) implies \(p_1\to p_{k+1}\text{.}\) It takes two steps to get to \(p_1\to p_{k+1}\) from \(p_1\to p_k\) This means it takes \(2(100-1)\) steps to get to \(p_1\to p_{100}\) (subtract 1 because \(p_1\to p_2\) is stated as a premise). A final step is needed to apply detachment to imply \(p_{100}\)
You have attempted of activities on this page.
PrevTopNext