### Unit 1: The Logic of Compound Statements

Great thinkers have studied logic since the time of the Greek philosopher Aristotle; its rules serve as the basis for the study of every branch of knowledge − including (and perhaps especially) computer science. Logic is an abstraction and formalization of reasoning we use every day, in mathematics, science, and, in particular, computer science. Logic deals with logical systems consisting of symbols that represent statements that are either true or false, definitions of operations for combining statements (for example, addition is an operation in arithmetic for combining numbers), rules for manipulating statement and operator symbols, and rules for inferring new statements from given statements. In Unit 1 and Unit 2, we will study two logical systems: the propositional calculus and the first order predicate calculus.

The following guidance will help you get started in our study of logic in discrete structures. The definitions and rules are called axioms or postulates (we use these terms synonymously). We use axioms and known true statements to prove the truth or falseness of theorems. A theorem is a statement that has a hypothesis (assumptions) and a conclusion. Much of our work will involve proving theorems. You may notice that several different notations are used in logic, depending on the author, text, or reference. In this course, we use several different notations so that you are introduced to these differences.

Logic is an extensive field of study and selected topics are included in discrete structures. These topics vary depending on the institution or school, course, instructor, and text. To expose you to some of the variation, we use two main resources, as well as include supplementary resources and our own original content. In this unit, we will examine various rules of logic (such as negations, conjunctions, and disjunctions) in order to determine how they can create conditional statements, arguments, and rules but also prove the truthfulness or falseness of any argument, whether presented in mathematical terms or in everyday language.

Note: Discrete structures is the term used for discrete mathematics for computer science. Discrete mathematics is often referred to as finite mathematics.

**Completing this unit should take you approximately 9 hours.**

Upon successful completion of this unit, you will be able to:

- define propositions and the logic operators: NOT, AND, OR, and XOR;
- calculate truthfulness or falseness of compound propositions using truth tables;
- transform compound propositions using DeMorgan's Law and other identities;
- define tautology and contradiction; and
- apply rules of inference.

### 1.1: Compound Statements

In logic, we define operations on statements, which result in new statements (that is, 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 section 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 this section explains.

Read Section 1, "Boolean Functions and Computer Arithmetic", up to example 6 on pages BF-1 to BF-4. Example 4 includes XOR. This section 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. Example 5 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 here.

### 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 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 (that is, 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. These further introduce the use of logic in representing English or natural language statements, as well as for statements in mathematics.

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".

We have seen that some statements in English can be translated to logic. We have also seen 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. 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. Earlier, we introduced translation between English statements and logic. This section, in addition to tautology and contradiction, adds to the translation story by discussing the relationship with set theory. Thus, you can translate to and from English, logic, and set symbols.

### 1.2: Conditional Statements

As you have likely noticed there is a similarity between the language of logic and a natural language, such as English. In fact, there is a similarity between implication in logic and the conditional statement in English, an if statement. In the follow subsections, we will study the application of operations to the logical if statement.

### 1.2.1: Logical Equivalences Using Conditional Statements

Read Section 1.1.2 and Section 1.1.3 on pages 4 and 5. The conditional statement in English can be translated to implication in logic.

Read the section titled "Implication" up to the exercises on pages Lo-4 to Lo-9. Example 3 also covers the Negation of a Conditional Statement, the Contrapositive of a Conditional Statement, and the Converse and Inverse of a Conditional Statement.

### 1.2.2: If and Only If, Necessary and Sufficient Conditions

Read example 5 on pages Lo-7 to Lo-8. In the statement "A if and only if B", abbreviated A iff B, A is called the necessary part and B the sufficient part.

### 1.2.3: Proving Validity or Invalidity of an Argument Using Truth Tables

Read Section 1.2 on pages 5 and 6 and 1.4 on pages 6–8 to learn about logical equivalence of statements. The term validity refers to an argument or proof. We say an argument is valid if its conclusion logically follows from its premises. We can do this by showing that a statement is logically equivalent to a premise, or by showing that a statement logically follows from a premise. Logically follows from, or is a consequence of, means that the conclusion is true if the premise is true.

Read example 7 on pages BF-7 and BF-8. This is an example where a given expression is transformed into a logically equivalent expression, which, in turn, is translated into another equivalent express, and so on.

Read this article.

### 1.3: Modus Ponens and Modus Tollens

A proof, or an argument, is a series of statements where each statement logically follows from the previous one(s). Logically follows means that there is a logic rule of inference that derives it from the previous statement(s). One famous rule of inference is modus ponens.

Read over the text from Wikipedia on rules of inference. Rules of inference are used to show that one statement is a consequence of another statement and, thus, are used for constructing proofs. The summary table is located before the truth table and the examples. The Rules of Inference are referred to by names in the 3rd column in the table. In this course, alternate names are also used. Those that have corresponding alternate names are listed in the following table:

**Wikipedia Name****Alternate Name**Disjunction

Generalization

Conjunction

Specialization

Elimination

Generalization

Modus Ponens

Modus Tollens

Hypothetical Syllogism

Transitivity

Disjunctive Syllogism

Disjunctive Elimination

Resolution

Elimination

Read Section 1, "The Axiomatic Method", up to Section 3 on pages 3–7. Reading Section 3 on pages 7–9 is optional.

Review example 4 (Right Triangles and the Pythagorean theorem) on pages Lo-6 to Lo-7. It illustrates some of the rules of inference.

Read this summary of Modus Ponens and other types of reasoning.

### Unit 1 Assessment

Take this assessment to see how well you understood this unit.

- This assessment
**does not count towards your grade**. It is just for practice! - You will see the correct answers when you submit your answers. Use this to help you study for the final exam!
- You can take this assessment as many times as you want, whenever you want.

- This assessment