1.1.3: Precedence rules
- Page ID
These operators can be used in more complicated expressions, such as p ∧ ¬q or (p ∨q) ∧ (q ∨ r). A proposition made up of simpler propositions and logical operators is called a compound proposition. Just like in mathematics, parentheses can be used in compound expressions to indicate the order in which the operators are to be evaluated. In the absence of parentheses, the order of evaluation is determined by precedence rules. For the logical operators defined above, the rules are that ¬ has higher precedence than∧, and ∧ has precedence over ∨. This means that in the absence of parentheses, any ¬operators are evaluated first, followed by any ∧ operators, followed by any ∨ operators.
For example, the expression ¬p ∨ q ∧ r is equivalent to the expression (¬p) ∨ (q ∧ r), while p ∨ q ∧ q ∨ r is equivalent to p ∨ (q ∧ q) ∨ r.
This still leaves open the question of which of the ∧ operators in the expression p ∧q ∧ r is evaluated first. This is settled by the following rule: When several operators of equal precedence occur in the absence of parentheses, they are evaluated from left to right. Thus, the expression p ∧ q ∧ r is equivalent to (p ∧ q) ∧ r rather than to p ∧ (q ∧ r). In this particular case, as a matter of fact, it doesn’t really matter which ∧ operator is evaluated first, since the two compound propositions (p ∧ q) ∧ r and p ∧ (q ∧ r) always have the same value, no matter what logical values the component propositions p, q, and r have. We say that ∧ is an associative operation. We’ll see more about associativity and other properties of operations in the next section.
In practice however you should always add parentheses in places where ambiguity may arise. In fact some text books even add them to single operators as well, e.g., writing (p ∧ q) instead of p ∧ q. Although for this course we do not require them around single operators, we should never need the precedence rules outlined above. Your parentheses should make clear the order of operations!
Every compound proposition has a main connective. The main connective is the con- nective that is evaluated last, according to the precedence rules and parentheses. There should be no ambiguity over which is the main connective in a compound proposition.