Glossary
230
Review Questions
231
Exercises
231
Short Questions and Answers
232
Chapter 7 Complexity Theory
235
7.1 Introduction
235
7.2 Polynomial-Time Algorithms
236
7.3 Non-deterministic Polynomial Time Algorithms
237
7.4 Integer Bin Packing
237
7.5 Boolean Satisfiability
238
7.6 Additional NP Problems
239
7.7 NP-Complete Problems
239
Glossary
240
Review Questions
240
Exercises
241
Short Questions and Answers
242
Chapter 8 Propositions and Predicates
245
8.1 Propositions
245
8.1.1 Connectives
246
8.1.2 Tautology, Contradiction and Contingency
255
8.1.3 Logical Identities
258
8.2 Logical Inference
265
8.3 Predicates and Quantifiers
276
8.4 Quantifiers and Logical Operators
281
8.5 Normal Forms
289
Glossary
292
Review Questions
293
Exercises
294
Short Questions and Answers
299
Answers to Exercises
304
University Question Papers
320
Bibliography
341
Index
343
Contents
xiii