Skip to main content

Discrete Mathematics for Computer Science: An open educational resource.

Ken Levasseur, Al Doerr, Michiel Smid, Oscar Levin, Charles M. Grinstead, J. Laurie Snell, Eric Lehman, F. Thomson Leighton, Albert R Meyer, Jeff Erickson, Kenneth P. Bogart, Carol Chritchlow, David Eck, OpenDSA Project, L.J. Miller

Section 4.1 Propositions and Logical Operators

Subsection 4.1.1 Propositions

Definition 4.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 4.1.2. Some Propositions.

β€œFour is an even number”; β€œfour is an odd number”; β€œ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 such as the words β€œand” and β€œor”. 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.”
πŸ”—
πŸ”—

Subsection 4.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 connective and.
πŸ”—

Definition 4.1.3. Logical Conjunction (AND).

If p and q are propositions, their conjunction, p and q (denoted p∧q), is defined by the truth table
πŸ”—
pqp∧q000010100111
The statement p∧q is only true if both p and q are true.
πŸ”—
πŸ”—
πŸ”—
Notes:
πŸ”—
  1. To read this truth table, you must realize that any one line represents a case: one possible set of values for p and q.
  2. The numbers 0 and 1 are used to denote false and true, respectively. Sometimes you will see F and T instead. The use of 0 and 1 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.
  3. 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.
  4. Just as the letters x, y and z are frequently used in algebra to represent numeric variables, p, q and 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.
  5. One final comment: The order in which we list the cases in truth table rows is standardized in this book. It is important to be consistent with the ordering so that all possible combinations are represented.
    • There will always be 2n rows in a truth table with n propositions
    • From top to bottom, the first column should have 12 of the rows as 0s followed by 12 of the rows as 1s. The second column should have 14 of the rows 0s followed by 14 of the rows 1s, then another 14 rows of 0s followed another 14 rows of 1s. The final column of simple propositions should have rows of alternating 0s and 1s.
    • 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 4.1.4. Logical Disjunction (OR).

If p and q are propositions, their disjunction, p or q (denoted p∨q), is defined by the truth table
πŸ”—
pqp∨q000011101111
The statement p∨q is true if p or q or both are true.
πŸ”—
πŸ”—
πŸ”—

Definition 4.1.5. Logical Negation (NOT).

If p is a proposition, its negation, not p, denoted Β¬p, and is defined by the truth table
πŸ”—
p¬p0110
The statement Β¬p is true if p is false.
πŸ”—
πŸ”—
πŸ”—
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:
πŸ”—
  1. I’m going to quit if I don’t get a raise.
  2. If I pass the final, then I’ll graduate.
  3. 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 β€œIfCondition, 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 4.1.6. Conditional Statement.

The conditional statement β€œIf p then q,” denoted pβ†’q, is defined by the truth table:
πŸ”—
pqp→q001011100111
πŸ”—

Example 4.1.7. 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 4.1.8. 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 4.1.9. 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 it’s contrapositive, which may be somewhat easier.
πŸ”—

Definition 4.1.10. 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
πŸ”—
pqp↔q001010100111
πŸ”—
πŸ”—
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.”
πŸ”—
List 4.1.11. Conditional Alternative Forms
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.
  • if p, q.
  • q whenever p.
  • q when p.
  • q unless Β¬p.
  • p is sufficient for q.
  • a sufficient condition for q is p.
  • q is necessary for p.
  • a necessary condition for p is q.
πŸ”—
List 4.1.12. Biconditional Alternative Forms
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.
πŸ”—
πŸ”—

Exercises 4.1.3 Exercises for Section 4.1

1.

Let d = β€œI like discrete structures”, c = β€œI will pass this course” and s = β€œI will do my assignments.” Express each of the following propositions in symbolic form:
πŸ”—
  1. I like discrete structures and I will pass this course.
  2. I will do my assignments or I will not pass this course.
  3. It is not true that I both like discrete structures, and will do my assignments.
  4. I will not do my assignment and I will not pass this course.
πŸ”—
Answer.
  1. d∧c
  2. s∨¬c
  3. ¬(d∧s)
  4. ¬s∧¬c
πŸ”—

2.

For each of the following propositions, identify simple propositions, express the compound proposition in symbolic form, and determine whether it is true or false:
πŸ”—
  1. The world is flat or zero is an even integer.
  2. If 432,802 is a multiple of 4, then 432,802 is even.
  3. 5 is a prime number and 6 is not divisible by 4.
  4. 3∈Z and 3∈Q.
  5. 2/3∈Z and 2/3∈Q.
  6. The sum of two even integers is even and the sum of two odd integers is odd.
πŸ”—
πŸ”—

3.

Let p=β€œ2≀5”, q = β€œ8 is an even integer,” and r = β€œ11 is a prime number.” Express the following as a statement in English and determine whether the statement is true or false:
πŸ”—
  1. ¬p∧q
  2. p→q
  3. (p∧q)β†’r
  4. pβ†’(q∨(Β¬r))
  5. pβ†’((Β¬q)∨(Β¬r))
  6. (Β¬q)β†’(Β¬p)
πŸ”—
Answer.
  1. 2>5 and 8 is an even integer. False.
  2. If 2β©½5 then 8 is an even integer. True.
  3. If 2β©½5 and 8 is an even integer then 11 is a prime number. True.
  4. If 2β©½5 then either 8 is an even integer or 11 is not a prime number. True.
  5. If 2β©½5 then either 8 is an odd integer or 11 is not a prime number. False.
  6. If 8 is not an even integer then 2>5. True.
πŸ”—

4.

Rewrite each of the following statements in symbolic form. Make sure you define the propositional variables:
πŸ”—
  1. If an integer is a multiple of 4, then it is even.
  2. The fact that a polygon is a square is a sufficient condition that it is a rectangle.
  3. If x=5, then x2=25.
  4. If x2βˆ’5x+6=0, then x=2 or x=3.
  5. x2=y2 is a necessary condition for x=y.
πŸ”—
πŸ”—

5.

Write the converse of the propositions in exercise 4. Compare the truth of each proposition and its converse.
πŸ”—
Answer.
Only the converse of d is true.
πŸ”—
πŸ”—
πŸ”—
PrevTopNext