Wipro Class 2

BITS-WIPRO Collaborative Programme: MS in Software Engineering, ( I Semester) MATHEMATICAL STRUCTURES A collection of objects with operation defined on them and the accompanying properties form a mathematical structure or system. In this whole semester we deal with Discrete Mathematical Structures. An important property is closure. A structure is closed with respect to an operation if that operation produces another member of collection of objects. Example: 1 The collection of sets with the operations of union, intersection and complement and their accompanying properties is a discrete mathematical structure. Example:2 The collection of 3 by 3 matrices with the operations of addition, multiplication and transpose is a mathematical structure. Example 3: The structure of 5 by 5 matrices is closed with respect ot addition because the sum of two 5by 5 matrices is another 5 by 5 matrix. Example 4: The structure the set of all odd integers is not closed with respect to addition because the sum of two odd integers is an even integer. This structure does have the closure property with respect to multiplication, since the product of two odd integers is an odd number. An operation that combines two objects is a binary operation. An operation that requires only one object is a unary operation. SEQUENCE A sequence is simply a list of objects in order; a first element, second element, third element and so on. This list may stop after n-steps or it may go forever. In the first case we say that the sequence is finite and in the second case we say that the set is infinite. Ex: 1. The sequence 1,0,0,1,0,1,0,0,1,1,1 is a finite sequence with repeated terms. The digit 0 for example occurs as the second, third, fifth, seventh and eighth element of the sequence. 2.

The list 3,8,13,18,23,…….. is an infinite sequence. The dots in the expression mean” and

so on” i.e. continue the pattern established by the first few elements. The nth term of a sequence is generally denoted by an; thus a1 denotes the first term, a2 denotes the second term and so on .A sequence can be described either by specifying an for n=1,2,3,4,….. or specifying the first term a1 and the relation connecting the nth term an with one or more of the preceding terms. In the former case we say that the sequence is defined by an explicit formula and in the later case by a recursive formula.

Prepared by Dr. K. V. Prasad, E-mail:[email protected], 9448687862

1

BITS-WIPRO Collaborative Programme: MS in Software Engineering, ( I Semester) Ex:

1.

The sequence 1,-1,1,-1,1,-1,…………… is specified by the explicit formula an =

(-1)n+1, n greater than equal to 1,. 2.

The sequence -10,-7,-4,-1,2,5,…… is specified by the recursive formula an=an-1+3 for n greater than equal to 2 and a1=-10.

Array: A sequence is a set whose elements are arranged in order. In a sequence of elements of a set A, every element of A has a position. The position themselves may be thought of as the elements of a sequence; this sequence is called an Array. An array may be pictorially represented as a sequence of boxes as shown below ………………………….. In this representation, the first box represents the first position, the second box the second position, and so on.The element assigned to the position n in an array S is denoted by S[n] and the sequence S[1],S[2],S[3], …. is called the sequence of values of the array S. Ex: Consider the set A={-1,0,1} and the finite sequence -1,0,1,-1,0,1,-1,0,1 obtained by using the elements of A. Here S[1]=S[4]=S[7]=-1

S[2]=S[5]=S[8]=0

S[3]=S[6]=S[9]=1.

Computer representation of sets and subsets Characteristic function Associated with a set A ⊆ U let us define the function fA(x) over U by, if x ∈ A ⎧1 f A (x ) = ⎨ this function is called the characteristic function of A over U. ⎩ 0 if x ∉ A Ex: Suppose U={a,b,c,d,e,f,g} is the universal set. A={a,b,d,g}, then by the characteristic function fU(x)=1 for x=a,b,c,d,e,f,g if x = a, b, d , g ⎧1 And f A ( x ) = ⎨ ⎩ 0 if x = c, e, f In view of these , the set U may be represented as the array 1

1

1

1

1

1

1

1

0

0

1

And the set A may be represented as the array 1

1

0

Prepared by Dr. K. V. Prasad, E-mail:[email protected], 9448687862

2

BITS-WIPRO Collaborative Programme: MS in Software Engineering, ( I Semester) Strings Finite sequence of letters or other symbols, written without commas between the elements are referred as strings and the elements in a string are called letters. The number of letters in a string is called its length. The length of a wordu is denoted by l(u). Example: ENGINEERING is a string of length 11 U=aabbccc is string of length 7. This string is also written as u=a2b2c3. Languages Given a finite set A , we can construct strings with letters drawn from A. The set of all such strings is denoted by A*. This set contains the empty string as well. The set A is called the alphabet. A subset of A* is called the language over the alphabet A Example: A={a,b,c}then the strings u=abbc=ab2c, v=aaabcc=a3bc2. belongs to A*. Catenation of strings If u =a1,a2,a3,a4,…..an and v=b1,b2,b3,b4,b5,……bk are two strings whose alphabet is some set A then the set uv is given by u.v=uv=a1a2a3a4…..an b1b2b3b4…bk is called the catenation of u and v in that order. Note: The empty string is denoted by ∧ Catenation of languages Let L amd M be two languages on an alphabet A. Then the catenation of L and M denoted by LM, is the language on A defined by LM = {uv / u ∈ L, v ∈ M }, that is, LM is the set of all strings which arise from the catenation of a string from L with a string from M. Ex: 1. L1={a,ab}, L2={ab2,bc}, L3={ab,bc2} are the languages over the alphabet A={a,b,c}, then L1L2={a2b2,abc,abab2,ab2c}, L1L3={a2b,abc2,abab,ab2c2}. 2. Let A={ab,bc,ca}. Find whether the following strings belongs to A*. (i) ababab

(ii) abc

(iii)abba (iv)abbcbaba (v) bcabbab (vi) abbbcba. Solution:

Here tha alphabet A consists of the letters ab,bc,ca. (i)

The string ababab=

(ab)(ab)(ab) is made up of the letters of A. Therefore , this string belongs to A*. (ii) The string abc canot be obtained from the given alphabet; therefore this string doesnot belongs to A*. (iii)abba doesnot belongs to A*. (iv) abbcbaba doesnot belongs to A*. (v) bcabbab doesnot belongs to A*. (vi) abbbcba doesnot belongs to A*. 3.

Given the strings u=a2ba3b2 and v=bab3 find the strings uv,vu, v2, ∧ u , u ∧, u ∧ v 2 also find their length.

Prepared by Dr. K. V. Prasad, E-mail:[email protected], 9448687862

3

BITS-WIPRO Collaborative Programme: MS in Software Engineering, ( I Semester) Solution: uv= (a2ba3b2)(bab3)= a2ba3b3ab3;

uv = 13 ,vu= (bab3)(a2ba3b2) = bab3a2ba3b2;

vu = 13 ,v2=vv=(bab3) (bab3)=bab4ab3, v = 10 , 2

∧ u = ∧u = u = a 2 b a 3b 2 , ∧ u = u ∧ = u = 8, u ∧ v 2 = uv 2 = 18 . Regular expression, Regular languages

Let A be a non-empty alphabet. Then the following are called regular expression over A. (i)

The empty string

(ii)

Every element of A

(iii)

The catenation αβ of every two regular expressions over A

(iv)

A regular expression enclosed in a pair of parenthesis.

(v)

(α ) and (α ) where α *

*

is regular expression over A.

Associted with each regular expression r over A, there is defined a regular set or a regular language. The rules of correspondence between a regular expression r and on the corresponding regular language are given below: L(∧ ) = {∧} (2)for a ∈ A, L(a ) = {a} (3)

(1)

( )

L{αβ } = L(α ) L(β ) (4) L α * = ( L(α )) * .

Division of Integers

