zunia.vn

Tuyển sinh 2024 dành cho Gen-Z

zunia.vn

» Công Nghệ Thông Tin

» Tin học văn phòng

Tin học cơ sở - Chương 5

Chia sẻ: Nguyễn Văn Thành | Ngày: | Loại File: DOC | Số trang:7

Báo xấu

117
lượt xem 23
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

Người đặt nền móng cho ngành toán học này là D. Boole (1815-1864). Do vậy đại số logic còn có tên gọi là đại số Boole. Đại số logic có nhiều ứng dụng, ở đây, chúng ta quan tâm đến các khía cạnh liên quan đến thiết kế các mạch logic bên trong MTĐT. Như đã thấy, kết quả thực hiện các phép toán số học với các số nhị phân là một số nhị phân mới. Do vậy, ta có thể hình dung thiết bị thực hiện các phép toán trong MTĐT như là thành phần chức năng biến đổi nhị phân. Thiết bị đặc...

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Tin học cơ sở - Chương 5

Ch¬ng 5 - Mét sè kiÕn thøc vÒ ®¹i sè logic CHƯƠNG 5. MỘT SỐ KIẾN THỨC VỀ ĐẠI SỐ LOGIC Người đặt nền móng cho ngành toán học này là D. Boole (1815-1864). Do v ậy đ ại số logic còn có tên gọi là đại số Boole. Đại s ố logic có nhi ều ứng d ụng, ở đây, chúng ta quan tâm đến các khía cạnh liên quan đ ến thi ết k ế các m ạch logic bên trong MTĐT. Như đã thấy, kết quả thực hiện các phép toán s ố h ọc v ới các s ố nh ị phân là một số nhị phân mới. Do vậy, ta có thể hình dung thi ết b ị th ực hi ện các phép toán trong MTĐT như là thành phần chức năng bi ến đ ổi nh ị phân. Thi ết b ị đặc biệt đó cho phép nạp số liệu dạng nhị phân ở đầu vào và l ấy kết qu ả có dạng nhị phân ở đầu ra. Vậy có thể xem bộ biến đ ổi ch ức năng đó nh ư là m ột thiết bị có nhiều đầu vào và nhiều đầu ra. Tại một thời điểm xác đ ịnh, ở m ỗi đ ầu vào chỉ nạp được một bit và từ mỗi đầu ra chỉ cho ra đ ược m ột bit d ữ li ệu. Đ ể hiểu rõ hơn về nguyên lý xây dựng các bộ biến đổi nhị phân ta s ẽ tìm hi ểu m ột số vấn đề có liên quan dưới đây. 5.1. CÁC HÀM ĐẠI SỐ LOGIC Xét tập D = {0, 1}, các giá trị của tập D còn g ọi là giá tr ị logic hay nh ị phân. Đ ại lượng x chỉ có thể nhận giá trị trong tập D gọi là bi ến Boole (hay bi ến logic, bi ến nhị phân). Hàm của n biến nhị phân F(x 1, x2, ..., xn) chỉ nhận hai giá trị 0 và 1 gọi là hàm Boole (hoặc hàm logic). Mỗi hàm boole n bi ến có th ể cho b ằng m ột b ảng có n+1 cột, n cột đầu là giá trị của các bi ến x 1, x2, ..., xn tương ứng. Cột cuối cùng là giá trị của hàm ứng với các giá trị của biến. Ví d ụ n = 2, các giá tr ị x1, x2 và các hàm tương ứng f(x1, x2) được cho như trong Bảng 5.1 x1 x2 f(x1,x2) 0 0 1 0 1 0 1 0 0 1 1 1 Bảng 5.1. Hàm logic 2 biến Dễ dàng thấy, với mỗi n có đúng 2 n cách tổ hợp khác nhau giá trị các biến x 1, x2, ..., xn. Một hàm Boole là một cách cho tương ứng mỗi một trong số 2 n với một trong hai giá trị 0 và 1. Vì thế nó sẽ tương ứng v ới m ột cách phân ho ạch t ập 2 n bộ giá trị này thành 2 nhóm, một nhóm hàm có giá tr ị 1, m ột nhóm hàm có giá tr ị 0. Như vậy mọi hàm boole n biến hoàn toàn được xác định b ởi m ột t ập con trong 2 n bộ giá trị để giá trị của hàm là 1. Ta đã bi ết đ ối v ới m ột t ập có k ph ần t ử thì t ập tất cả các tập con của nó sẽ có 2k phần tử. Do vậy có đúng 2n hàm Boole n biến. Với n = 1, có 4 hàm nhị phân. Các hàm đó được cho trong B ảng 5.2 37
Ch¬ng 5 - Mét sè kiÕn thøc vÒ ®¹i sè logic x F1 F2 F3 F4 0 0 1 0 1 1 0 1 1 0 Bảng 5.2. Các hàm logic 1 biến Hàm F1 và F2 là hàm hằng (không phụ thuộc vào đối số x): F1(x) ≡ 0 là hàm hằng 0 F2(x) ≡ 1 là hàm hằng 1 Giá trị F3(x) luôn bằng giá trị biến x, đó là hàm đồng nh ất: F3(x) ≡ x Hàm F4(x) luôn có giá trị ngược lại với giá trị biến x mà ta g ọi là hàm ph ủ đ ịnh và ký hiệu  x. Dễ thấy   x = x Dấu  có thể xem là dấu phép toán một ngôi, cho phép t ừ giá tr ị x xác đ ịnh giá tr ị  x. Phép toán đó cũng có tên là phép ph ủ đ ịnh (m ột s ố tài li ệu dùng d ấu - trên đầu đối tượng bị phủ định thay cho dấu  đứng trước đối tượng). Với n = 2, có 16 hàm logic. Giá trị của các hàm được cho ở bảng 5.3. F10 F11 F16 F12 F13 F14 F15 F2 x y F1 F3 F4 F5 F6 F7 F8 F9 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 0 1 0 0 0 0 1 1 1 1 0 0 0 0 1 1 1 1 1 0 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 1 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 Bảng 5.3. 16 hàm logic 2 biến Ta xét một vài hàm quan trọng: • F2(x, y) có giá trị 1 khi và chỉ khi x, y đồng thời có giá tr ị 1. Hàm này đ ược kí hiệu là (x∧ và gọi là phép nhân logic hay phép hội. y) • F7(x, y) có giá trị 1 khi và chỉ khi x, y có giá trị khác nhau. Hàm này chính là chữ số hàng đơn vị khi cộng số học x với y. Vì vậy F7 còn g ọi là phép cộng theo module 2. • F8(x,y) có giá trị 0 khi và chỉ khi x, y đồng th ời có giá tr ị 0. Hàm F8(x,y) được kí hiệu (x ∨y) và còn gọi là phép cộng logic hay phép tuyển. 38
Ch¬ng 5 - Mét sè kiÕn thøc vÒ ®¹i sè logic • F10(x,y) có giá trị 1 khi và chỉ khi x, y có cùng giá trị nh ư nhau, ho ặc 0 hoặc 1. Hàm F10(x,y) có kí hiệu (x ∼ y) và còn gọi là phép tương đương • F14(x,y) có giá trị 0 khi và chỉ khi x có giá trị 1 đ ồng th ời y có giá tr ị 0. Hàm F14(x,y) được kí hiệu (x ⇒y) và còn gọi là phép kéo theo. Bài đọc thêm: Logic mệnh đề Lần đầu tiên logic mệnh đề được đề cập đến trong m ột bài báo c ủa Boole có tên là "Các quy lu ật của ý nghĩ". Theo đó mỗi mệnh đề là một khẳng định. Mệnh đ ề s ẽ nh ận giá trị chân lý là "đúng" hay "sai" tuỳ thuộc vào khẳng định có phù hợp với th ực t ế hay không. Sau đó Boole đ ưa ra các phép toán để tính giá trị chân lý của những mệnh đề phức tạp. Giả sử P và Q là hai mệnh đề nào đó. Mệnh đề "P và Q" s ẽ nh ận giá trị là đúng n ếu c ả P và Q đều đúng. Nếu thể hiện giá trị đúng bằng 1 và giá trị sai là 0 ta th ấy giá tr ị chân lý c ủa m ệnh đ ề "P và Q" chính là phép nhân logic các giá trị chân lý c ủa P và Q. Do v ậy trong ngôn ng ữ Tin h ọc người ta gọi luôn phép nhân logic là phép "AND". Giá trị chân lý của mệnh đề "P hoặc Q" chính là phép c ộng logic các giá tr ị chân lý c ủa P và Q. "P hoặc Q" sẽ đúng chỉ cần ít nhất P hoặc Q đúng. Trong trong ngôn ng ữ Tin h ọc, ng ười ta cũng g ọi phép cộng logic là phép "OR". Giá trị chân lý của mệnh đề "Không phải P" sẽ đúng nếu P sai và ng ược l ại. Giá trị này có th ể tính bằng phép phủ định logic giá trị chân lý của P. Trong trong m ột s ố ngôn ng ữ Tin h ọc, phép ph ủ định logic còn có một tên gọi khác là phép "NOT". Phép cộng theo module 2 còn gọi là phép "hoặc loại trừ" (OR Exclusive) và trong ngôn ng ữ tin h ọc người ta gọi nó là phép "XOR". 5.2. BIỄU DIỄN CÁC HÀM ĐẠI SỐ LOGIC Một hàm đại số logic cũng có thể được xác đ ịnh thông qua các hàm đ ại s ố logic khác, ví dụ hàm F7(x,y) trong Bảng 5.3 có thể cho bằng công thức sau: ( x ∧  y ) ∨ ( x ∧ y ) Hai công thức dưới đây gọi là công thức đối ngẫu De Morgan.  (x ∧y) =( x) ∨(  y),  ( x V y) = ( x) ∧( y) Các công thức này cho thấy có thể biểu di ễn phép c ộng qua phép nhân và phép phủ định (và ngược lại), chẳng hạn, x V y =  ( x) ∧( y). Sau đây là hai công thức khác : (x ⇒ y) =  x ∨y, ( x ∼ y) = (x ∨ y) ∧ (y ∨x). Có nhiều cách chứng minh một đẳng thức logic trong đó có m ột cách ch ứng minh rất đơn giản là so sánh giá trị của hai v ế v ới t ất c ả các b ộ đ ối s ố c ụ th ể. Vì ch ỉ có một số hữu hạn các bộ đối số nên chúng ta có thể kể ra tất c ả các tr ường h ợp trong một bảng giá trị. Chẳng hạn để chứng minh công thức của hàm F7 nói trên ta có thể lập một bảng và so sánh giá trị của hai vế ứng với m ỗi b ộ giá tr ị c ủa các đối như Bảng 5.4: 39
Ch¬ng 5 - Mét sè kiÕn thøc vÒ ®¹i sè logic  x ∧y x ∧ y ( x ∧ y) ∨ (x ∧ y) x y F7(x,y) 0 0 0 0 0 0 0 1 0 1 1 1 1 0 0 1 1 1 1 1 0 0 0 0 Bảng 5.4. Giá trị F7(x,y) Qua các ví dụ trên ta thấy rằng các hàm đại số logic này có thể bi ểu di ễn qua các hàm đại số logic khác. Một tập hợp hữu hạn các hàm đại số logic được gọi là một hệ hàm đ ủ n ếu m ọi hàm đại số lôgic khác đều có thể biểu diễn được qua hệ hàm này. Có th ể ch ứng minh không khó khăn lắm rằng hệ hai hàm phủ định và c ộng logic là h ệ hàm đ ủ. Do công thức đối ngẫu De Morgan ta thấy hệ hai hàm ph ủ đ ịnh và nhân logic cũng là hệ hàm đủ. 5.3. ÁP DỤNG ĐẠI SỐ LOGIC TRONG VIỆC THIẾT KẾ CÁC MẠCH LOGIC MTĐT biểu diễn thông tin bằng các trạng thái c ủa các thành ph ần v ật lý. Thông thường các thành phần này có hai trạng thái đ ối lập. Ví d ụ nh ư m ột m ạch đi ện đóng hoặc mở, chiều của từ trường một vùng vật liệu từ nhiễm t ừ theo chiều này hoặc chiều kia... Nếu dùng trạng thái này ch ỉ giá tr ị 1 và tr ạng thái kia ch ỉ giá tr ị 0 thì ta thấy rằng MTĐT là một máy làm việc trên h ệ nh ị phân. M ọi phép x ử lý máy có thể thực hiện được thực chất là các hàm đại số logic. Các h ệ v ật lí th ực hi ện các hàm đại số logic gọi là các mạch logic. Ta minh họa một số mạch logic đơn giản dùng các công t ắc ng ắt ho ặc đóng mạch có điều khiển (gọi là các rơle) với quy ước rằng trạng thái có đi ện th ể hi ện giá trị logic 1, trạng thái không có điện thể hiện giá trị logic 0. Phần tử AND Cho mạch điện có hai rơle K1, K2 mắc nối tiếp như Hình 5.1. Ch ỉ khi có dòng điện điều khiển để đóng K1 và K2 thì mới có dòng điện qua R. Vì v ậy s ự ph ụ thuộc trạng thái R vào các trạng thái K1, K2 có th ể bi ến đ ổi R= K1 ∧K2 R K1 K2 Hình 5.1. Sơ đồ phần tử AND 40
Ch¬ng 5 - Mét sè kiÕn thøc vÒ ®¹i sè logic Phần tử OR Cho mạch điện cũng có hai rơle K1, K2 với tính ch ất nh ư v ừa xét, nh ưng đ ược mắc song song theo Hình 5.2: K1 R K2 Hình 5.2. Sơ đồ phần tử OR Dễ nhận thấy R không có dòng điện (thể hiện giá trị 0) khi và ch ỉ khi K1 và K2 đồng thời ngắt mạch (thể hiện giá trị 0). Do đó, giá tr ị logic R th ể hi ện là t ổng logic của các giá trị của K1 và K2 thể hiện. Phần tử NOT Xét mạch điện có sơ đồ như trên Hình 5.3. Khi K mở, dòng đi ện ph ải đi qua R, còn khi K đóng, do điện trở của K vô cùng bé so v ới R nên dòng đi ện đi qua K mà không đi qua R. Do vậy, giá trị logic R thể hiện là ph ủ đ ịnh giá tr ị mà K th ể hi ện. Hình 5.3. Sơ đồ phần tử NOT K R O T Trên thực tế các mạch logic thường được chế tạo từ các mạch bán dẫn ho ặc các mạch vi điện tử với kích thước siêu nhỏ. Người ta cũng ch ế t ạo nh ững m ạch (phần tử) OR, AND, NOT, NAND (NOT AND), NOR (NOT OR), XOR và c ả nh ững mạch có chức năng phức tạp thực hiện các xử lý phức t ạp h ơn. Các h ệ này g ọi là các hệ logic. Như vậy có thể hình dung các h ệ logic nh ư nh ững h ộp đen (mà ta không quan tâm đến cấu trúc bên trong) có một số đầu vào và m ột s ố đ ầu ra. Các tín hiệu ở đầu vào và đầu ra là các tín hiệu nh ị phân (t ương ứng v ới m ột trong hai trạng thái vật lý). Ta đã bi ết h ệ hàm ph ủ đ ịnh, tuy ển và h ội là m ột h ệ hàm đủ. Như vậy về mặt nguyên tắc có thể chồng chất các phần tử NOT và OR và AND để tạo nên bất cứ một máy thực hiện các phép biến đổi nhị phân nào. Ví d ụ sau đây minh họa việc lập mạch cộng hai bit. Bộ cộng 2 bit Hình 5.4 41
Ch¬ng 5 - Mét sè kiÕn thøc vÒ ®¹i sè logic Phép cộng hai số một bit a và b có th ể cho ra m ột s ố có hai bit là cd. Bit c ch ỉ bằng 1 khi và chỉ khi a, b đồng thời bằng 1 (ứng với trường h ợp 1 + 1 = 10). Do đó c = a ∧b. Còn d, như đã trình bày trước đây, chính là t ổng theo module 2 c ủa a và b có biểu diễn qua các hàm cộng, nhân và phủ định logic nh ư sau d = ( a ∧  b ) ∨ ( a ∧ b ) b a Vậy sơ đồ mạch logic của phép cộng hai bit có thể xây dựng như trong Hình 5.5. Trên đây là một ví dụ đơn giản cho th ấy người ta có thể xây dựng các mạch thực hiện các chức năng xử lý như thế nào. Đương nhiên mạch của một bộ xử lý có thể thực hiện được hàng trăm loại phép tính và O O hàng trăm chức năng điều khiển sẽ rất phức T T tạp. Bộ vi xử lý Itanium của Intel xuất xưởng trong năm 2001 là một mạch điện chứa t ới vài chục triệu transitor. c d Hình 5.5. S ơ đồ bộ cộng hai bit Bài tập 1. Dùng phương pháp bảng hãy chứng minh các công th ức đ ối ng ẫu De Morgan, biểu diễn của phép tương đương và phép kéo theo. 2. Hãy chứng minh công thức biểu diễn một hàm đ ại s ố logic d ưới d ạng chu ẩn hội f(x1,x2,...xn) = ∨(e1∧ 2∧ en) e .. {(x1,x2...xn) / f(x1,x2,...xn)=1} trong đó ei chính là xi nếu trong bảng giá trị x i = 1 và bằng x nếu trong bảng giá i trị xi=0. 3. Nếu cộng hai số nhiều bit thì mỗi bit c ủa t ổng s ẽ là t ổng c ủa 3 bit, hai bit c ủa hai số hạng và bit nhớ từ hàng bên phải. Như vậy để xây d ựng b ộ c ộng hai s ố nhiều bit trước hết phải xây dựng bộ cộng 3 bit. Hãy xây d ựng b ộ c ộng 3 bit b ằng cách tổng hợp từ hai bộ cộng hai bit. 4. Sau khi có bộ cộng 3 bit, hãy xây dựng bộ cộng 2 số n bit. 42
Ch¬ng 5 - Mét sè kiÕn thøc vÒ ®¹i sè logic 43

CÓ THỂ BẠN MUỐN DOWNLOAD

THÔNG TIN

TRỢ GIÚP

HỖ TRỢ KHÁCH HÀNG

Theo dõi chúng tôi

Chịu trách nhiệm nội dung:

Nguyễn Công Hà - Giám đốc Công ty TNHH TÀI LIỆU TRỰC TUYẾN VI NA

LIÊN HỆ

Địa chỉ: P402, 54A Nơ Trang Long, Phường 14, Q.Bình Thạnh, TP.HCM

Hotline: 093 303 0098

Email: support@tailieu.vn

Giấy phép Mạng Xã Hội số: 670/GP-BTTTT cấp ngày 30/11/2015 Copyright © 2022-2032 TaiLieu.VN. All rights reserved.