1.1: Compound Statements
In logic, we define operations on statements, which result in new statements, i.e. compound statements, much like in arithmetic where we have operations on numbers that result in a new number. We will see some of these logic operations in the next subunit.
1.1.1: The NOT, AND, OR, and XOR Symbols
Read Section 1 through the end of Section 1.1.1 on pages 1 - 3. This reading discusses logical symbols or operators that apply to propositions (the operands) to form a compound statement. A proposition is a statement that is either true (T) or false (F). Propositions are often denoted by single letters, for example, P or Q. The resulting truth or falseness of the compound statement is determined either using a truth table based on the truth or falseness of the operands or, as we will see later, by applying inference rules to prove that the compound statement is inferred from true statements.
Truth tables for operations - negation, conjunction, and disjunction -are derived from the definition of the operation, as seen in this reading.
Read Section 1: "Boolean Functions and Computer Arithmetic" up to example 6 on pages BF-1 to BF-4. Example 4 includes XOR. This reading presents material similar to Devadas and Lehman, but uses the language of Boolean functions. Throughout our study, we will see the relationship of English statements, logic, Boolean functions, and sets, and will learn how to translate between them to represent the same meaning. Exclusive OR is defined in example 4. Example5 discusses the relation of Boolean functions and logic.
XOR is the exclusive OR symbol. It differs from OR in that the resulting value is true if and only if exactly one of the operands is true. Thus, the result value in the truth table for XOR is false (F) for the row where each operand has the value true (T).
Truth tables for operations, such as exclusive OR, are derived from the definition of the operation, as seen in this reading.
1.1.2: Translating from English to Symbols
Read the beginning paragraphs in the Logic section up to Section 1, and then read Section 1.2 and Section 1.3 on pages 3 - 6.
This reading (and the following readings for this section) shows the relationship of natural language, in our case English, to the language of logic. Logic deals with simple statements, called propositions, that are either true or false, and operators - for example, NOT, AND, and OR - that combine propositions to form compound statements. Translating from English to logic involves analyzing English statements, i.e. parsing them, into elementary statements that can be expressed as propositions, connected by conjunctions, which usually can be expressed as logic operations. However, since natural languages are not always precise, we have to be careful to understand the semantics, or meaning, of an English statement and then express that same meaning using logic.
Read the beginning of Logic, "Section 1: Propositional Calculus," from pages Lo-1 to page Lo-3, up to the "Implication" paragraph. This reading also applies to Subunit 1.1.3 of this course.
These brief readings further introduce the use of logic in representing English or natural language statements, as well as for statements in mathematics. The translation discussion is continued in section 1.1.5 below.
Read this article for a brief summary and review of translating English to logic symbols.
1.1.3: Double Negative Property
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.
1.1.4: Negations of AND and OR: DeMorgan's Law
Study Theorem 2 (Algebraic rules for Boolean Functions) on pages BF-6 and BF-7.
Study Theorem 1 (Algebraic rules for statement forms) on page Lo-3.
A similar argument could be used to prove DeMorgan's law, which is very useful and widely used in communication, mathematics, engineering, and the sciences. Please make sure to familiarize yourself with DeMorgan's law before moving on to other sections of this course.
1.1.5: Tautologies and Contradictions
Study definition 1 (Tautology, contradiction) in Section 1 on pages Lo-2 and Lo-3. In Subunit 1.1.2 of this course, we introduced translation between English statements and logic. This reading, in addition to tautology and contradiction, adds to the translation story by discussing the relationship with set theory. Thus, you can translate from and to English, logic, and set symbols. The discussion of translation will continue when you study implication in the Subunit 1.2.1.