Applied Discrete Structures

In traditional logic, a declarative statement with a definite truth value is considered a proposition. Although our ultimate aim is to discuss mathematical logic, we won’t separate ourselves completely from the traditional setting. This is natural because the basic assumptions, or postulates, of mathematical logic are modeled after the logic we use in everyday life. Since compound sentences are frequently used in everyday speech, we expect that logical propositions contain connectives like the word “and.” The statement “Europa supports life or Mars supports life” is a proposition and, hence, must have a definite truth value. Whatever that truth value is, it should be the same as the truth value of “Mars supports life or Europa supports life.”

There are several ways in which we commonly combine simple statements into compound ones. The words/phrases and, or, not, if ... then..., and ...if and only if ... can be added to one or more propositions to create a new proposition. To avoid any confusion, we will precisely define each one’s meaning and introduce its standard symbol. With the exception of negation (not), all of the operations act on pairs of propositions. Since each proposition has two possible truth values, there are four ways that truth can be assigned to two propositions. In defining the effect that a logical operation has on two propositions, the result must be specified for all four cases. The most convenient way of doing this is with a truth table, which we will illustrate by defining the word and.

Notes:

Note: Negation is the only standard operator that acts on a single proposition; hence only two cases are needed.

Consider the following propositions from everyday speech:

All three propositions are conditional, they can all be restated to fit into the form “If Condition, then Conclusion.” For example, the first statement can be rewritten as “If I don’t get a raise, then I’m going to quit.”

A conditional statement is meant to be interpreted as a guarantee; if the condition is true, then the conclusion is expected to be true. It says no more and no less.

The order of the condition and conclusion in a conditional proposition is important. If the condition and conclusion are exchanged, a different proposition is produced.

The converse of “If you receive a grade of 95 or better in the final exam, then you will receive an A in this course,” is “If you receive an A in this course, then you received a grade of 95 or better in the final exam.” It should be clear that these two statements say different things.

There is a proposition related to $p\to q$ that does have the same logical meaning. This is the contrapositive.

As we will see when we discuss logical proofs, we can prove a conditional proposition by proving its contrapositive, which may be somewhat easier.

Finally, there a third variation on the proposition $p\to q\text{,}$ the inverse, which we will see that has the same logical meaning as the converse.

The inverse of "If it snows today, we have a day off." would be "If it doesn’t snow today, we don’t have a day off." Can you see that the original proposition and the inverse are saying different things?

Our final logical operator is a conjunction of two conditionals

Note that $p\leftrightarrow q$ is true when $p$ and $q$ have the same truth values. It is common to abbreviate “if and only if” to “iff.”

Although “if ... then...” and “...if and only if ...” are frequently used in everyday speech, there are several alternate forms that you should be aware of. They are summarized in the following lists.

All of the following are equivalent to “If $p$ then $q$”:

All of the following are equivalent to “$p$ if and only if $q$”: