CISC5400 Discrete Structures Spring 2017 Assignment 1 Due February 24 1. For each of the following sequences given recursively, write out the first five (or more if necessary) terms of the sequence. Use the idea developed in my lecture to discover a close formula for each sequence. (a) a1= 1; an = an-1 + (2n-1) (b) a1= -3; an = an-1 + 4n 2. Express each of the following sums using sigma notation: (a) 2+3+4+ ...+16+17+18 (b) 1/2 + 2/4 + 3/8 + 4/16 +5/32 3. Prove each of the following propositions: (a) If a divides b and a divides c, then a divides b+c. (b) If a divides b and a divides c, then a2 divides bc. 4. Solve each of these logic puzzles by using truth tables. (a) You come across three inhabitants of an island somewhere in Atlantic Ocean. A says, \"B or C is lying,\" B says, \"C is lying,\" and C says \"Both A and I are telling the truth.\" Who if anyone is telling the truth? (b) You come across three inhabitants of an island somewhere in Atlantic Ocean. A says, \"B and C are both lying,\" B says, \"Only one of the other two is lying,\" and C says \"At least one of us is lying.\" Who if anyone is telling the truth? (c) You come across three inhabitants of an island somewhere in Atlantic Ocean. A says, \"If B is lying, then so is C,\" B says, \"If C is lying, then so is A\" and C says \"If A is lying, the so is B.\" Who if anyone is telling the truth? 5. Use the letter f to represent the statement \"this person is female,\" a for \"this person is over age 30,\" and m for \"this person is a math major.\" Use these names along with the basic operations and (), or (), and not () to write each of the following English sentences with symbolic logic: (a) This person is a female math major over age 30. (b) Either this person is not female or this person is over age 30. 6. Use truth tables to check if each of the given pairs of symbolic logic statements are equivalent. (a) (q p) (p q) and p q (b) (p q) (q r) and (p r) q 1. 1) Solution a) a1 1; an an 1 (2n 1) a2 a1 (2 1 1) 1 3 4 2 2 a3 a2 (2 2 1) 4 5 9 32 a4 a3 (2 3 1) 9 7 16 4 2 a2 a4 (2 4 1) 16 9 25 52 an n 2 ..................................................... b) a1 3; an an 1 4n a2 a1 4 2 3 8 5 a3 a2 4 3 5 12 17 a4 a3 4 4 17 16 33 a5 a4 4 5 33 20 53 Homogenous solution Characteristic equation is m-1=0 =>m=1 Therefore, homogenous solution is an c1 (1)n c1 Particular solution Here f(n)=4n Since homogenous solution contain constant term. Therefore, particular solution is an cn 2 dn an 1 c(n 1) 2 d ( n 1) cn 2 2cn c dn d an an1 4n cn 2 2cn c dn d dn d 4n 2cn d c 4n On equating both side same coefficient, we get 2c=4 =>c=2 and d-c=0 and d=2 Therefore, particular solution is anp 2n 2 2n Therefore, general solution is an c1 2n 2 2n a1 3 3 c1 2 2 c1 7 an 7 2n 2n 2 This is required closed form. ...................................................................................... 2) a) 18 2 3 4 16 17 18 n n2 b) 5 1 2 3 4 5 n n 2 4 8 16 32 n 1 2 ......................................................................... 3) a) since a divides b and a divides c b=al and c=am Adding both where l,m are integers. (Because l and m are integers so l+m is also integer.) b c al am b c a (l m) a divides b+c .......................... b) Since a divides b and a divides c => b=al and c=am where l, m are integers. Multiply both, we get (Because l and m are integers so lm is also integer.) bc a 2lm a2 divides bc ................................................................. 4) Let p: A is truthful q: B is truthful r: C is truthful a) p q r T T T T F F T T F F T T T F T F T F p F F F F T T q F F T T F F r F T F T F T q r F T T T F T pr T F T F F F F F F F T F T T T T F T T T F F From last three columns not all entries of single row are T. Therefore statements are not consistent. No one is telling truth. ................................... b) p q r T T T T F F F F T T F F T T F F T F T F T F T F p r q F F F F T T T T F F T T F F T T F T F T F T F T q r F F F T F F F T pr F T F T T F T F ( p q r ) F T T T T T T T Clearly statements are consistent (check blue line all T). A is telling truth (p has value T) ....................................................... c) p q r T T T T F F F F T T F F T T F F T F T F T F T F p F F F F T T T T q F F T T F F T T r F T F T F T F T q r r p p q T T F T T T F T T F T F T T T T T T T T F F T T All are telling truth or all are telling lie. ............................................................................ 5) a) b) am f a ................................................................................... 6) p q T T F F T F T F p q q p p q p q (p q) (q p ) F F T T F T F T F T F F F F T T F T T T F T T T Clearly, last and second last columns have same truth values. Therefore, both statements are equivalent. ...................................................................... b) p q r T T T T F F T T F F T T T F T F T F pq T T T T T T qr T T T F T T pr ( p q) ( q r ) T T T F T T ( p r) q T F T F F F T T T F T T F F F F T F F F T F F F ................................................................................. F F F F 1) Solution a) a1 1; an an 1 (2n 1) a2 a1 (2 1 1) 1 3 4 2 2 a3 a2 (2 2 1) 4 5 9 32 a4 a3 (2 3 1) 9 7 16 4 2 a2 a4 (2 4 1) 16 9 25 52 an n 2 ..................................................... b) a1 3; an an 1 4n a2 a1 4 2 3 8 5 a3 a2 4 3 5 12 17 a4 a3 4 4 17 16 33 a5 a4 4 5 33 20 53 Homogenous solution Characteristic equation is m-1=0 =>m=1 Therefore, homogenous solution is an c1 (1)n c1 Particular solution Here f(n)=4n Since homogenous solution contain constant term. Therefore, particular solution is an cn 2 dn an 1 c(n 1) 2 d (n 1) cn 2 2cn c dn d an an 1 4n cn 2 2cn c dn d dn d 4n 2cn d c 4n On equating both side same coefficient, we get 2c=4 =>c=2 and d-c=0 and d=2 Therefore, particular solution is anp 2n2 2n Therefore, general solution is an c1 2n 2 2n a1 3 3 c1 2 2 c1 7 an 7 2n 2n 2 This is required closed form. ...................................................................................... 2) a) 2 3 4 16 17 18 18 n n2 b) 5 1 2 3 4 5 n n 2 4 8 16 32 n 1 2 ......................................................................... 3) a) since a divides b and a divides c b=al and c=am Adding both b c al am b c a(l m) where l,m are integers. (Because l and m are integers so l+m is also integer.) a divides b+c .......................... b) Since a divides b and a divides c => b=al and c=am where l, m are integers. Multiply both, we get bc a 2lm (Because l and m are integers so lm is also integer.) a divides b c 2 ................................................................. 4) Let p: A is truthful q: B is truthful r: C is truthful a) 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 p F F F F T T T T q F F T T F F T T From last three columns not all entries of single row are T. Therefore statements are not consistent. No one is telling truth. ................................... r F T F T F T F T q r F T T T F T T T pr T F T F F F F F b) p T T T T F F F F q T T F F T T F F p r T F T F T F T F F F F F T T T T q F F T T F F T T r F T F T F T F T q r F F F T F F F T pr F T F T T F T F ( p q r ) F T T T T T T T Clearly statements are consistent (check blue line all T). A is telling truth (p has value T) ....................................................... c) 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 p F F F F T T T T q F F T T F F T T r F T F T F T F T q r r p T T F T T T F T T F T F T T T T All are telling truth or all are telling lie. ............................................................................ 5) a) a m b) f a ................................................................................... p q T T T T F F T T 6) p T T F F q T F T F p F F T T q q p F T F T F T F F p q (p q) (q p) p q F F T T F T T T F T T T Clearly, last and second last columns have same truth values. Therefore, both statements are equivalent. ...................................................................... b) p q r T T T T F F F F T T F F T T F F T F T F T F T F pq T T T T T T F F qr T T T F T T T F pr ( p q) (q r ) T T T F T T F F ................................................................................. T F T F F F F F ( p r) q T T T F T T F F 1) Solution a) a1 1; an an 1 (2n 1) a2 a1 (2 1 1) 1 3 4 2 2 a3 a2 (2 2 1) 4 5 9 32 a4 a3 (2 3 1) 9 7 16 4 2 a2 a4 (2 4 1) 16 9 25 52 an n 2 ..................................................... b) a1 3; an an 1 4n a2 a1 4 2 3 8 5 a3 a2 4 3 5 12 17 a4 a3 4 4 17 16 33 a5 a4 4 5 33 20 53 Homogenous solution Characteristic equation is m-1=0 =>m=1 Therefore, homogenous solution is an c1 (1)n c1 Particular solution Here f(n)=4n Since homogenous solution contain constant term. Therefore, particular solution is an cn 2 dn an 1 c(n 1) 2 d ( n 1) cn 2 2cn c dn d an an1 4n cn 2 2cn c dn d dn d 4n 2cn d c 4n On equating both side same coefficient, we get 2c=4 =>c=2 and d-c=0 and d=2 Therefore, particular solution is anp 2n 2 2n Therefore, general solution is an c1 2n 2 2n a1 3 3 c1 2 2 c1 7 an 7 2n 2n 2 This is required closed form. ...................................................................................... 2) a) 18 2 3 4 16 17 18 n n2 b) 5 1 2 3 4 5 n n 2 4 8 16 32 n 1 2 ......................................................................... 3) a) since a divides b and a divides c b=al and c=am Adding both where l,m are integers. (Because l and m are integers so l+m is also integer.) b c al am b c a (l m) a divides b+c .......................... b) Since a divides b and a divides c => b=al and c=am where l, m are integers. Multiply both, we get (Because l and m are integers so lm is also integer.) bc a 2lm a2 divides bc ................................................................. 4) Let p: A is truthful q: B is truthful r: C is truthful a) p q r T T T T F F T T F F T T T F T F T F p F F F F T T q F F T T F F r F T F T F T q r F T T T F T pr T F T F F F F F F F T F T T T T F T T T F F From last three columns not all entries of single row are T. Therefore statements are not consistent. No one is telling truth. ................................... b) p q r T T T T F F F F T T F F T T F F T F T F T F T F p r q F F F F T T T T F F T T F F T T F T F T F T F T q r F F F T F F F T pr F T F T T F T F ( p q r ) F T T T T T T T Clearly statements are consistent (check blue line all T). A is telling truth (p has value T) ....................................................... c) p q r T T T T F F F F T T F F T T F F T F T F T F T F p F F F F T T T T q F F T T F F T T r F T F T F T F T q r r p p q T T F T T T F T T F T F T T T T T T T T F F T T All are telling truth or all are telling lie. ............................................................................ 5) a) b) am f a ................................................................................... 6) p q T T F F T F T F p q q p p q p q (p q) (q p ) F F T T F T F T F T F F F F T T F T T T F T T T Clearly, last and second last columns have same truth values. Therefore, both statements are equivalent. ...................................................................... b) p q r T T T T F F T T F F T T T F T F T F pq T T T T T T qr T T T F T T pr ( p q) ( q r ) T T T F T T ( p r) q T F T F F F T T T F T T F F F F T F F F T F F F ................................................................................. F F F F 1) Solution a) a1 1; an an 1 (2n 1) a2 a1 (2 1 1) 1 3 4 2 2 a3 a2 (2 2 1) 4 5 9 32 a4 a3 (2 3 1) 9 7 16 4 2 a2 a4 (2 4 1) 16 9 25 52 an n 2 ..................................................... b) a1 3; an an 1 4n a2 a1 4 2 3 8 5 a3 a2 4 3 5 12 17 a4 a3 4 4 17 16 33 a5 a4 4 5 33 20 53 Homogenous solution Characteristic equation is m-1=0 =>m=1 Therefore, homogenous solution is an c1 (1)n c1 Particular solution Here f(n)=4n Since homogenous solution contain constant term. Therefore, particular solution is an cn 2 dn an 1 c(n 1) 2 d (n 1) cn 2 2cn c dn d an an 1 4n cn 2 2cn c dn d dn d 4n 2cn d c 4n On equating both side same coefficient, we get 2c=4 =>c=2 and d-c=0 and d=2 Therefore, particular solution is anp 2n2 2n Therefore, general solution is an c1 2n 2 2n a1 3 3 c1 2 2 c1 7 an 7 2n 2n 2 This is required closed form. ...................................................................................... 2) a) 2 3 4 16 17 18 18 n n2 b) 5 1 2 3 4 5 n n 2 4 8 16 32 n 1 2 ......................................................................... 3) a) since a divides b and a divides c b=al and c=am Adding both b c al am b c a(l m) where l,m are integers. (Because l and m are integers so l+m is also integer.) a divides b+c .......................... b) Since a divides b and a divides c => b=al and c=am where l, m are integers. Multiply both, we get bc a 2lm (Because l and m are integers so lm is also integer.) a divides b c 2 ................................................................. 4) Let p: A is truthful q: B is truthful r: C is truthful a) 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 p F F F F T T T T q F F T T F F T T From last three columns not all entries of single row are T. Therefore statements are not consistent. No one is telling truth. ................................... r F T F T F T F T q r F T T T F T T T pr T F T F F F F F b) p T T T T F F F F q T T F F T T F F p r T F T F T F T F F F F F T T T T q F F T T F F T T r F T F T F T F T q r F F F T F F F T pr F T F T T F T F ( p q r ) F T T T T T T T Clearly statements are consistent (check blue line all T). A is telling truth (p has value T) ....................................................... c) 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 p F F F F T T T T q F F T T F F T T r F T F T F T F T q r r p T T F T T T F T T F T F T T T T All are telling truth or all are telling lie. ............................................................................ 5) a) a m b) f a ................................................................................... p q T T T T F F T T 6) p T T F F q T F T F p F F T T q q p F T F T F T F F p q (p q) (q p) p q F F T T F T T T F T T T Clearly, last and second last columns have same truth values. Therefore, both statements are equivalent. ...................................................................... b) p q r T T T T F F F F T T F F T T F F T F T F T F T F pq T T T T T T F F qr T T T F T T T F pr ( p q) (q r ) T T T F T T F F ................................................................................. T F T F F F F F ( p r) q T T T F T T F F