SUPPLEMENTARY NOTES AND EXERCISES
pdf
keyboard_arrow_up
School
The Hong Kong University of Science and Technology *
*We aren’t endorsed by this school
Course
271
Subject
Mathematics
Date
Nov 24, 2024
Type
Pages
15
Uploaded by JusticeNeutronCapybara57
8 SUPPLEMENTARY NOTES AND EXERCISES The numbering of the sections here refers to the earlier paragraph which the section could have followed immediately. 1.3/1 Exercise. Is a set of coplanar vectors closed under the opera-
tion of (i) addition (ii) subtraction (iii) vector products (iv) scalar products? 1.6/1 Exercise. A,(a.cosa,b.sina) and B,(a.cosf3,b.sinf3) are two points on the ellipse x
2
fa
2 + y
2
Jb
2 = 1. Find the equation of the chord joining them. What fact, other than the Commutative Law, is required to show that the chord AB is the same as the chord BA ? 1.6/2 Exercise. For line joining A, (x', y') to B, (x", y") show that the line BA is the same. 1.16/1 Exercise. If a, b, c are non-zero numbers, and satisfy the Distributive Laws, then a+b+c=l 1.22/1 Show that, in the following statements, another true state-
ment is obtained by interchanging the words 'equal' and 'parallel': 'Lines that are parallel to the same line are parallel to each other.' 'A quadrilateral is a parallelogram if it has both pairs of opposite sides equal.' 'The lines joining the extremities of equal and parallel lines arc themselves equal.' Show that this is not a true example of duality, by giving examples of true statements which lead thus to false ones. 1.22/1 Exercise. A figure is defined by an ordered series of n vertices A
1
, A
2
, •.• , A,., no three of which are collinear. Pairs of con-
secutive vertices are joined to form the n sides of the figure, and the 52 A. P. Bowran, A Boolean Algebra
© A. P. Bowran 1965
SUPPLEMENTARY NOTES AND EXERCISES 53 lines joining the non-consecutive pairs of vertices form the n(n -
3)/2 diagonals. Interchanging the words 'sides' and 'vertices', and putting 'inter-
sections' for 'diagonals', write down the dual statement, and draw figures for both when n = 5. 1.22/2 Exercise. A quadrilateral consists of its four sides a, b, c, d; six vertices (ab), (ac), ..
. , and the diagonal triangle formed by joining pairs of the three points (ab, cd), (ac, bd), (ad, be). Describe and draw the dual figure. 1.25/1 Exercise. Use 1.23, 1.24, 1.4, to prove that 0' = 1 and 1' = 0. 1.25/2 Exercise. Write down the duals of the following statements: (i) Au A= A (ii) Au 1 = 1 (iii) (A u B) n (A u B') = A (iv) (Au B u C') n (Au B u C) = A u B (v) A u B u (A' n B') = 1 (vi) A n (A' u B) = A n B 1.25/3 Exercise. From 1.23 prove 1V0=1 Onl=O 0U0=0 1 n 1 = 1 1.27/1 Exercise. If a, b, c ... are numbers, and we write a F b to mean 'a is a factor of b', which of the laws of 1.27 are true when we write F in place of = ? 2.4/1 Exercise. Prove what you can from the postulates given in 2.3. 2.9/1 Exercise. Prove that: (i} X u Y u (X n A) u (Y n B) = X u Y (ii) X u (X n Y) u (X n Y n Z) = X (iii) A+ A.B + A.B.C + A.B.C.D.E.F.G =A (iv) (A+ B).(A + B + C).(A + B + C +D)= A+ B 2.10/1 Exercise. Prove (7), A U A = A, without using (8). (Hint-
A = A u 0 = A u (A n A') = ... ) 2.16/1 Exercise. Simplify: (i) (A.B + C)' (ii) X + Y + X'. Y'. Z (iii) Au B u C u (A' n B' n C' n D) (iv) (X + X. Y + X'. Z)'
54 A BOOLEAN ALGEBRA (v) (An B') u (A' n B) (vi) [{(A + B)' + A}' + B]' (vii) P.Q.R.S' + P'.R + Q'.R + R.S 2.19/1 Exercise. (i) If A.X = A.Y and A' .X= A' .Y, then X= Y (ii) If A + X = A + Y and A' + X = A' + Y, then X = Y 2.22/1 Exercise. Express (a) without the + sign and (b) without the (.) sign, the following: (i) A+ B.C.(B +D) (ii) (A+ B').(B' + C).(C +A') (iii) (X + X. Y + X'. Z)' 2.29/1 Exercise. Express as polynomials: (i) (A.C + B.C')' (ii) (X n Y')' u Y 2.30/1 Exercise. Show that, for the disjunctive normal form of expressions in the n elements A
1
, ••• , An: (i) The product of any two different terms is 0. (ii) If all the A's are given the value 0 or the value 1, show that there is one and only one set of values that will give any one term of F n the value 1. (iii) To every expression in the A's there corresponds one and only one disjunctive normal form. (iv) If a disjunctive normal form P, has m terms, then them sets of values, 0 or 1, of the A's which give P the value of 1, will determine P uniquely. (v) From n A's we can form a total of 2
2
n different expressions. 2.30/2 Exercise. Find the disjunctive normal forms of: (i) Xu Y (ii) Xu Y U Z (see 2.30, exercise) (iii) A.B + B'.C' 2.30/3 The reduction of this form of expression to some simpler equivalent expression is particularly useful in work on wiring diagrams. Example. Find a simple expression for E = A.B.C + A'.B.C + A.B'.C + A.B'.C' + A'.B'.C. + A'.B'.C'
Your preview ends here
Eager to read complete document? Join bartleby learn and gain access to the full version
- Access to all documents
- Unlimited textbook solutions
- 24/7 expert homework help
SUPPLEMENTARY NOTES AND EXERCISES E' = A.B.C' + A'.B.C' = B.C' .(A+ A') = B.C' E = B' + C 2.30/4 Exercise. Simplify: (i) A.B +A' .B +A' .B' (ii) Y.Z + Y'.Z' + Y'.Z + Y.Z' (iii) P. Q. R + P. Q'. R + P. Q'. R' + P'. Q'. R (iv) A'.B.C + A.B.C' + A'.B.C' + A'.B'.C' 2.43/1 Exercise. Prove that: (i) (A~B)~C = A~(B~C) = (A~C)~B (ii) (A~ B)~ (C~ D)= (A~ C)~ (B~ D) = (A~D)~(B~C) (iii) If A~ B = 0, then A = B (iv) (A + X)~ (A + Y) = A'. (X~ Y) 55 2.30/1 (iii) (12) (v) (A + X)~ (A + Y) ~(A + Z) = A' + (X~ Y ~ Z) (vi) (A.X)~(A.Y)~(A.Z) = A.(X~Y~Z) 2.43/2 Exercise. Four variables, A, B, C, D can each take only the values 0 or 1. Z is a function of A, B, C, D which takes the value 1 if, and only if, an even number of the elements A, B, C, D are equal to 1. Show that Z = (A~B~C~D)' What is the corresponding function if we change the word 'even' to 'odd'? 3.2/1 Exercise. Name sets that P could be if n(P) is: (i) 4 (ii) 5 (iii) 11 (iv) 12 (v) a large, but finite number (vi) an infinite number. 3.2/2 Exercise. What is n(R) where R is the soa routes from A to B along roads represented by lines in the diagram, if movement is always in a northerly or an easterly direction? A
56 A BOOLEAN ALGEBRA 3.4/1 Exercise. Name the third set in each of the following: (i) l = the soa Members of Parliament C = , , , the House of Commons C'= " (ii) R = , , rational numbers R' = " " irrational , 1 = ? " " . (iii) A= {Tom, Dick, and Harry} A' = {Jack and Jill} 1 = ? (iv) 1 = {a, b, c, d, e} P = {a, b, c, d} P' =? (v) 1 = the soa prime numbers Q = , , odd primes Q' =? 3.5/1 Care must be taken with the word or, which can be translated into the language of sets in various ways; these can be seen by con-
sidering the following passages: (I) 'The girl I marry must be good-looking or a good cook.' (II) 'I will wear a cap or a trilby hat.' (III) 'All members of the school, whether boys or girls, must attend on Sports Day.' In (I) we have an example of the 'inclusive or'-she must be good-
looking, or a good cook, or both, i.e. she must be a member of (L u C), where and L = the soa good-looking girls C = , , good cooks (II) differs from this in an obvious way, for he intends to wear one or the other, but not both. So, if D = the soa men wearing a cap and T = , , , , trilby hat he will be a member of the set (D u T) n (D n T)' = (D n T') u (D' n T) = DAT (D or T, and not D and T) 2.43 (iii)
SUPPLEMENTARY NOTES AND EXERCISES 57 Example (III) is again different. If B = the soa boys, and G = the soa girls, then the set (B n G) is an empty set. If here we are regard-
ing the soa members of the school as 1, the universal set, then B u G + 1 and B n G = 0 and so, by (4) and (4D) we have B = G' Otherwise, if BuB # 1, we have (BuG) = [B n (G u G')] u [G n (BuB')] (4, 6) = (B n G) u (B n G') u (G n B) u (G n B') (2) = (B n G') u (B' n G) (3) since 3.5/2 Exercise. Classify the use of or as similar to its use in (I), (II), (III), above, as used or implied in the following: (a) 'Candidates should have passed 'A' level in Mathematics or Physics.' (b) His wife had bought him two ties for Xmas; he wore one on Xmas Day; she burst into tears and said, 'I felt, somehow, that you didn't like the other one I' (c) 'Did you cross the Channel by boat or 'plane?' (d) '£1,000 REWARD for----, dead or alive.' (e) 'Over-drive is an optional extra.' 3.5/3 and also has its dangers. If B = the soa black minstrels and \V = , , white " then the 'Black and White Minstrels' are not members of the set (B n W), for this is the set of minstrels that are both black and white, i.e., an empty set. 3.9/1 Exercise. Prove that: (i) If A £ B for all A, then B = 1 (ii) ..............
B, then A = 0 (iii) .......
, then A. B = A. What can you deduce from Example 2.28? Prove it. 3.13/1 Exercise. From the statements: 3 (i) All racing motorists are quick-witted. (ii) Plato was a profound thinker.
Your preview ends here
Eager to read complete document? Join bartleby learn and gain access to the full version
- Access to all documents
- Unlimited textbook solutions
- 24/7 expert homework help
58 A BOOLEAN ALGEBRA (iii) All philosophers are profound thinkers. (iv) Nobody is both quick-witted, and also a profound thinker. can it be deduced that: (a) Plato was a philosopher (b) , , not a racing motorist? Prove your deductions. 3.13/2 Another notation for sets, usually for sets of numbers, in-
volves the use of {} to represent the set, and of I meaning 'such that'; so we have {n I n is a positive integer} read as 'the set of all n, such that n is a positive integer', and then {x I x = 2n -
1} is the soa positive odd numbers and similarly {x I x = n
2
} is the soa squares 3.13/3 Exercise. Express in this notation the following sets of num-
bers: (i) 1, 2, 4, 8, 16, .. . (ii) 1, 4, 7, 10, 13, .. . (iii) 1, 2, 6, 24, 120, .. . 3.13/4 Note that, although the members of a set are not arranged in any order, there is nothing to stop us thinking about them in an order, if that helps us. The soa acute angles {a), can be written {a I 0 < a < 7Tj2} and then the soa obtuse angles can be written as or as {,8 I ,8 = a + 7T/2} {,8 I ,8 = 7T -
a} and we see that, if the a's in the soa acute angles are arranged in ascending order of magnitude, then so will the first set of obtuse angles be, but that the second will be in descending order. 3.13/5 Exercise. Express in words: (i) {xI x = n(n + 1)/2} (ii) {xI -
1 < x < + 1} (iii) {x I x > 0}
SUPPLEMENTARY NOTES AND EXERCISES 59 3.13/6 Another symbol in common use is E, meaning 'is a member of' thus 2793 E {x I x = 3n} or z E (A n B) iff z E A and also z E B Care must be taken to distinguish between the statements a E {a, b, c} and {a} c {a, b, c} which are both true, and a c {a, b, c} which is not true. Exercise. Given three sets, A, B, C: (i) If A c B and B c C, is A c C? (ii) , A E B and B E C, is A E C? 3.13/7 The concept of the subsets of a set leads to an easy example of a lattice, an arrangement of a set and its subsets, in such a way that a line sloping down the page joins a set to its subsets, thus {p.q.r.s} { } 3.13/8 Exercise. (i) Construct the lattice for {a, b, c}. How many such figures are contained in the figure of 3.13/7? (ii) How many vertices has such a lattice for a set with n members? 3.13/9 Exercise. For stage lighting on cycloramas, back-cloths, etc., 'colour addition' is used. Three colours, 'primary red', 'primary
60 A BOOLEAN ALGEBRA green', and 'primary blue', are used together at strengths controlled by dimmers, and often the colour obtained is made paler by adding unfiltered 'white' light. For experiment and demonstration, to a full-
strength colour or colours another is gradually added or subtracted. Show that a lattice for a set of four elements shows how to do this completely, and use it to write out a scheme that will explore all possible changes without any repetition. 3.13/10 Exercise. C
1 is a given circle, radius 4r, and L is a straight line whose distance from the centre of cl is z. s is the soa real circles, radius r, in the plane of C
1 and L. If X = {S I S touches C
1
} Y = {S I S touches L} find values of z such that n(X n Y) = 0, 1, 2, 4, 6, 7, 8 3.13/11 The co-ordinates, x, y, of a point in a Cartesian plane are well known. We vary the notation slightly, and write (x,y) to represent an 'ordered number pair' to stress the fact that here the order of the numbers does matter. 3.13/12 Exercise. (i) Sis a set of points in a Cartesian plane such that, if (x, y) E S, so is (y, x). What geometrical property has the figure? Similarly, describe figures for which (ii) If <x,y), then< -x, -y) (iii) .............
( -y, -x) (iv) .............
( -x, y) 3.13/13 Exercise. Give diagrams for the following sets of points: (i) A= {<x,y) llxl < 1 and IYI < 1} (ii) B = {(x,y) I y > x} (iii) C = {<x, y) 11 < x:~ + y:~ < 4} (iv) E = {<x, y) 11-! < x < 21; and 11 < y < 2·!} (v) An B 3.13/14 Exercise. If A = {(x, y) I x + y = 7} ~ B=«~~~~-y=~ find AnB (sometimes, called the intersection of A and B).
Your preview ends here
Eager to read complete document? Join bartleby learn and gain access to the full version
- Access to all documents
- Unlimited textbook solutions
- 24/7 expert homework help
SUPPLEMENTARY NOTES AND EXERCISES 61 3.13/15 Exercise. Extending this to three dimensions, if A= {(x,y,z) I x > O,y > O,z > 0} B = {(x, y, z) I x + y + z = 1} C = {(x,y,z) I x < j-,y < t,z < !} draw diagrams of (An B) and (An B n C). 3.13/16 Exercise. Express in the notation of 3.13/2 the following sets of points: (i) inside a triangle bounded by the axes, and the line x + y = 7 (ii) inside the parabola y
2 = 4ax and between the lines x = a and x = 2a (iii) above the line x + y = 1, but less than one unit length from the origin In each case give a rough sketch. 3.13/17 Exercise. Describe in words {xI x -:;6 x} 3.17/1 Exercise. From All men who are Europeans, or fair, but not both, are good-
tempered. All Europeans are tall, or fair, or both. All dark Europeans are short. Prove that all bad-tempered, fair people are Europeans. 3.17/2 Use the language of sets to clarify the following: (i) Four tailors had shops in the same street of a Chinese town. The first one advertised 'I am the best tailor in town'. The second went one better and announced, 'I am the best tailor in China'. The third said, 'I am the best tailor in the world', and the fourth claimed, 'I am the best tailor in the street'. (ii) Extract from electioneering speech 'If my party is returned to power, we will see to it that every miner, yes, and every Welsh miner, gets full consideration from the government.'
62 A BOOLEAN ALGEBRA (iii) Conversation 'No nice little girl eats raw fish.' 'Angela eats raw fish.' 'Then Angela is not a nice little girl.' 'On no! Angela is my kitten.' (iv) Advertisement 'Ninety-nine dentists out of a hundred recommend "Kleener-
teef" .' (v) Address Mr. A. B. Charles, 73, Dover Road, East borough, Kent. 3.17/3 Exercise. Express the normally accepted meaning of the following phrases in the language of sets: (a) There's no good snake but a dead snake. (b) No dogs admitted unless led. (c) Children under 16, unless accompanied by an adult, are not admitted. (d) There's no smoke without a fire. (e) All that glisters is not gold. (f) Social Club Car Park-for members only. 3.21/1 The following is from Lewis Carroll. 'In a very hotly fought battle, at least 70% of the combatants lost an eye, at least 75% lost an ear, at least 80% lost an arm, and at least 85% lost a leg.' How many lost all four members? 3.21/2 Exercise. Of a section of the population of a town, the following was the report. 'The number of immigrants was 87, of whom 51 were married, and 68 were in full employment; the total number of those fully employed was 290, and of them 160 were married. Of the 266 married people, 27 were employed immigrants.' Show that this is impossible.
SUPPLEMENTARY NOTES AND EXERCISES 63 3.32/2 We saw, in 2.38-2.41, that the 'solution' of an equation in X is usually expressed in the form A.X = B.X' = 0 A provided that A. B = 0. The notation of sets enables us to write this as B £ X £ A', if B £ A', and this Venn diagram makes clear the sort of limitation put on X by these equations. (Note that A' here is represented by the area inside the closed curve.) 3.32/3 Exercise. Illustrate the following identities by means of the Venn diagram: (i) A + A'. B = A + B (ii) A+ B.C =(A+ B).(A +C) (iii) (A + B)' = A'. B' (iv) (A' + B') = (A.B)' (v) X.Y + X'.Y' + X.Z = X.Y + X'.Y' + Y'.Z (see2.36) 3.32/4 Exercise. Repeat 3.32/3 for the Carroll diagram. 4.7/1 Exercise. Show that: (i) To each term of the complete disjunctive normal form there corresponds a region of the Venn diagram. (ii) To each term of the disjunctive normal form of a function there is one row of its truth table for which the function takes the value 1. (iii) A function is defined by its truth table. 4.7/2 Exercise. From these truth tables, find X, Y, Z as functions of A, B, C.
Your preview ends here
Eager to read complete document? Join bartleby learn and gain access to the full version
- Access to all documents
- Unlimited textbook solutions
- 24/7 expert homework help
64 A BOOLEAN ALGEBRA A B c I X y z 1 1 1 1 0 1 0 1 1 0 0 1 1 0 1 1 1 0 1 1 0 1 0 0 1 0 0 0 1 1 0 1 0 0 1 0 0 0 1 0 0 1 0 0 0 1 1 0 4.9f1 Exercise. If A is the statement 'men must work' and B 1s 'women must weep' express in words: (i) Au B = 1 (ii) A n B = 0 (iii) A' u B = 0 (iv) A~ B = 1 4.16/1 Exercise. Prove that: If (X u Y) ~ B, then X ....
-? B or Y ....
-? B 4.20/1 Exercise Statement A " " " " " B c D E F F is true and D is false One and only one of C and D is true. A and E are both true. Either C or F is true, or both. B and F are both true or both false. A, D, and E are all true. Which are true ? 5.17/1 Exercise. An adding machine consists of a half-adder and 12 adders. What is the largest total it can register? 6.12/1 Exercise. (i) 2 + 2 = 4. What is the probability of the truth of this if each of the three numbers is correct to the nearest whole number? (ii) Show that the answer to 3.13/12 (vii) gives the corresponding probability for 2. 2 = 4.
SUPPLEMENTARY NOTES AND EXERCISES 65 6.12/2 Exercise. The angles of a triangle are measured to the nearest degree, and added. What is the probability of an answer of 180°? Show that: (i) The angles can be written (A + at, (B + bt, (C + ct or (A' + a't, .
.. where capital letters are whole numbers and small letters are positive fractions, and A+ B + C = 179 a+b+c= 1 A' + B' + C' = 178 a'+ b' + c' = 2 (ii) If X = {(a, b, c) I 0 < a, b, c < 1, and a + b + c = 1} Y = {(a', b', c') I 0 < a', b', c' < 1, a' + b' + c' = 2} there is a one-to-one relation between the members of X and Y. (Put a' = 1 -
x). (iii) A member of X, (a, b, c), will provide an answer of 180 if one of a, b, cis greater than 1/2. (iv) The probability of an answer of 180 from X or Y is the same. (v) The answer to 3.13/15 gives the probability as 3/4, and a probability of 1/8 for 179° or 181°. (vi) Prove that the sum of the perpendicular distances to the sides of an equilateral triangle from a point inside it is constant and equal to the altitude of the triangle. (vii) By letting the altitudes of the triangle LMN in Fig. (i) rcpre-
L Fig. (i) sent 180 units, and denoting the perps. by a, {3, y we have a + fJ + y = 180 and so points P inside triangle LMN represent triangles whose angles are a
0
, {3°, y
0
• 4
66 A BOOLEAN ALGEBRA (viii) In Fig. (ii) continuous lines represent integral values of a, {3, y, and dotted lines are for to. Comparing with (i) we have Fig. (ii) a = A + a or A' + a', etc. Show that points in the areas shaded horizontally represented triangles with an answer of 179°, and in areas shaded vertically, 181°. (ix) Check that this gives the probabilities of the angle-sums as 179 181/1440 180 3/4 181 179/1440 (x) Explain the difference between the answers given in (v) and (ix).
Your preview ends here
Eager to read complete document? Join bartleby learn and gain access to the full version
- Access to all documents
- Unlimited textbook solutions
- 24/7 expert homework help