## Discrete Structures

Search:

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 (i.e. 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.

1.1 Compound Statements

Note: 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

1.1.2 Translating from English to Symbols

1.1.3 Double Negative Property

1.1.4 Negations of AND and OR: DeMorgan’s Law

1.1.5 Tautologies and Contradictions

1.2 Conditional Statements

Note: 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, i.e. 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

1.2.2 Negation of a Conditional Statement

Note: Conditional English sentences can be difficult to interpret, particularly when they are negated. Logic helps us to correctly interpret such statements. This topic, negation of a conditional statement, is addressed in the reading on implication in Subunit 1.2.1.

1.2.3 Contrapositive of a Conditional Statement

Note: Given a conditional statement, we can derive several new statements from it by inserting negation and/or inverting the antecedent and consequent. For example, from P implies Q, we can derive NOT Q implies NOT P. These two statements, namely the implication, P implies Q, and the derived statement are logically equivalent. This derivation is called the contrapositive of the implication. Contrapositive is discussed in the Bender and Williamson reading in Subunit 1.2.1.

1.2.4 Converse and Inverse of a Conditional Statement

Note: In addition to negation of a conditional statement and contrapositive, two other common derivations from a conditional statement are the converse and inverse. These are discussed in the readings for Subunit 1.2.1.

1.2.5 If and Only If, Necessary and Sufficient Conditions

1.2.6 Proving Validity or Invalidity of an Argument Using Truth Tables

1.3 Modus Ponens and Modus Tollens

Note: 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, which we will study in the next subunits.

1.3.1 Rules of Inference

Unit 2: The Logic of Quantified Statements In the previous unit, we discussed the logical analysis of compound statements, including those comprised of simple statements joined by OR, AND, NOT, etc. operators. This analysis provides us with a better understanding of human reasoning, but cannot be used to determine the validity of the majority of mathematical situations. In some cases, it becomes necessary to separate statements into parts, just as we parse sentences in order to facilitate comprehension. In this unit, we will learn to analyze and understand the special roles that keywords and predicates (i.e. for all and some) play − exercises that constitute the foundation of predicate calculus.

BLOG COMMENTS POWERED BY DISQUS