Biểu thức & hàm Boolean

Đại số Boolean là đại số logic. Nó xử lý các biến có thể có hai giá trị rời rạc, 0 (Sai) và 1 (Đúng); và các phép toán có ý nghĩa logic. Phương pháp vận dụng logic biểu tượng sớm nhất được phát minh bởi George Boole và sau đó được gọi là Đại số Boolean.

Đại số Boolean ngày nay đã trở thành một công cụ không thể thiếu trong khoa học máy tính vì khả năng ứng dụng rộng rãi của nó trong lý thuyết chuyển mạch, xây dựng các mạch điện tử cơ bản và thiết kế máy tính số.

Các hàm Boolean

A Boolean functionlà một loại hàm toán học đặc biệt $ f: X ^ n \ rightarrow X $ độ n, trong đó $ X = \ lbrace {0, 1} \ rbrace $ là miền Boolean và n là số nguyên không âm. Nó mô tả cách lấy đầu ra Boolean từ đầu vào Boolean.

Example- Cho $ F (A, B) = A'B '$. Đây là một hàm bậc 2 từ tập hợp các cặp biến Boolean có thứ tự đến tập $ \ lbrace {0, 1} \ rbrace $ trong đó $ F (0, 0) = 1, F (0, 1) = 0, F (1, 0) = 0 $ và $ F (1, 1) = 0 $

Biểu thức Boolean

A Boolean expressionluôn tạo ra giá trị Boolean. Một biểu thức Boolean bao gồm sự kết hợp của các hằng số Boolean (Đúng hoặc Sai), các biến Boolean và các kết nối logic. Mỗi biểu thức Boolean đại diện cho một hàm Boolean.

Example - $ AB'C $ là một biểu thức Boolean.

Nhận dạng Boolean

Luật bổ sung kép

$ \ sim (\ sim A) = A $

Luật bổ sung

$ A + \ sim A = 1 $ (HOẶC Biểu mẫu)

$ A. \ sim A = 0 $ (AND Form)

Luật lý tưởng

$ A + A = A $ (HOẶC Dạng)

$ A. A = A $ (Dạng AND)

Luật nhận dạng

$ A + 0 = A $ (HOẶC Dạng)

$ A. 1 = A $ (Dạng AND)

Luật thống trị

$ A + 1 = 1 $ (HOẶC Biểu mẫu)

$ A. 0 = 0 $ (Dạng AND)

Luật thay thế

$ A + B = B + A $ (HOẶC Dạng)

$ A. B = B. A $ (Mẫu AND)

Luật kết hợp

$ A + (B + C) = (A + B) + C $ (HOẶC Dạng)

$ A. (B. C) = (A. B). C $ (Mẫu AND)

Luật hấp thụ

$ A. (A + B) = A $

$ A + (A. B) = A $

Luật đơn giản hóa

$ A. (\ sim A + B) = A. B $

$ A + (\ sim A. B) = A + B $

Luật phân phối

$ A + (B. C) = (A + B). (A + C) $

$ A. (B + C) = (A. B) + (A. C) $

Định luật De-Morgan

$ \ sim (A. B) = \ sim A + \ sim B $

$ \ sim (A + B) = \ sim A. \ sim B $

Biểu mẫu chuẩn

Đối với biểu thức Boolean, có hai dạng chính tắc:

• Dạng tổng của minterms (SOM)
• Sản phẩm của dạng maxterms (POM)

Dạng Tổng Minterms (SOM) hoặc Sum of Products (SOP)

Một minterm là một sản phẩm của tất cả các biến được lấy ở dạng trực tiếp hoặc bổ sung của chúng. Bất kỳ hàm Boolean nào cũng có thể được biểu diễn dưới dạng tổng của các phần 1 của nó và phần nghịch đảo của hàm có thể được biểu thị dưới dạng tổng các phần 0 của nó. Vì thế,

F (danh sách các biến) = ∑ (danh sách các chỉ số trong 1 phút)

và

F '(danh sách các biến) = ∑ (danh sách các chỉ số 0 phút)

A	B	C	Kỳ hạn	Minterm
0	0	0	XYZ'	m 0
0	0	1	XYZ	m 1
0	1	0	XYZ'	m 2
0	1	1	XYZ	m 3
1	0	0	XYZ'	m 4
1	0	1	XYZ	m 5
1	1	0	XYZ'	m 6
1	1	1	XYZ	m 7

Example

