[PDF] Discrete Mathematics Problems - University of North Florida PDF problems.pdf

This booklet consists of problem sets for a typical undergraduate discrete mathematics own, without the temptation of a solutions manual These problems On a multiple choice test with 100 questions and 5 answers per ques - tion, how

11 jui 2014 · Is the compound proposition in question 1 a tautology? Answer: No a b c d e f g

[PDF] free pdf version - Discrete Mathematics - An Open Introduction

2 jan 2019 · Before we can begin answering more complicated (and fun) problems, we must lay down some foundation We start by reviewing mathematical

[PDF] Discrete Mathematics Exam 1 Solutions

16 oct 2014 · (a) Count the number of possible ways to answer all the questions on that test Solution Each question has four possible answers so there are

[PDF] CS201A: Math for CS I/Discrete Mathematics - CSE - IIT Kanpur

23 nov 2017 · Answer all 8 questions It has 4 pages + 1 page for the standard normal distribution table 2 Please start each answer to a question on a fresh

[PDF] Discrete Mathematics Multiple Choice Questions With Answers

17 août 2017 · and answers pdf , discrete mathematics solved mcqs computer science solved, engineering mathematics multiple choice questions answers,

[PDF] Sample Exam Paper - University of Kent

Candidates may not attempt more than ONE question from each of the TWO questions in sections B and C MA 304 Discrete Mathematics – p 1/6 Page 2 MA304

[PDF] Discrete Structures Final exam sample questions - Cornell CS

Justify your answer Solution Alice transmits ak mod m to Bob, who then computes (ak)k−1 mod m Because Bob mis-

[PDF] Notes on Discrete Mathematics - Computer Science

31 déc 2020 · cs yale edu/homes/aspnes/classes/202/notes-2013 pdf xxi Introduction This is a course on discrete mathematics as used in Computer Science It's Answers to these questions are summarized by a probability, a number

[PDF] discrete mathematics springer pdf

[PDF] discrete time fourier series coefficients calculator

[PDF] discrete time fourier series matlab code

[PDF] discrete time fourier transform matlab code

[PDF] discriminant negatif racine complexe

[PDF] discriminant négatif solution complexe

[PDF] discuss physical evidence of service servicescape and ambiance

[PDF] discuss the characteristics of oral language

[PDF] disk cleanup windows 7 cmd

[PDF] disk cleanup windows 7 download

[PDF] disk cleanup windows 7 stuck

[PDF] disk cleanup windows 7 system files

[PDF] disk cleanup windows 7 takes forever

[PDF] disk cleanup windows 7 temporary files

[PDF] disk cleanup windows 7 windows update cleanup

[PDF] Discrete Mathematics Problems - University of North Florida

Discrete Mathematics Problems

William F. Klostermeyer

School of Computing

University of North Florida

Jacksonville, FL 32224

E-mail: wkloster@unf.edu

0 Preface3

1 Logic5

1.1 Basics . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5

1.2 Truth Tables and Logical Equivalences . . . . . . . . . . . . . 6

1.3 Quantifiers . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9

1.4 Circuits . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11

2 Sets13

3 Functions17

4 Integers and Matrices21

5 Proofs25

5.1 Direct Proofs . . . . . . . . . . . . . . . . . . . . . . . . . . . 25

5.2 Proofs by Contradiction . . . . . . . . . . . . . . . . . . . . . 26

5.3 Proofs by Induction . . . . . . . . . . . . . . . . . . . . . . . 27

6 Graphs31

6.1 Basic Problems . . . . . . . . . . . . . . . . . . . . . . . . . . 31

6.1.1 Graphs . . . . . . . . . . . . . . . . . . . . . . . . . . 31

6.1.2 Directed Graphs . . . . . . . . . . . . . . . . . . . . . 35

6.2 Problems Requiring Proofs . . . . . . . . . . . . . . . . . . . 35

7 Counting39

8 Other Topics47

8.1 Relations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 47

2CONTENTS

8.2 Algorithm Analysis . . . . . . . . . . . . . . . . . . . . . . . . 47

