University of California, San Diego: Edward Bender and S. Williamson's "Arithmetic, Logic and Numbers: Boolean Functions and Computer Arithmetic"
Read example 3 on page BF-2 in Section 1: "Boolean Functions and Computer Arithmetic" of the Bender and Williamson reading.
We have seen that some statements in English can be translated to logic. We have also seen in the Bender and Williamson reading in 1.1.1, the equivalence of logic and Boolean functions. The term "equivalence" is used here in the context of equivalence of representations. The term "equivalence" in logic is used to mean that two propositions have the same truth value. Thus, the same word has two similar, yet different, meanings depending on the context in which it is used. Assignment of true to a proposition corresponds to a Boolean function that maps the proposition to 1. Assignment of false to a proposition corresponds to a Boolean function that maps the proposition to 0. The logic operators are translated to operations on Boolean functions.
NOT is a unary operator, meaning it has one operand. The other operators AND, OR, and XOR are binary operators, meaning they have two operands. "NOT P," as a Boolean function is written as, NOT (P), or ~P, where P is in the set {0,1}. As a unary logic operator, it is defined by the truth table referenced in subunit 1.1.1, and as a Boolean function it is defined in example 3 in Devadas and Lehman.
The truth table for NOT P, can be used to evaluate the truth or falseness of NOT (NOT P), which is T when P is T, and F when P is F. Thus, it has the same values as P. We say that NOT (NOT P) and P are equivalent as logic operators. Using Boolean functions, NOT (NOT (P)) is evaluated as follows: P is either 0 or 1. When P is 1, NOT (NOT (1)) = 1. When P is 0, NOT (NOT (0)) = 0. Thus, NOT (NOT) (P) = identity function.