Logic and Discrete Mathematics E-Book

Willem Conradie

• Herausgeber: John Wiley & Sons
• Kategorie: Wissenschaft und neue Technologien
• Sprache: Englisch

Seitenzahl: 219

Veröffentlichungsjahr: 2015

Beschreibung

Solutions manual to accompany Logic and Discrete Mathematics: A Concise Introduction

This book features a unique combination of comprehensive coverage of logic with a solid exposition of the most important fields of discrete mathematics, presenting material that has been tested and refined by the authors in university courses taught over more than a decade.

Written in a clear and reader-friendly style, each section ends with an extensive set of exercises, most of them provided with complete solutions which are available in this accompanying solutions manual.

Leseprobe

Table of Contents

Cover

Title Page

Copyright

Preface

About the Companion Website

Chapter 1: Preliminaries

1.1 Sets

1.2 Basics of Logical Connectives and Expressions

1.3 Mathematical Induction

Chapter 2: Sets, Relations, Orders

2.1 Set Inclusions and Equalities

2.2 Functions

2.3 Binary Relations and Operations on Them

2.4 Special Binary Relations

2.5 Equivalence Relations and Partitions

2.6 Ordered Sets

2.7 An Introduction to Cardinality

2.8 Isomorphisms of Ordered Sets. Ordinal Numbers

2.9 Application: relational databases

Chapter 3: Propositional Logic

3.1 Propositions, Logical Connectives, Truth Tables, Tautologies

3.2 Propositional Logical Consequence. Valid and Invalid Propositional Inferences

3.3 Semantic Tableaux

3.4 Logical Equivalences. Negating Propositional Formulae

3.5 Normal forms. Propositional Resolution

Chapter 4: First-Order Logic

4.1 Basic Concepts of First-Order Logic

4.2 The Formal Semantics of First-Order Logic

4.3 The Language of First-Order Logic: A Deeper Look

4.4 Truth, Logical Validity, Equivalence and Consequence in First-Order Logic

4.5 Semantic Tableaux for First-Order Logic

4.6 Prenex and Clausal Normal Forms

4.7 Resolution in First-Order Logic

4.8 Applications of First-Order Logic to Mathematical Reasoning and Proofs

Chapter 5: Number Theory

5.1 The Principle of Mathematical Induction revisited

5.2 Divisibility

5.3 Computing Greatest Common Divisors. Least Common Multiples

5.4 Prime Numbers. The Fundamental Theorem of Arithmetic

5.5 Congruence Relations

5.6 Equivalence Classes and Residue Systems Modulo

5.7 Linear Diophantine Equations and Linear Congruences

5.8 Chinese Remainder Theorem

5.9 Euler's Function. Theorems of Euler and Fermat

5.10 Wilson's Theorem. Order of an Integer

5.11 Application: Public Key Cryptography

Chapter 6: Combinatorics

6.1 Two Basic Counting Principles

6.2 Combinations. The Binomial Theorem

6.3 The Principle of Inclusion – Exclusion

6.4 The Pigeonhole Principle

6.5 Generalized Permutations, Distributions and the Multinomial Theorem

6.6 Selections and Arrangements with Repetition; Distributions of Identical Objects

6.7 Recurrence Relations and Their Solution

6.8 Generating Functions

6.9 Recurrence Relations and Generating Functions

6.10 Application: Classical Discrete Probability

Chapter 7: Graph Theory

7.1 Introduction to Graphs and Digraphs

7.2 Incidence and Adjacency Matrices

7.3 Weighted Graphs and Path Algorithms

7.4 Trees

7.5 Eulerian Graphs and Hamiltonian Graphs

7.6 Planar Graphs

7.7 Graph Colourings

End User License Agreement

Pages

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

33

34

35

36

37

38

39

40

41

42

43

44

45

46

47

48

49

50

51

52

53

54

55

56

57

58

59

60

61

62

63

64

65

66

67

68

69

70

71

72

73

74

75

76

77

78

79

80

81

82

83

84

85

86

87

88

89

90

91

92

93

94

95

96

97

98

99

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

129

130

131

132

133

134

135

136

137

138

139

140

141

142

143

144

145

146

147

148

149

150

151

152

153

154

155

156

157

158

159

160

161

162

163

164

165

166

167

168

169

170

171

172

173

174

175

176

177

178

179

180

181

182

183

184

Guide

Cover

Table of Contents

Preface

Begin Reading

List of Tables

Chapter 2: Sets, Relations, Orders

Table 2.1

Table 2.2

Table 2.3

Table 2.4

Table 2.5

Table 2.6

Table 2.7

Table 2.8

Table 2.9

Chapter 7: Graph Theory

Table 7.1 Exercise 1(a)

Table 7.2 Exercise 1(b)

Table 7.3 Exercise 4(a)

Table 7.4 Exercise 4(b)

Logic and Discrete Mathematics

A Concise Introduction, Solutions Manual

Willem Conradie

University of Johannesburg, South Africa

Valentin Goranko

Stockholm University, Sweden

Claudette Robinson

University of Johannesburg, South Africa

This edition first published 2015

© 2015 John Wiley and Sons Ltd

Registered office

John Wiley & Sons Ltd, The Atrium, Southern Gate, Chichester, West Sussex, PO19 8SQ, United Kingdom

For details of our global editorial offices, for customer services and for information about how to apply for permission to reuse the copyright material in this book please see our website at www.wiley.com.

The right of the author to be identified as the author of this work has been asserted in accordance with the Copyright, Designs and Patents Act 1988.

All rights reserved. No part of this publication may be reproduced, stored in a retrieval system, or transmitted, in any form or by any means, electronic, mechanical, photocopying, recording or otherwise, except as permitted by the UK Copyright, Designs and Patents Act 1988, without the prior permission of the publisher.

Wiley also publishes its books in a variety of electronic formats. Some content that appears in print may not be available in electronic books.

Limit of Liability/Disclaimer of Warranty: While the publisher and author have used their best efforts in preparing this book, they make no representations or warranties with respect to the accuracy or completeness of the contents of this book and specifically disclaim any implied warranties of merchantability or fitness for a particular purpose. It is sold on the understanding that the publisher is not engaged in rendering professional services and neither the publisher nor the author shall be liable for damages arising herefrom. If professional advice or other expert assistance is required, the services of a competent professional should be sought

Library of Congress Cataloging-in-Publication Data

A catalogue record for this book is available from the British Library.

ISBN: 9781118762677

Preface

This manual contains answers and solutions to roughly three quarters of the exercises in Logic and Discrete Mathematics: A Concise Introduction by Willem Conradie and Valentin Goranko. Most solutions are worked out in full detail. In deciding which solutions to include we were guided by two principles: fundamental exercises were given preference above the more esoteric ones intended mainly for enrichment; where a number of very similar exercises occur in succession, complete solutions were given for a few while the others were omitted or provided with answers only. We trust that these solutions will be a very valuable resource to students and instructors using Logic and Discrete Mathematics.

About the Companion Website

This book is accompanied by a companion website:

www.wiley.com/go/conradie/logic

The website includes:

• Lecture Slides

• Quizzes