REDISCOVER MATHEMATICS FROM 0 AND 1 BOOK 1: THE SWORD AND THE SHIELD Section 1: Identity, Division ,Symmetry Chapter 3:Symbolic logic, Mathematical logic and logic of signals 1 CHAPTER 3:SYMBOLIC LOGIC, MATHEMATICAL LOGIC AND LOGIC OF SIGNALS Boolean algebra is a mathematical structure designed by an undergraduate student in America, with a view to translate descriptive logic into the symbolic language of Algebra, so that large pieces of logic or multiple pieces of them could be handled mechanically instead of conjuring everything in mind . This was required before the advent of computer languages where may be millions of logical files are used in programming. Moreover in the development of electronics, thousands of tiny electrical circuits are used in integrated circuits or ICs. How they are formed and joined to one another -the question is addressed by Boolean Algebra, symbolic logic, Circuit logic, logical gates like 'Or' gate, 'AND' gate,' NOT gate, and gradually complicated combinations of them. This chapter is aimed at giving the bare fundamentals. §18:Boolean Algebra From the study of set theory you must be thinking that the operations like union, intersection, symmetric difference etc. have some algebraic structure underlying them . In case it is so, we can work out on them as if doing algebra and we could do some mechanical processing just as we do with equations with brevity. For example, equal thing added to equal things give equal results – is the underlying description of the process of transposition in equations. Imagine what a load of literature we had undergone if transposition had not been used in symbols !. Similarly, there is Boolean algebra in symbols, which not only takes care of set-theoretic operations but connects logical whole sentences in an useful manner also. An wonderful application of the subject is switching logic in electrical circuits. Definition -A Boolean algebra is non-empty set B with two binary operations defined in it, denoted by ‘ + ‘ and ‘ . ‘ ( in generalized sense, not always in arithmetic sense) , each having closure, associative, commutative properties, either operation being distributive over the other, not only ‘ . ‘ over ‘ + ‘ . but also vice versa. Also the operations assure an identity element , ‘0’ ( a symbol, not zero) of the operation ‘ + ‘ and ‘1’ , ( a symbol, not one), identity of ‘.’; and each member x in the set has a complement ( or negation of x), denoted by x’ such as x + x’ = 0 and x.x’ =0. In other words, a non-empty set B is a Boolean algebra, if, a) For ( for all) x, y ∈B, x + y ∈B and x.y ∈B, closure property of + and . b) For x, y ∈B, x + y = y + x and, x.y = y.x Commutative property of + and . c) For x, y, z ∈B, x+(y+z) = (x+y )+z , and (x.y).z = x.(y.z) both + and . associative. d) For x, y, z ∈B, x+(y.z) = (x+y ).(x+z) , and x.(y+z) = x.y + x.z both distributive. e) ∃( there exists) ‘0’ in B : (such that) x + 0 = x = 0 + x x ∈ B, ‘ 0 ‘ is called identity of +. f) ∃‘1’ in B : x .1 = x = 1.x x ∈ B, ‘ 1 ‘ is called identity of ‘.’. (The left identity is the same as the right identity because of commutative property; this is in case of both the operations.)REDISCOVER MATHEMATICS FROM 0 AND 1 BOOK 1: THE SWORD AND THE SHIELD Section 1: Identity, Division ,Symmetry Chapter 3:Symbolic logic, Mathematical logic and logic of signals 2 g) ∃x’ ∈B for each x ∈B, called complement or negation of x, : x + x’ = 1 , x . x’ = 0 Examples of the last property is relatively rare; at least it is not true in case B is the set of real numbers and if + and . stand for addition and multiplication respectively. Remember that the symbols ‘+’ and “.” are borrowed from Algebra to represent the binary operations they stand for, and not addition or multiplication. Still then we continue to ‘call’ the operation “+’ as ‘addition’ and ‘ . ‘ as ‘ multiplication’ Comparing with set theory, the operation ‘+’ is analogous to the set theoretic operation ‘U’ i.e., union and the operation ‘.’ Is analogous to the set theoretic operation ‘∩’i.e., intersection. The symbol ‘1’ in Boolean Algebra is analogous to the universal set in set theory and the symbol ‘0’ in Boolean Algebra is analogous to the null set (Φ) in set theory. Just watch ' , ' A A U A A This does not mean that everything in set theory is just translated into algebraic symbols and set theory may be dispensed with, never. The following examples shall illustrate which are Boolean algebra and which are not. Example1 Let P S be the set of all subsets in S. The operations ‘+’, ‘.’ and “ ’ ” are defined by , . , ' A B A B A B A B A S A verify that the structure , ,.,' , P S S is a Boolean algebra. This is Boolean Algebra of sets. Take A, B and C any three statements in S and write , for for And follow the above line of arguments. For an example which is not a Boolean algebra, see example 8 below. Not only the many instances of set theory, Boolean Algebra also takes care of a large part or symbolic logic or mathematical logic ( see example 6 below). First let us be familiar with some operators associated with symbolic logic or mathematical logic. §19:Symbolic logic Let us see the analogy of union and intersection operations in set theory and the connector operations disjunction (symbol , ‘or’) and conjunction (symbol , ‘and’), joining Statements (sentences) in mathematical logic or symbolic logic with ∪and ∩, joining sets in set theory. In symbolic logic, the symbol ‘c’ called ‘ contradiction’ plays the role of 0 in mathematics or φin set theory. If p denotes any statement, ~ p denotes negation of p which plays the role of complement A’ in set theory. The symbol t stands for tautology plays the role of 1 in mathematics or U , universal set in set theory .REDISCOVER MATHEMATICS FROM 0 AND 1 BOOK 1: THE SWORD AND THE SHIELD Section 1: Identity, Division ,Symmetry Chapter 3:Symbolic logic, Mathematical logic and logic of signals 3 REMEMBER a) Associativity A B C A B C in set theory is analogous to p q r p q r in symbolic logic. b) Associativity A B C A B C in set theory is analogous to p q r p q r in symbolic logic. c) commutativity A B B A in set theory is analogous to p q q p in symbolic logic. d) commutativity A B B A in set theory is analogous to p q q p in symbolic logic. e) distributivity A B C A B A C in set theory is analogous to p q r p q p r in symbolic logic. f) distributivity A B C A B A C in set theory is analogous to p q r p q p r in symbolic logic. g) Existence of identities A A in set theory is analogous to p c p in logic. h) Existence of identities A U A in set theory is analogous to p t p . in logic. i) Corresponding to complement law ' A A U in set theory there is ~ p p t in logic. j) Corresponding to complement law ' A A in set theory there is ~ p p c in logic. It should be observed that there is some similar algebraic structure underlying both set theory and symbolic logic . We can safely say that symbolic logic and set theory are both instances of Boolean Algebra under proper operation. To further emphasize and illustrate this point, see these typical examples.REDISCOVER MATHEMATICS FROM 0 AND 1 BOOK 1: THE SWORD AND THE SHIELD Section 1: Identity, Division ,Symmetry Chapter 3:Symbolic logic, Mathematical logic and logic of signals 4 k) De’ Morgan’s Laws : Corresponding to De’ Morgan’s Laws in set theory ' ' ' A B A B and ' ' ' A B A B we have ~ ~ ~ p q p q , and ~ ~ ~ p q p q . Example2 The operations ‘+’ and ‘.’ And “ ‘ “are defined on the set of all logical statements, S say; as , . , ' ~ p q p q p q p q p p . To show that , ,., ', , S c t is a Boolean algebra. A Boolean algebra is generally written in this manner, writing the set, the two binary operations, negation, contradiction and tautology in a bracket. We just verify a) . . p q q p as p q q p commutative property p q q p as p q q p b) . . . . p q r p q r as p q r p q p associative property p q r p q r as p q r p q r c) . . . . . p q r p q p r as p q r p q p r distributive property p q r p q p r as p q r p q p r d) A contradiction of every statement is a ‘ no statement’ ; denote it by 0 – it is also a statement which is in the set S this is precisely our ‘contradiction element’ c. Also there is a statement which accepts every statement . this is precisely the tautology element t and may be denoted by 1. Now it may be verified that 0 existence of identity elements for 0 and 1 .1 p p as p c p p p as p t p e) For each statement p in S, there exists ' ~ p p in S such that ' 1 p p as ' p p t (tautology) and . ' 0 p p as ' p p c , the contradiction element. This completes the proof. In logical statements one thing to note is that contradiction c plays the role of or null set in set theory and 0 in arithmetic . One may be confused to reconcile to it in the elementary stage and may ask how they are the same thing or equivalent. But the fact is, they are neither the same thing nor equivalent but REDISCOVER MATHEMATICS FROM 0 AND 1 BOOK 1: THE SWORD AND THE SHIELD Section 1: Identity, Division ,Symmetry Chapter 3:Symbolic logic, Mathematical logic and logic of signals 5 the corresponding things in proper context. Just remember that 0 and are neither same nor equivalent but they correspond. In the same manner, tautology t in logic corresponds to 1 in arithmetic and universal set U in set theory. Example3 Take 0,1 A and let the binary operations “+” and ‘.” and “ ‘ “ be defined as on the tables Table for ‘+’ + 0 1 0 0 1 1 1 1 Table for ‘.’ . 0 1 0 0 0 1 0 1 Table for “ ‘ “ ‘ 0 1 1 0 The tables for ‘+’ and “.” themselves restate the closure laws , for, result of combination of every member with every other is given and shown to be a member. Verify associative law with the help of the tables for the two binary operations. Note that “ ‘ “ is not an operation , but tabulates the existence of negation element for any element. Verify the distributive laws with the help of both the tables taken together , i.e., like 1. 1 1 1.1 1 1.1 1.1 1 1 1 1. 1 1 1.1 1.1 and distributive law for “.”. Similarly distributive law for “+’ may be verified. Also verify that the zero element of ‘+’ is 0 and unit element of ‘.” Is 1. The last table confirms existence of negation elements of every member, 0’ = 1 and 1’ = 0. Now everything is verified and the structure given is a Boolean algebra . Example4 Denote D4 the set of all divisors of 4, i.e. 4 1, 2,4 D . Define ‘+’ and ‘.’ as REDISCOVER MATHEMATICS FROM 0 AND 1 BOOK 1: THE SWORD AND THE SHIELD Section 1: Identity, Division ,Symmetry Chapter 3:Symbolic logic, Mathematical logic and logic of signals 6 least common multiple of , . greatest common divisor of , 4 complement 'of any element a is given by ' = a b a b a b a b a a a Show that 4 , ,.,',0,1 D is not a Boolean algebra Construct the tables of binary operations and complement list as Table for ‘+’ + 1 2 4 1 1 2 4 2 2 2 4 4 4 4 4 Table for ‘.’ . 1 2 4 1 1 1 1 2 1 2 2 4 1 2 4 Table for “ ‘ “ ‘ 1 2 4 4 2 1 Verify that criteria of Boolean algebra such as closure, associativity, commutativity are satisfied for both operations. Verify that the ‘unit element’ or ‘ identity of addition ‘ is 4 and the ‘zero element ‘ is ‘0’. To verify distributivity, note that 1 +( 2.4) = 1 + 2 = 2 using tables for ‘addition’ and ‘multiplication’. Also verify similarly (1 + 2). ( 1 + 4) = 2.4 =2; so 1 + ( 2.4 )= (1 + 2).(1 + 4 ). So the distributive law of + over . are verified. To verify distributivity of ‘ . ‘ over ‘ + ‘ note that 1.(2+4)=1.4=1 and (1.2)+(1.4)=1+1=1; so we get, 1.(2+4)=(1.2)+(1.4). So both the distributive laws are verified. To find out complements, note that 1’ = 4 ( unit element of 4 D ) and 1.4 = 1 (zero element of 4 D ). So 4’ =1. From the table for “ ‘ “ we get 2’ =2. But from the other tables 2 + 2’ = 2 + 2 =2 nor 4.REDISCOVER MATHEMATICS FROM 0 AND 1 BOOK 1: THE SWORD AND THE SHIELD Section 1: Identity, Division ,Symmetry Chapter 3:Symbolic logic, Mathematical logic and logic of signals 7 And 2.2’ = 2.2 =2 , not 1. Thus 2’ is not 2. This is a contradictory result . Thus the structure is not a Boolean algebra. Exercise1 If 6 D is the set of divisors of 6 and + means lcm of two numbers and ‘.’ means GCD of the numbers, 6 complement 'of any element a is given by ' = a a a , show that the structure is a Boolean algebra. Exercise2 Show that 8 D is not a Boolean algebra , D8 defined as the set of divisors of 8 and the operations and complement define as : ‘+’ means LCM, ‘.’ means GCD and complement 8 ' = a a Exercise3 If 1,2 S P the power set of 1,2 , the binary operations ‘+’ stands for union, ‘.’ Stands for intersection, ‘ stands for complement, null set stands for 0 element and the set 1,2 stands for unit element 1, show that the structure is a Boolean algebra. Exercise4 Do the above exercise for 1,2,3 in place of 1,2 . Exercise5 For a set 1,2,3,........ n S the binary functions ‘+’ is defined as max , x y x y , the ‘.’ Function is defined as . min , x y x y , verify that conditions of closure, associativity, commutativity are satisfied. Exercise6 (remember) In any Boolean algebra, the identity elements are unique. Proof : If not, let 0 be another identity element 0 . Since both are identities, 0 0 0 and 0 0 0 . Since ‘+’ is commutative, 0 0 0 0 . This implies 0 0 , i.e. the identity element is unique. Similarly prove 1 1 REDISCOVER MATHEMATICS FROM 0 AND 1 BOOK 1: THE SWORD AND THE SHIELD Section 1: Identity, Division ,Symmetry Chapter 3:Symbolic logic, Mathematical logic and logic of signals 8 §20:Duality in Boolean Algebra In Geometry, there are many theorems which still hold good if ‘point’s in the theorem are replaced by ‘line’s and vice versa. Such a relationship between points and lines is called a Duality . In any Boolean algebra, if we interchange the two operations and interchange their identity elements, the result shall still be another Boolean algebra. As example let us write dual statement of 1 . 0 x y y . If ‘+’ is replaced by ‘.’ and 1 is replaced by 0 and vice versa, the statement shall be simply converted to 0. 1. x y y . Try finding the dual statements of 1) 1. 0 x x and 2) 1. ' 0 ' x x and verify that the dual statements are 0 .1 x x and 0 ' 1. ' x x respectively. This simple theorem is the result of commutativity, associativity and distributivity of the two operations. The reader can work out the details as an exercise. In fact we may prove dual of any statement in a Boolean algebra to be true. Exercise 7 (remember) To prove dual of statement x x x i.e. . x x x to be true First understand the validity of x x x . In the Boolean algebra B, x x x means p p p if x in B stands for statement p and + stands for . More clearly, 0 (0 ) . ' . ' 0 . ' ' ' '.' .1 ' 1 x x being identity x x x as x x x x x x distributivity of over x x as x x x x Now to prove the dual statement . x x x We haveREDISCOVER MATHEMATICS FROM 0 AND 1 BOOK 1: THE SWORD AND THE SHIELD Section 1: Identity, Division ,Symmetry Chapter 3:Symbolic logic, Mathematical logic and logic of signals 9 .1 (1 ) . ' ' 1 . . ' '.' ' ' . 0 . ' 0 . x x being identity x x x as x x x x x x distributivity of over x x as x x x x You would be delighted to compare the two proofs; just ‘+’ and ‘.’ Are interchanged and 0 and 1 are interchanged mechanically. This , i.e. symmetry is the beauty of dual statement. Exercise 8 (remember) Find the dual statements of the following:(the statements are not necessarily true, however just work with them) . Hint : Just replace ‘.’ with ‘+’ , and ‘0’ with ‘1’ and vice versa . a) ' ' ' . x y x y b) . 0 x y x c) . ' ' ' x y x y d) ' '. ' x y x y e) . 1 x x y x f) . ' x y y x y g) ' . ' 1 x y x y h) ' . ' '. ' . x y x y x y x y i) ' . ' . ' ' 0 x y y z x z j) . 1 . x y x x x y y Exercise 9 (remember) To prove dual of statement 1 1 x i.e. .0 0 x to be trueREDISCOVER MATHEMATICS FROM 0 AND 1 BOOK 1: THE SWORD AND THE SHIELD Section 1: Identity, Division ,Symmetry Chapter 3:Symbolic logic, Mathematical logic and logic of signals 10 First understand the validity of 1 1 x . In the Boolean algebra B, 1 1 x means p t t if x in B stands for statement p and + stands for , where t stands for tautology. More clearly, 1 ' (1 ) '.1 '.1 ' ' . 1 '.' ' ' 1. 1 ' 1 1 x x being identity and this is law ofcomplements x x as x x x x x distributivity of over x as x x x Now to prove the dual statement .0 0 x We have 0 . ' (0 ) . ' 0 ' 0 ' . ' .0 '.' ' ' 0 .0 . ' 0 .0 x x being identity and it is by law of complements x x as x x x x x distributivity of over x as x x x Exercise 10 (remember) To prove dual of statement . x x y x i.e. . x x y x to be true First prove . x x y x . In the Boolean algebra B, . x x y x means p p q q if x , y in B stands for statement p , q and + stands for , ‘.’ stands for . More clearly, .1 (1 ) . 1 1 1, . .1 '.' ' ' x x being identity x y as y as in the previous example x y x distributivity of over . .1 . x y x as x x x x y Now to prove the dual statement . x x y x We haveREDISCOVER MATHEMATICS FROM 0 AND 1 BOOK 1: THE SWORD AND THE SHIELD Section 1: Identity, Division ,Symmetry Chapter 3:Symbolic logic, Mathematical logic and logic of signals 11 0 (0 ) .0 .0 0 . 0 ' ' '.' . 0 . x x being identity x y as y by above example x y x distributivity of over x y x as x x x x y Exercise 11 (remember) To prove dual of statement 0 ' 1 i.e. 1' 0 to be true. By example 66 above, we have, 1 1 x for all x in B. In particular , taking 0 x and putting it in the above , we have 0 1 1 , so 0 ' 1 . Now to prove the dual1' 0 , take .0 0 x for all x in B.( by example 66) Putting a particular value 1 x in this, we have 1.0 0 By commutativity, 0.1 0 , so 1' 0 . Exercise 12 (remember) It is trivial to note that ' ' x x and this statement itself is its dual statement. The former may be proved from ' 1 x x , the definition of ' x . By commutativity, ' 1 x x , so that x is the complement of ' x . Exercise 13 (remember) To prove ' ' ' x y x y and its dual statement ' ' ' xy x y . To prove ' ' ' x y x y , it is sufficient to show that '. ' 1 x y x y , i.e. '. ' x y and x y are complements of each other. NowREDISCOVER MATHEMATICS FROM 0 AND 1 BOOK 1: THE SWORD AND THE SHIELD Section 1: Identity, Division ,Symmetry Chapter 3:Symbolic logic, Mathematical logic and logic of signals 12 '. ' '. ' , '. ' , ' . ' , , 1. ' ' 1, '', , 1, ' 1, x y x y y x x y by commutativity y x x y by associativity y x x x y by distributivity y x y as x x being complements of eachother y x y x y y by commutativity x as y y complem 1, 66 ents by example above Hence '. ' 1 x y x y , so ' '. ' x y x y Similarly, for proving the dual statement ' ' ' xy x y , we need to prove . '. ' 0 x y x y , i.e. '. ' x y and x y are complements of each other. Exercise 14 Prove that a) ' ' ' . x y x y b) . 1 x x y x c) . 1 x x y x d) . 1 . x y x x x y y e) . ' 0 . x y x y x f) if 0 . ' '. x y x y x y for all y. g) if 0 0 x y x y h) If x y x z and ' ' x y x z , then y z Exercise 15: Remember Remembering the principle of duality in Boolean algebra De’ Morgan’s laws may be stated in this form: a) ' '. ' x y x y REDISCOVER MATHEMATICS FROM 0 AND 1 BOOK 1: THE SWORD AND THE SHIELD Section 1: Identity, Division ,Symmetry Chapter 3:Symbolic logic, Mathematical logic and logic of signals 13 b) . ' ' ' x y x y dot replacing + and vice versa as per principle of duality. Prove by showing that truth tables are same for both sides. X Y X+Y (X+Y)' 0 0 0 1 0 1 1 0 1 0 1 0 1 1 1 0 X Y X' Y' X'.Y' 0 0 1 1 1 0 1 1 0 0 1 0 0 1 0 1 1 0 0 0 You can observe the results are identical for both sides of a) . Similarly prove b). Exercise 16: Remember Prove the following with the help of truth tables. a) 1 1, .0 0 x x (boundedness laws) b) . , . x x y x x x y x ( absorption laws) c) '. , . ' . x x y x y x x y x y (elimination laws) d) If 1, . 0 x y x y , then ' x y (Unique complement theorem) e) ' ' " , 0' 1 x x x (Involution theorem) §21:TRUTH VALUE OF LOGICAL STATEMENTS We have seen how Boolean Algebra handles logical statements in Algebraic fashion. It is now time to do some mathematics with statements themselves. We have already shown informally what are logical statements and how they are connected by operators ‘AND’ and ‘OR’, represented by symbols ( called Conjunction operator) and (Disjunction operator) respectively and also have seen how they are analogous to the set theoretic operations and respectively. Logically, all statements fall into one of the following two categories – True , False. We just want to bring under a structure, all sorts of ethics and beliefs included. Whenever we accept some statement say p to be true, we assign a ‘truth value, i.e. T’ to it and similarly when we accept a statement say q to be false, we assign a ‘truth value F’ to it. Sometimes True is denoted by Yes or 1 and False is denoted by No or 0 also.REDISCOVER MATHEMATICS FROM 0 AND 1 BOOK 1: THE SWORD AND THE SHIELD Section 1: Identity, Division ,Symmetry Chapter 3:Symbolic logic, Mathematical logic and logic of signals 14 For example, let p: Hari is brother of Ram, q: Hari is son of Shiva. Then p q: Hari is brother of Ram and Hari is son of Shiva. Similarly p q: Hari is brother of Ram or Hari is son of Shiva. As told previously the statements p, q may be accepted as true or false by choice. If both the statements p, q are true, then p q is true as well as p q is true. But in case p is true and q is false, p q cannot be true (evidently both are not true). In this case at least one of the statements is true obviously; i.e., p q. These facts could be listed in the following table called ‘truth table’ . Truth table for p q p q p q T T T T F F F T F F F F Note that combination of both statements are false when each of them is false. ( it is contrary to the notion negative of negative is positive, because here the statements are joined, not one operating on the other) Truth table for p q p q p q T T T T F T F T T F F F Closely watch the difference between the tables before proceeding from here. There is another operator “NOT” apart from the operators AND’ and ‘OR’, called negation operator, the negation of statement p is denoted by p. If truth value of p if T then that of p is F and vice versa. The truth table for ~ p is obviously the following one. Here negation of negation of p is p. p ~ p T F F T RememberREDISCOVER MATHEMATICS FROM 0 AND 1 BOOK 1: THE SWORD AND THE SHIELD Section 1: Identity, Division ,Symmetry Chapter 3:Symbolic logic, Mathematical logic and logic of signals 15 The operator or connector ‘OR’ in mathematics is never used in mutually exclusive sense. The statement p q means p, or q or both. It is not either exclusively p or q. §22:The connector ‘if…….then’ and contrapositive statements Two statements may be joined with the help of a conditional connector ‘if…….then’; in symbols p q and the statement p q is called a conditional statement. In this type of statements, p is called antecedent and q is called consequent. For example : ‘If it rains today, the pond cannot be dug’. We could write p: It rains today; q: the pond cannot be dug. The same compound statement may also be written in many other ways. For example, the pond cannot be dug if it rains today. When it rains today, the pond cannot be dug. The pond can be dug only if it does not rain today. ‘It rains today’ is sufficient condition for ‘the pond cannot be dug’. Remember The order in which the two statements are written is not important , but the writing should be unambiguous so that p q . Further , in mathematical logic, statements are viewed objectively. Even p and q are unrelated statements, one may choose to write p q , there is no bar, for we are studying a structure only. For example one may write p : You see a falling star , and q: you would pass the exam and one may connect the two such as If you see a falling star, you would pass the exam. Still as another example, take p: 2 + 4 =8 and q : Ram would get a hat ; and connect the two as : if 2 + 4 =8 then Ram would get a hat. This consideration shall be evident when we study the truth value of p q . Remember a) When p is true and q is true, evidently p q is true. b) When p is true and q is false, p q is false. (We need not preempt p q , only it follows that p q is false. Understandably we have accepted forming of p q even if p and q are unrelated subjects. As an example, if p: Ram is son of Hari and q: Shiva is son of Gopal, the statement p q becomes, If Ram is son of Hari and q: Shiva is son of Gopal. The combined statement should be evidently false in case the second statement ( q) is false, as the implication q is false. c) When p is false and q is true, p q is true. REDISCOVER MATHEMATICS FROM 0 AND 1 BOOK 1: THE SWORD AND THE SHIELD Section 1: Identity, Division ,Symmetry Chapter 3:Symbolic logic, Mathematical logic and logic of signals 16 For example, if p : 9 is not divisible by 3 and q: 45 is divisible by 3, we have the combined statement p q : if 9 is not divisible by 3 then 45 is divisible by 3. Since the consequence of this combined statement ‘45 is divisible by 3’ is true, there is no objection in accepting the combined statement to be true. d) When p is false and q is false, p q is true. For example p : 2 + 4 = 5 and q: 2 + 3 = 6 both statements are false. If we connect the two false statements with ‘if…. then’, it would be ‘If 2 + 4 = 5 then 2 + 3 = 6’. It is true that a false statement shall generate a false statement. Truth table for p q The above facts may easily be remembered by looking at the truth table for p q . p q p q T T T T F F F T T F F T Remember p q is false only when truth value of p is T and truth value of q is F, otherwise it is true. In this way the symbol is different from i.e., “Implies”. The latter whenever connects two statements, the combined statement is supposed to be necessarily true; but not in case of . To carry the structure forward, let us work out some more truth tables, so that writing the statements and connecting them only through symbols would be more facilitated. ( Perhaps now you understand when negative of negative is positive and when it is not) Truth table for ~ p q This would show how ‘if… then ‘ i.e., is correlated to and . To this end, we copy the truth table for p q in the first three columns in the table below, then take ~ p in the fourth column, and q in the fifth column and work out ~ p q in the last. See for yourself the last column using table for worked out in the beginning.REDISCOVER MATHEMATICS FROM 0 AND 1 BOOK 1: THE SWORD AND THE SHIELD Section 1: Identity, Division ,Symmetry Chapter 3:Symbolic logic, Mathematical logic and logic of signals 17 p q p q ~ p q ~ p q T T T F T T T F F F F F F T T T T T F F T T F T Truth table for ~ p q ~ p q ~ p q F T T F F F T T T T F T Remember The truth table for p q is same as the truth table for ~ p q as evident from above and so we may write the statements p q and ~ p q are equivalent statements; Remember ~ p q p q . Let : p do not reach the station on time, : q you miss the train. Then p q stands for “ if you do not reach the station on time, then you miss the train” and ~ p q stands for “Either you reach the station on time or you miss the train”. This is a small but powerful result and is required in many of the problem below. An equivalent statement of the above is ~ ~ p q p q which would be proved below, with the help of De’ Morgan’s laws stated below. De’ Morgan’s laws applied to statements Remember Remember De’ Morgan’s laws in set theory, ' ' ' A B A B and ' ' ' A B A B . These applied to statements become ~ ~ ~ p q p q and ~ ~ ~ p q p q respectively; as ~ p in logical statements correspond to ' A (complement of A in set theory). RememberREDISCOVER MATHEMATICS FROM 0 AND 1 BOOK 1: THE SWORD AND THE SHIELD Section 1: Identity, Division ,Symmetry Chapter 3:Symbolic logic, Mathematical logic and logic of signals 18 If p q then ~ ~ q p , this is called contrapositive statement of p q . This is shown as follows: ~ ~ ~ ~ ~ ~ ~ p q p q q p q p q p in view of commutativity and as per the above result. For example contrapositive statements are like this : The contrapositive of “ If you can gather 100 Rupees then surely you could gather 10 Rupees” is “ If you cannot gather 10 rupees , you cannot gather 100 rupees. The contrapositive of “ if you can swim across the river then you can swim the backyard pool” is “if you cannot swim across the backyard pool, you cannot swim across the river”. Further practice in the following paragraphs shall reinforce your understanding of symbolic representation of mathematical logic. Exercise 17 Rewrite the following sentences in symbolic form p q a) If you study well you would get good results b) If you are lucky you win a lottery c) If you say no to tobacco you would not catch cancer ( The sentences are given only for exercise. Do not connect them to real life situation . for example in a) let p: you study well and q: you would get good results. We rewrite p q . In real life, studying well is not sufficient for getting good results, it might be luck or situation too. Similarly in b) if you don’t win a lottery, you might still be lucky otherwise. In c) you may observe that many non-smokers also get cancer.) Similarly you might observe that unrelated subjects are connected by ‘if….then’ in the following. Remember that we are here only studying structure of mathematical logic, not ethics religion or belief. Exercise 18 Rewrite the symbolic form p q in plain language. a) p: 2 + 3 = 7 , q: 4 + 6 = 14 ( if 2 + 3 = 7 then 4 + 6 = 14) b) p: 2 + 2 =5, q: Sita would get a chocolate. ( if 2 + 2 =5 then Sita would get a chocolate) c) p: any integer is divisible by 3, q: sum of its digits are divisible by 3.( if any integer is divisible by 3, then the sum its digits is divisible by 3)REDISCOVER MATHEMATICS FROM 0 AND 1 BOOK 1: THE SWORD AND THE SHIELD Section 1: Identity, Division ,Symmetry Chapter 3:Symbolic logic, Mathematical logic and logic of signals 19 The following exercises are on truth value. Exercise 19 In the following the truth value of p is T, that of q is F and that of r is T. Find the truth value of the logical expressions. A) p q r . Ans. T F T T T T ,as T F T and T T T .( refer truth value table for p q . B) p q r Ans. T F T T T T C) p q r . Ans. T F T T T T , as F T T and T T T . D) p q r . Ans. T F T T T T , as F T T and T T T E) ~ p q r .Ans. ~ ~ T F T T T T F F , as T F T and T F F F) p q r . Ans. T F T F T F ,as T F F and F T F . Exercise 20 Prepare the truth tables of the following statements: a) p q r b) p q r c) p q r d) ~ ~ p q q e) ~ p r q r Truth table method of proving logical statements Apart from analytical proof, we could also prove a logical statement from truth tables. This would be evident from the following exercise. Exercise 21 To prove p q r p r q r We have to make truth tables for a) , p q and p q b) , p q and p q r c) , p q and p r , d) for , p q and q r , e) for , p q and p r q r and then show that REDISCOVER MATHEMATICS FROM 0 AND 1 BOOK 1: THE SWORD AND THE SHIELD Section 1: Identity, Division ,Symmetry Chapter 3:Symbolic logic, Mathematical logic and logic of signals 20 the truth tables for b) and for e) are one ant the same by making a common table for all of the above, combining the above truth tables together. Remember that This is general method of proving these kind of problems. We do the common table here for all of a) ,b), c) ,d) and e) above and you can extract the individual tables from it as an exercise. p q r p q p r q r p q r p r q r T T T T T T T T T T F T F F F F T F T T T T T T T F F T F T F F F T T T T T T T F T F T T F F F F F T F T T T T F F F F T T T T The reader should verify that the last two columns are identical, showing that p q r p r q r . Exercise 22 To show that ~ ~ p q p q Remember Hint : Just take negative of both sides of ~ p q p q and apply De’ Morgan’s laws. Exercise 23 Show that ~ ~ ~ ~ q p p q (Just the contrapositive of the above) Exercise 24 Using truth table method, show that p q and q p do not imply one and the same thing. §23:Biconditional statements Two logical statements may be combined with , i.e., “implies and is implied by”. For example look at the following statements REDISCOVER MATHEMATICS FROM 0 AND 1 BOOK 1: THE SWORD AND THE SHIELD Section 1: Identity, Division ,Symmetry Chapter 3:Symbolic logic, Mathematical logic and logic of signals 21 a) Three angles of a triangle are equal three sides are equal. b) Prakash is son of Ramesh Ramesh is father of Prakash. Either side of each of the statements follow from the other side. In logic we generalize the concept as “if and only if” and denoted by , not by . The reason is , the truth value of a combined statement joined by is always true; but the truth value of a combined statement joined by is true only if both the sides are true and also true if both sides are false. Remember. The truth table for p q is given below: p q p q T T T T F F F T F F F T It is easy to understand the fourth line, that one false statement follows from another false statement and vice versa. The second and third line simply say that a true statement cannot follow from a false one and vice versa. More generally, p q p q q p Remember Again we could make truth tables for , , , , , p q p q q p p q p q q p separately, draw the common table from them and show equivalence of the last two table columns as in ex 73 above. For brevity we are giving here only the common table, the reader should draw individual tables first and draw the common table from them as an exercise. p q p q q p p q p q q p T T T T T T T F F T F F F T T F F F F F T T T T The last two columns show the equivalence as desired. Exercise 25REDISCOVER MATHEMATICS FROM 0 AND 1 BOOK 1: THE SWORD AND THE SHIELD Section 1: Identity, Division ,Symmetry Chapter 3:Symbolic logic, Mathematical logic and logic of signals 22 To prove ~ ~ ~ p q p q p q Remember We can prove this with the help of truth tables. Also see the following for analytical approach. ~ ~ ~ ~ ~ ' ' ~ ~ ~ ~ ~ ~ p q p q q p by definition p q p q q p p q p q q p by De morgan s laws p q q p p q p q p q p q Exercise 26 Show that ~ ~ p q p q p q §24:Premises, conclusion and arguments Sometimes we draw some conclusion from a collection or sequence of statements. The sequence of the statements along with conclusion together form what is called an argument. The statements which lead to the conclusion are called antecedents or premises or hypotheses ( plural of hypothesis). Sometimes the conclusion may be a valid one or may be invalid also. We would discuss some methods to test the validity of an argument. But remember that an argument is merely a sequence of statements ending in some conclusion; not necessarily a dispute. If 1 2 3 , , ,..... n S S S S is a sequence of statements leading to a conclusion S , then the argument is denoted by 1 2 3 , , ,..... ; n S S S S S . An argument 1 2 3 , , ,..... ; n S S S S S is said to be valid if S is true whenever all of 1 2 3 , , ,..... n S S S S are true. Example ; Let 1 : S n is a natural number; 2 : S a natural number is an integer; 3 : S an integer is a rational number; 4 : S a rational number is a real number and : S n is a real number. Here 1 2 3 4 , , , S S S S are premises or hypotheses or antecedents S is the conclusion and it is valid. The sequence 1 2 3 4 , , , ; S S S S S is an argument and it is valid. Methods to test validity of an argument We construct a truth table for the hypotheses and the conclusion. If truth value all of the hypotheses are true in a row and the conclusion is also true in that row, then the argument is valid. Such a row in which all hypotheses are true is called a critical row. There may be more than one critical row in REDISCOVER MATHEMATICS FROM 0 AND 1 BOOK 1: THE SWORD AND THE SHIELD Section 1: Identity, Division ,Symmetry Chapter 3:Symbolic logic, Mathematical logic and logic of signals 23 such a table. The conclusion should be true in every critical row; otherwise the argument shall be invalid. The last statement may be differently worded as follow; which gives an alternative test of validity of any argument. The argument 1 2 3 , , ,..... ; n S S S S S is valid if the statement “if 1 2 3 ..... n S S S S then S is a tautology” is true, else invalid. If there is no critical row; i.e., there is no row in which all the hypotheses are true, the argument is considered invalid. Example 5; Test the validity of the following argument. 1 2 :~ , : , : ~ S q S p q S p q . Let us construct the truth table as follows: hypothesis hypothesis conclusion p q ~ q p q ~ p q T T F T F T F T T T F T F T F F F T F F The third row is the only critical row and the conclusion is also true there. So the argument is valid. Example6 ; Test the validity of the following argument. 1 2 :~ , : , :~ S p S p q S q Let us construct the truth table as follows: hypothesis hypothesis conclusion p q ~ p p q ~ q T T F T F T F F T T F T T T F F F T F T The third row is the only critical row and the conclusion is false there. So the argument is invalid. Example7 ; Show that the following argument is valid. 1 2 : , : ~ , : S p q S p S q REDISCOVER MATHEMATICS FROM 0 AND 1 BOOK 1: THE SWORD AND THE SHIELD Section 1: Identity, Division ,Symmetry Chapter 3:Symbolic logic, Mathematical logic and logic of signals 24 In the alternative method, we would verify the conditional “if ~ p q p , then q ” is a tautology. Let us construct the truth tables for 1 2 , , S S and S as follows. 1 S 2 S 1 2 S S 1 2 S S S S p p q ~ p ~ p q p ~ p q p q q T T F F T T T T F F T F F T T T T T F F T F T F The fifth column is seen to be a tautology. Hence the argument is valid. Exercise 27: Examine the validity of the argument: 1 2 : ; : ; : S If p then q S p S q Let us construct the truth table as follows: Hypotheses Conclusion p q p q p q T T T T T T F F T F F T T F T F F T F F The first row is the only critical row and conclusion is also true. So the argument is valid Exercise 28: Show that the following argument is invalid: . 1 2 : ; :~ ; : S p q r S r S p q Let us construct the truth table as follows: Hypotheses Conclusion p q r q r p q r ~ r p q T T T T T F T T T F T T T T T F T T T F T T F F F T T T F T T T T F T F T F T T T T F F T T T F F F F F F F T FREDISCOVER MATHEMATICS FROM 0 AND 1 BOOK 1: THE SWORD AND THE SHIELD Section 1: Identity, Division ,Symmetry Chapter 3:Symbolic logic, Mathematical logic and logic of signals 25 The fourth, sixth and eighth rows are critical rows in all of which conclusion is true. So the argument is valid. Exercise 29: Show that the following argument is invalid: 1 2 : ~ ; : ; : S p q r S q p r S p r Let us construct the truth table as follows: Hypotheses Conclusion p q r ~ r ~ q r p r ~ p q r q p r p r T T T F T T T T T T T F T T F T F T F T F F T F T T F F T T F T T F F T T F T F T F F T F T T F T F F F T F F F T T T F F F T T F T T T Mark the critical rows are the third, 6th and 9th and 10th rows. In the sixth row, the conclusion is F. So the argument is invalid. Exercise 30: Show that the following argument is invalid. 1 2 : , : ~ , :~ S p q S p S q Let us construct the truth table as follows: 2 S S 1 S 1 2 S S 1 2 S S S p q ~ p ~ q p q ~ p q p ~ ~ p q p q T T F F T F T T F F T T F T F T T F T T F F F T T F F T Since the last column is not a tautology (not always having truth value T) the argument is invalid.REDISCOVER MATHEMATICS FROM 0 AND 1 BOOK 1: THE SWORD AND THE SHIELD Section 1: Identity, Division ,Symmetry Chapter 3:Symbolic logic, Mathematical logic and logic of signals 26 The student should compare the two methods and understand the similar reason behind them. In one method, all the critical rows must have conclusion T and in the second method, the conclusion must be always true for being a tautology. Show the validity or invalidity of the arguments below: Misc Exercise 31: a) 1 2 : ; :~ ; :~ S p q S p S q (invalid) b) 1 2 : ; :~ ; : S p q S q S p (valid) c) 1 2 : ; :~ ; : S p q S p S q (valid) d) 1 2 : ; : ; : S p q S q S p (invalid) e) 1 2 : ; : ; : S p q S q p S p q (valid) f) 1 2 3 : ; : ~ ; : ; : S p q S p q S p r S r (Invalid) g) 1 : ; : ; S p S p q (Valid) h) 1 : ; : ; S q S p q (Valid) i) 1 : ; : ; S p q S p (Valid) j) 1 : ; : ; S p q S q (Valid) k) 1 2 : ; :~ ; :~ S p q S q S p (Valid) l) 1 2 3 : ; : ; :~ , : S p S p q S q r S r (valid) m) 1 2 : ; : ; : S p q S p r S p q r (valid) n) 1 2 3 : ~ ; : ; : ; : S p q r S p q S q p S r (Invalid) §25:Boolean expressions and functions: If , ,.,',0,1 B be a Boolean algebra in the usual sense, where 1 2 , ,......... n B x x x , a Boolean expression in these variables would be defined like this: a) 1 2 0,1, , ,......... n x x x , each of them is a Boolean expression. b) If x and y are Boolean expressions, then ', , ( . . ), . , . ., x x y i e x y x y i e x y are Boolean expressions. Example: Show that 1 2 3 . x x x is a Boolean expression and find its value if 1 2 3 0, 0 1 x x and x REDISCOVER MATHEMATICS FROM 0 AND 1 BOOK 1: THE SWORD AND THE SHIELD Section 1: Identity, Division ,Symmetry Chapter 3:Symbolic logic, Mathematical logic and logic of signals 27 The expression is a Boolean expression evidently as conditions a) and b) are satisfied. Its value becomes 1 2 3 . 0.0 1 0 1 1 x x x Exercise: Show that 1 2 3 . ' x x x is a Boolean expression and find its value when 1 2 3 0, 0 1 x x and x . Ans. 0, as 1’ = 0. Boolean Function: Functions represented by Boolean expressions are Boolean Functions. In other words, if 1 2 , ,..... n X x x x be some Boolean expression in the variables mentioned, then 1 2 1 2 , ,..... , ,..... n n f x x x X x x x is a Boolean function. Example Remember the definition of function from the previous chapter, it is a single valued correspondence between two sets A and B and is denoted by : f A B Its domain is the subset of A for which the correspondence exists and the range or co-domain is the set of corresponding values in B. The function 2 : 0,1 0,1 f , is a Boolean function if 1 2 1 2 2 . . ' f x x x x x . The right hand side expression is evidently a Boolean expression , hence it is a Boolean function. Its domain is 2 0,1 0,1 0,1 0,0 , 1,0 , 0,1 , 1,1 X , the Cartesian product of 0,1 0,1 and . We would use only Boolean functions whose domain is given by 0,1 n , where n is a natural number, and call it an n-place Boolean function. The structure of the domain is by the number of variables in the expression. For example, in a function 1 2 3 . ' x x x , we see that each member of the domain contains three variables, of the type 1 2 3 , , x x x , which is a member of 3 0,1 0,0,1 , 0,1,1 , 1,0,1 , 1,0,0 ,........... etc. as the variables can take only values 0 or 1. Exercise a) Find 1 1 2 3 '. . ' x x x x if 1 2 3 0, 1, 1 x x x . Ans. 1 b) Find 1 1 2 3 '. . ' x x x x if 1 2 3 1, 0, 0 x x x . Ans. 0 c) Find 1 1 2 3 '. . ' x x x x if 1 2 3 0, 0, 1 x x x . Ans. 1REDISCOVER MATHEMATICS FROM 0 AND 1 BOOK 1: THE SWORD AND THE SHIELD Section 1: Identity, Division ,Symmetry Chapter 3:Symbolic logic, Mathematical logic and logic of signals 28 Exercise 32: Construct input-output table for the Boolean expressions as follows: a) 1 2 1 2 2 . . ' f x x x x x b) 1 2 1 2 . '. f x x x x c) 1 2 3 1 2 3 . . . ' f x x x x x x d) 1 2 3 1 2 3 . . . ' . f x x x x x x Arrow diagram for Boolean function The input-output tables for Boolean functions may be represented by an arrow diagram. For example, take the following table: Input Output x1 x2 x3 x 1 1 1 1 1 1 0 1 1 0 1 0 1 0 0 1 0 1 1 0 0 1 0 0 0 0 1 0 0 0 0 1 We can take ordered triplets of the inputs such as (1, 1, 1), (1,1,0) etc. and construct an arrow diagram connecting the ordered triplets of inputs to the respective output. Compare the arrow diagram with the input-output table like the one given below:REDISCOVER MATHEMATICS FROM 0 AND 1 BOOK 1: THE SWORD AND THE SHIELD Section 1: Identity, Division ,Symmetry Chapter 3:Symbolic logic, Mathematical logic and logic of signals 29 Verify that the arrow diagram is equivalent to the input -output table. Exercise Make an arrow diagram for the following table: Input Output x1 x2 x3 x 1 1 1 1 1 1 0 0 1 0 1 0 1 0 0 1 0 1 1 0 0 0 1 1 0 0 1 0 0 0 0 0 Boolean function from input-output tables. The following example would illustrate how do we construct a Boolean function for a given input-output table. Input Output x1 x2 x3 f(x1, x2, x3) 1 1 1 1 1 1 0 0 (1,1,1) 1,1,0) (1,0,0) (1,0,1) (1,1,1) (0,1,1) (0,1,0) (0,0,1) (0,0,0) 0 1REDISCOVER MATHEMATICS FROM 0 AND 1 BOOK 1: THE SWORD AND THE SHIELD Section 1: Identity, Division ,Symmetry Chapter 3:Symbolic logic, Mathematical logic and logic of signals 30 1 0 1 0 1 0 0 1 0 1 1 0 0 1 0 1 0 0 1 0 0 0 0 0 Observe that there is 1 in the output in the 3rd, 6th and 8th row. We can take 1 2 3 . . 1 x x x when all input are 1 each. If any input 2 x is 0 in any row, we can put 2 ' 1 x in this case and still get the result 1 2 3 . '. 1 x x x . Thus we get 1 2 3 . . 1 x x x in the 3rd row, 1 2 3 . '. ' 1 x x x in the 6th row, and 1 2 3 '. . ' 1 x x x in the 8th row. We can write 1 2 3 1 2 3 1 2 3 . . . '. ' '. . ' 1 x x x x x x x x x for the rows where output is 1. ( Note that 1 or 1 is 1, i.e., 1 + 1 = 1). Observe that this represents the complete table; for it is automatically understood that the output is 0 for all other inputs. Thus 1 2 3 1 2 3 1 2 3 1 2 3 . . . . . '. ' '. . ' f x x x x x x x x x x x x is the Boolean function representing the table, as you may verify that when any member in the bracket in the left side of the equation is 0, the right side is 0. We can now list the rules for finding Boolean function for an input output table. 1) Identify all rows having output 1 2) Take the combinations of inputs 1 2 3 . . x x x where all the inputs are 1 and take complements of inputs if anyone is 0; i.e., put 2 ' x in place of 2 x , if 2 0 x . 3) Then combine all such expressions with ‘OR’ i.e. ‘.’. 4) This is the Boolean function 1 2 3 . . f x x x , we need not write 1 2 3 , , f x x x Exercise Construct a Boolean function for the following input output table. Input output x1 x2 y 1 1 1 1 0 0 0 1 0 0 1 0 Ans. 1 2 1 2 . . f x x x x The other outputs except 1 are automatically taken care of, in the Boolean function thus arrived at. ( observe) ExerciseREDISCOVER MATHEMATICS FROM 0 AND 1 BOOK 1: THE SWORD AND THE SHIELD Section 1: Identity, Division ,Symmetry Chapter 3:Symbolic logic, Mathematical logic and logic of signals 31 Construct a Boolean function for the following input output table. Input Output x1 x2 x3 x 1 1 1 1 1 1 0 0 1 0 1 0 1 0 0 1 0 1 1 0 0 0 1 1 0 0 1 0 0 0 0 0 Exercise Construct a Boolean function for the following input output table. Input Output x1 x2 x3 x 1 1 1 1 1 1 0 1 1 0 1 1 1 0 0 0 0 1 1 0 0 1 0 0 0 0 1 0 0 0 0 1REDISCOVER MATHEMATICS FROM 0 AND 1 BOOK 1: THE SWORD AND THE SHIELD Section 1: Identity, Division ,Symmetry Chapter 3:Symbolic logic, Mathematical logic and logic of signals 32 §26:LOGIC OF ELECTRICAL CIRCUITS AND SIGNALS Look at the electrical circuits above; in the series circuit , first one, the lamp would be on only when both the switches are closed (on) and the lamp would be off when any one of the switches if open (off). Compare this with the truth table of p q denoting truth values 1 for T and 0 for F. This is same as the Input-Output table for binary operation AND. Also mark here that performing the operation AND is same as taking minimum of 1 and 0. See the table below. p q p q 1 1 1 1 0 0 0 1 0 0 0 0 Switches lamp p q On/off closed closed on closed open off open closed off open open off Switches lamp p q On/off closed closed on closed open on open closed on open open off p q battery lamp Switches p and q are in parallel; lamp would be lighted when any one of the switches are closed. p q battery lamp Switches p and q are in series; lamp would be lighted when both switches are closed.REDISCOVER MATHEMATICS FROM 0 AND 1 BOOK 1: THE SWORD AND THE SHIELD Section 1: Identity, Division ,Symmetry Chapter 3:Symbolic logic, Mathematical logic and logic of signals 33 Exercise 32: remember Show that if p, q etc have values 1 2 , x x , which are Boolean variables 0 or 1, then the input-output table for AND is represented by a Boolean function 1 2 1 2 , . f x x x x , the Boolean expression where ‘.’ represents AND. Hint : Show that their input-output tables are same. In the parallel circuit , compare the table with truth table of p q , using 1 and 0 for T and F respectively. This is same as the Input-Output table for binary operation OR. Also mark here that performing the operation OR is same as taking maximum of 1 and 0. See the table below. p q p q 1 1 1 1 0 1 0 1 1 0 0 0 Exercise 33: remember Show that if p, q etc have values 1 2 , x x , which are Boolean variables 0 or 1, then the input-output table for OR is represented by a Boolean function 1 2 1 2 , f x x x x , the Boolean expression where ‘+’ Represents OR. Hint : Show that their input-output tables are same. In electrical engineering and in electronics, large number of tiny electrical circuits are integrated to give desired outputs. These are called integrated circuits or ICs. These ICs of chips are having various uses today, in computers, music systems, cars , calculators, digital watches, robots and industrial control systems etc. Depending upon their level of integration ( number of circuit components or logic gates) the ICs are called SSI ( small scale integration, no. of ICs 10), MSI ( Medium scale integration, no. of ICs 100),LSI,( Large scale integration, no. of ICs 1000), or VLSI ( very large scale integration, no. of ICs > 1000). A logic gate means a logical operation is performed on logical inputs and results in a single output. The logic is commonly Boolean logic. The AND gate and the OR gate is represented in the following symbols with their inputouttpu function shown in their side.REDISCOVER MATHEMATICS FROM 0 AND 1 BOOK 1: THE SWORD AND THE SHIELD Section 1: Identity, Division ,Symmetry Chapter 3:Symbolic logic, Mathematical logic and logic of signals 34 Logic gates are not necessarily series or parallel electrical circuits only. They may be combinations of them or other electrical contrivances to meant to modify the input values of currents or signals or bits to desired output. For example there is a NOT gate corresponding to NOT function in Boolean Algebra, i.e. complement in set theory. This is a logical requirement to develop logical tools involving gates and may not be represented by a simple series of parallel electrical circuit. The gate concepts are useful in optical systems, even in mechanical systems. The diagram or symbol for it is given below along with input-output table. Such a gate inverts the input signal, 1 to 0 and 0 to 1. In other words T to F and F to T. As such it is called an inverter. Do not confuse it with home or office inverter which is used to supply output current even if the input current is cut off; but not does not make out put current 0 when there is input current in the mains. As an example of a NOT gate we can cite the example of a burglar alarm or bank safety siren; it buzzes only when the circuit breaks. The small circle in the symbol for NOT gate ( and in many other we would know later on) is called ‘bubble’. The logical gates are primarily used theoretically to modify the pulse waveform of signals apart from carrying out mathematical logical operations. It is explained below: A and B are two square wave input signals taking values 0 ( at the lower level) and 1 (at the higher level) at different times as given below. If the two signals are combined by the operation OR, the output signal Y = A OR B, i.e. A+B is calculated with the help of the two figures for A and B as given below. x x’ 1 0 0 1 NOT NOT x x’ NOT gate converting signal x to x’ OR OR 1 x 2 x 1 2 x x AND AND 1 x 1 2 . x x 2 xREDISCOVER MATHEMATICS FROM 0 AND 1 BOOK 1: THE SWORD AND THE SHIELD Section 1: Identity, Division ,Symmetry Chapter 3:Symbolic logic, Mathematical logic and logic of signals 35 It is evid entl y und erst ood that the output signal Y is clearly A OR B, i.e. A+B. SIGNALS 1 t t 1 2 t t t 2 3 t t t 3 4 t t t 4 5 t t t 5 6 t t t 6 t t Input signal A 0 1 1 0 0 1 0 Input signal B 0 0 1 0 0 0 1 Output signal A OR B 0 1 1 1 0 1 1 Input signal A Input signal B Output signal A OR B t1 t2 t3 t4 t6 t6REDISCOVER MATHEMATICS FROM 0 AND 1 BOOK 1: THE SWORD AND THE SHIELD Section 1: Identity, Division ,Symmetry Chapter 3:Symbolic logic, Mathematical logic and logic of signals 36 It is evid entl y und erst ood that the output signal Y is clearly A AND B, i.e. A.B Exercise 32: Construct input-output table for the combination of gates shown in the figure. If x1 = 0 passes through NOT gateit becomes x1’ = 1, input for AND gate. If the other input for AND gate is x2 = 0, then the output x = 0. Similarly work out output for all possible values of inputs and complete the table as follows: SIGNALS 1 t t 1 2 t t t 2 3 t t t 3 4 t t t 4 5 t t t 5 6 t t t 6 t t Input signal A 0 1 1 0 0 1 0 Input signal B 0 0 1 1 0 0 1 Output signal A AND B 0 0 1 0 0 0 0 x1 x2 x x1’ Input signal A Input signal B Output signal A AND B t1 t2 t3 t4 t6 t6REDISCOVER MATHEMATICS FROM 0 AND 1 BOOK 1: THE SWORD AND THE SHIELD Section 1: Identity, Division ,Symmetry Chapter 3:Symbolic logic, Mathematical logic and logic of signals 37 x1 x1’ x2 x 1 0 1 0 0 1 0 0 1 0 0 0 0 1 1 1 Exercise 35: Find the output x for the above combination of gates if x1 = 1, x2 = 0, x3 = 1. Ans. x = 0 . Hint : observe that x4 = 1, x4’ = 0, so x = 0. . Exercise 36: Complete the input-output table for the above. Hint. Complete the table for all possible values of inputs Exercise Find the input-output tables for the following two circuits and show that they have the same output s for the same inputs. Such circuits are called equivalent circuits. x1 x2 x4 x4’ x3 x 1 0 1 0 1 0 1 1 1 0 1 0 0 0 0 1 0 0 0 1 1 0 0 0 x1 x2 y1 1st circuit x1 x2 x3 x4 x4’ xREDISCOVER MATHEMATICS FROM 0 AND 1 BOOK 1: THE SWORD AND THE SHIELD Section 1: Identity, Division ,Symmetry Chapter 3:Symbolic logic, Mathematical logic and logic of signals 38 Exercise: Find out the input-output tables for the two circuits given below and show that they are equivalent. a) Hint: The input-output table for the 1st circuit is given below: Input Output x1 x2 y 1 1 1 1 0 0 0 1 0 0 0 0 2nd circuit y x1 x2 1st circuit x1 x2 y x1 x2 y2 2nd circuitREDISCOVER MATHEMATICS FROM 0 AND 1 BOOK 1: THE SWORD AND THE SHIELD Section 1: Identity, Division ,Symmetry Chapter 3:Symbolic logic, Mathematical logic and logic of signals 39 b) MISC. Exercise 36: Find the input-output tables for the following circuits: a) b) x1 x2 x3 x x’ x1.x2 1st circuit 2nd circuitREDISCOVER MATHEMATICS FROM 0 AND 1 BOOK 1: THE SWORD AND THE SHIELD Section 1: Identity, Division ,Symmetry Chapter 3:Symbolic logic, Mathematical logic and logic of signals 40 c) d) Take note of the jumping of the wire here. e) f)REDISCOVER MATHEMATICS FROM 0 AND 1 BOOK 1: THE SWORD AND THE SHIELD Section 1: Identity, Division ,Symmetry Chapter 3:Symbolic logic, Mathematical logic and logic of signals 41 Combinatorial circuits In the above combination work out output x if inputs x1 = 0, x2 = 1, x3 = 0. Clearly x1.x2 = 0, x3 =0 so x’ = 0, and ultimately x = 1. Try another set of values of the input variables x1 = 0, x2 = 1, x3 = 1. In this case he final output is 0. But note here that the final output is unique for each set of input values. The output may be different for different sets of input values. Such a circuit is called combinatorial circuit and its logic is called combinatorial logic. You may observe the following circuit is not a combinatorial circuit. For a set of values x1 = 1 and x2 = 0, we have x1.x2 =x’ = 0, so that x = 1. But proceeding in the lower branch from left, we get x2 = x , so x = 0. The value of output is not same for the same set of inputs if we arrive at the output by different methods. So this circuit is not a combinatorial circuit. Rules for making combinatorial circuits 1) Two input wires may not be combined together except through gates. 2) An output wire can be used as input into a different gate. 3) An input wire may be split and the branches may be fed into different gates as inputs. 4) No output wire can be fed back as input into the same gate. Apart from combinatorial circuits, in which the output does not depend upon sequence of choosing the various inputs, there are circuits which give output which depends upon sequence of choosing the inputs. Such circuits are called sequential circuits and the corresponding logic is called sequential logic. Both the circuits have application in computers and elsewhere. There is some rule of precedence of arithmetic processes when we simplify any arithmetic expression . for example, multiplication or division take precedence over addition or subtraction. In circuit logic we x1 x2 x x1.x2 =x’ x1 x2 x3 x x’ x1.x2REDISCOVER MATHEMATICS FROM 0 AND 1 BOOK 1: THE SWORD AND THE SHIELD Section 1: Identity, Division ,Symmetry Chapter 3:Symbolic logic, Mathematical logic and logic of signals 42 are given some problems of simplification, i.e. finding equivalent simple circuits for complicated circuits. Here some gates get precedence over others. To find a combinatorial circuit for a given Boolean expression, i.e., in the process of simplifying a Boolean expression, first of all, we identify all NOTs in the expression and draw NOT gates for them. Then we find out the innermost parentheses and draw the figure for the expression in it, by taking suitable inputs and working outputs. Next we take the next level innermost parentheses and repeat the process. When all such parentheses are worked out , we combine the drawings suitably according to the expression given and the resulting circuit is a combinatorial circuit. Follow the example. Example 8: Find a combinatorial circuit with its input-output table corresponding to the Boolean function 1 1 2 . ' x x x .There is only one NOT gate 1 ' x here which is represented by the following figure. Then the expression in the innermost parentheses ( the only one of the kind here) is 1 2 ' x x which can be represented by an OR gate given below. The two circuits can be joined suitably as under. Now the expression 1 1 2 . ' x x x corresponds to an AND circuit with inputs 1 x and 1 2 ' x x . OR 2 x x1’ 1 x 1 2 ' x x OR 1 ' x 2 x 1 2 ' x x x1’ x1REDISCOVER MATHEMATICS FROM 0 AND 1 BOOK 1: THE SWORD AND THE SHIELD Section 1: Identity, Division ,Symmetry Chapter 3:Symbolic logic, Mathematical logic and logic of signals 43 The above two circuits may be combined with the help of an AND gate as follows. The input-output table for 1 1 2 . ' x x x is given below, as also may be verified from the last figure. Inputs output 1 x 2 x 1 1 2 . ' x x x 1 1 1 1 0 0 0 1 0 0 0 0 Example 9: Find a combinatorial circuit for the Boolean expression 1 2 1 2 . '. ' x x x x and its input-output table. In the first step, we construct NOT gates for x1 and x2, i.e., join x1 and x1’ with a NOT gate and join x2 and x2’ with a NOT gate. In the next step we join x1 and x2 with an AND gate and also join x1’ and x2’ with a AND gate. In the final step we join 1 2 1 2 . '. ' x x and x x through an OR gate. Logic gates and Boolean algebra Hitherto we have witnessed logical gates heavily rely on Boolean algebra. Especially the combinatorial circuits are nothing but a different form of Boolean algebra. Could all Boolean algebras be represented by logic gate combinations ? In fact, Boolean algebras are represented a collection of either of ANDTTOOR gates , also of OR-TO-AND gates. See the diagrams below: x1 x1’ x2 x2’ 1st step OR 2 x x1’ 1 x 1 2 ' x x x1 x1.(x1’+x2)REDISCOVER MATHEMATICS FROM 0 AND 1 BOOK 1: THE SWORD AND THE SHIELD Section 1: Identity, Division ,Symmetry Chapter 3:Symbolic logic, Mathematical logic and logic of signals 44 Do convince yourself by trying any of the above examples in Boolean algebras. These ultimate forms are called canonical forms. OR-TO-AND AND-TO-ORREDISCOVER MATHEMATICS FROM 0 AND 1 BOOK 1: THE SWORD AND THE SHIELD Section 1: Identity, Division ,Symmetry Chapter 3:Symbolic logic, Mathematical logic and logic of signals 45 The input-output table is given below. Inputs Output x1 x2 1 1 1 1 0 0 0 1 0 0 0 1 x1 x2 x2’ 3rd step x1’ x1’.x2’ x1.x2 x1.x2+ x1’.x2’ x1 x2 x2’ 2nd step x1’ x1’.x2’ x1.x2REDISCOVER MATHEMATICS FROM 0 AND 1 BOOK 1: THE SWORD AND THE SHIELD Section 1: Identity, Division ,Symmetry Chapter 3:Symbolic logic, Mathematical logic and logic of signals 46 Misc Exercise Find combinatorial circuits for the following Boolean expressions and their input-output tables. a) 1 1 2 '. x x x b) 1 2 3 2 . ' x x x x c) 1 2 3 3 '. x x x x NAND and NOR gates, There are other logic gates apart from AND, OR and NOT. We combine a NOT gate after an AND gate and call it a NAND gate. As the NOT gate follows the AND gate, the final output is negation of the AND logic. In common language the concept is ‘ not both’ .See the table below for NAND gate Input for AND Output for AND Negation of AND Final output x y x.y (x.y)’ z = (x.y)’ 0 0 0 1 1 0 1 0 1 1 1 0 0 1 1 1 1 1 0 0 Or simply as Input for AND Final output for NAND x y z = (x.y)’ 0 0 1 0 1 1 1 0 1 1 1 0 The logic is quite understandable; only you have to remember that NOT follows AND; otherwise there may be confusion. The diagram for this is given below. But the symbol for NAND is not the above figure. It is given a separate symbol as given below:REDISCOVER MATHEMATICS FROM 0 AND 1 BOOK 1: THE SWORD AND THE SHIELD Section 1: Identity, Division ,Symmetry Chapter 3:Symbolic logic, Mathematical logic and logic of signals 47 . Similarly we take an OR gate followed by and NOT gate and call it an NOR gate. Remember that NOT gate follows OR gate and not vice versa. The input output table for NOR gate is given below Input for OR Output for OR Negation of OR Final output x y x.y (x.y)’ z = (x.y)’ 0 0 0 1 1 0 1 1 0 0 1 0 1 0 0 1 1 1 0 0 Or simply as Input for OR Final output x y z = (x.y)’ 0 0 1 0 1 0 1 0 0 1 1 0 The diagram for NOR gate is given below, but the symbol would be further simplified. And the symbol is given by exercise Show that the equivalent circuit of the following is simply an OR gate. NOR NANDREDISCOVER MATHEMATICS FROM 0 AND 1 BOOK 1: THE SWORD AND THE SHIELD Section 1: Identity, Division ,Symmetry Chapter 3:Symbolic logic, Mathematical logic and logic of signals 48 Hint : work out the input output table. exercise Show that the equivalent circuit of the following is simply an OR gate. Hint : work out the input output table. exercise An input signal can be split into two and then fed into a gate. By working out the input output table in the following figure, show that the equivalent circuit is simply a NOT gate. Hint: The input output table is simply that of a NOT gate (Verify). exercise Find out the equivalent logical operation carried out by the circuit in the following figure. Ans. AND gate.REDISCOVER MATHEMATICS FROM 0 AND 1 BOOK 1: THE SWORD AND THE SHIELD Section 1: Identity, Division ,Symmetry Chapter 3:Symbolic logic, Mathematical logic and logic of signals 49 exercise Find out the equivalent logical operation carried out by the circuit in the following figure. Ans. OR gate. exercise Find out the equivalent logical operation carried out by the circuit in the following figure. Ans. OR gate. exercise Find out the equivalent logical operation carried out by the circuit in the following figure. Ans. A NOT gate. exercise Find out the equivalent logical operation carried out by the circuit in the following figure.REDISCOVER MATHEMATICS FROM 0 AND 1 BOOK 1: THE SWORD AND THE SHIELD Section 1: Identity, Division ,Symmetry Chapter 3:Symbolic logic, Mathematical logic and logic of signals 50 Ans. An AND gate. NAND gates and NOR gates are universal gates in the sense that all other gates can be formed out of only NAND gates as well as , out of only NOR gates. From the above examples you must have understood that by now (last two exercises). Exclusive OR i.e. XOR and exclusive NOR, i.e., XNOR A light bulb is either on or off; but not both. The exclusive OR , i.e., XOR gate works on this logic. The input output table is given below. Input Output A B A XOR B 0 0 0 0 1 1 1 0 1 1 1 0 And is represented by the symbol. . XNOR gate works on opposite logic of XOR gate; if inputs are A and B, A XNOR B means A iff B and is true only when A and B are same. The input output table and its symbol for XNOR are given below . Input Output A B A XNOR B 0 0 1 0 1 0 1 0 0 1 1 1 XNOR XOR