CSE/IT/IS 214/Math E 211 – DISCRETE STRUCTURES
References:
R1 Kolman, Bernard and Busby, Robert . ( 1987 ) .Discrete Mathematical Structures for Computer Science, 2nd ed. . London : Prentice Hall International
R2 Johnsonbaugh, Richard . ( 1993 ) . Discrete Mathematics, 3rd ed.. Macmillian Publishing Company
R3 Kolman, Bernard , Busby, Robert C. and Ross, Sharon Cutler . ( 2000 ) . Discrete Mathematical Structures, 4th ed. . Upper Saddle River, New Jersey : Prentice-Hall Inc.
CHAPTER I. LOGIC AND PROOFS
LOGIC is the discipline that deals with reasoning. On an elementary level, logic provides rules and techniques for determining whether a given argument is valid. Logical reasoning is used in mathematics to prove theorems, in computer science, to verify the correctness of programs and to prove theorems, in natural and physical sciences to draw conclusions from experiments, in social sciences, and in our everyday lives, to solve a multitude of problems
A STATEMENT or a PROPOSITION is a declarative sentence that is either true or false but not both. It is typically expressed as a declarative sentence (as opposed to question or command ). Propositions are the basic building blocks of any theory of logic.
Which of the following are statements or proposition ?
1. The only positive integer that divide 7 are 1 and 7 itself.
2. 2 + 4 = 6
3. The earth is round.
4. 4 – x = 7.
5. Do you speak Chinese ?
6. Take two paracetamol.
7. Buy three tickets for the Manny Pacquiao bout on June 29, 2008.
8. The only positive integer that divide 12 are 3, 4 and itself.
9. A square is a rectangle having all sides equal.
10. Please come on time everyday to avoid being late.
11. Why is it required to enroll prerequisite subjects first ?
12. The rock samples from the moon were studied in the NASA laboratory.
Answers :
1. true, n is prime if n > 1 and can only be divided by 1 and itself ( statement )
2. true. 3. true ( statement )
4. is a declarative sentence, but not a statement, since it is true or false depending on the
value of x that is used.
5. is a question, so it is not a statement.
6. it is not a statement, it is a command.
7. is neither true nor false, it is a command.
LOGICAL CONNECTIVES AND COMPOUND STATEMENTS
The Connectives are AND, OR, NOT, IF...THEN, and IF and ONLY IF
Let us define the meaning of these connectives by showing the relationship between the truth value (i.e. true or false) of composite propositions and those of their component propositions. They are going to be shown using truth table In the tables P and Q represent arbitrary propositions, and true and false are represented by T and F, respectively.
In mathematics, the letters x, y, z . . . denote variables that can be replaced by real numbers, and they can be combined by the operations + , x , – , and ¸. In logic, the letters p, q, r . . . denote propositional variables, that is, variables that can be replaced by statements. Statements or propositional variables can be combined by logical connectives to obtain compound statements or propositions..
Definition 1.1.1 : Let p and q be propositions.
The conjunction of p and q, denoted by p L q, is the proposition p and q.
The disjunction of p and q, denoted by p V q, is the proposition p or q.
The negation of p, denoted by ~p or (
P), is the proposition not p.
P), is the proposition not p. Propositions such as p L q and p V q that result from combining propositions are called compound propositions. The compound statement p L q is true when both p and q are true; otherwise, it is false. The compound statement p V q is true if at least one of p or q is true, it is false when both p and q are false.
The truth values of propositions such as conjunctions and disjunctions can be described by truth tables. The truth table of a proposition p made up of the individual propositions p1. . . pn, lists all possible combinations of truth values for p1. . . pn, T denoting true and F denoting false and for each such combination lists the truth value of p.
Truth Tables
P AND Q ( P ^ Q )
P | Q | P ^ Q |
T | T | T |
T | F | F |
F | T | F |
F | F | F |
P OR Q (P V Q )
P | Q | P V Q |
T | T | T |
T | F | T |
F | T | T |
F | F | F |
not p ( ~ p )
p | (~ P) |
T | F |
F | T |
AND : The table shows that (P ^ Q) is true if both P and Q are true, and that it is false in any other case.
NOT : The table shows that if P is true, then (~P) is false, and that if P is false, then (~P) is true.
Examples :
1. p : 2 + 3 = 7 , q : A century is 100 years.
a) P is false and q is true. The conjunction p L q : 2 + 3 = 7 and a century is 100 years is false.
b) The disjunction p V q : 2 + 3 = 7 and a century is 100 years is true.
2. p : Kidapawan City is the capital of Cotabato. , q : Cotabato is in Mindanao.
a) P is true and q is true. The conjunction p ^ q : Kidapawan City is the capital of
Cotabato and Cotabato is in Mindanao is true.
b) The disjunction p V q : The conjunction p L q : Kidapawan City is the capital of
Cotabato and Cotabato is in Mindanao is true.
3. p : i 2 = –1 , q : e = 2.7182818
4. P : i = √–1 , q : The seventh month is August.
5. P : The 2nd day of the week is Friday , q : June 12 is labor day.
6. p : Rizal is from Leyte. , q : Dagohoy is from Bohol
7. P : Snakes are reptiles. , q : Birds are mammals.
Example : P : Discrete mathematics is easy. Not P : Discrete mathematics is not easy.
P : The price of rice is increasing. Not P : The price of rice is not increasing.
Evaluate the truth value for each proposition if the statements p = F , q = T and r = F.
1. p V q 4. p V r 7. p L r 10. p L q
2. ~P V r 5. r V q 8. r L q 11. ~P L r
3. ~P V ~q 6. p V ~r 9. p L~r 12. ~P L~q
Write the truth table for each proposition.
1. p ^~q 2. ( p V q ) ^ ~ p 3. (~p V ~q ) V p 4. ( p ^ q ) V (~p V q )
Determine whether each statement is True or False.
1. 3 < 7 and 7 < 9 2. It is not the case that ( 3 < 7 and 7 < 9 )
Formulate the symbolic expression in words using p : Today is Friday,
q : It is sunny, and r : It is cold.
1. p V q 3. ( p ^ q ) ^ (~ ( r V p ) )
2. ~ ( p V q ) ^ r 4. ( p ^ r ) V q
QUANTIFIERS
We used the notation P ( x ) to denote a sentence or a statement P concerning the variable object x. The set defined by P ( x ), written { x | P ( x ) }, is a collection of all objects for which P is sensible and true. For example, { x | x is a positive integer less than 4} is the set { 1, 2, 3 } described by listing its elements.
A sentence P ( x ) is also called predicate, because in English the property is grammatically a predicate. P ( x ) is also called a propositional function, because each choice of x produces a proposition P ( x ) that is either true or false. Another use of predicate is in programming. Two common constructions are “ if P ( x ), then execute certain steps”, and “ while Q( x ), do specified actions”. The predicates P ( x ) and Q ( x ) are called the guards for the block of programming code. Often the guard for block is a conjunction or disjunction.
Example : Let A = { x | x is an integer less than 6 }. Here P ( x ) is the sentence “ x is an integer less than 6.” The common property is “ is an integer less than 6”. Since P ( 3 ) is true, 3 Î A , P ( 7 ) is false, 7 Ï A.
1. Universal Quantifier
The Universal Quantifier of a predicate P ( x ) is the statement “For all values of x, P ( x ) is true”. It is assumed that only values of x that make sense in P ( x ) are considered. The universal quantification P ( x ) is denoted by "x P ( x ). The symbol " is called a universal quantifier. Universal quantification can also be stated as “For every x”, “Every x”, or “For any x”.
Example 2. The sentence P ( x ) : – ( – x ) = x is a predicate that make sense for real numbers x.
The universal quantification of P ( x ), "x P(x), is a true statement, because for all real numbers, – ( – x ) = x.
Example 3. Let Q ( x ) : x + 3 < 7. Then "x Q ( x ), is a false statement because Q ( 6 ), is not true.
A predicate may contain several variables. Universal quantification maybe applied to each of the variables. For example the commutative property can be expressed as "x "y x ÿ y = y ÿ x. The order in which the universal quantifier are considered does not change the truth value. Often mathematical statements contain implied universal quantification.
Example 4. Commutative property on sets:
2. Existential Quantifier
The Existential Quantification of a predicate P ( x ) is the statement “There exist a value of x for which P ( x ) is true”. The existential quantification of P ( x ) is denoted by $x P ( x ). The symbol $ is called the existential quantifier. $x can also be read as “There exist an x”, “There is some x”, “There exist an x”, or “There is at least one x”.
Example 5. Let Q ( x ) : x + 2 < 5. The existential quantification of Q ( x ), $x Q( x ) is a true
statement because Q (1) is a true statement. Q (4) is false.
Example 6. The statement $y y + 4 = y is false. There is no value of y for which the proportional
function y + 4 = y produces a true statement.
More examples.
1. Let p: For all positive integers n, n2 + 41 n + 41 is a prime number.
Then ~p is : There is at least one positive integer n for which n2 + 41n + 41 is not prime.
2. Let q : There is some integer k for which 12 = 3k. Then ~q : For all integers k, 12 is not = 3k.
Exercises from reference R3.
P ( x ) : x is even, Q( x ): x is a prime number, R ( x , y ) : x + y is even. The variables x and y are
integers. Write an English sentence corresponding to the following :
CONDITIONAL PROPOSITIONS AND LOGICAL EQUIVALENCE
Definition 1.2.1 : Let p and q be propositions.
If p and q are propositions, the compound proposition if p then q is called a conditional
proposition or implication and is denoted by p --> q.
The proposition p is called hypothesis ( or antecedent ) and the proposition q is called the conclusion ( or consequent ). The truth value is defined by the following table :
p | q | p --> q |
T | T | T |
T | F | F |
F | T | T |
F | F | T |
In logic, implication is used in a much weaker sense. To say that the compound statement p --> q is true simply asserts that if p is true, then q will also be found to be true. In other words, p --> q says that we will not have p true and q false at the same time. The truth values in the table shows p --> q in terms of the truth values of p and q. Observed that p --> q is considered false only if p is true and q is false. In particular, if p is false, then p --> q is true for any q.
Example :
1. p : I am thirsty 2. p : It is smoking.
q : I will drink. q : 4 + 5 = 9
Answers: 1. If I am thirsty, then I will drink.
2. If it is smoking, then 4 + 5 = 9.
In the English language, and in mathematics, each of the following expressions is an equivalent form of the conditional statement p ® q :
p implies q
q, if p
p only if q
p is a sufficient condition for q
q is a necessary condition for q
If p --> q is an implication, then the converse of p --> q is the implication q --> p, and the contrapositive of p --> q is the implication ~q --> ~p.
Examples :
1. Give the converse and contrapositive of the implication “If it is raining, then I get wet”.
Solution : p : It is raining
q : I get wet.
Converse : If I get wet, then it is raining.
Contrapositive : If I do not get wet, then it is not raining.
Definition 1.2.2 : Let p and q be propositions.
If p and q are propositions, the compound proposition p if and only if q denoted by
p <---> q is called an equivalence or biconditional proposition. The truth value is defined by the truth table below. Observe that p « q is true only when both p and q are True or when both are False. p «q is also stated as p is a necessary and sufficient condition for q. Truth table is :
P | q | p <---> q |
T | T | T |
T | F | F |
F | T | F |
F | F | T |
Example : 1. Is the statement 5 > 3 if and only if 0 < 5 – 3 true ?
Let p : 5 > 3 , q : 0 < 5 – 3. Since p is true and q is true, then p <---> q is true.
In general, a compound statement may have many component parts, each of which is itself a statement, represented by some proportional variable. The statement
s : p --> ( q ^ ( p --> r ) )
involves three propositions, p, q, and r, each of which may independently be true or false. There are altogether 23 = 8 possible combinations of truth values for p, q, and r, and the truth value for s contains n components statements, there will be 2 n entries needed in the truth table for s.
Step 1. The first n columns of the table are labeled by the component propositional variables.
Further column are constructed for all intermediate combinations of statements,
culminating in the given statement.
Step 2. Under each of the first n headings, we list the 2 n possible n-tuples of truth values of the component statement s. Each n-tuple is listed on a separate row.
Step 3. For each row we compute, in sequence, all remaining truth values.
No comments:
Post a Comment