Consider the following division 9) 58(6 54 04. Here, 9 is called the Divisor, 58 is called the Dividend, 6 is called the quotient, and 4 is the reminder. The division can also be shown as 58= 6*9+4. Note that the remainder is positive and less than the divisor. The following two divisions are wrong

9) 58(5

b) 9)58(7

45

63

13

-5.

In the first cae, the remainder >divisor. In (b), the remainder is negative. Statement of Division Algorithm Given two integers a and b where a>0, two unique integers q

and r can always be found such that b=aq + r where 0 ≤ r < a

.this is known as Division

Algorithm. Q is called quotient and r is called the remainder.

Prepared by Dr. K. V. Prasad, E-mail:[email protected], 9448687862

4

BITS-WIPRO Collaborative Programme: MS in Software Engineering, ( I Semester) Greatest Common Divisor: Consider the the integers 12 and 18. The positive divisors of 12

are 1,2,3,4,6,12. The positive divisors of 18 are 1,2,3,6,9, 18. Therefore the common divisors of 12 and 18 are 1,2,3,6. Clearly 6 is the GCD of 12 and 18. Euclid’s algorithm to find the GCD of two given numbers a and b and to express the GCD as ax+by.

1) Find the GCD of 32 and 54 and express it in the from 32x+54y. 32)54(1 32 22

22) 32(1 22 10

22=54-32(1)

10)22(2 20 02

10=32-1(22)

2)10(5 10 00.

2=22-2(10), 0=10-2(5).

Taking the equation (3), 2 = 22 -2 (10) =[54-1(32)]-2[32-1(22)] =54-3(32)+2(22) =54-3(32)+2[54-1(32)] =3(54)-5(32) =54(3)+32(-5), where, x=-5, y=3. 2) . Find the GCD of 495 and 675 and find k and l such that (495,675)=495k+675l. 495) 675(1 495 180

180)495(2 360 135

180= 675-1(495)

135)180(1 135 45

135=495- 2(180),

45)135(3 135 000 45=180-1(135),

0=135-3(45).

Therefore GCD is 45. 45= 180- 1 (135) = 675- 1 (495)- 1[495- 2(180)] = 675-2(495)+2 (180) = 675-2 (495)+ 2 [ 675- 1(495)] = 675(3)+ 495(-4),

therefore k=-4 and l=3.

3.Find the GCD of 275 and 726 and express it in the form 275 x+726 y. 4. Find the GCD of 506 and 1155 and express it in the form 506m+1155n.

Prepared by Dr. K. V. Prasad, E-mail:[email protected], 9448687862

5

BITS-WIPRO Collaborative Programme: MS in Software Engineering, ( I Semester) MATHEMATICAL INDUCTION

Suppose we want to prove that a certain statement p(n) is true for all integers n ≥ n0 where n0 is a fixed integer. A standard method of proving such a statement is one called the method of Mathematical Induction. The method consists of the following two steps

(1) Basic Step: Verify the statement p(n) is true for n=n0. (2) Induction step: Assuming that p(n) is true for n=k where k is any positive integer ≥ n0 , prove that p(n) is true for n=k+1. Examples:

1.

Prove

by

mathematical

induction

that,

for

all

positive

integers

n ≥ 1,

⎛ n(n + 1) ⎞ 1 + 2 + 3 + 4 + ................... + n = ⎜ ⎟. ⎝ 2 ⎠ Solution: Here we have to prove that

⎛ n(n + 1) ⎞ p(n): 1 + 2 + 3 + 4 + ................... + n = ⎜ ⎟ for all integers n ≥ n0 where n0=1. ⎝ 2 ⎠ 1 Basic Step: We note that p(1) is the statement 1 = 1.(1 + 1) which is clearly true. Thus , the 2 statement p(n) is verified for n=1. Induction step: We assume that the statement p(n) is true for n=k where k is any integer ≥ 1 . That is, we assume that the following statement is true ⎛ k (k + 1) ⎞ P(k): 1 + 2 + 3 + 4 + ................... + k = ⎜ ⎟ ⎝ 2 ⎠

(1)

on the basis of this assumption, we prove that the statement p(n) for n = k+1. ⎛ (k + 1) (k + 2 ) ⎞ P(k+1): 1 + 2 + 3 + 4 + ................... + k + (k + 1) = ⎜ ⎟ is true. 2 ⎝ ⎠

(2)

Now by using (1) , we find that k (k + 1) + (k + 1) 2 ⎡k ⎤ = (k + 1) ⎢ + 1⎥ ⎣2 ⎦ (k + 1) (k + 2) = 2

1 + 2 + 3 + 4 + ................... + k + (k + 1) =

This is precisely the statement (ii). Thus the truth ness of p(n) for n=k+1 is established.

Prepared by Dr. K. V. Prasad, E-mail:[email protected], 9448687862

6

BITS-WIPRO Collaborative Programme: MS in Software Engineering, ( I Semester) Example2: Prove by mathematical induction that, for all positive integers n ≥ 1 ,

⎛ n(n + 1)(2n + 1) ⎞ 12 + 2 2 + 3 2 + 4 2 + ................... + n 2 = ⎜ ⎟. 6 ⎝ ⎠ Solution: here we have to prove that

⎛ n(n + 1)(2n + 1) ⎞ p(n): 12 + 2 2 + 3 2 + 4 2 + ................... + n 2 = ⎜ ⎟ for all integers n ≥ n0 where n0=1. 6 ⎝ ⎠ 1 Basic Step: We note that p(1) is the statement 12 = 1.(1 + 1)(2 + 1) which is clearly true. Thus , 6 the statement p(n) is verified for n=1. Induction step: We assume that the statement p(n) is true for n=k where k is any integer ≥ 1 . That is, we assume that the following statement is true ⎛ k (k + 1)(2k + 1) ⎞ P(k): 12 + 2 2 + 3 2 + 4 2 + ................... + k 2 = ⎜ ⎟ 6 ⎝ ⎠

(1)

on the basis of this assumption, we prove that the statement p(n) for n = k+1. ⎛ (k + 1)(k + 2)(2k + 3) ⎞ 2 P(k+1): 12 + 2 2 + 3 2 + 4 2 + ................... + k 2 + (k + 1) = ⎜ ⎟ is true. 6 ⎝ ⎠

(2)

Now by using (1) , we find that k (k + 1)(2k + 1) + (k + 1) 2 6 ⎡ k (2k + 1) ⎤ = (k + 1) ⎢ + (k + 1)⎥ 6 ⎣ ⎦ (k + 1) (k + 2) (2k + 3) (k + 1) = 2k 2 + 7 k + 6 = 6 6

12 + 2 2 + 3 2 + 4 2 + ................... + k 2 + (k + 1) 2 =

[

]

This is precisely the statement (ii). Thus the truth ness of p(n) for n=k+1 is established. Example3: Prove by mathematical induction that, for all positive integers

⎛ n 2 (n + 1)2 13 + 2 3 + 33 + 4 3 + ................... + n 3 = ⎜⎜ 4 ⎝

n ≥ 1,

⎞ ⎟. ⎟ ⎠

Solution: Here we have to prove that

⎛ n 2 (n + 1)2 p(n): 13 + 2 3 + 33 + 4 3 + ................... + n 3 = ⎜⎜ 4 ⎝

⎞ ⎟ for all integers n ≥ n0 where n0=1. ⎟ ⎠

Prepared by Dr. K. V. Prasad, E-mail:[email protected], 9448687862

7

BITS-WIPRO Collaborative Programme: MS in Software Engineering, ( I Semester)

1 2 Basic Step: We note that p(1) is the statement 13 = 12.(1 + 1) which is clearly true. Thus , the 4 statement p(n) is verified for n=1. Induction step: We assume that the statement p(n) is true for n=k where k is any integer ≥ 1 . That is, we assume that the following statement is true ⎛ k 2 (k + 1)2 P(k): 13 + 2 3 + 33 + 4 3 + ................... + k 3 = ⎜⎜ 4 ⎝

⎞ ⎟ ⎟ ⎠

(1)

on the basis of this assumption, we prove that the statement p(n) for n = k+1. ⎛ (k + 1)2 (k + 2)2 P(k+1): 13 + 2 3 + 33 + 4 3 + ................... + k 3 + (k + 1) 3 = ⎜⎜ 4 ⎝

⎞ ⎟ is true. (2) ⎟ ⎠

Now by using (1) , we find that or This is precisely the statement (ii). Thus the truth ness of p(n) for n=k+1 is established. Example:4 By mathematical induction prove that n!≥ 2 n −1 for all integers n ≥ 1 Solution: Here we have to prove the statement: p(n): n!≥ 2 n −1 for all integers n ≥ 1 , where n0=1. Basic step: for n=n0=1, the statement p(n) reads 1! ≥ 21-1; that is, 1 ≥ 1, which is obviously true. Thus p(n) is verified for n=1. Induction step: We assume that p(n) is true for n=k, where k is any integer ≥ 1; that is we assume that, k!≥ 2 k −1 or 2 k −1 ≤ k! is true. This yields

2 k = 2. 2 k −1 ≤ 2 k! . < (k + 1) k!= (k + 1)!

This yields (k + 1) ≥ 2 k . This is precisely the statement p(n) for n=k+1. Thus on assumption that p(n) is true for n=k.We have proved that p(n) is true for n=k+1. Example: 5 Prove by mathematical induction that 3 / (n 3 − n) for every int eger n ≥ 2 . Solution: we first that 3 / (n 3 − n) stands for “3 divides n3-n” Accordingly, the statement to be proved here reads p(n):n3-n is multiple of 3 for every integer n ≥ 2 Basic step: For n=2, the statement p(n) reads 23-2 is a multiple of 3. This is clearly true. Thus, p(n) is verified for n=2. Induction Step: we assume that p(n) is true for n=k where k is any integer k ≥ 2 . ; that is assume that k3-k is a multiple of 3. so that k3-k =3m for some integer m. Prepared by Dr. K. V. Prasad, E-mail:[email protected], 9448687862

8

BITS-WIPRO Collaborative Programme: MS in Software Engineering, ( I Semester)

Then (k+1)3-(k+1)= k3+3(k2+k)-k= 3 (m+k2+k) which means that (k+1)3-(k+1) is a multiple of 3. This is precisely the statement p(n) for n=k+1. Thus on the assumption that p(n) is ture for n=k, it is proved that p(n) is true for n=k+1.

Prepared by Dr. K. V. Prasad, E-mail:[email protected], 9448687862

9

BITS-WIPRO Collaborative Programme: MS in Software Engineering, ( I Semester) Mathematical Logic Proposition: A proposition is a statement (declaration) which, in a given context, can be said to

be either true or false, but not both. Ex: 1 The number 3 is a prime number 2. Every prime number is a multiple of 3 3. Every square is a rectangle. 4. Every rectangle is a square The sentences 1 and 3 are true statements where as 2 and 4 are false statements. Connectives

The words or phrases like NOT,AND,OR, IF….THEN, IF AND ONLY IF, such words or phrases are called connectives. The new propositions obtained by the use of connectives are called compound propositions. Negation A proposition obtained by inserting the word ‘not’ at an appropriate place in a given

proposition is called negation of the given proposition. The negation of a proposition p is denoted by ¬ p , the symbol ¬ denoting the word NOT. Ex: P: 2 is a prime number, then the negation of p is 2 is not a prime number i.e, ¬ p : 2 is not a prime number. The truth table for negation is as given below

¬p P T F F T Conjunction: A compound proposition obtained by combining two given propositions by inserting the word “and” in between them is called the conjunction of the given propositions. The conjunction of two propositions p and q is denoted by p ∧ q .Here the symbol ∧ denoting the word AND. Ex: p: 2 is a prime number, q: 6 is a multiple of 3, then p ∧ q : 2 is a prime number and 6 is a multiple of 3.The conjunction of p ∧ q is true only when p is true and q is true; in all the other cases it is false. The truth table for conjunction is as follows P T T F F

q T F T F

p∧q T F F F

Prepared by Dr. K. V. Prasad, E-mail:[email protected], 9448687862

10

BITS-WIPRO Collaborative Programme: MS in Software Engineering, ( I Semester) Disjunction: A compound proposition obtained by combining two given propositions by

inserting the word “or” in between them is called the disjunction of the given propositions. The disjunction of two propositions p OR q is denoted by p ∨ q .Here the symbol ∨ denoting the word OR. Ex: p: 2 is a prime number, q: 6 is a odd number, then p ∨ q : 2 is a prime number or 6 is an odd number. The disjunction of p ∨ q is false only when p is false and q is false; in all the other cases it is true. The truth table for disjunction is as follows p∨q p q T T T T F T T T F F F F Conditional: A compound proposition obtained by combining two given propositions by using

the word “if and Then” at appropriate places is called a conditional proposition or just a conditional. Ex: 1.ABC is equatorial

2. ABC isosceles, The following statement can be written by using

conditional statement as If ABC is equatorial then ABC is isosceles”.If p and q are two propositions, the conditional proposition “ if p, then q” is denoted by p → q . Note: the conditional proposition p → q is not same as q → p . The conditional p → q is false only when p is true and q is false; in all other cases it is true. p→q P Q T T T F F T T T F T F F Biconditional: Let p and q be two propositions. Then the conjunction of the conditionals

p → q and q → p is called the biconditional of p and q; is denoted by p ↔ q . Thus , p ↔ q is

same as ( p → q ) ∧ (q → p ) .As such p ↔ q is read as if p then q and if q then p. The following is the truth table for p ↔ q p T T

q T F

p→q T F

q→ p T T

p↔q T F

Prepared by Dr. K. V. Prasad, E-mail:[email protected], 9448687862

11

BITS-WIPRO Collaborative Programme: MS in Software Engineering, ( I Semester)

F T F F Tautologies and Contradictions:

T T

F T

F T

A compound proposition which is always true regardless of the truth values of its components is called a tautology. A compound proposition which is always false regardless of the truth values of its components is called a contradiction. A compound proposition that can be either true or false, depending on the truth values of its components is called a contingency. In other words , a contingency is a compound proposition which is neither a tautology nor a contradiction. Examples: Construct the truth tables for the following compound propositions (i )

p ∧ ¬q

(ii ) p → ¬q

(iii ) p ∧ (q → ¬r ) (iv) ( p ∧ q ) → ¬r

¬q F T F T

p → ¬q F T T T ( p ∧ q ) → ¬r F T T T T T T T

Solution: P T T F F p T T T F T F F F

q T F T F q T T F T F T F F

r T F T T F F T F

p ∧ ¬q F T F F ¬r ( p ∧ q) T F T T F F F F F T F T F F F T

Prove that, for any propositions p.q.r the propositions

q → ¬r F T T F T T T T

p ∧ (q → ¬r ) F T T F T F F F

[( p → q ) ∧ (q → r )]→ ( p → r ) is

a

tautology p

q

T T T F T F F F

T T F T F T F F

r T F T T F F T F

p→q

q→r

( p → q ) ∧ (q → r )

p→r

[( p → q ) ∧ (q → r )] → (p → r)

T T F T F T T T

T F T T T F T T

T F F T F F T T

T F T T F T T T

T T T T T T T T

Prepared by Dr. K. V. Prasad, E-mail:[email protected], 9448687862

12

BITS-WIPRO Collaborative Programme: MS in Software Engineering, ( I Semester) Logical Equivalence: Two propositions p and q are said to be logically equivalent whenever p

and q have the same truth value, or equivalently the bi conditional p ↔ q is a tautology. Then we write p ≡ q . Here this symbol stands for logically equivalent to . The following are some important results valid for all propositions p,q,and r. 1.

(a) p ∨ p ≡ p

p∧ p≡ p

2.

(a) p ∨ q ≡ q ∨ p

3.

(a ) p ∨ (q ∨ r ) ≡ ( p ∨ q ) ∨ r

4.

(a) p ∨ (q ∧ r ) ≡ ( p ∨ q) ∧ ( p ∨ r )

5.

¬(¬p ) ≡ p

6.

(a ) ¬( p ∨ q ) ≡ ¬p ∧ ¬q

7.

¬( p → q ) ≡ ¬p ∧ (¬q )

(b)

(b)

p∧q ≡ q∧ p (b) p ∧ (q ∧ r ) ≡ ( p ∧ q ) ∧ r (b) p ∧ (q ∨ r ) ≡ ( p ∧ q ) ∨ ( p ∧ r )

(b) ¬( p ∧ q ) ≡ ¬p ∨ ¬q

Example: 1) For any two propositions p,q , prove that

