Discrete Mathematics and Combinatorics

Chapter 3

Logic

Learning Objectives

On completing this chapter, you should be able to:

• identify statements

• assign truth values to complex statements obtained by combining atomic statements with the help of logical connectives

• identify tautologies and contradictions

• write down the normal forms of given statements

• prove or disprove the validity of logical implications by the methods of truth table, inference theory or automatic theorem proving

• identify statement functions

• formulate statements using quantifiers in addition to logical connectives

• prove or disprove the validity of logical implications of predicate calculus by the method of inference theory

Imagine a child returning home from school. She finds a pair of slippers on the door step, ...