DISCRETE MATHEMATICS AND ITS APPLICATIONS by Kenneth H. Rosen

Chapter 1 -- The Foundations: Logic and Proof, Sets, and Functions

1.1 Logic

A proposition is a statement that is either true or false, but not both. ( p )
Propositional logic is the area of logic that deals with propositions.
A truth table displays the relationships between the truth values of propositions.
Logical operators: Negation ( ( p, not p ) Conjunction ( p ( q, p and q ) Disjunction ( p ( q, p or q ) Exclusive or ( p ( q, p or q but not both ) Implication ( p ( q, if p then q ) Biconditional ( p ( q, p if and only if q )
Propositions that are related to an implication p ( q Converse of an implication p ( q ( q ( p ) Contrapositive of an implication p ( q ( ( q ( ( p ) Inverse of an implication p ( q ( ( p ( ( q )
Compound propositions may be formed using various logical operators.
Generally accepted precedence of the logical operators (from highest to lowest): (, (, (, (, (
System specifications are a series of statements that spell out the requirements of the system in question. The specifications are said to be consistent if there is an assignment of truth values to the variables in the expressions that makes all the expressions true.
A Boolean variable is one whose value is either true or false.
Computer bit operations correspond to logical operations of Boolean variables.
Bitwise operations are bit operations extended to bit strings.

Exercises in 1.1

1.2 Propositional Equivalences

A compound proposition that is always true is a tautology.
A compound proposition that is always false is a contradiction.
A compound proposition that is neither a tautology nor a contradiction is a contingency.
Compound propositions that always have the same truth value are called logically equivalent (denoted by ().
Some well known logical equivalences (See Table 5 on p. 24 of the textbook)
|Equivalences |Name |
|p ( T ( p |Identity laws |
|p ( F ( p | |
|p ( T ( T |Domination laws |
|p ( F ( F | |
|p ( p ( p |Idempotent laws |
|p ( p ( p | |
|( ( ( p) ( p |Double negation law |
|p ( q ( q ( p |Commutative laws |
|p ( q ( q ( p | |
|(p ( q) ( r ( p ( (q ( r) |Associative laws |
|(p ( q) ( r ( p ( (q ( r) | |
|p ( (q ( r) ( (p ( q) ( (p ( r) |Distributive laws |
|p ( (q ( r) ( (p ( q) ( (p ( r) | |
|( (p ( q) ( ( p ( ( q |De Morgan's laws |
|( (p ( q) ( ( p ( ( q | |

Logical equivalences involving