( p → q ) ≡ ¬p ∨ q .Hence

rewrite the

following statement without using the conditional “ If I have enough money, then I will buy a car”. p T T F F In view of the result just proved ,

p→q q T T F F T T F T the equivalent

¬p F F T T version

¬p ∨ q T F T T of the conditional “ If I have enough

money, then I will buy a car” reads thus, “ If I donot have enough money or I will buy a car”. 2) Prove the following statements are equivalent (1) It is not the case thjat boys are dull and girls are not hard working (2) Boys are not dull or girls are hard working. Consider the propositions: p: Boys are dull q: Girls are hard working. Then the first of the given statements is the compound proposition ¬[ p ∧ ¬q ] .This is equivalent to ¬p ∨ q . When written in words, this compound proposition reads: boys are not dull or girls are hard working. This is indeed the second of the given statements. 3) Write down the negation of the following proposition “ If x is an integer, then x is a rational number”

Prepared by Dr. K. V. Prasad, E-mail:[email protected], 9448687862

13

BITS-WIPRO Collaborative Programme: MS in Software Engineering, ( I Semester)

Solution: The given proposition reads p → q where p: x is an integer, q: x is a rational number. Therefore according to the result ¬[ p ∧ ¬q ] ≡ p ∧ (¬q ) therefore the negation of the given proposition reads “If x is an integer and x is not a rational number”. 4) Write down the negation of the following statement “ If x is not a real number then it is not a rational number and not an irrational number”. Solution: p: x is a real number, q: x is a rational number r: x is an irrational number. Then the given proposition has the following symbolic form ¬p → (¬q ∧ ¬r ) ¬p → (¬q ∧ ¬r ) ≡ ¬p [¬(¬q ∧ ¬r )]