8.3 Recurrence Relations . . . . . . . . . . . . . . . . . . . . . . . 47

8.4 Generating Functions . . . . . . . . . . . . . . . . . . . . . . . 47

8.5 Boolean Algebra . . . . . . . . . . . . . . . . . . . . . . . . . 47

Chapter 0 Preface

This booklet consists of problem sets for a typical undergraduate discrete mathematics course aimed at computer science students. These problem may be used to supplement those in the course textbook. We felt that in order to become proficient, students need to solve many problems on their own, without the temptation of a solutions manual! These problems have been collected from a variety of sources (including the authors themselves), including a few problems from some of the texts cited in the references.

Difficult problems are marked with a•.

References to the bibliography are indicated by [x], where x is the num- ber of a bibliography entry. 3

4CHAPTER 0. PREFACE

Chapter 1

Logic

1.1 Basics

Evaluate each of the following.

If 2 is even, then 5=6.

If 2 is odd, then 5=6.

If 4 is even, then 10 = 7+3.

If 4 is odd, then 10= 7+3.

In the following, assume thatpis true,qis false, andris true. 5. p∨q∨r(you may want to add parentheses!) 6.

¬q∧p

7. p→(q∨p) 5

6CHAPTER 1. LOGIC

8. q⊕p 9. r⊕p 10. q→ ¬p 11. (q∧p)∨(q∨(r∧p))

1.2 Truth Tables and Logical Equivalences

Give truth tables for each of the following:

1. p∨q∧r 2.

¬p→q

3. (p∨q)⊕p 4. (p∧q)∨(q→p) 5. (p→q)→ ¬q 6. (p∨q)→(q∧ ¬p) 7. (p∧q)∨ ¬r 8. (p↔ ¬q)→p

1.2. TRUTH TABLES AND LOGICAL EQUIVALENCES7

9. (p∨q)↔(p∧q)

Which of the following are tautologies?

10. (p∨ ¬p)⊕p 11. (p∧q)∨(¬p∧ ¬q) 12. (p→ ¬p)→ ¬q 13. (p∨q)⊕(¬p∧ ¬q) Prove or disprove each of the following using (a) truth tables and (b) the rules of logic. 14. (p∧q)→(p∨q)⇔True 15.

¬(p∧q)∨q⇔True

16. [2] (p∧(p→q))→q⇔True 17. p→q⇔ ¬q→ ¬p 18.

¬(¬p∧q)∨q⇔p∨q

19.

¬(¬p∧q)∨q⇔q→p

20. p∧(q∨r)⇔p∨(q∧r) 21.
p∧(q∨r)⇔p∧(q∧r)

8CHAPTER 1. LOGIC

22.
(p∧ ¬(q∧ ¬r))∨(p∧q)⇔r 23.
p→(p∨q)⇔True Re-write the following using only¬;∧;∨ 24.
p→(q∨r) 25.
p⊕(q→r) 26.

¬q→ ¬(p→q)

Re-write the following CNF formulae into DNF

27.
(p∨q∨r)∧(¬p∨q) 28.
(p∨q∨r)∧(¬p∨q∨ ¬r)∧(p∨ ¬q)

Use truth tables to verify the following:

29.
[2] (p∨(p∧q))⇔p 30.
[2] (p∧(p∨q))⇔p 31.
•Show that (p∨q∨r∨s) can be re-written into an equivalent CNF formula such that each clause contains exactly 3 variables or negations of variables. 32.
Show that p→not (not q and not p) is logically equivalent to True.

1.3. QUANTIFIERS9

1.3 Quantiers

Evaluate each of the following for the universeZ, the set of integers 1.

P(2), whereP(x) =x≤10

P(4) whereP(x) = (x= 1)∨(x >5)

P(x) whereP(x) = (x <0)∧(x̸= 23)

4. ∃x(x= 5)∧(x= 6) 5. ∃x(x= 5)∧(x≤5) 6. ∀x(x= 5)∧(x≤5) 7. ∀x(x <0)∨(x≤2x)quotesdbs_dbs2.pdfusesText_2

[PDF] [PDF] Discrete Mathematics Problems - University of North Florida