Mathematical Foundation of Computer Science

DHARM N-COM\CMS12-1.PM5 344 MATHEMATICAL FOUNDATION OF COMPUTER SCIENCE r to p through t if β is a string of all b’s, r to p th ...

DHARM N-COM\CMS12-1.PM5 INTRODUCTION TO TURNING MACHINE 345 State Diagram (B, B, R) p (B, B, R) (X, , L)a (Y, , L)b (, ,R)aa (, ...

DHARM N-COM\CMS12-1.PM5 346 MATHEMATICAL FOUNDATION OF COMPUTER SCIENCE Number 0 is represented by 0 Number 1 is represented by ...

DHARM N-COM\CMS12-1.PM5 INTRODUCTION TO TURNING MACHINE 347 (x 1 + 1)0’s (x 2 + 1)0’s 00001 BBB q 0 Breaker Fig. 12.20 Turing ma ...

DHARM N-COM\CMS12-1.PM5 348 MATHEMATICAL FOUNDATION OF COMPUTER SCIENCE (0, 0, R) (0, X, R) (1, 1, R) (0, 0, R) (B, B, L) (0, B, ...

DHARM N-COM\CMS12-1.PM5 INTRODUCTION TO TURNING MACHINE 349 tape cells contains (x + 1) 0’s corresponding to string x followed b ...

THIS PAGE IS BLANK ...

Boolean Algebra A.1 Introduction A.2 Definition of Boolean Algebra A.3 Theorems of Boolean Algebra A.4 Boolean functions A.7 Sim ...

A Boolean Algebra 352 A.1 INTRODUCTION Like any other mathematical system, Boolean algebra, is defined by a set of elements X, a ...

DHARM N-COM\APPENDIX.PM5 BOOLEAN ALGEBRA 353 and also operator ‘+’ is distributive over operator ‘. ’ whenever, x + (y. z) = (x ...

DHARM N-COM\APPENDIX.PM5 354 MATHEMATICAL FOUNDATION OF COMPUTER SCIENCE Since, 0 + 0 = 0 and 0 + 1 = 0 + 1 = 1 (existence of a ...

DHARM N-COM\APPENDIX.PM5 BOOLEAN ALGEBRA 355 Since, postulates are the basic axioms of algebraic structures and so they required ...

DHARM N-COM\APPENDIX.PM5 356 MATHEMATICAL FOUNDATION OF COMPUTER SCIENCE Theorem involving 2/3 variables can be proved algebraic ...

DHARM N-COM\APPENDIX.PM5 BOOLEAN ALGEBRA 357 xyzF 1 F 2 F 3 F 4 0001000 0010100 0100010 0110001 1000011 1010101 1100111 1110101 ...

DHARM N-COM\APPENDIX.PM5 358 MATHEMATICAL FOUNDATION OF COMPUTER SCIENCE f = (x + y)′′′′′. (x′ + y′)′ Simplification of such Bo ...

DHARM N-COM\APPENDIX.PM5 BOOLEAN ALGEBRA 359 Then, f ′ = X + Y = q′ p + r p + q′ s′ + r s′ + p′ r′ + q r′ + p′ s + q s = 1 (read ...

DHARM N-COM\APPENDIX.PM5 360 MATHEMATICAL FOUNDATION OF COMPUTER SCIENCE Thus we can express the Boolean function f containing n ...

DHARM N-COM\APPENDIX.PM5 BOOLEAN ALGEBRA 361 Similarly we can obtain, f 2 (x, y, z) = x′yz + xy′z′ + xy′z + xyz′ + xyz = m 3 + m ...

DHARM N-COM\APPENDIX.PM5 362 MATHEMATICAL FOUNDATION OF COMPUTER SCIENCE (ii) Consider the next Boolean function f 2 (x, y, z) = ...

DHARM N-COM\APPENDIX.PM5 BOOLEAN ALGEBRA 363 = r′s′ + r′s + r s′ + r s ( t′ + t = 1) P2 = r′ (s + s′) + r (s′ + s) P4 = r′ × 1 + ...