What is an algebra?
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
6
Uploaded by JusticeNeutronCapybara57
1 INTRODUCTION 1.1 What is an algebra? How can we form a new one, and how, then, can we use it? In this introductory chapter we try to answer these questions and to give a general idea of the subject. An algebra is concerned with elements and with operations, which we are careful not to define. They obey certain laws, called postulates, and from them we deduce theorems. Any meanings we may later give to these elements and operations will, if they satisfy the postulates, also satisfy all the theorems of the algebra. So, in Chapter 2 we develop a Boolean algebra and then go on to apply it to (1) sets, and probability (2) statements (3) circuits 1.2 Our elements will be represented by capital letters, A, B, C, ... , and operations by U and r. or by + and . , thus (A u B) and (A r. B) or (A+ B) and (A.B) These are called binary operations, because in each case two ele-
ments are involved; we have also a unary operation, which derives the element A' from the one element, A. For reasons that will be obvious later, we usually read Au B as A or B, and A r. B as A and B. 1.3 The set of elements of an algebra and its operations are such that, if A and Bare elements, so also are (A U B), (A r. B), and A'; the set of elements is then said to be closed under these operations. Exercise. Show that the set of the positive integers, which is closed under addition and multiplication, is not closed under subtraction nor under division. What set of numbers is closed under (i) subtrac-
tion (ii) division (iii) both? 1 A. P. Bowran, A Boolean Algebra
© A. P. Bowran 1965
2 A BOOLEAN ALGEBRA 1.4 The postulates of an algebra must be self-sufficient; no other assumption about the elements or the operations may be made. We will now consider some of these postulates as applied to arithmetic, and the algebra of numbers. The commutative law a+b=b+a a.b = b.a These statements appear trivial in the algebra of numbers, but they sometimes have their uses. 1.5 Exercise. Show that the chord joining the points (at
1, aft
1
) and (at
2
, aft
2
) on the rectangular hyperbola xy = a
2 is x + t
1
.t
2
.y-
a(t
1 + t
2) = 0 That the commutative law tells us that interchanging t
1 and t
2 in this equation does not alter its truth gives us a check on our working, for it follows from the fact that the line joining A to B is the same as the line joining B to A. 1.6 Exercise. A, (at~, 2at
1
), and B, (at~, 2at
2
), are two points on the parabola y
2 = 4ax. Apply the commutative law as a check on the equation of the chord AB and also on the co-ordinates of the point where the tangents at A and B meet. 1.7 Exercise. Show that the Commutative Law, which is true for addition and for multiplication, does not hold for division nor for subtraction. 1.8 The associative law (a+ b) + c = a + (b + c); (a.b).c = a.(b.c) This law is not a necessary assumption in the Boolean algebra we intend to develop, but it is included here because it seems so funda-
mental in the algebra of numbers. 1.9 Exercise. Is this law true for the operations of (i) subtraction (ii) division? 1.10 Example (a + b) + c = (b + a) + c = b +(a+ c) =(a+ c)+ b =etc. 1.4 1.8 1.4 and obviously we can arrange the letters a, b, c in any order we choose,
INTRODUCTION 3 and bracket which pair we like, without altering the value of the expression. This allows us to write it as a+b+c where addition is still a binary operation; this expression merely emphasises the ability to add the sum of any pair of the numbers to the remaining number. 1.11 Exercise. In a manner similar to 1.10, justify the expression a.b.c 1.12 Exercise. (i) Prove that (tl. t2). (t3. t4) = (tl. t3). (t2. t4) (ii) What is the corresponding statement for the operation of addition? 1.13 From 1.5, the chord joining the points t
1 , t
2 , is x + (t
1
.t
2
).y-
a.(t
1 + t
2) = 0 and the chord t
3
, t
4 is x + (t
3
.t
4
).y-
a.(t
3 + t
4) = 0 and they are perpendicular if (t1. t2). (t
3. t4) + 1 = 0 1.14 Exercise. Show that this and 1.12 (i) give the statement: 'The orthocentre of the triangle formed by three points on a rectangular hyperbola also lies on the same hyperbola.' 1.15 Exercise. A, B, C, Dare four points on a parabola. The tangents at A, B meet in L, those at C, D meet in M , , A, C , P, , B, D , Q , , A, D , R, , B, C , S and X, Y, Z are the midpoints of LM, PQ, RS. Use 1.6 and 1.12 (ii) to make a statement about XYZ. 1.16 The distributive law a.(b +c)= (a.b) + (a.c) a+ (b.c) =(a+ b).(a +c) While the former of these is familiar to us from the algebra of numbers, the latter is not! It comes naturally from the former if we follow the
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
4 A BOOLEAN ALGEBRA rule that was followed in the previous postulates, namely, to change a statement to its dual, we interchange the signs (.) and ( + ), or their equivalents {rl) and {U). We must also interchange the elements 0 and 1, if they occur. 1.17 The theory of duality is obviously very useful, for if, whenever we assume a postulate, we also assume its dual, then the dual of every theorem we prove will also be true. 1.18 Exercise. Write down the duals of the following statements: (i) a + a' .b = a + b (ii) (y + z).(z + x).(x + y) = y.z + z.x + x.y (iii) (a + b)' = a'. b' (iv) a.b + b.c + c.a' = a.b + c.a' 1.19 There exists an important duality between points and straight lines in a plane. If A, B, C ... are points and a, b, c ... are lines, we can see that the following pairs of statements are dual: two points A, B determine a straight line (AB) A, B, C are three points on m C is a point on the line AB two lines a, b, determine a point (ab) a, b, c are three lines through JVI c is a line through the point ab 1.20 Exercise. If X is a statement and Xa is its dual, prove that (Xa)a =X 1.21 Exercise. State the dual of the following theorem, and draw a figure to illustrate it. If A, B, C are three points on a straight line, J, and similarly for A', B', C' onj', and also BC' meets B' C in X CA' , C'A , Y AB' , A'B , Z then X, Y, Z lie on a straight line p. 1.22 Exercise. Desargues' theorem states that, if two triangles ABC and A'B'C' are such that AA', BB', CC' are concurrent, then the points of intersection of corresponding sides of these triangles are collinear. What is remarkable about its dual? 1.23 To each of the binary operations there corresponds an identity element, which is such that the operation by this element leaves the other element unaltered. These are, in the algebra of numbers, zero
INTRODUCTION 5 for the operation of addition and unity for the operation of multiplica-
tion, and we use the same symbols, 0 and 1, in other algebras. So these elements are, in fact, defined by the postulates, that there shall exist different elements, 0 and 1, such that A + 0 = A and that A. 1 = A, for all A. 1.24 The complementary element has no corresponding element in arithmetic. It gives A', the complement of A, satisfying A + A' = 1 A.A' = 0. We shall prove that A defines A' uniquely. 1.25 Exercise. Using this and 1.4, show that (A')'= A 1.26 Exercise. What are the identity elements for the operations of (i) subtraction (ii) division? 1.27 As nearly all the working we have done so far has been in the algebra of numbers, we have not had cause to examine the function of the = sign in other algebras. If we (see 1.1) are deliberately vague about the meaning of our elements and also our operations, 'equality' must be treated in the same way, and we 'define' the meaning of the = sign by some rules it must obey. These are (I) The Reflexive Law (II) The Symmetric Law Oil) The Transitive Law A=A If A = B, then B = A If A = B and B = C, then A = C This is the law that allows us to 'simplfy' an equation. For if A = B, and A, B have simpler forms A
1 = A and B
1 = B, then and so (IV) (IVD) A
1 =A =B B = B
1 Al = Bl If A = B, then A + C = B + C, and the dual If A= B, then A.C = B.C (III) (II) (Ill) It is very important to note that, unlike the algebra of numbers, the converse is not true-that is to say, that A + C = B + C does not imply that A = B, nor does A. C = B. C. We shall later prove if both A + C = B + C and also A. C = B. C, then A = B. (V) If A = B, then A' = B' 1.28 Exercise. From these laws prove that (i) If A= B, then (A. X)+ Y = (B.X) + Y (ii) If A = B, C = B, and A = Y, then Y = C
6 A BOOLEAN ALGEBRA 1.29 Exercise. Rewrite the postulates of 1.27 for the ~ sign in the algebra of numbers. 1.30 Exercise. Check whether the Commutative and Associative Laws hold for an algebra of four elements 0, 1, B, C, and two opera-
tions, @ and &, where results of these operations are given by the tables @ 0 1 B c & 0 1 B c --
--------
--
----------
0 0 1 B c 0 0 0 0 0 1 1 B c 0 1 0 1 B c B B c 0 1 B 0 B 0 B c c 0 1 B c 0 c B 1 It is usual, in tables of this sort, to take the first element from the top row and the second from the first column, e.g. B@ 1 = C B&C=B What geometrical property of the table follows from the Commutative Law? 1.31 Exercise. An algebra contains only two elements, 0 and 1, and two operators, nand U, and we know that duality applies. From the given table, complete the other. u 0 1 ------
0 0 1 1 1 1 n 1 0 1-------
1 0
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