_ L MODULE 3 Boolean Algebra, Fundamentals of Truth tables and Precedence Algebra Algebra means reunion on broken parts. It is the study of mathematical symbols and rul es for manipulating the symbols. Algebra can be regarded as elementary, abstract or mo dem depending on the level or field of study. Algebra has computations similar to arithmetic but with letters standing for numbers whi ch allows proofs of properties that are true regardless of the numbers involved. For exam ple, quadratic equation: ax? + bx + = 0 where a, b, ccan be any number (a0). Algebra i sused in many studies, for example, elementary algebra, linear algebra, Boolean algebra, and so on. 1 Polynomials ‘Apolynomial involves operations of addition, subtraction, multiplication, and non-negati ve integer exponents of terms consisting of variables and coefficients. For example, x¢ + 2x= 3 is a polynomial in the single variable x. Polynomial can be rewritten using commu tative, associative and distributive laws. ‘An important part of algebra is the factorization of polynomials by expressing a given po lynomial as a product of other polynomials that cannot be factored any further. Another i mportant part of algebra is computation of polynomial greatest common divisors. x2 + 2 x= 3.can be factored as (x- 1)(x+3) 12 Boolean Algebra Boolean algebra is the branch of algebra in which the values of the variables are true val ues denoted by 1 and 0 or true and false respectively. Boolean algebra can be used to describe logic circuit; itis also use to reduce complexity of digital circuits by simplifying the logic circuits. Boolean algebra is also referred to as B oolean logic. It was developed by George Boole sometime on the 1840s and is greatly us ed in computations and in computer operations. The name Boolean comes from the na me of the author Boolean algebra is a logical calculus of truth values. It somewhat resembles the arithmet “d rT_ L “] ic algebra of real numbers but with a difference in its operators and operations. Boolean operations involve the set {0, 1), that is, the numbers 0 and 1. Zero [0] represents “false” o r “off” and One [1] represent 1 -Thue, on 0 - False, off This has proved useful in programming computer devices, in the selection of actions bas ed on conditions set. Basic Boolean operations 1. AND The AND operator is represented by a period or dot in-between the two operands e. g “XY The Boolean multiplication operator is known as the AND function in the logic do main; the function evaluates to 1 only if both the independent variables have thev alue 1 2. OR The OR operator is represented by an addition sign. Here the operation + is differe nt from that defined in normal arithmetic algebra of numbers. E.g. X+Y The # operator is known as the OR function in the logic domain; the function has a value of 7 if either or both of the independent variables has the value of 1 3. NOT The NOT operator is represented by X' or X. This operator negates whatever value is contained in or assigned to X. It changes its value to the opposite value. For instance, if the value contained in X is 1, X' giv es 0 as the result and if the value stored in X is 0, X' gives 1 as the result. In some texts, NOT may be represented as X To better understand these operations, truth table is presented for the result of any of the operations on any two variables. -_ L Truth Tables Atruth table is a mathematical table used in logic to compute the functional values of lo gical expressions on each of their functional arguments. It is specifically in connection w ith Boolean algebra and Boolean functions. Truth tables can be used to tell if a propositi on expression is logically valid. In a truth table, the output is completely dependent on th einput. Itis composed of a column for each input entry and another column the corresp onding output. Each row of the truth table therefore contains one possible configuration of the input variables (for instance, X=true Y=false), and the result of the operation for th ose values Applications of truth table 1. The truth table can be used in analyzing arguments 2. It is used to reduce basic Boolean operations in computing 3. It is used to test the validity of statements. In validating statements, the follow ing three steps can be followed a. Represent each premise (represented as inputs) with a symbol (a variable). b. Represent the conclusion (represented as the final result) with a symbol (a vari able) ©. Drawa truth table with columns for each premise (input) and a column for the conclusion (result) Truth tables are a means of representing the results of a logic function using a table. Th ey are constructed by defining all possible combinations of the inputs to a function in th e Boolean algebra, and then calculating the output for each combination in turn. The bas ic truth table shows the various operators and the result of their operations involving two variables only. More complex truth tables can be built from the knowledge of the foundat ional truth table. The number of input combinations in a Boolean function is determined by the number of variables in the function and this is computed using the formula 2”. Number of input combinations =2". Where nis number of variable(s) For example, a function with two variables has an input combination of 27=4, Another w ith three variables has 2?=8 input combinations, and so on. AND “d rTx [¥ [XY NOT‘The NOT operation is a unary operator, it accepts only one input. Example: Draw a truth table for A+B BC_}ASBC *Draw a truth table for AB+BC. AB [BC | AB+BC =|=[=[=Jefefefe]>|a a)alelel/a[alelole =Jel=lel=le|=Telo =)=]=]=Jolelolo|> =|=}elel=|=\elele alolalolsfolatolo alelelo[slolelo «Draw a truth table for A(B+ D). A[B[D [B+D | A(B+D) 0 O}0j\0 0 oo o}j1 41 0 o41j011 0 oj j1jiii 0 1jololo /o Tiojiii it Tiijol i tai AB | ABC + ABC c ojo joj1 oi 1 ojo ji|1 ojo jo oj1 jojijojijo jo foo{1 |i{1fofofo |{o fo ilo jojo jaja it o fi iio /1/ol1jolo jo fo 1|1 /olo joli1 lo jo fo 1{1 |i Jo jojojo jo fo Basic Logic Gates Logic can be viewed as black boxes with binary input (independent variable) and binary output (dependent variable). It also refers to both the study of modes of reasoning and t he use of valid reasoning. In the latter sense, logic is used in most intellectual activities Logie in computer science has emerged as-a discipline and it has been extensively appli edin the fields of Artificial Intelligence, and Computer Science, and these fields provide a rich source of problems in formal and informal logic. Boolean logic, which has been considered as a fundamental part to computer hardware, particularly, the system's arithmetic and logic structures, relating to operators AND, NOT, and OR, Logic gates Alogic gate is an elementary building block of a digital circuit. Complex electronic circuit sare built using the basic logic gates. At any given moment, every terminal of the logic g ate is in one of the two binary conditions low (0) of high (1), represented by different volt age levels There are 3 basic logic gates: AND, OR, NOT. Other gates- NAND, NOR, XOR and XNOR are based on the3 basic gates. ‘The AND gate The AND gate is so called because, if 0is called “false” and 1 is called "true! the gate act sin the sameway as the logical ‘and” operator. The following illustration and table show the circuit symbol and logic combinations for an AND gate The output is “true when both inputs are "true." Otherwise, the output is “false.”Louiclunctions = Z2AB “rath Table: The OR gate The OR gate gets its name from the fact that it behaves after the way of the logical “or” The output is "true’ if either or both of the inputs are "true." If both inputs are "false; then the output is “false.” amputs, gurput a z B Logie Function: = Z = A+B ‘nwh Table Tnpuls—— Quiput A B Zz oo] 0 oo 1 104 1 1 1 The NOT gate Alogical inverter, sometimes called a NOT gate to differentiate it from other types of elec ‘tronic inverter devices, has only one input. It reverses the logic state (i.e. its input). “d rTInput Duiput a Zz Logie Function: 7 = Truth Table: oput Output AZ 0 1 1 0 As previously considered, the AND, OR and NOT gates’ actions correspond with the AND, OR and NOT operators. More complex functions can be constructed from the three basic gates by using DeMorg ans Law. ‘The NAND gate ‘The NAND gate operates as an AND gate followed by a NOT gate. It acts in the manner 0 f the logical operation “and' followed by negation. The output is “false’ if both inputs are “ue! Otherwise, the output is “true’. It finds the AND of two values and then finds the op posite of the resulting value. Loputs ouput at Zz s— TogieTuneton: 7 9B tiuth abe: Inputs Ouiput A plz oo) 1 oO 1 1 to 4 1 1 | 0_ L ‘The NOR gate ‘The NOR gate is a combination of an OR gate fallowed by an inverter Its outputis "true" if both inputs are false." Otherwise, the output is “false’. It finds the OR of two values an d then finds the complement of the resulting value. snp a B lopietimeion: 7 = TaB Truth Table: Inputs Ourput The XOR gate The XOR (exclusive-OR) gate acts in the sameway as the logical “either/or The output i s"true’ if either, but not both, of the inputs are "true." The output is ‘false’ if both inputs a re “false or if both inputs are “true. Another way of looking at this circuit is to observe th at the output is 1 if the inputs are different, but 0 if the inputs are the same. =>) >, A @ B) XOR gate ABE 0 fo jo of 0 h The XNOR gate ‘The XNOR (exclusive-NOR) gate is a combination of an XOR gate followed by an inverter “] -_ L Its output is ‘true" ifthe inputs are the same, and'false' if the inputs are different. It perfo rms the operation of an XOR gate and then inverts the resulting value. XNOR gate