≡ ¬p [¬¬q ∨ ¬¬r ] ≡ ¬p ∧ (q ∨ r )

Thus the negation of the given proposition reads “ x is not a real number and it is a rational or an irrational number” Converse, Inverse and Contra positive

Consider a conditional p → q .Then (1) q → p is called the converse of p → q (2) ¬p → ¬q is called the inverse of p → q (3) ¬q → ¬p is called the contrapositive of p → q . Example: Test the validity of the following arguments (1) If two sides of a triangle are equal, then the opposite angles are equal Two sides of a triangle are not equal Therefore, the opposite angles are not equal. Solution: p: Two sides of a triangle are equal,

q: The opposite angles are equal. Then the

argument is symbolically expresses in the following form [( p → q ) ∧ ¬p ] → ¬q and prepare the following table p q p → q r ≡ [( p → q ) ∧ ¬p ] T T T F T F F F F T T T F F T T Test the validity of the following argument

r → ¬q T T F T

If I study I will not fail in the examination If I donot watch TV in the evenings,I will study I failed in the examination Therefore, I must have watched TV in the evenings

Prepared by Dr. K. V. Prasad, E-mail:[email protected], 9448687862

14

BITS-WIPRO Collaborative Programme: MS in Software Engineering, ( I Semester)

Solution: p: I study q: I fail in the examination

