## Propositions and Logical Operators

Read these sections to supplement your understanding of propositional logic.

**3.1 Propositions and Logical Operators**

**3.1.1 Propositions**

**Definition 3.1.1 Proposition. **A proposition is a sentence to which one and only one of the terms *true *or *false *can be meaningfully applied.

**Example 3.1.2 Some Propositions. **"Four is even", "4 ∈ {1, 3, 5}", and "43 *> * 21" are propositions.

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".

**3.1.2 Logical Operations**

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*.

**Definition 3.1.3 Logical Conjunction. **If *p *and *q *are propositions, their conjunction, *p *and *q *(denoted *p* ∧ *q*), is defined by the truth table

Notes:

- To read this truth table, you must realize that any one line represents a case: one possible set of values for
*p*and*q*. - The numbers 0 and 1 are used to denote false and true, respectively. This is consistent with the way that many programming languages treat logical, or Boolean, variables since a single bit, 0 or 1, can represent a truth value.
- For each case, the symbol under
*p*represents the truth value of*p*. The same is true for*q*. The symbol under*p*∧*q*represents its truth value for that case. For example, the second row of the truth table represents the case in which*p*is false,*q*is true, and the resulting truth value for*p*∧*q*is false. As in everyday speech,*p*∧*q*is true only when both propositions are true. - Just as the letters
*x*,*y*,*z*are frequently used in algebra to represent numeric variables,*p*,*q*,*r*seem to be the most commonly used symbols for logical variables. When we say that*p*is a logical variable, we mean that any proposition can take the place of*p*. - One final comment: The order in which we list the cases in a truth table is standardized in this book. If the truth table involves two simple propositions, the numbers under the simple propositions can be interpreted as the two-digit binary integers in increasing order, 00, 01, 10, and 11, for 0, 1, 2, and 3, respectively.

**Definition 3.1.4 Logical Disjunction. **If *p *and *q * are propositions, their disjunction, *p *or *q *(denoted *p *∨ *q*), is defined by the truth table

**Definition 3.1.5 ****Logical Negation. **If *p *is a proposition, its negation, not *p*, denoted *¬**p*, and is defined by the truth table

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:

- I'm going to quit if I don't get a raise.
- If I pass the final, then I'll graduate.
- I'll be going to the movies provided that my car starts.

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.

**Definition 3.1.6 Conditional Statement. **The conditional statement "If *p *then *q* ", denoted *p **→ **q*, is defined by the truth table

**T****able 3.1.7 Truth Table ****for ***p **→ **q*

**Example 3.1.8 Analysis ****of a Conditional Proposition. **Assume your instructor told you "If you receive a grade of 95 or better in the final examination, then you will receive an A in this course". Your instructor has made a promise to you. If you fulfill his condition, you expect the conclusion (getting an A) to be forthcoming. Suppose your graded final has been returned to you. Has your instructor told the truth or is your instructor guilty of a falsehood?

Case I: Your final exam score was less than 95 (the condition is false) and you did not receive an A (the conclusion is false). The instructor told the truth.

Case II: Your final exam score was less than 95, yet you received an A for the course. The instructor told the truth. (Perhaps your overall course average was excellent.)

Case III: Your final exam score was greater than 95, but you did not receive an A. The instructor lied.

Case IV: Your final exam score was greater than 95, and you received an A. The instructor told the truth.

To sum up, the only case in which a conditional proposition is false is when the condition is true and the conclusion is false.

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.

**Definition 3.1.9 Converse. **The converse of the proposition *p **→ **q *is the proposition *q **→ **p*.

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 **→ **q *that does have the same logical meaning. This is the contrapositive.

**Definition 3.1.10 Contrapositive. **The contrapositive of the proposition *p **→ **q *is the proposition *¬* *q** **→ ¬**p*.

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

**Definition 3.1.11 Biconditional Proposition. **If *p *and *q *are propositions, the biconditional statement "*p *if and only if *q*", denoted *p **↔ **q*, is defined by the truth table

Note that *p **↔ **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*":

*p*implies*q*.*q*follows from*p*.*p*, only if*q*.*q*, if*p*.*p*is sufficient for*q*.*q*is necessary for*p*.

All of the following are equivalent to "*p *if and only if *q*":

*p*is necessary and sufficient for*q*.*p*is equivalent to*q*.- If
*p*, then*q*, and if*q*, then*p*. - If
*p*, then*q*and conversely.

Source: Al Doerr and Ken Levasseur, http://faculty.uml.edu/klevasseur/ads-latex/ads.pdf

This work is licensed under a Creative Commons Attribution-NonCommercial-ShareAlike 3.0 License.