Discrete Mathematics (Math 2182)

Chapter1:- Introduction logic

1.1 Logical connectives
Definition:- An assertive or declarative sentences which is true or false but not both at the same time
is called a statement or proposition
Example: Which one of the following sentences are proposition
a. 5+9 3+11
b. I like to a responsible citizen
c. +1>0 for all
d.
e.
f. how is mathematics
Answer:-
a. yes, because it is false sentence
b. no, because it is sample express one‟s own opinion we cannot determine whether it is
true or false.
c. yes, because it is true sentence.
d. no, because cannot determine unless is assigned a specific value.
e. yes, because it is true sentence for all
f. no, because it is question.
Notations: - propositions are denoted by small letters p, q, r, s etc.

Logical connectives are:-

i. negation (not) ( )
ii. and (conjunction) ( )
iii. or (disjunction) ( )
iv. if - - - ,then (implication) ( conditional) (⇒) ( )
v. if and only if (Bi-implication) (Bi-conditional) ( ) ( )

Note:- we write „0‟ for false and „1‟ for true.

Definition:- A statement which is the combination of two or more simple statements is called a
compound (or complex) statement

Let and are simple statement

1 1 0 1 1 1 1
1 0 0 0 1 0 0
0 1 1 0 1 0 0
0 0 1 0 0 0 1

1
Example: 1. Suppose and are and are . Then what is the truth value of ( ) ( )?

2. Let have truth values 1, 0, 1 respectively. Determine the true values of

a. b. ( ) c. ( ) d. ( ) ( )
Solution:-1. ( ) ( )
( ) ( )

1
2. exercise.

Note:- consider and are simple propositions

i. is called the converse of
ii. is called the inverse of
iii. is called the contrapositive of
Example: If the function is continuous, then the function is differentiable.

Solution:-

i) Converse:- If the function is differentiable, then the function is continuous.

ii) Inverse:- If the function is not continuous, then the function is not differentiable.
iii) Contrapositive:- If the function is not differentiable, then the function is not continuous.

1.2 Tautology, contradiction and logical equivalence

Definition:- A compound statement is said to be

i. Tautology if and only if it is true (1) for every possible combinations.

ii. Contradiction if and only if it is false (0) for all possible combinations.

Example: which one of the following is tautology or contradiction or neither?

a. ( ) ( ) b. ( ) ( )

c. , ( )- d. ( ) ( )

Answer:- a and c are tautology. But b and d are contradiction

Definition: - Two statements involving the same simple propositions are said to be equivalent if and only
if they have identical truth tables.

Example: Show that the following composition is equivalence.

a. b. ( ) ( )

c. ( ) d. ( )( ) ( )

2
1.2.1 Some properties of equivalence

1. Commutative: -

2. Associativ፡ - ( ) ( ) ( ) ( )

3. Distributive:- ( ) ( ) ( ) ( ) ( ) ( )

4. de-Morag‟s law:- ( ) ( ) ( )

5. Law of contrapositive:-

6. Idempotent laws:-

7. Identity laws:- if is false b is is true

8. In verso laws:-

9. Domination laws:-

1.3 quantified propositions

Definition : - An open proposition is a sentence which contains one or more variables and becomes a
proposition when each of its variables replaced by specific number(s), name(s), or individual(s).

Example: Which one of the following is an open proposition?

( )

( )

( ) is the father of

( ) is a square root of

( ) is a whole numbers

( )

( ) is a red cow

Answer:- open propositions are : , but is propositions

3
Remarks:-

1. The phrase „‟for some x‟‟ or “there exits an x‟‟ or „‟for at least one x” is called existential quantifier ( )
( x) P(x) is read as there exist some x such that p(x) is true. Here ( x) p(x) is quantified proposition
2. The phrase “for all x” or „‟for every‟‟ or „‟for each x‟‟ is called universal quantifier ( )
( x) p(x) is read as for all x such that p(x) is true.
Example: 1. let ( ) 0 ; universal set . Then the truth value of ( )( ) is true.
( )( 0) is false.
2. Let ( ) , . Then the truth value of
( )( ) is true.
( )( ) is false.
Let ( ) . Then the truth value of ( ) ( ) is false.
let ( ) . Then the truth value of ( ) ( ) is false.

Exercise
Let * + ( ) ( ) is prime number, ( ) is even. Then determine
the truth value of

( ) ( ) ( ) ( ) ( ), ( ) ( )- ( ) ( )

Answer:- a. T b. F, b/se ( ) ( ) ( ) are false

c. F, for instance ( ) is T. since 3 is prime and ( ) is F b/se 3 is not even d. T