r: I watch TV in the evenings. Then the given

[( p → ¬q ) ∧ (¬r → p ) ∧ q ]→ r s = ( p → ¬q ) t = (¬r → p ) (s ∧ t ) ∧ q

argument may be symbolically expressed in the following form

p q r T T T F T F T T F F T F T F T T T F T F F T T F F T T T T T F T F T F F F F T T T F F F F T F F Consider the following argument: I will grade A in this course or I will not graduate If I donot graduate, I will join the army I got grade A Therefore I will not join the army. Solution: p: I get grade A in this curse, q: I donot graduate argument reads in the symbolic form p T T T T F F F F

q T T F F T T F F

r T F T F T F T F

r: I join the army. Then the given

{[( p ∨ q ) ∧ (q → r )] ∧ p}→ ¬r

s = p∨q T T T T T T F F

¬r F T F T F T F T

t = (q → r ) T F T T T F T T

(s ∧ t ) ∧ p T F T T F F F F

OPEN SENTENCES; QUANTIFIERS

In mathematical discussions, statements such as those given below are encountered (1)

x+3=5

(2)

x2<10

(3)

x divides 4

(4)

x =21/2.

These statements are not propositions unless the symbol x is specified. Statements of this kind are called open sentences and the unspecified symbols, such as x in the statements above , are called variables. Open sentences containing one variable x are denoted by p(x), q(x),etc. The truth set of an open sentence p(x) is denoted by T[p(x)]. If S is an replacement set for an open sentence p(x), the truth set T[p(x)] of p(x) is given by T[p(x)]= {x ∈ s / p ( x) is true} .The

