Bài giảng Nhập môn Tin học - Chương 5: Đại số Boole

Bài giảng Nhập môn Tin học - Chương 5 trình bày về đại số Boole. Nội dung chính trong chương này gồm có: Đại số boole là gì? Khái niệm cơ bản về đại số Boole, độ ưu tiên của các toán tử, các tiên đề của đại số Boole, nguyên lý đối ngẫu,... Mời các bạn cùng tham khảo.
Nội dung trích xuất từ tài liệu:
Bài giảng Nhập môn Tin học - Chương 5: Đại số BooleChương5:ĐạisốBooleĐạisốboolelàgì?LàphéptoánđạisốliênquanđếnhệthốngsốnhịphânDonhàtoánhọcngườiAnhđưaranăm18151864nhằm Đơngiảnhóaviệctrìnhbày Thaotácvớilogicmệnhđề1938ClaudeđềxuấtsửdụngđạisốBooletrongthiếtkếmạchCungcấpcáchtiếpcậntiếtkiệmvàđơngiảnĐượcsửdụngrộngrãitrongthiếtkếmạchđiệntửtrongmáytínhKháiniệmcơbảnvềĐạisốBooleCácphéptoántrongđạisốBoolethựchiệntrêncácbiếncó2giátrị0và1, gồm Cộnglogic:‘+’hayOR Nhânlogic:‘.‘hayAND Phépbù:‘’hayNOTKháiniệmcơbảnvềĐạisốBooleBảngchântrị: A B AANDB AORB NOTA 0 0 0 0 1 0 1 0 1 1 1 0 0 1 0 1 1 1 1 0ĐộưutiêncủacáctoántửToántửcóđộưutiêncaonhấtđượcđịnhtrịđầutiên.Biểuthứcđượctínhtừtráisangphải Độưutiên Toántử 1 ()Biểuthứctrongngoặc 2 _(NOT) 3 .(AND) 4 +(OR)ĐộưutiêncủacáctoántửCáctiênđềcủađạisốBooleCáctiênđềcủađạisốBooleNguyênlýđốingẫuCósựđốingẫugiữatoántửAND,ORvàbit0,1CácđịnhlýcủađạisốBooleCácđịnhlýcủađạisốBooleHàmBooleMộthàmBoolelàmộtbiểuthứcđượcthựchiệnvới: Cácbiếnnhịphân CáctoántửAND,OR,NOT Cácdấungoặcvàđấu= GiátrịcủahàmBoolecóthểlà0hoặc1 MộthàmBoolecóthểđượcbiểudiễndạng:  Mộtbiểuthứcđạisố  MộtbảngchântrịHàmBooleHàmBoolebiểudiễndướidạngbiểuthứcđạisố: Hoặc Với:X,YvàZđượcgọilàcácbiếncủahàm. HàmBooleHàm Boole biểu diễn dưới X Y Z W dạngbảngchântrị 0 0 0 0Số hàng của bảng là 2n, n là 0 0 1 1 số các biến nhị phân được sử 0 1 0 0 dụngtronghàm. 0 1 1 0 1 0 0 1 1 0 1 1 1 1 0 1 1 1 1 1SựdưthừaKháiniệm: Literal:làcácbiếntronghàmBoole Termcủanbiến làsựkếthợpcủacácbiếnmàmỗibiếnchỉxuấthiệnmột lầnduynhất. Vídụ:termcủa3biếnA,B,ClàA.B.CMộtbiểuthứclàdưthừanếunócóchứa Literallặp:XXhayX+X Biếnvàbùcủabiến:XX’hayX+X’ Hằng:0hay1TốithiểuhóahàmBooleTốithiểuhàmBoolean: Giảmsốphầntử(Term) Giảmsốbiến(Literal)Phươngpháp: Sửdụngphươngphápđạisố Ápdụngcácđịnhlý,tiênđề,cácluậtnhiềulầnđểtốithiểuhàmBooleantới mứcthấpnhất.TốithiểuhóahàmBoolePhầnbùcủahàmBoolePhầnbùcủahàmBooleVídụ:tínhphầnbùcủahàmsau: Bước1:ChuyểntoántửANDthànhORvàngượclại. Bước2:tínhphầnbùcủacácbiếnDạngchínhtắccủahàmBooleMộthàmnbiếnluônđượcbiểudiễndưới2dạng:Dạngtổngcáctích(sumofproductSOP):biểuthứcđượcbiểudiễndưới dạng tổng(sum)các toánhạng (term), mỗi toánhạng là tích (product) của cácliteralDạngtíchcáctổng (productofsumPOS):biểuthứcđượcbiểudiễndưới dạngtíchcáctoánhạng,mỗitoánhạnglàtổngcủacácliteral ...