Order of Operations

In lesson 1.3, we established that the first operation is \(\neg,\) and that \(\wedge, \vee,\) and \(\oplus\) are on the same level of operation. The \(\rightarrow\) and \(\leftrightarrow\) operations come last. The two conditional operations are on the same level.

As an example, when computing \(T \vee F \rightarrow \neg T\), the first operation is \(\neg T.\) \[T \vee F \rightarrow \neg T = T \vee F \rightarrow F\] Next comes \(\vee\) in the order of operations, so the next step is \[T \vee F \rightarrow F = T \rightarrow F\] Last, evaluate the \(\rightarrow\) operation. \[T \rightarrow F = F\]

Basic Properties

Any statement implies itself, and any statement is equivalent to itself, so for any statement \(P\), \[P \rightarrow P = T\] \[P \leftrightarrow P = T\]

If, and only if, is commutative: For any statements \(P\) and \(Q\), \(P \leftrightarrow Q = Q \leftrightarrow P.\)

Implies is not commutative. For example, \(T \rightarrow F \neq F \rightarrow T\) since \(T \rightarrow F = F\) and \(F \rightarrow T = T.\)

Neither \(\rightarrow\) nor \(\leftrightarrow\) are associative. You need to use parentheses in order to say which operation comes first, even among a statement that only has \(\rightarrow\) or only has \(\leftrightarrow\) operations.

For example, the statement \(F \rightarrow T \rightarrow F\) is not well defined without parentheses. \[(F \rightarrow T) \rightarrow F = T \rightarrow F = F\] \[F \rightarrow (T \rightarrow F) = F \rightarrow F = T\]

Combining \(\neg, \wedge, \vee, \oplus, \rightarrow,\) and \(\leftrightarrow\)

Claim: For any statements \(P\) and \(Q,\) \(P \rightarrow Q = \neg P \vee Q.\)

This claim can be verified with a truth table.

Claim: For any statements \(P\) and \(Q,\) \(P \leftrightarrow Q = (P \rightarrow Q) \wedge (Q \rightarrow P).\)

This claim can be verified with a truth table.

Contrapositive The statement "If \(P\) then \(Q\)" is equivalent to the statement "If not \(Q\), then not \(P\)." It is important to note that "If \(P\) then \(Q\)" is not equivalent to "If \(Q\) then \(P\)," which is a common fallacy.

To show this is true, let's first convert the English completely into logic. What we have is the following:
Claim: For any statements \(P\) and \(Q,\) \(P \rightarrow Q = \neg Q \rightarrow \neg P.\)

This claim could be verified with another truth table, but truth tables will soon get large and tiresome. We can also perform algebraic computations with the rules we have already established. \begin{align} P \rightarrow Q & = \neg P \vee Q \\ & = \neg P \vee \neg \neg Q \\ & = \neg \neg Q \vee \neg P \\ & = \neg Q \rightarrow \neg P \end{align} The first was shown with a truth table at the beginning of this chalkboard. The second line follows from \(Q = \neg \neg Q.\) The third line uses the commutativity of \(\vee,\) and the fourth line uses the same property as line 1 except with \(\neg Q\) in place of \(P\) and \(\neg P\) in place of \(Q:\) \(\neg Q \rightarrow \neg P = \neg \neg Q \vee \neg P.\)

Transitivity If and only if, \(\leftrightarrow,\) is transitive. In other words, if \(P \leftrightarrow Q\) and \(Q \leftrightarrow R,\) then \(P \leftrightarrow R.\)

To break down the English into logic, we get the following:
Claim: For any statements \(P,\) \(Q,\) and \(R,\) \(((P \leftrightarrow Q) \wedge (Q \leftrightarrow R)) \rightarrow (P \leftrightarrow R).\)

It can be shown that this is always true with a truth table or verified algebraically, but either method is more than we want to show here.

We will verify one more claim to give another example of using our rules to compute algebraically.

Claim: \(P \wedge Q \rightarrow R = (P \rightarrow R) \vee (Q \rightarrow R)\)

Before we show the claim, we will point out that for any statement \(P,\) \[P = P \vee P.\] This fact will be used in the derivation below. You can check by plugging in both possible values for \(P:\) \[T = T \vee T\] \[F = F \vee F\]

The claim can be directly computed. \begin{align} P \wedge Q \rightarrow R & = \neg (P \wedge Q) \vee R \\ & = (\neg P \vee \neg Q) \vee R \\ & = (\neg P \vee \neg Q) \vee (R \vee R) \\ & = \neg P \vee \neg Q \vee R \vee R \\ & = \neg P \vee R \vee \neg Q \vee R \\ & = (P \rightarrow R) \vee (Q \rightarrow R) \end{align} The first line replaces \(P \wedge Q\) implies \(R\) with not \(P \wedge Q\) or \(R.\)
The second line uses De Morgan's law to pass the negation through the parentheses.
The third line uses the fact that \(R \vee R = R.\)
In the fourth line, the parentheses are dropped. This can be done because \(\vee\) is associative, so we can compute in any order.
The fifth line rearranges the statements. This can be done because \(\vee\) is commutative.
The last line uses the facts that \(P \rightarrow R = \neg P \vee R\) and \(Q \rightarrow R = \neg Q \vee R.\)

Related Lessons