Introduction to Computer Engineering PDF

INTRODUCTION TO COMPUTER ENGINEERING WEEK-3 Dr. İdris KAHRAMAN BOOLEAN ALGEBRA ▪ Boolean Algebra was created by the mathematician George Boole in the 1850s as a result of his desire to give symbolic form to Aristotle's science of logic. ▪ ―true,1 – false,0, Yes – No, Open – Closed, 1 – 0 etc. ▪...

INTRODUCTION TO COMPUTER ENGINEERING WEEK-3 Dr. İdris KAHRAMAN BOOLEAN ALGEBRA ▪ Boolean Algebra was created by the mathematician George Boole in the 1850s as a result of his desire to give symbolic form to Aristotle's science of logic. ▪ ―true,1 – false,0, Yes – No, Open – Closed, 1 – 0 etc. ▪ Boolean Algebra is a symbolic system consisting of the basic logical operations AND (AND,. , ^ ), OR (OR, + , v ) and NOT (NOT, ˉ , ΄ ) BOOLEAN ALGEBRA ▪ Boolean Algebra forms the basis for the design of circuits used in computers. ▪ It does not use numerical quantities as variables as in algebra, but inputs with a truth value of 1 (one) or a falsity value of 0 (zero) and allows operations with propositions. ▪ The capital of Turkey is Adana (false,0 - 0) ▪ The capital of Turkey is Ankara (true,1 - 1) BOOLEAN ALGEBRA ▪ Let x and y be two propositions. Let us denote true propositions by 1 (one) and false propositions by 0 (zero). ▪ AND(⋀) – OR(⋁) ▪ Accordingly: x y 𝒙⋀𝒚 = 𝒙. 𝒚 𝒙⋁𝒚 = 𝒙 + 𝒚 𝐀 y' true,1 true,1 true,1 true,1 0 0 true,1 false,0 false,0 true,1 0 1 false,0 true,1 false,0 true,1 1 0 false,0 false,0 false,0 false,0 1 1 FUNDAMENTALS OF BOOLEAN ALGEBRA Commutative Law Associative Law Distributive Law 𝐴+𝐵 =𝐵+𝐴 𝐴 + 𝐵 + 𝐶 = 𝐴 + 𝐵 + 𝐶 = 𝐴 + (𝐵 + 𝐶) 𝐴. 𝐵 + 𝐶 = 𝐴. 𝐵 + 𝐴. 𝐶 𝐴. 𝐵 = 𝐵. 𝐴 𝐴. 𝐵. 𝐶 = 𝐴. 𝐵. 𝐶 = 𝐴. (𝐵. 𝐶) 𝐴 + 𝐵. 𝐶 = 𝐴 + 𝐵. (𝐴 + 𝐶) Complement Law AND Law OR Law 𝐴. 𝐴 = 0 𝐴. 1 = 𝐴 𝐴+0= 𝐴 𝐴+𝐴 = 1 𝐴. 0 = 0 𝐴+1= 1 Identity Law De Morgan Theorem Ingestion Law 𝐴+𝐴 = 𝐴 𝐴. 𝐵 = 𝐴 + 𝐵 𝐴 + 𝐴. 𝐵 = 𝐴 𝐴. 𝐴 = 𝐴 𝐴 + 𝐵 = 𝐴. 𝐵 𝐴. (𝐴 + 𝐵) = 𝐴 EXAMPLES ▪ Example 1. Find the equivalent of the following expression using theorems. 𝐹 = 𝐴(𝐴 + 𝐵) ▪ Example 2. Find the equivalent of the following expression using theorems. 𝐹 = 𝐴𝐵 + 𝐴𝐵) VENN DIAGRAM FOR BOOLEAN LOGIC VENN DIAGRAM FOR BOOLEAN LOGIC VENN DIAGRAM FOR BOOLEAN LOGIC TRUTH TABLE ▪ A truth table is a table that shows all the possibilities taken by the variables in a Boolean expression. ▪ Truth tables are considered to be the simplest and most useful method for analyzing digital circuitry. A B ▪ n number of inputs can take 𝟐𝒏 number of input values. 0 0 0 1 1 0 1 1 TRUTH TABLES AND SIMPLIFYING THE PROCESS ▪ Example: Truth table of the operation/function A.B+A If A=0 and B=0, A.B=0 A B A.B A.B+A Then A.B+A= 0+0= 0 0 0 0 0 If A=0 and B=1, A.B=0 Then A.B+A= 0+0= 0 0 1 0 0 If A=1 and B=0, A.B=0 1 0 0 1 Then A.B+A= 1+0= 1 If A=1 and B=1, A.B=1 1 1 1 1 Then A.B+A= 1+1= 1 TRUTH TABLES AND SIMPLIFYING THE PROCESS Example: Simplify the following statements 𝐹 = 𝐴. 𝐵 + 𝐴. 𝐵 + 𝐵 ▪ 𝐹 = 𝐴. 𝐵 + 𝐴. 𝐵 + 𝐵 = 𝐵. 𝐴 + 𝐴 + 𝐵 = 𝐵. 1 + 𝐵 ▪ 𝐹 = 𝐴. 𝐵. 𝐶 + 𝐴. 𝐵. 𝐶 + 𝐴. 𝐵 =𝐵+𝐵 =1 ▪ 𝐹 = 𝐴. 𝐴 + 𝐵 ▪ 𝐹 = 𝐴𝐵 + 𝐴𝐵 𝐹 = 𝐴. 𝐵. 𝐶 + 𝐴. 𝐵. 𝐶 + 𝐴. 𝐵 ▪ 𝐹 = 𝐴𝐵 + 𝐴𝐵 + 𝐵 = 𝐴. 𝐵 𝐶 + 𝐶 + 𝐴. 𝐵 = 𝐴. 𝐵. 1 + 𝐴. 𝐵 ▪ 𝐹 = 𝐴 + 𝐴𝐵 + 𝐴𝐶 = 𝐴. 𝐵 + 𝐴. 𝐵 = 𝐵(𝐴 + 𝐴) = 𝐵. 1 =𝐵 LOGIC GATES ▪ Logic gates, which are frequently encountered in electronic circuits, produce logical results in accordance with the data received from the input within the framework of a certain Boolean Algebra. ▪ Logic gates contain various elements such as diodes, transistors, resistors, capacitors. ▪ Integrated circuits are systems that operate with low power but high speed, are small in size and have very few external wiring. LOGIC GATES AND TRUTH TABLES AND GATE OR GATE A B Z A B Z 0 0 0 0 0 0 0 1 0 0 1 1 1 0 0 1 0 1 1 1 1 1 1 1 NOT GATE A Z 0 1 1 0 NAND (AND NOT) GATE NOR (OR NOT) GATE 𝑋 = 𝐴. 𝐵 𝑋 =𝐴+𝐵 X A B Z A B Z 0 0 1 0 0 1 0 1 1 0 1 0 1 0 1 1 0 0 1 1 0 1 1 0 XOR GATE XNOR GATE 𝑋 = 𝐴 ⊕ 𝐵 = 𝐴. 𝐵 + 𝐴. 𝐵 𝑋 = 𝐴 ⊗ 𝐵 = 𝐴𝐵 + 𝐴. 𝐵 A B Z A B Z 0 0 0 0 0 1 0 1 1 0 1 0 1 0 1 1 0 0 1 1 0 1 1 1 XOR EXAMPLE In cryptography ▪ Data : 10101100 ▪ Key: 11010011 ▪ XOR Result: 01111111 (Encrypted data) ▪ To decrypt, we XOR again: ▪ 01111111 XOR 11010011 = 10101100 (Original data) Equality check ▪ Data 1: 10101100 ▪ Data 2: 10101000 ▪ XOR Result: 00000100 ▪ Data1 and Data2 are not equal LOGIC GATES AND TRUTH TABLES A B Z 0 0 0 0 1 1 1 0 1 1 1 1 LOGIC GATES AND TRUTH TABLES A B C B+C Z 0 0 0 0 0 0 0 1 1 0 0 1 0 1 0 0 1 1 1 0 1 0 0 0 0 1 0 1 1 1 1 1 0 1 1 1 1 1 1 1 OBTAINING MATHEMATICAL EXPRESSION FROM LOGIC DIAGRAM 𝐹 = 𝑋. 𝑌 + 𝑍 𝐹 = (𝑋. 𝑌 + 𝑍) ⊗ 𝑍 𝐹 =𝑋⊕𝑌+𝑋⊗𝑌