Note:- The negation of ( )( ) ,( ( ) ( ) ⇒ ( )- is

, , ( ) ( )⇒ ( )--
, , ( ) ( )⇒ ( )--
( ) , ( ) ( )⇒ ( )-
, ( ( ) ( )) ( )-
[, ( ) ( )- ( )]
Example:-Let ( ) and the universal set then
. The truth value of ( ) is ___________
. The truth value of ( ) is ___________
Solution:- i. true, once we select any x, the integer does exist.
ii. The statement is read as “there exists an integer y so that for all integers ‟‟.

This statement is false, once an integer is selected, the only value is (satisfy ).

But if ( ) is true then every integer ( ) would sequel to (for someone fixed ).

Note:- ( ) and ( ) are generally not logically equivalent.

4
Remark-1. ( ) ( ) ( ) ( ) means ( ) is false for every .

2. ( ) ( ) ( ) ( ) means there is an for which ( ) is false

Exercise:- if , then say true or false

a. ( )(√ ) b. ( )( )( ) c. ( )( )( )
d. ( )( )( ) e. ( )( )( ) f. ( )( )( )
g. ( )( )( )
Answer:- a. F b. T c. F d. F e. T f. T g. F

1.4 Arguments and validity

Consider the following example:
Example: 1. What can be concluded about , if p is 1 and ⇒ is 1?
Answer:- if is 1 and ⇒ is 1, we conclude from rule of implication that is 1.
In this example, the statements ⇒ are called premises and is called the conclusion.
Definition:- A logical deduction (argument form) is an assertion that a given set of statement p1,
p2, -------pn is called premises yield another statement g, called conclusion. Such a logical
deduction is donated by:
p1, p2, -------------, pn g or p1
P2
.
.
.

Example: 2. in example 1 above, the argument form is denoted by: p

⇒

Example: 3. “if the function f is not continuous, then the function q is not differentiable. q is
differentiable. Therefore f is continuous”.
Solution: - let p: f is continues
q: q is differentiable. Then
The argument form is given by: p ⇒ q

Definition:- An argument form p1, p2, - - - , pn q is said to be

i. Valid if q is whenever p1, p2, - - - , pn are 1
ii. Invalid if there is a case in which all of p1, p2, - - -, pn are 1 but q is 0.
To prove the given compound statement is veiled or not use a
i. Truth table and check the compound statement is tautology or not
ii. Direct method

5
Note: - i. p1, p2, - - -, pn are all 1 means that p1 p2 - - - pn is 1.

ii. The argument form p1,p2, - - - pn g is valid iff the statement (p1 p2 - - - pn) ⇒ g is tautology.

Example: 1. Test the validity of the following argument form using truth table or direct method.

a. ⇒ b. ⇒
⇒
c. ( ⇒ )
. ⇒
. ⇒ ⇒
. ( )⇒

Solution: a.

p g r g p⇒g g⇒r (p⇒g) ( p⇒r) [(p⇒g) ( p⇒r)]⇒p

T T T F T T T T
T T F F T T T T
T F T T F F F T
T F F T F F F T
F T T F T T T T
F T F F T T T F
F F T T T T T F
F F F T T F T F

Since [(p⇒g) ( p⇒r)]⇒p is not tautology, the argument is invalid

d. Using direct method

1. r is T-----------premise

2. r⇒p is T-----permise

3. P is T----------- (definition of ⇒ and step 2)

4. P is F------------ (definition of )

5. P g is T---------premise

6. g is T-----------(definition of and step 5

Thus the argument form ⇒ is valid.

6
e. Using direct method

1. g is T------------premise

2. g is F-------------by definition of and step 1

3. g ⇒ p is T ----------premise

4. p is T----------by definition of ⇒ and step 3

5. p is F ------------by definition of and step 4

6. r ⇒ p is T-----------premise

7. r is F ----------- by definition of ⇒ and step 6

The argument is not valid.

f. Using direct method

1. p is T-----------premise

2. p is T--------definition of step 1

3. g is T--------definition of step 1

4. (P r) ⇒ s is T--------premise

5. S is T------------by definition of ⇒ step 4

6. P s is T by step 2 and 5

Hence argument is valid

Exercise:- Check the following argument is valid or not

a. p ⇒ g, g p

b. p ⇒ g, p, r ⇒ g r

c. p ⇒ g, r⇒ g r⇒ p

d. r s, ( s ⇒ p) ⇒ r p⇒r

7
1.5 methods of proof
1.5.1 Direct proof and proof by contra positive

Example: 1. If x is odd, then is odd

2. If x is even, then is even

3. If x, y are odd, then xy is odd

4. If is odd, then x is odd (Hint:- use contra positive)

5. If 3x+2 is even, then x is even, where x is an integer

6. If x is odd, then 3x+2 is odd.

Solution:-

1. Given x is odd w.t.s is odd

⇒
⇒ ( ) ( ) , which is odd

2, 3, 4, 5 and 6 are exercise

1.5.2 Indirect proof

It is a proof when we temporary assume that conclusion is not true. Then we reach a contradiction
to our assumption. Therefore proving the conclusion is true

Example: 1. If , then

Proof:- Assume . Then the value of x is contradicts with 5.

⇒ ⇒

Thus contradict as a result our assumption is false. Thus

2. If ABC is isosceles, then the base angle cannot equal 95

Proof:-Assume the base angles measure 95
Then the sum of the base angles would be 95 + 95 =190
This contradicts the sum (i.e the sum of the interior angles of a is 180 )
The base angles of an isosceles 95

8
1.5.3 Proof by induction
( )
Examples: 1. Prove 1+2+3-----------+ n =
Proof:-1. Basis case:- it is for n = 1
( )
2. Induction step:-Assume it is true for n = k, i.e. 1+2+3----------+ k =
( )( )
We went to show that it is true for n = k+1,i.e. 1+2+3---------+ k + (k+1) =
( ) ( )( )
Now 1+2+3--------+k+k+1= + (k+1) =
2. Prove ( ) =
Proof:- 1. basis case:- For n=1, =
2. Induction step:- Assume it is true for n = k,i.e ( ) =
( )
WTS:- it is true for n = k+1, i.e. ( ) =
( )
Now = ( ) ( ) ( )
3. Prove: ( ) ( )

( ) , -

( ) ( )
Proof:- d. 1. P (1) =1(1+1) =2, which is true for n=1
2. Assume it is true for n=k i.e. P(k)=k(k+1)= +k is even
WTS:- P(k+1)is true i.e. P(k+1) = (k+1)(k+2) is even
now, P(k+1) = (k+1)(k+2) = +3k+2
= ( +k) +2k+2
= 2j+2k+2, for some j
= 2(j+k+1) is even
Thus the induction step is true
Exercise:- a, b and c.