Study Guide for Discrete Mathematics
Section 1.1 – Logic
The human brain is vastly more complex than any computer technology yet invented. It is yet unmatched in areas such as creativity and planning. For many years it was thought that the human brain would always be superior to computers in areas such as Symbolic Logic and Calculus. However, that is now known not to be the case. The reason is simple. Symbolic Logic and Calculus and the like are symbol-substitution, rule-based systems. I.e. in order to solve a problem or prove a theorem in such disciplines one need only apply the correct symbol substitution rules in the correct order. This can be accomplished using a computer utilizing clever algorithms and sheer brute-force computational power.
The fact that such automated, rule-based systems work so well leads us to a new standard in proof rigor. Every step in a computer-generated proof is the application of a symbol substitution rule. The computer program can give you a legitimate reason for each and every line of the proof. Although you will not be held to such a standard in your proofs please keep in mind that you have not produced a true proof unless each step (the transition from one line of the proof to the next) is simply an application of one of the basic rules of the system or the application of a previously proven theorem.
One distinct advantage to proving theorems in symbolic logic as opposed to proving theorems in , say, topology (a branch of mathematics) is that, due to the fact that there are only two values (T and F) for variables in symbolic logic, one may use truth tables to prove theorems. Although the truth table is a valid mechanism for proving theorems in symbolic logic it is not applicable in every circumstance. You will be required to know how to prove theorems using the other methods that have been discussed in class.
Examples:
Excellent examples of using truth tables to prove statements are given in the text.
Excellent examples of formal proofs using logical equivalences are given in the text.
Basic Statements and their Derivatives
Statement: p Þ q
Converse: q Þ p
Inverse: Ø p Þ Ø q
Contrapositive: Ø q Þ Ø p
Note that the Statement and the Contrapositive are equivalent to each other. And the Converse and Inverse are equivalent to each other.
Example:
State the Converse, Inverse and Contrapositive of the following statement in English.
Statement: If it rains today then the ground will be wet this afternoon
Converse: If the ground is wet this afternoon then it rained today
Inverse: If it did not rain today then the ground is not wet this afternoon
Contrapositive: If the ground is not wet this afternoon then it did not rain today.
IF And Only IF
We often see statements of the form "P if and only if Q". For example, "I will carry an umbrella today if and only if it rains." Such a formulation can sometimes be confusing. However it is actually quite simple if one understands the following breakdown.
"P if and only if Q" is actually two statements.
"P if Q" is equivalent to "If Q then P" and
"P only if Q" is equivalent to "If P then Q"
Many other formulations of implications occur in mathematics, logic and everyday conversation. One notable one is "Necessary and Sufficient". For example, "P is necessary for Q" means that QÞ P and "P is sufficient for Q" means that P Þ Q.