Consider the statement \(F \wedge T \vee T\). If we compute the \(\wedge\) first, we get \[F \wedge T \vee T = F \vee T = T\] If we compute the \(\vee\) first, we get \[F \wedge T \vee T = F \wedge T = F\] So, what is the value of \(F \wedge T \vee T\)? It isn't well defined!
For mathematicians to make clear statements, they need to agree on an order of operations. The first operation to be performed is always \(\neg\). So, \[T \vee \neg T = T \vee F = T\] Notice the \(\neg\) is computed before the \(\vee\).
The \(\wedge, \vee\), and \(\oplus\) operations are on the same level of order of operation.
We use parentheses to impose an order of operations. For example, \(\neg T \wedge F = F \wedge F = F,\) but if we want the negation to be the last operation, we do \(\neg(T \wedge F) = \neg F = T.\) Similarly, we can use parentheses to tell which of \(\wedge\) or \(\vee\) should be computed first: \[(F \wedge T) \vee T = F \vee T = T\] \[F \wedge (T \vee T) = F \wedge T = F\]
However, not only can you use parentheses, but you must! The original statement, \(F \wedge T \vee T\), is logically ambiguous. It could be true or false. We need to have parentheses to tell us which operation should be computed first.
The order of operations on \(\neg, \vee, \wedge,\) and \(\oplus\) is \(\neg\) first. The rest come second. Parentheses are needed to indicate the order between \(\vee, \wedge,\) and \(\oplus.\)
Now that we have defined operations and decided the order in which to perform them, we should study their properties.
Negation is the only unary operator, which means it takes one input. Performing negation twice will cancel the negation.
Claim: For any statement \(P\), \(\neg\neg P = P.\)
This claim and the following claims can be verfied by plugging in values. For this claim, \[\neg\neg T = \neg F = T\] \[\neg\neg F = \neg T = F\] That is everything there is to check.
The operations \(\wedge, \vee,\) and \(\oplus\) are commutative and associative. As an example, we state explicitly what this means for \(\wedge.\)
The operation \(\vee\) distributes over \(\wedge\), and the operation \(\wedge\) distributed over \(\vee.\) For any statements \(P,\) \(Q,\) and \(R,\) \[P \vee (Q \wedge R) = (P \vee Q) \wedge (P \vee R)\] \[P \wedge (Q \vee R) = (P \wedge Q) \vee (P \wedge R)\] We will check the distributivity of \(\vee\) over \(\wedge\) with truth tables.
De Morgan's Laws are about the interactions of \(\neg, \wedge\), and \(\vee.\) \[\neg (P \wedge Q) = \neg P \vee \neg Q\] \[\neg (P \vee Q) = \neg P \wedge \neg Q\]
Let's consider an example of \(\neg (P \vee Q) = \neg P \wedge \neg Q\) in the form of an English statement. Let \(P\) be the statement "I want green beans" and \(Q\) be the statement "I want lima beans."
\(\neg (P \vee Q) := \) "I do not want green beans or lima beans."
\(\neg P \wedge \neg Q := \) "I do not want green beans and I do not want lima beans."
Both statements mean the same thing.
The statement \(\neg P \vee \neg Q\) means something different.
\(\neg P \vee \neg Q :=\) "I do not want green beans or I do not want lima beans."
This shows that when analyzing language, \(\neg (P \wedge Q) \neq \neg P \wedge \neg Q.\)
So, remember to flip the \(\wedge\).
Go here to see how the operations and, or, and not are very similar to the operations union, intersect, and complement on sets.