Discrete Mathematics and Its Applications¶
Preface¶
The book is designed not only to be a successful textbook, but also to serve as a valuable resource students can consult throughout their studies and professional life.
Goals of a Discrete Mathematics Course¶
This text stresses mathematical reasoning and the different ways problems are solved. Five important themes are interwoven in this text:
- Mathematical Reasoning: Students must understand mathematical reasoning in order to read, comprehend, and construct mathematical arguments. This text starts with a discussion of mathematical logic, which serves as the foundation for the subsequent discussions of methods of proof. Both the science and the art of constructing proofs are addressed. The technique of mathematical induction is stressed through many different types of examples of such proofs and a careful explanation of why mathematical induction is a valid proof technique.
- Combinatorial Analysis: An important problem-solving skill is the ability to count or enumerate objects. The discussion of enumeration in this book begins with the basic techniques of counting. The stress is on performing combinatorial analysis to solve counting problems and analyze algorithms, not on applying formulae.
- Discrete Structures: A course in discrete mathematics should teach students how to work with discrete structures, which are the abstract mathematical structures used to represent discrete objects and relationships between these objects.
- Algorithmic Thinking: Certain classes of problems are solved by the specification of an algorithm. After an algorithm has been described, a computer program can be constructed implementing it. The mathematical portions of this activity, which include the specification of the algorithm, the verification that it works properly, and the analysis of the computer memory and time required to perform it, are all covered in this text. Algorithms are described using both English and an easily understood form of pseudocode.
- Applications and Modeling: Discrete mathematics has applications to almost every conceivable area of study. Modeling with discrete mathematics is an extremely important problem-solving skill, which students have the opportunity to develop by constructing their own models in some of the exercises.
Chapter 1： The Foundations: Logic and Proofs¶
1.1 Propositional Logic¶
A proposition is a declarative sentence (that is, a sentence that declares a fact) that is either true or false, but not both.
We use letters to denote propositional variables (or sentential variables), that is, variables that represent propositions, just as letters are used to denote numerical variables. The conventional letters used for propositional variables are p, q, r, s, … . The truth value of a proposition is true, denoted by T, if it is a true proposition, and the truth value of a proposition is false, denoted by F, if it is a false proposition. Propositions that cannot be expressed in terms of simpler propositions are called atomic propositions.
The area of logic that deals with propositions is called the propositional calculus or propositional logic.
Many mathematical statements are constructed by combining one or more propositions. New propositions, called compound propositions, are formed from existing propositions using logical operators.
Definition 1
Let \(p\) be a proposition. The negation of \(p\), denoted by \(¬p\) (also denoted by \(p\)), is the statement “It is not the case that \(p\).”
The proposition \(¬p\) is read “not \(p\).” The truth value of the negation of \(p\), \(¬p\), is the opposite of the truth value of \(p\).
The negation of a proposition can also be considered the result of the operation of the negation operator on a proposition. The negation operator constructs a new proposition from a single existing proposition. We will now introduce the logical operators that are used to form new propositions from two or more existing propositions. These logical operators are also called connectives.
The use of the connective or in a disjunction corresponds to one of the two ways the word or is used in English, namely, as an inclusive or. A disjunction is true when at least one of the two propositions is true. That is, \(p ∨ q\) is true when both p and q are true or when exactly one of p and q is true.