Subsection 2.3.7 Operator Precedence for Logical Operators
Of course, the reason we’re talking about operator precedence is not that we care to review what we know about arithmetic. What we do need to do is to define an analogous precedence scheme for logical operators. Here’s the one that we will use:
| Arithmetic | Logic | |
|---|---|---|
| Highest | unary minus | not |
| exponentiation | and | |
| multiplication, division | or | |
| addition and subtraction | implies | |
| Lowest | is equivalent to |
Recall that precedence is not the only tool we have for indicating the order in which operations should be performed. We can always use parentheses, either when the defined precedence levels don’t lead to the interpretation that we want or when we’re not sure.
In fact, we’ll typically not count on you to remember this list. We’ll assume that not (our only unary operator) is done first (it’s got the tightest scope). For everything else, we’ll usually use parentheses.
Here are some pairs of equivalent expressions:
\(p \wedge \neg p \) \(p \wedge (\neg p) \) \(\neg \) is done before \(\wedge \) . \(p \wedge q \vee r \) \((p \wedge q) \vee r \) \(\wedge \) is done before \(\vee \text{.}\) \(p \wedge q \wedge r \) \(p \wedge (q \wedge r) \) again \(\wedge \) is done before \(\vee \text{.}\) \(\neg p \vee q \wedge r \) \((\neg p) \wedge (q \wedge r) \) \(\neg \text{.}\) then \(\wedge \) then \(\vee \) \(p \vee q \wedge r \rightarrow s \) \((p \vee (q \wedge r) \rightarrow s \) \(\rightarrow \) last
What happens when an expression contains two or more operators with the same precedence? The answer (by definition) is that the operations will be performed left to right.
So here are some more pairs of equivalent expressions:
\(p \wedge p \wedge r \) \((p \wedge q) \wedge r \) \(p \rightarrow q \rightarrow r \) \((p \rightarrow q) \rightarrow r \) \(p \rightarrow q \rightarrow r \wedge p \) \((p \rightarrow q) \rightarrow (r \wedge p) \)
In the case of logical expressions, the only way to have equal precedence operators is to have identical ones. (Note that this is true in the above examples.) And it turns out that all of our binary logical operators (∧, ∨, →, and ≡) are associative. In other words, we’ll get the same result however we associate them. We’ll prove this claim later. But if you can’t wait, go ahead and prove (by showing that they have identical truth tables), one of the cases:
\(((p \wedge q \wedge r ) \) is equivalent to \(( p \wedge ( q \wedge r ) ) \)
Exercises Exercises
1.
Which of the following is equivalent to: \(\neg p \vee q \rightarrow r \text{?}\)
\(\displaystyle \neg (p \vee q \rightarrow r) \)
\(\displaystyle \neg ( p \vee q) \rightarrow r \)
\(\displaystyle \neg p \vee ( q \rightarrow r ) \)
\(\displaystyle (( \neg p ) \vee q ) \rightarrow r \)
\(\displaystyle (\neg p ) \wedge ( q \rightarrow r ) \)
2.
Which of the following is equivalent to: \(q \rightarrow r \wedge p \vee s \text{?}\)
\(\displaystyle ( \rightarrow ( r \wedge p )) \vee s \)
\(\displaystyle q \rightarrow (( r \wedge p ) \vee s ) \)
\(\displaystyle q \rightarrow (r \wedge ( p \vee s ))\)
\(\displaystyle (q \rightarrow r) \wedge ( p \vee s)\)
\(\displaystyle ( (q \rightarrow r) \wedge p) \vee s \)