CS202: Discrete Structures

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.
Completing this unit should take you approximately 9 hours.