Prepared by Dr. K. V. Prasad, E-mail:[email protected], 9448687862

15

BITS-WIPRO Collaborative Programme: MS in Software Engineering, ( I Semester)

complement

of

the

set

T[p(x)]

in

S

is

denoted

by

T’[p(x)].

It

follows

that

T’[p(x)]= {x ∈ s / p ( x) is false}. Quantifiers:

Consider the following propositions (2)

For every integer x, x2 is a non-negative integer

(1)

All squares are rectangles

(3)

Some determinants are equal to zero (4) There exists a function whose derivative is itself.

In these propositions , the words “all”,”Every”,”Some”, “There exists”, are associated with the idea of a quantity. Such words are called Quantifiers. It has to be noted that the phrases “ For all” and “For every” are equivalent phrases. The phrases “ for any” and “for each” are also used as equivalents of these phrases. The symbol ∀ denote all these phrases. Each of these equivalent phrases is called Universal Quantifier. The phrases “ For some-one”, “for atleast one” and “There exists” are equivalent phrases. The symbol ∃ denote all these phrases. Each of these equivalent phrases is called the Existential Quantifier. Truth value of an quantified Statement:

Rule:1

The statement ∀ x ∈ S , p(x) is true only when p(x) is true for each x ∈ S ; that is,

T[p(x)]=S. Rule.2

