What Is Discrete Mathematics?

What is Discrete Mathematics? Discrete mathematics is the part of mathematics devoted tothe study of discrete (as opposed to continuous) objects. Examples of discrete objects: integers, steps taken by acomputer program, distinct paths to travel from point A topoint B on a map along a road network, ways to pick awinning set of numbers in a lottery. A course in discrete mathematics provides the mathematicalbackground needed for all subsequent courses in computerscience and for all subsequent courses in the many branchesof discrete mathematics. 2019 McGraw-Hill Education

Kinds of Problems Solved Using Discrete Mathematics1 How many ways can a password be chosen followingspecific rules? How many valid Internet addresses are there? What is the probability of winning a particularlottery? Is there a link between two computers in a network? How can I identify spam email messages? How can I encrypt a message so that no unintendedrecipient can read it? How can we build a circuit that adds two integers? 2019 McGraw-Hill Education

Kinds of Problems Solved Using Discrete Mathematics2 What is the shortest path between two cities using atransportation system? Find the shortest tour that visits each of a group of cities onlyonce and then ends in the starting city. How can we represent English sentences so that a computercan reason with them? How can we prove that there are infinitely many primenumbers? How can a list of integers be sorted so that the integers are inincreasing order? How many steps are required to do such a sorting? How can it be proved that a sorting algorithm always correctlysorts a list? 2019 McGraw-Hill Education

Goals of a Course in Discrete Mathematics 1 Mathematical Reasoning: Ability to read,understand, and construct mathematicalarguments and proofs. Combinatorial Analysis: Techniques forcounting objects of different kinds. Discrete Structures: Abstract mathematicalstructures that represent objects and therelationships between them. Examples aresets, permutations, relations, graphs, trees,and finite state machines. 2019 McGraw-Hill Education

Goals of a Course in Discrete Mathematics 2 Algorithmic Thinking: One way to solve many problems is tospecify an algorithm. An algorithm is a sequence of steps thatcan be followed to solve any instance of a particular problem.Algorithmic thinking involves specifying algorithms, analyzingthe memory and time required by an execution of thealgorithm, and verifying that the algorithm will produce thecorrect answer. Applications and Modeling: It is important to appreciate andunderstand the wide range of applications of the topics indiscrete mathematics and develop the ability to develop newmodels in various domains. Concepts from discretemathematics have not only been used to address problems incomputing, but have been applied to solve problems in manyareas such as chemistry, biology, linguistics, geography,business, etc. 2019 McGraw-Hill Education

Topics we will cover1. Math reasoning2. Combinatorial Analysis (counting)3. Discrete Structures4. Algorithmic Thinking5. Applications & Modeling 2019 McGraw-Hill Education

Discrete Mathematics is a Gateway Course Topics in discrete mathematics will be important inmany courses that you will take in the future:– Computer Science: Computer Architecture, DataStructures, Algorithms, Programming Languages,Compilers, Computer Security, Databases, ArtificialIntelligence, Networking, Graphics, Game Design, Theory ofComputation, – Mathematics: Logic, Set Theory, Probability, NumberTheory, Abstract Algebra, Combinatorics, Graph Theory,Game Theory, Network Optimization, The concepts learned will also be helpful in continuous areasof mathematics.– Other Disciplines: You may find concepts learned hereuseful in courses in philosophy, economics, linguistics, andother departments. 2019 McGraw-Hill Education

Propositional LogicSection 1.1 2019 McGraw-Hill Education

Section Summary1PropositionsConnectives Negation Conjunction Disjunction Implication; contrapositive, inverse, converse BiconditionalTruth Tables 2019 McGraw-Hill Education

PropositionsA proposition is a declarative sentence that is either true or false.Examples of propositions:a)b)c)d)e)The Moon is made of green cheese.Trenton is the capital of New Jersey.Toronto is the capital of Canada.1 0 10 0 2Examples that are not propositions.a)b)c)d)Sit down!What time is it?x 1 2x y z 2019 McGraw-Hill Education

Propositional LogicConstructing Propositions Propositional Variables: p, q, r, s, The proposition that is always true is denoted by T and theproposition that is always false is denoted by F. Compound Propositions; constructed from logical connectivesand other propositions Negation Conjunction Disjunction Implication Biconditional 2019 McGraw-Hill Education

Compound Propositions: NegationThe negation of a proposition p is denoted by p and has this truth table:pTF pFTExample: If p denotes “The earth is round.”, then p denotes “It is not the case that the earth isround,” or more simply “The earth is not round.” 2019 McGraw-Hill Education

ConjunctionThe conjunction of propositions p and q isdenoted by p q and has this truth table:pTTFFqTFTFP qTFFFExample: If p denotes “I am at home.” and qdenotes “It is raining.” then p q denotes “I amat home and it is raining.” 2019 McGraw-Hill Education

DisjunctionThe disjunction of propositions p and q isdenoted by p q and has this truth table:pTTFFqTFTFP qTTTFExample: If p denotes “I am at home.” and qdenotes “It is raining.” then p q denotes “I amat home or it is raining.” 2019 McGraw-Hill Education

The Connective Or in EnglishIn English “or” has two distinct meanings. “Inclusive Or” - In the sentence “Students who have taken CSE240 or Math310may take CSE247,” we assume that students need to have taken one of theprerequisites, but may have taken both. This is the meaning of disjunction. Forp q to be true, either one or both of p and q must be true. “Exclusive Or” - When reading the sentence “Soup or salad comes with thisentrée,” we do not expect to be able to get both soup and salad. This is themeaning of Exclusive Or (xor). In p q , one of p and q must be true, but notboth. The truth table for is: 2019 McGraw-Hill EducationpTqTP qFTFFTTTFFF

ImplicationIf p and q are propositions, then p q is a conditionalstatement or implication which is read as “if p, then q” and hasthis truth table:pqP qTTTFTFFFTFTTExample: If p denotes “I am at home.” and q denotes “It israining.” then p q denotes “If I am at home then it is raining.”In p q, p is the hypothesis (antecedent or premise) and q is theconclusion (or consequence). 2019 McGraw-Hill Education

Understanding Implication1In p q there does not need to be any connectionbetween the antecedent or the consequent. The“meaning” of p q depends only on the truth values ofp and q.These implications are perfectly fine, but would not beused in ordinary English. “If the moon is made of green cheese, then I have moremoney than Bill Gates. ” “If the moon is made of green cheese then I’m on welfare.” “If 1 1 3, then your grandma wears combat boots.” 2019 McGraw-Hill Education

Understanding Implication2One way to view the logical conditional is tothink of an obligation or contract. “If I am elected, then I will lower taxes.” “If you get 100% on the final, then you will get an A.”If the politician is elected and does not lowertaxes, then the voters can say that he or she hasbroken the campaign pledge. Something similarholds for the professor. This corresponds to thecase where p is true and q is false. 2019 McGraw-Hill Education

Different Ways of Expressing p qif p, then qp implies qif p, qp only if qq unless pq when pq if pq whenever pp is sufficient for qq follows from pq is necessary for pa necessary condition for p is qa sufficient condition for q is p 2019 McGraw-Hill Education

Discrete mathematics is the part of mathematics devoted to the study of discrete (as opposed to continuous) objects. Examples of discrete objects: integers, steps taken by a computer program, distinct paths to travel from point A to point B on a map along a road network, ways to pic