Sri Lanka Institute of Information Technology Mathematics for Computing - PDF

Sri Lanka Institute of Information Technology Faculty of Computing IT1130 - Mathematics for Computing Ms.Nilushi Dias Year 01 Semester 01 Year 01 Semester 01 1 / 57  Lecture 1 Logic Contro...

Sri Lanka Institute of Information Technology Faculty of Computing IT1130 - Mathematics for Computing Ms.Nilushi Dias Year 01 Semester 01 Year 01 Semester 01 1 / 57  Lecture 1 Logic Control Year 01 Semester 01 2 / 57 Outline 1 Number Systems 2 Boolean Algebra 3 Computer Arithmetic 4 Logic Gates Year 01 Semester 01 3 / 57 Number Systems Year 01 Semester 01 4 / 57 Number Systems Mathematical notation/symbols for representing values (numbers). In different systems, different symbols are used. Year 01 Semester 01 5 / 57 Positional Number System The most common base used in everyday activities is 10 (Decimal System). Different bases are used in other situations. The base can be written as a subscript to the number for easy identification. Example: 126510 0100000012 4 types of positional number systems are discussed: Decimal (Base = 10, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9). Binary (Base = 2, 0, 1). Octal (Base = 8, 0, 1, 2, 3, 4, 5, 6, 7, 8). Hexadecimal (Base = 16, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, A, B, C, D, E, F). Year 01 Semester 01 6 / 57 Positional Number System (cont’d) We are used to dealing with numbers in the decimal system. This is probably a result of having ten fingers. It is a positional number system. Roman number system is not such a system. The position of the symbol denotes the magnitude. A positional number system uses a base (aka radix). A number system with base b is a system that uses distinct symbols for b digits. Year 01 Semester 01 7 / 57 Positional Number System (cont’d) To determine the quantity, it is necessary to multiply each digit by an integer power of the base and then form the sum of all weighted digits. Example (724110):- Year 01 Semester 01 8 / 57 Binary Number System Mainly used in computers and computer-based devices. A computer contains electronic components that uses voltages. Therefore, numbers are represented in a computer with a base of 2. All other information is represented using a binary code as well. Letters of the alphabet and punctuation marks Microprocessor instruction Graphics/Video Sound Year 01 Semester 01 9 / 57 Number Base Conversion Should be able to convert a number in one base to another base. Examples will be discussed in converting, Decimal ↔ Binary Decimal ↔ Octal Decimal ↔ Hexadecimal Binary ↔ Octal Year 01 Semester 01 10 / 57 Repeated Division Method Can be easily used to convert a decimal number to another base. 1 Divide the number successively by the base. 2 After each division record the remainder. 3 The result is read from the last remainder upwards. Year 01 Semester 01 11 / 57 Repeated Division Method (Example) Convert 12310 to a binary representation. 123/2 q = 61 r = 1 61/2 q = 30 r = 1 30/2 q = 15 r = 0 15/2 q = 7 r = 1 7/2 q = 4 r = 1 4/2 q = 2 r = 0 2/2 q = 1 r = 0 12310 = 00110112 Year 01 Semester 01 12 / 57 Repeated Subtraction Method Can be used to convert a decimal number to binary. 1 Starting with the 1s place, write down all of the binary place values in order until you get to the first binary place value that is GREATER THAN the decimal number you are trying to convert. 2 AMark out the largest place value (it just tells us how many place values we need). 3 Subtract the largest place value from the decimal number. Place a “1” under that place value. Year 01 Semester 01 13 / 57 Repeated Subtraction Method 4 For the rest of the place values, try to subtract each one from the previous result. If you can, place a “1” under that place value. If you can’t, place a “0” under that place value. 5 Repeat Step 4 until all of the place values have been processed. Convert 12310 to binary using the repeated subtraction method Year 01 Semester 01 14 / 57 Other Base Conversions Binary/Octal/Hexadecimal to Decimal 1 Take the left most none zero bit, 2 Multiply by the base and add it to the bit on its right. 3 Now take this result, multiply by the base it and add it to the next bit on the right, 4 Continue in this way until the right-most bit has been added in. The fundamental setup of positional number systems can be used as well. Year 01 Semester 01 15 / 57 Other Base Conversions Binary to Octal/Hexadecimal 1 Form the bits into groups of three/four starting at the right and move leftwards. 2 Replace each group of three bits with the corresponding octal/hexadecimal digit. Octal/Hexadecimal to Binary The opposite of the above process is used Year 01 Semester 01 16 / 57 Conversion of Fractions Decimal Fractions to Binary Fractions 1 Begin with the decimal fraction and multiply by 2. The whole number part of the result is the first binary digit to the right of the point. 2 Disregard the whole number part of the previous result and multiply by 2 once again. The whole number part of this new result is the second binary digit to the right of the point. 3 Continue this process until we get a zero as our decimal part or until we recognize an infinite repeating pattern. Year 01 Semester 01 17 / 57 Conversion of Fractions (Example) Convert 0.62510 to binary. Convert 0.110 to binary. Convert 1.62510 to binary. Year 01 Semester 01 18 / 57 Conversion of Fractions (cont’d.) Binary Fractions to Decimal Fractions The fundamental setup of positional number systems used in converting binary integers to decimals can be used here. Represent 10.011012 as a decimal number Year 01 Semester 01 19 / 57 Summary Students should be able to, Understand the numerical system. Explain why computer designers chose to use the binary system for representing information in computers. Explain different number systems. Translate numbers between number system Understanding the pattern in each set of conversions will make it easier to remember the methods. Year 01 Semester 01 20 / 57 Boolean Algebra Year 01 Semester 01 21 / 57 Boolean Algebra A variable used in an algebraic formula so far, is assumed to take a set of numerical values. All variables in boolean equations can take only one of two possible values. Used symbols for the two values are 0 and 1. Rules first defined for logic by George Boole (1854), were adapted for the use in designing electronic circuits. The circuits in computers and other electronic devices have inputs, each of which is either a 0 or a 1. Year 01 Semester 01 22 / 57 Boolean Operators One major advantage in using these rules is to simplify an electronic circuit. Boolean algebra provides the operations and the rules for working with boolean variables. Three (3) boolean operators are discussed. Complement Boolean sum Boolean product Ten (10) rules are also discussed (aka Boolean Identities). Year 01 Semester 01 23 / 57 Boolean Operators Complement Defined as the opposite of the value that a boolean variable takes. Denoted with a bar (E.g.: A). 0 = 1 and 1 = 0. Boolean Sum Defined as the output to be 1 if at least one variable is 1. Denoted with the symbol + or by OR. 0 + 0 = 0, 0 + 1 = 1, 1 + 0 = 1 and 1 + 1 = 1. Year 01 Semester 01 24 / 57 Boolean Operators (cont’d.) Boolean Product Defined as the output to be 0 if at least one variable is 0. Denoted with the symbol ( ) or by AND. 0 0 = 0, 0 1 = 0, 1 0 = 0 and 1 1 = 1. When there is no danger of confusion, the symbol can be omitted. Order of boolean operators, 1 Complement. 2 Boolean products. 3 Boolean sums. Year 01 Semester 01 25 / 57 Boolean Identities 1 Law of Double Complement ¯ =A Ā 2 Idempotent Laws A+A=A A·A=A 3 Identity Laws A+0=A A·1=A 4 Domination/Null/Universal Bound Laws A+1=1 A·0=0 Year 01 Semester 01 26 / 57 Boolean Identities (cont’d.) 5 Commutative Laws A+B =B +A A · B =B · A 6 Associative Laws A + (B + C ) = (A + B) + C. A · (B · C ) = (A · B) · C 7 Commutative Laws A · (B + C ) = (A · B) + (A · C ) A + B · C = (A + B) · (A + C ) Year 01 Semester 01 27 / 57 Boolean Identities (cont’d.) 8 De Morgan’s Laws (A · B) = A + B (A + B) = A · B 9 Absorption Laws A · (A + B) = A A+A·B =A 10 Inverse Laws / Unit Zero Properties A+A=1 A·A=0 Year 01 Semester 01 28 / 57 Examples 1 Find the values of the following expressions. i. 1 · 0 ii. 1 + 1 iii. (1 + 0) 2 Prove both variants of the absorption law using other boolean identities. 3 Simplify the following expressions. i. ABD + ABD ii. (A + B)(A + B) iii. M = W X Y Z + W X Y Z + WX Y Z + W X Y Z Year 01 Semester 01 29 / 57 Truth Tables To verify the above rules, a truth table can be used. It’s also known as a Table of Combinations. It’s a table displaying all possible values for the variables and the outcomes for a boolean expression. If there are n number of variables, there will be 2n number of rows in the truth table. If the truth table for two boolean expressions shows the same outcomes for the same values for the variables, it can be concluded that the expressions are the same/equal. Year 01 Semester 01 30 / 57 Example 1 Use a table to express the values of each of these Boolean functions. i. AB ii. M = xy + (xyz) iii. F (x, y , z) = y (xz + xz) 2 Using a truth table, show that, xy + y z + xz = xy + y z + xz Year 01 Semester 01 31 / 57 Sum of Products (SoP) In some cases, the truth table might be known and we might want to know the expression that gives the truth table. This can be done by representing as a Sum of Products (SoP) of the variables and their complements. Steps:- 1 Select the rows in the truth table that gives 1 as the outcome. 2 Write how we can obtain 1 for the first selected row by using the product of the variables. 3 Repeat step two for all selected rows and use the sum to combine all results Year 01 Semester 01 32 / 57 Example Find the boolean expression for F from the given truth table Year 01 Semester 01 33 / 57 Product of Sums (PoS) Used for the same reason as a SoP. Product of Sums (PoS) has opposite steps of SoP. Steps:- 1 Select the rows in the truth table that gives 0 as the outcome. 2 Write how we can obtain 0 for the first selected row by using the sum of the variables. 3 Repeat step two for all selected rows and use the product to combine all results. Conversion can be done between the two using De Morgan’s rule. Year 01 Semester 01 34 / 57 Duality Principle In a boolean expression, if all the sums (+) and products (. ) are exchanged as well as if 1’s and 0’s are exchanged, the resulting expression is the opposite of the initial expression. This property is observed between SoP and PoS. The duel of the complement of one form is equal to the expression in the other form. Year 01 Semester 01 35 / 57 Summary Students should be able to, Understand the boolean expressions. Learn laws and rules of boolean algebra. Simplify boolean expressions using boolean identities. Use Sum of Products (SoP) and Product of Sums (PoS) to find boolean expressions. Understand similarities and differences between boolean variables as opposed to regular variables. Year 01 Semester 01 36 / 57 Computer Arithmetic Year 01 Semester 01 37 / 57 Introduction Recap: Binary numbers are a number system with base 2. Information represented inside a computer takes binary values. Previous lecture dealt with the conversions between different number systems. This lecture deals with basic mathematical operations (such as addition, subtraction, multiplication and division) for binary numbers. Year 01 Semester 01 38 / 57 Binary Addition Addition in the decimal number system. Add values rightmost position (least significant). If this addition is grater than 10, 1 is carried to the 2nd position and added. This process is carried for all the positions. Binary addition follows the same set of rules. If the addition is greater that 2, 1 is carried to the 2nd next position. Year 01 Semester 01 39 / 57 Binary Addition Evaluate the following. Year 01 Semester 01 40 / 57 Binary Subtraction Similar to subtraction in the decimal number system. Inverse of addition. If the values cannot be subtracted, borrow from the next position. Subtraction table, 0 - 0 = 0 1 - 0 = 1 1 - 1 = 0 0 - 1 = 1 with a borrow of 1. Year 01 Semester 01 41 / 57 Examples Evaluate the following. 10110 - 10010 1011011 - 10010 100010110 - 1111010 1010110 - 101010 101101 - 100111 1000101 - 101100 1110110 - 1010111 Compare the above results by converting them to decimal numbers. Year 01 Semester 01 42 / 57 Multiplication and Division Similar to multiplication and division in the decimal number system. Rules of binary multiplication, 0 × 0 = 0 0 × 1 = 0 1 × 0 = 0 1 × 1 = 1 Rules of binary division, 0÷1=0 1÷1=1 Year 01 Semester 01 43 / 57 Examples Evaluate the following. 1100 × 1010 1111 × 101 0011 × 11 1100110 × 1000 1000 ÷ 10 1010 ÷ 11 1111 ÷ 111 Compare the above results by converting them to decimal numbers. Year 01 Semester 01 44 / 57 Complementary Arithmetic Complements are used in digital computers for simplifying, the subtraction operation the logical manipulation. Two types of compliments for each base b system. r’s compliment (r - 1)’s compliment Example: For binary numbers, 2’s complement and 1’s complement. Year 01 Semester 01 45 / 57 Examples Get the 1’s and 2’s compliments of the following binary numbers. 1100011 0001111 1010100 1111011 Year 01 Semester 01 46 / 57 Logic Gates Year 01 Semester 01 47 / 57 Logic Gates A computer, or other electronic device, is made up of a number of circuits. The components in a logical circuit takes 0 and 1 as inputs. 1 is the state where there is a voltage on the input and 0 is the state where there is no voltage on the input. Year 01 Semester 01 48 / 57 Logic Gates Therefore, boolean algebra is used to model the circuitry in electronic devices. The absence of a voltage is usually denoted as 0 (zero) and the presence of a voltage is denoted by 1 (one). As mentioned earlier, concepts of boolean algebra can be used to simplify logical circuitry. There are a set of components that matches the boolean operators discussed earlier. These components are called Logic Gates. Year 01 Semester 01 49 / 57 Basic Logic Gates (NOT Gate Complement→ NOT Gate. Also known as inverter or complementer. Consists of a single input and a single output. As in the complement, the input gets inverted. Symbol: Truth Table: Year 01 Semester 01 50 / 57 Basic Logic Gates (OR Gate) Boolean Sum → OR Gate. Consists of two inputs and a single output. As in the sum, the output is 1 if at least one input is 1. Symbol: Truth Table: Year 01 Semester 01 51 / 57 Basic Logic Gates (AND Gate) Boolean Product → AND Gate. Consists of two inputs and a single output. As in the product, the output is 0 if at least one input is 0. Symbol: Truth Table: Year 01 Semester 01 52 / 57 Derived Logic Gates (NAND Gate) Created by combining an AND gate with a NOT gate. Symbol: Truth Table: Year 01 Semester 01 53 / 57 Derived Logic Gates (NOR Gate) Created by combining an OR gate with a NOT gate. Symbol: Truth Table: Year 01 Semester 01 54 / 57 Derived Logic Gates (XOR Gate) Similar to the OR Gate. Consists of two inputs and a single output. The output is 1 if ONLY ONE input is 1. Symbol: Truth Table: Year 01 Semester 01 55 / 57 Summary Students should be able to, Get an understanding about the need and usage of logic gates. Understand basic logic gates and the connection with boolean operators. The functions obtained by the logic gates. Draw truth tables for the logic gates. Draw circuit diagrams for the logic gates using the standard symbols. Drawing circuit diagrams from boolean expressions and vice versa. Year 01 Semester 01 56 / 57 Thank You! Year 01 Semester 01 57 / 57