The statement ∃ x ∈ S , p(x) is false only when p(x) is false for every x ∈ S ; that is,

T[p(x)]= null set. Negation of the Quantified Statement

To Construct the negation of the quantified statement change the quantifier from universal to existential and vice versa and also replace the open sentence by its negation. Examples: 1. Find the negation of the proposition “ No rectangle is a square”. Solution: Now let S denote the set of all rectangles and p(x): x is a square. Then, the given proposition reads: ∀ x ∈ S , ¬p( x). The negation of this is ∃ x ∈ S , p ( x). or in words, “There exists a rectangle which is a square” or Some rectangles are squares. Example:2. Write down the following proposition in symbolic form and write its negation “ All integers are rational numbers and some rational numbers are not integers” Solution: Let p(x): x is a rational number, q(x)”x is an integer,

and Z: Set of all integers, q:

Set of all rational numbers.

Prepared by Dr. K. V. Prasad, E-mail:[email protected], 9448687862

16

BITS-WIPRO Collaborative Programme: MS in Software Engineering, ( I Semester)

Then, in symbolic form, the given proposition reads {∀ x ∈ z , p ( x)} ∧ {∃ x ∈ q, ¬q ( x)} . The negation of this is {∃ x ∈ z , ¬p ( x)} ∨ {∀ x ∈ q, q ( x)} . In words, this reads “ Some integers are not rational numbers or every rational number is an integer”. Methods of Proof

There are two standard methods of proving a conditional: Direct method or indirect method. The direct method of proving a conditional p → q has the following lines of argument. 1. Hypothesis: First assume that p is true. 2. Analysis: Starting with the hypothesis and employing the rules of logic and other known facts , infer that q is true. 3. Conclusion: p → q is true. The indirect method of proving a conditional p → q has the following lines of argument. The conditional p → q the contrapositive is ¬q → ¬p and that p → q and ¬q → ¬p are logically equivalent. In some practical situations, we first prove that the contrapositive

¬q → ¬p is true by direct method and then as a consequence we infer that the conditional p → q is true. This method of proving a conditional is called the indirect method of proof. Examples: Give a direct proof of the statement: “ The square of an odd number is an odd number”. Solution: Here the conditional to be proved as: If N is an odd number, then N2 is an odd number. Suppose that N is an odd number. Then N = 2k+1 for some integer k. Consequently, N2= (2k+1)2= 4k2+4k+1 we observe that the RHS is not divisible by 2 .This means that N2 is an odd number. The required result is thus proved by a direct proof. Example:2 Give an indirect proof of the statement: “ the product of two even integers is an even integer”. Here, the conditional to be proved is p → q , where, p: a and b are even integers and q: ab is an even integer. We first prove that the contrapositive ¬q → ¬p is true. Assume that ¬q is true. That is, assume that ab is not an even integer. This means that a is not divisible by 2 and b is not divisible by 2 .That is, a is not an even integer and b is not an even integer. This implies that the proposition “ a and b are even integers” is false. That is , p is false or equivalently

¬p

is true. We have thus proved the contrapositive statement

Prepared by Dr. K. V. Prasad, E-mail:[email protected], 9448687862

17

BITS-WIPRO Collaborative Programme: MS in Software Engineering, ( I Semester)

¬q → ¬p .Consequently, it follows that p → q is true; that is, the statement “if a and b are even integers, then ab is an even integer” is true.

Prepared by Dr. K. V. Prasad, E-mail:[email protected], 9448687862

18