In lesson 1.3, we established that the first operation is and that and are on the same level of operation. The and operations come last. The two conditional operations are on the same level.
As an example, when computing , the first operation is Next comes in the order of operations, so the next step is Last, evaluate the operation.
Any statement implies itself, and any statement is equivalent to itself, so for any statement ,
If, and only if, is commutative: For any statements and ,
Implies is not commutative. For example, since and
Neither nor are associative. You need to use parentheses in order to say which operation comes first, even among a statement that only has or only has operations.
For example, the statement is not well defined without parentheses.
Claim: For any statements and
This claim can be verified with a truth table.
Claim: For any statements and
This claim can be verified with a truth table.
Contrapositive The statement "If then " is equivalent to the statement "If not , then not ." It is important to note that "If then " is not equivalent to "If then ," 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 and
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. The first was shown with a truth table at the beginning of this chalkboard. The second line follows from The third line uses the commutativity of and the fourth line uses the same property as line 1 except with in place of and in place of
Transitivity If and only if, is transitive. In other words, if and then
To break down the English into logic, we get the following:
Claim: For any statements and
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:
Before we show the claim, we will point out that for any statement This fact will be used in the derivation below. You can check by plugging in both possible values for
The claim can be directly computed.
The first line replaces implies with not or
The second line uses De Morgan's law to pass the negation through the parentheses.
The third line uses the fact that
In the fourth line, the parentheses are dropped. This can be done because is associative, so we can compute in any order.
The fifth line rearranges the statements. This can be done because is commutative.
The last line uses the facts that and
T
T