Cho, $ F (x, y, z) = x 'y' z '+ xy' z + xyz '+ xyz $

Hoặc, $ F (x, y, z) = m_0 + m_5 + m_6 + m_7 $

Vì thế,

$ F (x, y, z) = \ sum (0, 5, 6, 7) $

Bây giờ chúng ta sẽ tìm phần bù của $ F (x, y, z) $

$ F '(x, y, z) = x' yz + x 'y' z + x 'yz' + xy 'z' $

Hoặc, $ F '(x, y, z) = m_3 + m_1 + m_2 + m_4 $

Vì thế,

$ F '(x, y, z) = \ sum (3, 1, 2, 4) = \ sum (1, 2, 3, 4) $

Dạng Sản phẩm của Maxterms (POM) hoặc Sản phẩm của Tổng (POS)

Một maxterm là sự bổ sung của tất cả các biến được lấy ở dạng trực tiếp hoặc bổ sung của chúng. Bất kỳ hàm Boolean nào cũng có thể được biểu diễn dưới dạng tích của 0-maxterms của nó và nghịch đảo của hàm có thể được biểu thị dưới dạng tích của 1-maxterms của nó. Vì thế,

F (danh sách các biến) = $ \ pi $ (danh sách các chỉ số 0-maxterm).

và

F '(danh sách các biến) = $ \ pi $ (danh sách các chỉ số 1-maxterm).

A	B	C	Kỳ hạn	Maxterm
0	0	0	x + y + z	M 0
0	0	1	x + y + z '	M 1
0	1	0	x + y '+ z	M 2
0	1	1	x + y '+ z'	M 3
1	0	0	x '+ y + z	M 4
1	0	1	x '+ y + z'	M 5
1	1	0	x '+ y' + z	M 6
1	1	1	x '+ y' + z '	M 7

Thí dụ

Cho $ F (x, y, z) = (x + y + z). (x + y + z '). (x + y '+ z). (x '+ y + z) $

Hoặc, $ F (x, y, z) = M_0. M_1. M_2. M_4 $

Vì thế,

$ F (x, y, z) = \ pi (0, 1, 2, 4) $

$ F '' (x, y, z) = (x + y '+ z'). (x '+ y + z'). (x '+ y' + z). (x '+ y' + z ') $

Hoặc, $ F (x, y, z) = M_3. M_5. M_6. M_7 $

Vì thế,

$ F '(x, y, z) = \ pi (3, 5, 6, 7) $

Cổng logic

Các hàm Boolean được thực hiện bằng cách sử dụng các cổng logic. Sau đây là các cổng logic -

Cổng KHÔNG

Cổng NOT đảo một bit đầu vào thành một bit đầu ra.

A	~ A
0	1
1	0

Và cổng

Cổng AND là cổng logic chỉ cho đầu ra cao nếu tất cả các đầu vào của nó cao, nếu không thì cho đầu ra thấp. Dấu chấm (.) Được sử dụng để hiển thị hoạt động AND.

A	B	AB
0	0	0
0	1	0
1	0	0
1	1	1

HOẶC Cổng

Cổng OR là cổng logic cho đầu ra cao nếu ít nhất một trong các đầu vào cao. Dấu cộng (+) được sử dụng để hiển thị phép toán OR.

A	B	A + B
0	0	0
0	1	1
1	0	1
1	1	1

Cổng NAND

Cổng NAND là cổng logic chỉ cho đầu ra thấp nếu tất cả các đầu vào của nó cao, nếu không thì cho đầu ra cao.

A	B	~ (AB)
0	0	1
0	1	1
1	0	1
1	1	0

Cổng NOR

Cổng NOR là cổng logic cho đầu ra cao nếu cả hai đầu vào đều thấp, ngược lại nó cho đầu ra thấp.

A	B	~ (A + B)
0	0	1
0	1	0
1	0	0
1	1	0

Cổng XOR (Độc quyền HOẶC)

Cổng XOR là cổng logic cho đầu ra cao nếu các đầu vào khác nhau, ngược lại thì cho đầu ra thấp.

A	B	A⊕B
0	0	0
0	1	1
1	0	1
1	1	0

Cổng X-NOR (NOR độc quyền)

Cổng EX-NOR là cổng logic cho đầu ra cao nếu các đầu vào giống nhau, ngược lại nó cho đầu ra thấp.

A	B	A X-NOR B
0	0	1
0	1	0
1	0	0
1	1	1