Đại số Bool và hàm Bool | Tóm tắt lý thuyết Toán rời rạc | Đại học Ngoại Ngữ Tin Học TP Hồ Chí Minh

ĐẠI SỐ BOOL VÀ HÀM BOOL

ĐẠI SỐ BOOL

Định nghĩa 4.1.1:

Một đại số Bool là tập hợp 𝘗 cùng với hai phép tính (hai ngôi) 𝗏 và 𝖠 thỏa mãn các tính chất sau

1. Tính kết hợp : với mọi 𝑥, 𝑦, 𝑧 ∈ 𝘗:

𝑥 𝗏 ( 𝑦 𝗏 𝑧) = ( 𝑥 𝗏 𝑦) 𝗏 𝑧

và 𝑥 𝖠 ( 𝑦 𝖠 𝑧) = ( 𝑥 𝖠 𝑦) 𝖠 𝑧

2. Tính giao hoán: với mọi 𝑥, 𝑦, 𝑧 ∈ 𝘗:

𝑥 𝗏 𝑦 = 𝑦 𝗏 𝑥

và 𝑥 𝖠 𝑦 = 𝑦 𝖠 𝑥

3. Tính phân bố: với mọi 𝑥, 𝑦, 𝑧 ∈ 𝘗:

𝑥 𝗏 ( 𝑦 𝖠 𝑧) = ( 𝑥 𝗏 𝑦) 𝖠 ( 𝑥 𝗏 𝑧)

và 𝑥 𝖠 ( 𝑦 𝗏 𝑧) = ( 𝑥 𝖠 𝑦) 𝗏 ( 𝑥 𝖠 𝑧)

4. Phần tử trung hòa:

Tồn tại hai phần tử trung hòa 0,1 đối với hai phép toán 𝗏,𝖠 sao cho với mọi 𝑥 ∈ 𝘗 ta có:

𝑥 𝗏 0 = 𝑥

và 𝑥 𝖠 1 = 𝑥

5. Phần tử bù: với mọi 𝑥 ∈ 𝘗, tồn tại ∈ 𝐴 sao cho:

𝑥 𝗏 𝑥̅ = 1

và 𝑥 𝖠 𝑥̅ = 0

Ví dụ:

1. Một dàn bù phân bố là một đại số Bool với hai phép tính 𝗏,𝖠 chính là sup và inf của hai phần tử. Đặc 𝑃( 𝐸) là một đại số Bool dối với các phép tính tập hợp 𝖴 và ∩. Cũng thế 𝑀 cũng là một đại số Bool đối với các phép nối rời 𝗏 và nối liền 𝖠 của hai dạng mệnh đề. Do 30 không chia hết cho chính phương, ࣯30 là dàn bù phân bố và do đó là một đại số Bool đối với các phép toán :

𝑥 𝗏 𝑦 = 𝐵𝑆𝐶𝑁𝑁( 𝑥, 𝑦)

và 𝑥 𝖠 𝑦 = 𝑈𝑆𝐶𝐿𝑁( 𝑥, 𝑦)

2.  Tập hợp 𝐵 = { 0,1} là một đại số Bool dối với các phép toán :

𝑥 𝖠 𝑦 = 𝑥𝑦

𝑥 𝗏 𝑦 = 𝑥 + 𝑦 − 𝑥𝑦

Phần bù của 𝑥 chính là 𝑥̅ = 1 − 𝑥

Đại số Bool này đóng vai trò quan trọng trong lý thuyết về các hàm Bool.

Chú ý: phần bù 𝑥̅ của phần tử 𝑥 là duy nhất và hơn nữa ta có qui tắc De Morgan (Bài tập).

 $\overline{x} \overline{v} \overline{y}$ =  𝑥̅ 𝖠 𝑦̅ và $\overline{x} \overline{A}\overline{y}$ =  𝑥̅ 𝗏 𝑦̅

Trong các ví dụ trên, các phép toán đại số Bool được định nghĩa còn tự nhiên hơn cấu trúc thứ tự của dàn bù phân bố. vấn đề được đặt ra là liệu có thể suy cấu trúc của dàn bù phân bố từ cấu trúc đại số Bool không? Định lý sau đây là câu trả lời:

𝑥 ≺ 𝑦 ⟺ 𝑥 𝖠 𝑦 = 𝑥

Khi ấy ≺ là một thứ tự trên sao cho 𝘗 là một dàn bù phân bố đối với thứ tự này.

Hơn nữa, với 𝑥, 𝑦 ∈ 𝘗 ta có:

sup( 𝑥, 𝑦) = 𝑥 𝗏 𝑦

inf( 𝑥, 𝑦) = 𝑥 𝖠 𝑦

Chứng minh: Trước hết ta kiểm tra ≺ là một thứ thự trên 𝘗. Với mọi 𝑥 ∈ 𝘗 ta có:

𝑥 𝖠 𝑥 = ( 𝑥 𝖠 𝑥) 𝗏 0

= ( 𝑥 𝖠 𝑥) 𝗏 ( 𝑥 𝖠 𝑥̅)

= 𝑥 𝖠 ( 𝑥 𝗏 𝑥̅)

= 𝑥 𝖠 1 = 𝑥       (4.1.1)

nghĩa là 𝑥 ≺ 𝑥

Mặt khác với 𝑥, 𝑦 ∈ 𝘗 sao cho 𝑥 ≺ 𝑦 và 𝑦 ≺ 𝑥 ta có:

𝑥 𝖠 𝑦 = 𝑥 𝑣à 𝑦 𝖠 𝑥 = 𝑦

Do tính giao hoán của 𝖠 ta có 𝑥 = 𝑦

Với 𝑥, 𝑦, 𝑧 ∈ 𝘗 sao cho 𝑥 ≺ 𝑦 và 𝑦 ≺ 𝑧 ta có:

𝑥 𝖠 𝑦 = 𝑥 𝑣à 𝑦 𝖠 𝑧 = 𝑦

Suy ra

𝑥 𝖠 𝑧 = ( 𝑥 𝖠 𝑦) 𝖠 𝑧 = 𝑥 𝖠 ( 𝑦 𝖠 𝑧)

=  𝑥 𝖠 𝑦 = 𝑥

Nghĩa là 𝑥 ≺ 𝑧

Tóm lại ≺ là một thứ tự trên 𝘗.

Với 𝑥, 𝑦 ∈ 𝘗 tùy ý, ta có

( 𝑥 𝖠 𝑦) 𝖠 𝑥 = ( 𝑥 𝖠 𝑥) 𝖠 𝑦

Nhưng  𝑥 𝖠 𝑥 = 𝑥     ( do 4.1.1)

Nên ( 𝑥 𝖠 𝑦) 𝖠 𝑥 = 𝑥 𝖠 𝑦

Nghĩa là 𝑥 𝖠 𝑦 ≺ 𝑥

Tương tự     𝑥 𝖠 𝑦 = 𝑦 𝖠 𝑥 ≺ 𝑦

Như thế 𝑥 𝖠 𝑦 là chặn dưới chung của 𝑥, 𝑦

Gọi 𝑧 là một chặn dưới chung bất kỳ của 𝑥, 𝑦. Ta có:

𝑧 𝖠 𝑥 = 𝑧 𝑣à 𝑧 𝖠 𝑦 = 𝑧

Do đó 𝑧 𝖠 ( 𝑥 𝖠 𝑦) = ( 𝑧 𝖠 𝑥) 𝖠 𝑦 = 𝑧 𝖠 𝑦 = 𝑧

nghĩa là 𝑧 ≺ 𝑥 𝖠 𝑦

Như thế 𝑥 𝖠 𝑦 = inf( 𝑥, 𝑦)

Bây giờ do iv) của Định nghĩa 4.1.1, 1 chính là phần tử lớn nhất. Mặt khác, với 𝑥 ∈ 𝘗

0 𝖠 𝑥 = ( 0 𝖠 𝑥) 𝗏 0

= ( 0 𝖠 𝑥) 𝗏 ( 𝑥 𝖠 𝑥̅)

=  ( 0 𝗏 𝑥̅) 𝖠 𝑥

= 𝑥̅ 𝖠 𝑥 = 0                                                              (4.1.1)

Nghĩa là 0 là phần tử bé nhất của 𝘗.

Sau cùng với mọi 𝑥, 𝑦 ∈ 𝘗, ta có:

𝑥 𝖠 ( 𝑥 𝗏 𝑦) = ( 𝑥 𝗏 0) 𝖠 ( 𝑥 𝗏 𝑦)

∅ = 𝑥 𝗏 ( 0 𝖠 𝑦)

Mà  0 𝖠 𝑦  = 0 ( do 4.1.2)

Nên 𝑥 𝖠 ( 𝑥 𝗏 𝑦) = 𝑥 𝗏 0 = 𝑥

Nghĩa là 𝑥 ≺ 𝑥 𝗏 𝑦

Tương tự 𝑦 ≺ 𝑦 𝗏 𝑥 = 𝑥 𝗏 𝑦

Gọi 𝑧 là mộ chặn trên chung của 𝑥, 𝑦 ta có:

( 𝑥 𝗏 𝑦) 𝖠 𝑧 = ( 𝑥 𝖠 𝑧) 𝗏 ( 𝑦 𝖠 𝑧)

=  𝑥 𝗏 𝑦

Nghĩa là 𝑥 𝗏 𝑦 ≺ 𝑧

Như thế 𝑥 𝗏 𝑦 = sup( 𝑥, 𝑦)

Tóm lại 𝘗 là một dàn phân bố với phần tử lớn nhất và bé nhất là 1,0. Hơn nữa, do v)  của Định lý 4.1.1 𝑥̅ chính là phần bù của 𝑥.  đpcm

Do Định lý 4.1.1, mỗi đại số Bool hữu hạn được liên kết với một biểu đồ Hasse. Ta hãy quan sát aho đại số Bool ࣯30 và 𝑃({ 𝑎, 𝑏, 𝑐}) . Tuy được định nghĩa khác nhau, các đại số Bool này có hai biểu đồ Hasse “đồng dạng”

Định nghĩa 4.1.2:

Một đẳng cấu giữa hai đại số Bool 𝘗 và 𝐵 là một song ánh 𝜑: 𝘗 ⟷ 𝐵 sao cho với mọi 𝑥, 𝑦 ∈ 𝘗 ta có:

𝜑( 𝑥 𝗏 𝑦) =      𝜑( 𝑥) 𝗏 𝜑( 𝑦)

và    𝜑( 𝑥 𝖠 𝑦) =      𝜑( 𝑥) 𝖠 𝜑( 𝑦)

Mệnh đề 4.1.2 :

Nếu 𝜑: 𝘗 ⟷ 𝐵 là một đẳng cấu Đại số Bool thì 𝜑 cũng là đẳng cấu tập hợp có thứ tự với thứ tự trên 𝘗 và 𝐵 xác định bởi Định lý 4.1.1. Đặc biệt nếu 0,1 là phần tử trung hòa của 𝗏,𝖠 trong 𝐵 thì 𝜑( 0), 𝜑( 1) là phần tử trung hòa của 𝗏,𝖠 trong 𝐵.

Chứng minh: giả sử 𝑥, 𝑦 là hai phần tử trong 𝘗 sao cho 𝑥 ≺ 𝑦. Khi ấy ta có:

𝑥 𝖠 𝑦 = 𝑥     ⟹     𝜑( 𝑥) 𝖠 𝜑( 𝑦) = 𝜑( 𝑥)

⟹           𝜑( 𝑥) ≺ 𝜑( 𝑦)

Do 0 và 1 cũng là phần tử bé nhất và lớn nhất của 𝘗, ta thấy 𝜑( 0) và 𝜑( 1) cũng là phần tử bé nhất và lớn nhất của 𝐵, nghĩa là phần tử trung hòa đối với các phép toán 𝗏,𝖠 trong 𝐵 l đpcm

Trở lại hai đại số Bool ࣯30 và 𝑃({ 𝑎, 𝑏, 𝑐}) . Sự đẳng cấu của chúng không phải là trường hợp cá biệt. Ta có:

Đinh lý 4.1.3 (Stone): một đại số Bool hữu hạn 𝘗 luôn lương đẳng cấu với 𝑃( 𝐸), trong đó 𝐸 là một tập hợp hữu hạn.

Hệ quả 1: Số phần tử của một đại số Bool hữu hạn là một ũy thừa của 2.

Hệ quả 2: Hai đại số Bool hữu hạn có cùng số phần tử thì đẳng cấu với nhau.

Chứng minh: Thật vậy hai đại số Bool cho trước sẽ đẳng cấu với như sau:

𝜑: 𝑃( 𝐸1)       →     𝑃( 𝐸2)

𝐴           ⟼     ƒ( 𝐴)

Khi ấy ta có:

ƒ( 𝐴 𝖴 𝐵) = ƒ( 𝐴) 𝖴 ƒ( 𝐵)

nghĩa là  

 𝜑( 𝐴 𝗏 𝐵) = 𝜑( 𝐴) 𝗏 𝜑( 𝐵)

Hơn nữa do ƒ là song ánh ta cũng có:

ƒ( 𝐴 ∩ 𝐵) = ƒ( 𝐴) ∩ ƒ( 𝐵)

Nghĩa là    

𝜑( 𝐴 𝖠 𝐵) = 𝜑( 𝐴) 𝖠 𝜑( 𝐵)

Bây giờ để chứng minh Định lý Stone ta cần tìm tập hợp 𝐸. Để ý rằng ta có một đơn

ƒ: 𝐸 → 𝑃( 𝐸)

𝑥 ⟼ { 𝑥}

Hơn nữa trong 𝑃( 𝐸) các tập hợp { 𝑥} chính là các trội trực tiếp của ∅. Từ đó ta có:

Bổ đề 4.1.4:

Giả sử 𝘗 là một đại số Bool hữu hạn với phần tử bé nhất 0. Khi ấy mọi phần tử 𝑥 ≠ 0 đều có thể viết dưới dạng: 𝑥 = 𝑎₁ 𝗏 𝑎₂ 𝗏 …𝗏 𝑎_𝑛

trong đó { 𝑎₁, 𝑎₂,…, 𝑎_𝑛} là tập hợp các nguyên tử trội bởi 𝑥. Hơn nữa nếu 𝑏₁, 𝑏₂,…, 𝑏_𝑚 là các nguyên tử sao cho:

𝑥 = 𝑏₁ 𝗏 𝑏₂ 𝗏 …𝗏 𝑏_𝑚 thì { 𝑏₁, 𝑏₂,…, 𝑏_𝑚} =  { 𝑎₁, 𝑎₂,…, 𝑎_𝑛}

Chứng minh: Trước hết 𝘗\ { 0} là một tập hợp sắp thứ tự hữu hạn chứa 𝑥( ≠ 0) nên tồn tại một phần tử tối tiểu 𝑎 ≺ 𝑥. Rõ ràng 𝑎 là một nguyên tử của 𝘗. Nói cách khác tập hợp { 𝑎₁, 𝑎₂,…, 𝑎_𝑛} các nguyen tử trội bởi 𝑥 là không ∅.

Đặt 𝑦 = 𝑎₁ 𝗏 𝑎₂ 𝗏 …𝗏 𝑎_𝑛

Rõ ràng 𝑦 ≺ 𝑥.

Ta có:  

𝑥 =  𝑥 𝖠 ( 𝑦 𝗏 𝑦̅) =  ( 𝑥 𝖠 𝑦) 𝗏 ( 𝑥 𝖠 𝑦̅)

=  𝑦 𝗏 ( 𝑥 𝖠 𝑦̅)

Giả sử ( 𝑥 𝖠 𝑦̅)  ≠ 0

Khi  ấy  theo  trên  tồn  tại  một  nguyên  tử 𝑎 ≺ 𝑥 𝖠 𝑦̅. Như thế 𝑎 =  𝑎i  với 1 ≤ i ≤ 𝑛  nào đó

Đặt 𝑏 = 𝑎₁ 𝗏 𝑎₂ 𝗏 …𝗏 𝑎_i−1 𝗏 𝑎_i−1 𝗏 …𝗏 𝑎_𝑛

Ta có 𝑦 = 𝑎 𝗏 𝑏

Do đó 𝑦̅ =  𝑎̅ 𝖠 𝑏̅

Suy ra 𝑎  =  𝑎 𝖠  𝑦̅ =  𝑎 𝖠 𝑎̅ 𝖠 𝑏̅ =  0: mâu thuẫn.

Như thế ( 𝑥 𝖠 𝑦̅) =  0

Nghĩa là 𝑥 = 𝑦

Sau cùng giả sử 𝑏₁, 𝑏₂,…, 𝑏_𝑚 là các nguyên tử trội bởi 𝑥 sao cho

𝑥 = 𝑏₁ 𝗏 𝑏₂ 𝗏 …𝗏 𝑏_𝑚

Ta có :

{ 𝑏₁, 𝑏₂,…, 𝑏_𝑚} ⊂ { 𝑎₁, 𝑎₂,…, 𝑎_𝑛}

Mặt khác, với mỗi j cố định, 1 ≤ i ≤ 𝑛 ta có:

𝑎_j = 𝑎_j 𝖠 𝑥 = (𝑎_j 𝖠 𝑏₁) 𝗏 (𝑎_j 𝖠 𝑏₂) 𝗏 …(𝑎_j 𝖠 𝑏_𝑚)

Suy ra tồn tại 𝑘 sao cho 1 ≤ 𝑘 ≤ 𝑚 và

0 ≠ 𝑎_j 𝖠 𝑏_k ≺ 𝑎_j

Do 𝑎_j là nguyên tử ta có: 𝑎_j 𝖠 𝑏_k = 𝑎_j

Nghĩa là 𝑎_j ≺ 𝑏_k

Do 𝑏_k là nguyên tử và 𝑎j ≠ 0 ta có 𝑎j = 𝑏k

Như thế

{ 𝑎₁, 𝑎₂,…, 𝑎_𝑛} ⊂ {𝑏₁, 𝑏₂,…, 𝑏_𝑚}

Nghĩa là

{ 𝑎₁, 𝑎₂,…, 𝑎_𝑛} = { 𝑏₁, 𝑏₂,…, 𝑏_𝑚} l đpcm

Gọi 𝐸 là tập hợp tất cả các nguyên tử của 𝘗. Nhờ Bổ đề 4.1.4, ta có một ánh xạ 𝜑: 𝘗 → 𝑃( 𝐸) được định nghĩa như sau:

•  𝜑( 0) = ∅
•  Nếu 𝑥 ≠ 0 thì 𝜑( 𝑥) là tập hợp tất cả các nguyên tử trội bởi 𝑥. Bây giờ Định lý 4.1.3 là hệ quả của

Định lý 4.1.5 : 𝜑 là một đẳng cấu giữa 𝘗 và 𝑃( 𝐸) .

Chứng minh: Giả sử 0 ≠ 𝑥 ≺ 𝑦. Khi ấy các nguyên tử trội bởi 𝑥 cũng là nguyên tử trội bởi 𝑦 nên 𝜑( 𝑥) ⊂ 𝜑( 𝑦)

Ta viết 𝜑( 𝑥) = {𝑎1, 𝑎2,…, 𝑎𝑚} và     𝜑( 𝑦) = { 𝑏1, 𝑏2,…, 𝑏𝑛} Do Bổ đề 4.1.4 ta có:

𝑥 = 𝑎₁ 𝗏 𝑎₂ 𝗏 …𝗏 𝑎_𝑚

và      𝑦 = 𝑏₁ 𝗏 𝑏₂ 𝗏 …𝗏 𝑏_𝑛

Do { 𝑎_1, 𝑎₂,…, 𝑎_𝑚} ⊂ { 𝑏₁, 𝑏₂,…, 𝑏_𝑛} nên 𝑥 ≺ 𝑦

Trường hợp 𝑥 = 0 là hiển nhiên.

Tóm lại, ta đã chứng minh: ( 𝑥 ≺ 𝑦) ⟺ (𝜑( 𝑥) ⊂ 𝜑( 𝑦) )

Đặc biệt nếu 𝜑( 𝑥) = 𝜑( 𝑦) thì 𝑥 ≺ 𝑦 và 𝑦 ≺ 𝑥 nên 𝑥 = 𝑦: 𝜑 là đơn ánh.

Sau cùng, giả sử { 𝑎1, 𝑎2,…, 𝑎𝑚} ⊂ 𝐸

Đặt  𝑥 = 𝑎₁ 𝗏 𝑎₂ 𝗏 …𝗏 𝑎_𝑚 và  𝜑( 𝑥) = { 𝑏₁, 𝑏₂,…, 𝑏_𝑛} Do Bổ đề 4.1.4

𝑥 = 𝑎1 𝗏 𝑎2 𝗏 …𝗏 𝑎𝑚

và  { 𝑏1, 𝑏2,…, 𝑏𝑛} =  { 𝑎1, 𝑎2,…, 𝑎𝑚}.

Như thế 𝜑 là toàn ánh. l đpcm

HÀM BOOL

Xét sơ đồ mạch điện gồm 3 ngắt điện:

Tùy theo các ngắt điện 𝐴, 𝐵, 𝐶 được đóng hay mở sẽ có dòng điện đi từ 𝑀 đến 𝑁 hay không. Để biết các ngắt điện điều khiển việc cho dòng điện đi qua hay không, ta vẽ ra sơ đồ cho tất cả mọi trường hợp. Tuy nhiên điều này không thực hiện được nếu số ngắt điện quá lớn. Ví dụ nếu có 100 ngắt điện sẽ có 2100 sơ đồ khác nhau. Ngay cả trong trường hợp số ngắt điện bé, thì vẫn cần một cách sắp xếp có hệ thống các sơ đồ để có thể tra cứu dễ dàng từng trường hợp.

Trong trường ngắt điện lớn thì việc lập bảng giá trị là không thực tế. Ta cần tìm một công thức cho phép biểu diễn hàm 𝑑( 𝑎, 𝑏, 𝑐) theo các biến 𝑎, 𝑏, 𝑐 như các hàm đa thức trong trường hợp hàm biến thực chẳng hạn. Mặt khác ta cũng nhận xét rằng bảng trên rất giống bảng chân trị của các dạng mệnh đề. Thật ra khi khảo sát các dạng mệnh đề, điều ta quan tâm không phải là mệnh đề thu được 𝐸( 𝑃, 𝑄, 𝑅,…) khi ta thay các biến mệnh đề 𝑝, 𝑞, 𝑟,… lần lượt bởi các mệnh đề 𝑃, 𝑄, 𝑅,… mà là sự phụ thuộc chân trị của mệnh đề 𝐸( 𝑃, 𝑄, 𝑅,…) vào chân trị các mệnh đề 𝑃, 𝑄, 𝑅,… Nói cách khác ta đồng nhất dạng mệnh đề 𝐸( 𝑝, 𝑞, 𝑟,…) với bảng chân trị của nó. Thực chất ở đây là ta đang xem xét hàm 𝐸( 𝑝, 𝑞, 𝑟,…) theo các biến 𝑝, 𝑞, 𝑟,… trong đó 𝑝, 𝑞, 𝑟,… và cả 𝐸( 𝑝, 𝑞, 𝑟, …) cũng chỉ lấy hai giá trị 0,1. Đó là các hàm Bool theo định nghĩa dưới đây:

Định  nghĩa 4.2.1:

Một hàm Bool 𝑛 biến là một ánh xạ 𝐵𝑛 → 𝐵, trong đó 𝐵 =  {0,1}. Tập hợp các hàm Bool 𝑛 biến được ký hiệu bởi ℱ𝑛.

Chú ý:

1. Các hàm Bool còn được gọi là hàm logic hay hàm nhị phân

2. Nhắc lại tập hợp 𝐵 là đại số Bool đối với các phép toán

𝑎 𝖠 𝑏 = 𝑎𝑏

𝑎 𝗏 𝑏 = 𝑎 + 𝑏 − 𝑎𝑏

𝑎̅ =  1 − 𝑎

3. Các biến xuất hiện trong hàm Bool được gọi là biến Bool. Mỗi hàm Bool được liên kết với một bảng tương tự như bảng trên cho biết sự phụ thuộc của hàm Bool theo giá trị các biến Bool. Ta cũng gọi bảng giá trị này là Bảng chân trị của hàm Bool.

4. Theo ký hiệu của Chương 3 ℱ𝑛 chính là tập hợp 2𝐵 . Do đó số hàm Bool khác nhau chính là |ℱ𝑛| = 2|𝐵𝑛 | = 2( 2𝑛)

Mặt khác trong §1, tương ứng 𝐴 ⟼ 3Æ  là một đẳng cấu của tập hợp có thứ tự 𝑃( 𝐵𝑛) và ℱ𝑛 trong đó thứ tự trên ℱ𝑛 được xác định như sau: với ƒ, 𝑔 ∈ ℱ𝑛 thì

ƒ ≺ 𝑔 ⟺ ∀𝑎 = ( 𝑎1, 𝑎2,…, 𝑎𝑛) ∈ 𝐵𝑛, ƒ( 𝑎) ≤ 𝑔( 𝑎)

Khi ấy sup và inf của hai hàm ƒ, 𝑔 được cho bởi:

( ƒ 𝗏 𝑔) ( 𝑎) = ƒ( 𝑎) 𝗏 𝑔( 𝑎)

=  ƒ( 𝑎) + 𝑔( 𝑎) − ƒ( 𝑎) 𝑔( 𝑎) , ∀𝑎 ∈ 𝐵𝑛

và ( ƒ 𝖠 𝑔) ( 𝑎) = ƒ( 𝑎) 𝖠 𝑔( 𝑎)

=  ƒ( 𝑎) 𝑔( 𝑎), ∀𝑎 ∈ 𝐵𝑛

Và phần bù ƒ̅ của hàm Bool ƒ được cho bởi

ƒ̅( 𝑎) = ̅ƒ̅(̅𝑎̅)

= 1 − ƒ( 𝑎) , ∀𝑎 ∈ 𝐵𝑛

Ta sử dụng ký hiệu thông thường ƒ𝑔 và 1 − ƒ để chỉ các hàm ƒ 𝖠 𝑔 và ƒ̅ trong đó 1 chỉ hàm hằng 𝐵𝑛 → {1}

Với các phép toán trên, ℱ𝑛 trở thành một đại số Bool đẳng cấu với 𝑃( 𝐵𝑛) . Đặc biệt các nguyên tử trong ℱ𝑛 sẽ tương ứng với các nguyên tử trong 𝑃( 𝐵𝑛) . mà trong 𝑃( 𝐵𝑛) các nguyên tử chính là các tập hợp thu về một điểm nên ta có:

Mệnh đề 4.2.1

Các nguyên tử trong ℱ𝑛 là các hàm Bool chỉ khác 0 tại điểm duy nhất, hay nói cách khác, bảng chân trị của nó chỉ có một dòng duy nhất ở đó hàm khác 0. Các này dược gọi là các từ tối tiểu của ℱ𝑛.

Do Định lý Stone ta có:

Định lý 4.2.2 :

Mỗi hàm Bool ƒ đều được viết dưới dạng:

ƒ = 𝑚₁ 𝗏 𝑚₂ 𝗏 …𝗏 𝑚_𝑙     ( 4.2.1)                                               

Trong đó 𝑚₁, 𝑚₂,…, 𝑚_𝑙 là các từ tối tiểu trội bởi ƒ.

Do từ tối tiểu 𝑚_i chỉ khác 0 ở duy nhất một dòng, 𝑚_i sẽ được trội bởi ƒ khi và chỉ khi dòng mà 𝑚_i khác 0 cũng là một trong những dòng mà ƒ khác 0. Từ đó ta có qui tắc viết ra công thức (4.2.1) bằng cách chọn 𝑚i chính là các từ tối tiểu tương ứng với một dòng khác 0 nào đó của ƒ . Chẳng hạn như trong ví dụ về hàm 𝑑( 𝑎, 𝑏, 𝑐) biểu diễn mạch điện ở trên ta có

Ta có   

𝑑 = 𝑚₁ 𝗏 𝑚₂ 𝗏 𝑚₃ 𝗏 𝑚₄ 𝗏  𝑚₅     (4.2.2)

Bây giờ để có một công thức tường minh cho một hàm Bool bất kỳ, do (4.2.1) ta cần tìm một công thức tường minh cho tất cả các từ tối tiểu. Nhắc lại phép chiếu thứ i được cho bởi:

𝜋_i: 𝐵_𝑛                         →      𝐵

( 𝑥₁, 𝑥₂,…, 𝑥_𝑛)      ⟼    𝑥_i

Rõ ràng bản thân 𝜋i là một hàm Bool 𝑛 biến mà giá trị của nó chỉ phụ thuộc vào biến thứ i. Tương tự như trường hợp các hàm thực, ta sẽ dùng cùng ký hiệu 𝑥i dể chỉ hàm Bool

𝜋_i:  𝑥_i( 𝑎_1, 𝑎₂,…, 𝑎_𝑛) =  𝑎_i

Mệnh đề 4.2.3 

Các từ tối tiểu đều có thể viết dưới dạng: 𝑚 = 𝑏₁𝑏₂ …𝑏_𝑛 trong đó 𝑏_i = 𝑥_i hay 𝑏_i = 𝑥̅_i

Chứng minh: giả sử 𝑏i là từ đơn bằng 𝑥_i hay 𝑥̅_i. Ta sẽ chứng minh 𝑚 = 𝑏₁𝑏₂ …𝑏𝑛 là một từ tối tiểu. Chính xác hơn gọi 𝑎 = ( 𝑎₁, 𝑎₂,…, 𝑎_𝑛) là các phần tử của 𝐵𝑛 sao cho 𝑎_i = 1 nếu 𝑏_i = 𝑥_i và 𝑎_i = 0 nếu 𝑏_i = 𝑥̅_i. Ta sẽ chứng minh rằng 𝑚 khác 0 duy nhất tại 𝑎.

Thật vậy với 1 ≤ i ≤ 𝑛 ta có:

𝑏_i( 𝑎) = 𝑥_i( 𝑎) = 𝑎_i = 1

nếu

𝑏_i = 𝑥_i và  𝑏_i( 𝑎) =  𝑥̅_i( 𝑎) = 𝑎̅_i = 1 nếu 𝑏_i = 𝑥̅_i

Như thế 𝑏_i( 𝑎) = 1 với 1 ≤ i ≤ 𝑛

Suy ra 𝑚( 𝑎) = 1

Mặt khác nếu 𝑦 = ( 𝑦₁, 𝑦₂,…, 𝑦_𝑛) ≠ 𝑎 thì tồn tại i sao cho 1 ≤ i ≤ 𝑛 và 𝑦_i ≠ 𝑎_i.

Khi ấy:

𝑏_i( 𝑦) = 𝑥_i( 𝑦) = 𝑦_i = 0 (vì 𝑥 ≠ 𝑎i) nếu 𝑏_i = 𝑥_i

và 𝑏_i( 𝑦) = 𝑥̅_i( 𝑦) = 𝑎̅_i = 𝑦 (vì 𝑥 =  𝑎_i) nếu 𝑏_i  =  𝑥̅_i

Như thế 𝑏_i( 𝑦) = 0 và do đó 𝑚( 𝑦) = 0

Tóm lại 𝑚 là từ tối tiểu tương ứng với điểm 𝑎.

Ngược lại giả sử 𝑚 là từ tới tiểu khác 0 duy nhất tại điểm 𝑐 = ( 𝑐₁, 𝑐₂,…, 𝑐_𝑛) . Đặt:

𝑏_i = 𝑥_i nếu 𝑐_i = 1

và  𝑏_i = 𝑥̅_i nếu 𝑐_i = 0

Khi ấy theo chứng minh trên, 𝑏₁𝑏₂ …𝑏_𝑛  là từ tối tiểu tương ứng với điểm 𝑎 = ( 𝑎₁, 𝑎₂,…, 𝑎_𝑛) sao cho:

𝑎_i = 1 nếu 𝑏_i = 𝑥_i

và 𝑎_i = 0 nếu 𝑏_i = 𝑥̅_i

nói cách khác 𝑎_i = 𝑐_i, 1 ≤ i ≤ 𝑛

Do đó 𝑚 = 𝑏1𝑏2 …𝑏𝑛 l đpcm

Chú ý:

1. Do mỗi 𝑏i có thể lấy hai giá trị 𝑥i, 𝑥̅i nên ta tìm lại được số từ tối tiểu chính là số phần tử của 𝐵𝑛 ∶ 2𝑛.

2. Ta có qui tắc để viết biểu thức của một từ tối tiểu ứng với điểm 𝑎 = ( 𝑎₁, 𝑎₂,…, 𝑎_𝑛) : viết tích của tất cả các biến 𝑥₁𝑥₂ …𝑥_𝑛, sau đó biến thứ i  mà 𝑎_i  =  0 sẽ được gạch đầu. Chẳng hạn trong ví dụ về mạch điện ở trên các từ tối tiểu 𝑚₁, _𝑚2,…, 𝑚₅ có biểu diễn như sau:

𝑚₁     =     𝑎̅𝑏𝑐

𝑚₂     =     𝑎𝑏𝑐

𝑚3     =     𝑎𝑏̅𝑐

𝑚4     =     𝑎𝑏𝑐

𝑚5     =      𝑎𝑏𝑐

Do đó (4.2.2) trở thành: 𝑑 =  𝑎̅𝑏𝑐 𝗏 𝑎𝑏𝑐̅ 𝗏 𝑎𝑏̅𝑐 𝗏 𝑎𝑏𝑐̅ 𝗏 𝑎𝑏𝑐

𝗏 giữa 𝑎𝑏 và 𝑐. Nói cách khác 𝑎𝑏 𝗏 𝑐 = ( 𝑎𝑏) 𝗏 𝑐

Ngược lại nếu thực hiên phép 𝗏 trước ta phải viết: 𝑎( 𝑏 𝗏 𝑐)

3. Tổng quát hơn, do (4.2.1) và Mệnh đề 4.2.3 một hàm Bool bất kỳ ƒ có thể viết như là tổng Bool của các từ tối tiểu trội bởi ƒ, và mỗi từ tối tiểu này được viết như là tích của đủ 𝑛 biến. Công thức này được gọi là dạng nối rời chính tắc của ƒ.

4. Thay vì các từ tối tiểu, ta có thể xét các từ tối đại: đó là phần bù của các từ tối tiểu. Khi ấy do Mệnh đề 4.2.3, mỗi từ tối đại sẽ là tổng Bool của 𝑛 từ đơn. Hơn nữa áp dụng (4.2.1) cho ƒ̅, ta có thể viết ƒ như là tích của các từ tối đại: đây chính là dạng nối liền chính tắc của hàm Bool ƒ. Từ đây ta chỉ để ý đến dạng nối rời chính tắc và tổng quát hơn các công thức đa thức theo nghĩa dưới đây:

Định nghĩa 4.2.1

i. Một đơn thức là một tích khác 0 của các từ đơn

ii. Một công thức đa thức của hàm Bool ƒ là công thức biểu diễn ƒ dưới dạng tổng Bool của các đơn thức.

Chú ý: Do 𝑥i𝑥i = 𝑥i và 𝑥i𝑥̅i = 0 nên trong một đơn thức 𝑚, biến 𝑥i và 𝑥̅i có thể xuất hiện

nhưng không đồng thời xuất hiện. Nói cách khác mỗi đơn thức có thể viết như là tích 𝑏1𝑏2 …𝑏𝑛 trong đó 𝑏i lấy một trong 3 giá trị 1, 𝑥i, 𝑥̅i. Do đó số đơn thức khác nhau là 3𝑛. suy ra mỗi hàm Bool chỉ có một số hữu hạn công thức đa thức. Để ý rằng nếu 𝑏i  ≠ 1, ta nói 𝑏i là một thừa số của 𝑚. Như thế mỗi đơn thức được viết như là tích của tối đa 𝑛 thừa số khác nhau.

MẠNG CÁC CỔNG VÀ CÔNG THỨC ĐA THỨC TỐI TIỂU

Trong ví dụ về mạch điện ở §2, ta đã biểu diễn mạch điện dưới dạng một hàm Bool để khảo sát sự phũ thuộc của output 𝑑 (có dòng điện chạy qua hay không) theo các input 𝑎, 𝑏, 𝑐 (ngắt điện tương ứng đóng hay mở). Bây giờ ta hãy xét bài toán ngược lại: cho trước một hàm Bool ƒ( 𝑥, 𝑦, 𝑧,…). Hãy thiết kế một mạng các thiết bị vật lý cho phép tổng hợp nên hàm Bool ƒ. Ở đây ta không quan tâm đến các thiết bị vật lý cụ thể mà chỉ để ý đến các nối kết chúng trong một mạng để tổng hợp nên hàm Bool. Do Mệnh đề 4.2.2 và 4.2.3, mỗi hàm Bool đều có thể viết thành một công thức trong đó các biến logic (biến Bool) được nối kết lại với nhau bởi các phép toán 𝖠,𝗏, −. Do đó ta cần phải tổng hợp các phép toán trên. Thiết bị để tổng hợp các phép toán này gọi là các cổng được biểu diễn bởi các sơ đồ sau:

Tron các sơ đồ trên, 𝑥 và 𝑦 là hai tín hiệu vào với 2 trạng thái khác nhau cho phép chúng biểu diễn được các biến logic với hai giá trị 0,1. Ở đầu ra ta cũng có một tín hiêu biểu diễn cho một biến logic phụ thuộc vào các input theo các phép toán 𝖠,𝗏, −.

Ví dụ: để tổng hợp hàm Bool ƒ = 𝑥𝑦 𝗏 𝑥̅𝑧, ta có thể sử dụng mạng với các cổng sau:

trong đó có hai cổng AND, 1 cổng OR và một cổng NOT. Mặt khác ta cũng c2o thể viết hàm ƒ như sau:

ƒ  =  𝑥𝑦( 𝑧 𝗏 𝑧̅ ) 𝗏 𝑥̅( 𝑦 𝗏 𝑦̅ ) 𝑧

=  𝑥𝑦𝑧 𝗏 𝑥𝑦𝑧̅ 𝗏 𝑥̅𝑦𝑧 𝗏 𝑥̅𝑦̅𝑧

Đây là dạng nối rời chính tắc của ƒ vì các số hạng đều là từ tối tiểu. nếu sử dung công thức trên để thiết kế một mạng các tổng hợp f, ta phải sử dụng 8 cổng AND và 3 cổng OR, không kể một số cổng NOT.

Vấn đề được đặt ra là làm sao tìm được một công thứ tối ưu để tổng hợp một hàm Bool cho trước.

Bài toán tối ưu đầu tiên là tìm cách giảm số loại cổng từ 3 xuống còn 2, hoặc nếu được chỉ dùng một loại cổng.

Thật vậy, ta có thể tổng hợp cổng OR từ cổng NOT và cổng AND. Thật ra ta có thể đặt hai cổng này chung thành một cổng có tên là NAND với sơ đồ:

Thật vậy, ta có thể tổng hợp cổng OR từ cổng NOT và cổng AND. Thật ra ta có thể đặt hai cổng này chung thành một cổng có tên là NAND với sơ đồ

Từ đó có thể tổng hợp cổng OR mà chỉ dùng cổng NAND như trong bài tập nêu trên. Suy ra mọi hàm Bool đều được tổng hợp mà chỉ dùng cổng NAND ta cũng có thể dùng cổng NOR với sơ đồ sau:

Khi ấy ta cũng chứng minh được mọi hàm Bool đều được tổng hợp mà chỉ sử dụng cổng NOR.

Bài toán tối ưu tiếp theo là tối ưu hóa hai mục tiêu:

• Cực tiểu hóa thời gian châm trễ (delay): tuy thời gian chậm trễ khi đi qua một cổng là nhỏ nhưng nếu tích lũy qua nhiều lớp cổng thì nó trở thành đáng kể, nhất là trong các máy tính có tốc độ cao.
• Cực tiểu hóa số cổng sử dụng

Do thời gian chậm trễ kho đi qua cổng NOT là không đáng kể, dưới đây khi phân tích các  mạch  ta có thể bỏ qua  cổng  NOT.  Nói  cách  khác  các  biến 𝑥̅, 𝑦̅, 𝑧̅, … cũng được xem như là các biến input tương tự như 𝑥, 𝑦, 𝑧,…

Thật ra hai mục tiêu trên không thể đồng thời tối ưu hóa được. Do đó trước hết ta tối ưu hóa theo thời gian. Ta sẽ thiết kế các mạch chỉ có tối đa hai lớp cổng: lớp cổng AND rồi lớp cổng OR hay lớp cổng OR rồi lớp cổng AND. Tuy nhiên trường hợp sau luôn luôn có thể đưa được về trường hợp trước nếu ta xét ƒ.̅ Do đó ta chỉ xét các công thức có dạng OR (𝗏) của các số hạng là AND (𝖠) của từ đơn. Đây chính là các công thức đa thức

Trong lớp các công thức đa thức, ta có một số thuật toán cho phép tìm được công thức đa thức tối tiểu.

Định nghĩa 4.3.1

Xét hai công thức đa thức của hàm Bool ƒ:

ƒ = 𝑚1 𝗏 𝑚2 𝗏 ....  𝗏𝑚𝑝                    (4.3.1)

ƒ = 𝑀1 𝗏 𝑀2 𝗏 …𝗏 𝑀𝑞                     (4.3.2)

Ta nói (4.3.1) đơn giản hơn (4.3.2) nếu tồn tại một đơn ánh 𝜎: { 1,2,…, 𝑝} →{ 1,2,…, 𝑞} sao cho với 1 ≤ i ≤ 𝑝 thì số thừa số là từ đơn của 𝑚i không nhiều hơn số thừa số là từ đơn của 𝑀_𝜎(i) .

Chú ý:

1. Nếu (4.3.1) đơn giản hơn (4.3.2) thì 𝑝 ≤ 𝑞

2. Quan hệ “đơn giản hơn” giữa các công thức đa thức của ƒ rõ ràng có tính phản xạ và bắc cầu. Tuy nhiên quan hệ này không phản xứng.

3. Nói rằng (4.3.1) đơn giản hơn (4.3.2) và (4.3.2) đơn giản hơn (4.3.1) có nghĩa là tồn tại các đơn ánh

𝜎: { 1,2,…, 𝑝} → { 1,2,…, 𝑞}

và  𝑟: { 1,2,…, 𝑞} → { 1,2,…, 𝑝}

sao cho 𝜎, 𝑟 thỏa Định nghĩa 4.3.1. Khi ấy 𝜎, 𝑟 là song ánh và với 1 ≤ i ≤ 𝑝 thì số thừa số là từ đơn của 𝑚i không nhiều hơn số thừa số là từ đơn của 𝑚𝑟∘𝜎(i) . Do đó nếu gọi 𝑘 là số nguyên nhỏ nhất sao cho

$\frac{(r \circ \sigma )\circ (r\circ \sigma )\circ ...\circ (r\circ \sigma )\left(i\right)}{k}=i$

và $j=\frac{(r\circ \sigma )\circ (r\circ \sigma )\circ ...\circ (r\circ \sigma )\left(i\right)}{k-1}$

thì 𝑚_i và 𝑚_j có thừa số là từ đơn bằng nhau.

Suy ra với 1 ≤ i ≤ 𝑝 thì 𝑚_i và 𝑀_𝜎(i) có thừa số là từ đơn bằng nhau. Khi ấy ta nói (4.3.1) và (4.3.2) đơn giản như nhau. Rõ ràng quan hệ đơn giản như nhau là một quan hệ tương đương. Hơn nữa nếu hai công thức đa thức là đơn gản như nhau thì mạng các cổng tổng hợp chúng sẽ sử dụng cùng số cổng AND và cổng OR.

4. Tương tự như trong Chương 3, nếu chuyển qua các lớp tương đương thì quan hệ đơn giản hơn trở thành một thứ tự. Tuy nhiên ta cũng có thể khảo sát trực tiếp các quan hệ chỉ có hai tính chất phản xạ và bắc cầu. ta nói chứng là các quan hệ tiền thứ tự . Đối với quan hệ tiền thứ tự, khái niệm phần tử tối tiểu và tối đại vẫn còn ý nghĩa. Chẳng hạn như một công thức đa thức (𝐹) của hàm Bool ƒ được nói là tối tiểu nếu với bất kỳ công thức đa thức (𝐺) của ƒ “đơn giản hơn” (𝐹) thì (𝐺) và (𝐹) đơn giản như nhau. Bây giờ do tập hợp các công thức đa thức của một hàm Bool ƒ là hữu hạn, ta chứng minh được tương tự như Định lý 3.3.3, cho trước một công thức đa thức (𝐹) của ƒ thì sẽ tồ tại một công thức đa thức tối tiểu (𝐺) của ƒ sao cho (𝐺) đơn giản hơn (𝐹). Cũng như trường hợp các tập hợp có thứ tự, một hàm Bool ƒ có thể có nhiều công thức đa thức tối tiểu.

5.  Xét công thức đa thức (4.3.1) của hàm ƒ. Giả sử tồn tại một dơn thức 𝑚 sao cho 𝑚₁ $\underset{khác}{\prec }$𝑚 ≺ ƒ. Khi ấy ta có:

ƒ = 𝑚 𝗏 ƒ = ( 𝑚 𝗏 𝑚₁) 𝗏 𝑚₂ 𝗏 …𝗏 𝑚_𝑝

ƒ = 𝑚 𝗏 𝑚 ₂𝗏 …𝗏 𝑚_𝑝                     (4.3.3)

Do 𝑚₁ ≺ 𝑚 ta có thể viết: 𝑚𝑚₁ = 𝑚₁

Như thế mọi thừa số là từ đơn của 𝑚 cũng là một thừa số của 𝑚1 . Hơn nữa do 𝑚₁ ≠ 𝑚 nên có ít nhất một thừa số là từ đơn của 𝑚1 không xuất hiện trong 𝑚. Khi ấy công thức (4.3.3) rõ ràng đơn giản hơn (4.3.1) nhưng không đơn giản như nhau. Suy ra (4.3.1) không tối tiểu. Ta đã chứng minh.

Mệnh đề 4.3.1

Trong một công thức đa thức tối tiểu, các số hạng là đơn thức tối dại trội bởi ƒ.

Định nghĩa 4.3.2

Một đơn thức tối đại trội bởi hàm Bool ƒ được gọi là một tiền đề nguyên tố của ƒ.

Do Mệnh đề 4.3.1, để tìm công thức đa thức tối tiểu của  một hàm Bool ƒ, ta hạn chế tìm kiếm trong các công thức đa thức mà các số hạng là những tiền đề nguyên tố dôi một khác nhau. Các công thức này là rút gịn theo nghĩa sau:

Định nghĩa 4.3.3:

Công thức đa thức (4.3.1) của hàm ƒ được nói là rút gọn nếu với 1 ≤ i ≠ j ≤ 𝑝, thì 𝑚i không phải là ước thật sự của 𝑚j.

Bổ đề 4.3.2: nếu 𝑔  và ℎ  là hai hàm Bool thì 𝑔ℎ̅ 𝗏 ℎ =  𝑔 𝗏 ℎ

Chứng minh:

𝑔ℎ̅ 𝗏 ℎ  =  𝑔ℎ̅ 𝗏 ( 𝑔ℎ 𝗏 ℎ)

            = 𝑔(ℎ̅ 𝗏 ℎ) 𝗏 ℎ =  𝑔 𝗏 ℎ  l đpcm

ƒ =  𝑥𝑦𝑧 𝗏 𝑥( 𝑦 𝗏 𝑦̅) 𝑧̅ 𝗏 𝑥̅𝑦𝑧̅

ƒ = 𝑥𝑦𝑧 𝗏 𝑥𝑧̅ 𝗏 𝑥̅𝑦𝑧̅                   (𝐹2)

Tương tự   

ƒ =  𝑥𝑦𝑧 𝗏 𝑥𝑦̅𝑧̅ 𝗏 𝑦𝑧̅            (𝐹3)

và

ƒ =  𝑥𝑦 𝗏 𝑥𝑦̅𝑧̅ 𝗏 𝑥̅𝑦𝑧̅                       (𝐹4)

Áp dụng Bổ đề 4.3.2 cho (𝐹2), (𝐹3) và (𝐹4) ta được:

ƒ = 𝑥( 𝑦𝑧 𝗏 𝑧𝗏 𝑥̅𝑦𝑧

   = 𝑥( 𝑦 𝗏 𝑧)̅ 𝗏 𝑥̅𝑦𝑧̅

   = 𝑥𝑦 𝗏 𝑥𝑧̅ 𝗏 𝑥̅𝑦𝑧̅                    (𝐹5)

Tương tự       

ƒ = 𝑥𝑦𝑧 𝗏 𝑥𝑧̅ 𝗏 𝑦𝑧̅            (𝐹6)

và           

ƒ =  𝑥𝑦 𝗏 𝑥𝑦̅𝑧̅ 𝗏 𝑦𝑧̅                                (𝐹7)

Cuối cùng, áp dụng Bổ đề 4.3.2 cho một trong 3 công thức (𝐹5), (𝐹6) hay (𝐹7) ta được:       

ƒ = 𝑥𝑦 𝗏 𝑥𝑧̅ 𝗏 𝑦𝑧̅             (𝐹8)

Tám công thức trên đều là rút gọn và có biểu đồ Hasse:

Công thức (𝐹8 ) là công thức đa thức tối tiểu duy nhất nên cũng là công thức đơn giản nhất . Sử dụng công thức (𝐹8 ) để tổng hợp hàm Bool ƒ ta chỉ tốn 3 cổng AND và 2 cổng OR thay vì 8 cổng AND và 3 cổng OR nếu dùng (𝐹1 ). Ta có sơ đồ mạch các cổng ứng với (𝐹8 ) như sau:

PHƯƠNG PHÁP BIỂU ĐỒ KARNAUGH

Phương pháp biểu đồ Karnaugh cho phép tìm nhanh công thức đa thức tối tiểu của hàm Bool 3, 4 biến. Trường hợp 3 biến hoàn toàn tương tự nhưng đơn giản hơn trường hợp 4 biến. Do đó ta tập trung trình bày 4 biến. Nhắc lại một hàm Bool 4 biến là một ánh xạ 𝐵⁴ → 𝐵 nên để có thẻ biểu diễn bằng hình ảnh ta sẽ sử dụng một hình vuông gồm có 16 ô vuông nhỏ để biểu diễn 16 phần tử của 𝐵⁴. Khi ấy ta có thể biểu diễn một hàm Bool

ƒ: 𝐵⁴ → 𝐵 bằng các gạch chéo các ô ở đó ƒ bằng 1.

Như vậy vấn đề chính là đánh dấu 16 ô của hình vuông tương ứng với các phần tử của 𝐵⁴. Ta đã biết các phần tử của 𝐵⁴ có thể được sắp thứ tự theo thứ tự tự điển:

0000,0001,,0010,0011,…,1111

Ta có thể xếp các phần tử của 𝐵⁴ theo thứ tự lần lượt trên các dòng của hình vuông lớn. tuy nhiên cách này không thuận tiện bằng cách của Veitch và Karnaugh như sau:

Ở đây ký hiệu 𝑥 chỉ cột ở đó biến đầu tiên 𝑥 lấy giá trị 1, 𝑥̅ chỉ cột ở đó biến 𝑥 lấy giá trị 0. Tương tự cho biến thứ hai 𝑦. Các biến thứ ba   và thứ tư 𝑧, 𝑡 được gán với các dòng. Ví dụ ở hai dòng đầu biến 𝑧 lấy giá trị 1 và 2 dòg nsau biến 𝑧 lấy giá trị 0. Tương tự cho biến 𝑡. Cách biểu diễn trên của 𝐵4 rất thuận tiện cho việc biểu diễn các đơn thức. Thật vậy ta nhận xét rằng 2 ô liên tiếp nhau chỉ khác nhau một thành phần , ví dụ ô ở dòng 2 cột 2 và ô ở dòng 2 cột 3 chỉ khác nhau ở thành phần đầu tiên: 1111 và 0111. Mặt khác ô ở dòng 1 cột 1 và dòng 1 cột 4 cũng biểu diễn hai phần tử chỉ khác nhau một thành phần: 1010 và 0010. Ta quy ước rằng các ô này cũng được xem như kề nhau theo nghĩa rộng: 2 ô được nói là kề nhau theo nghĩa rộng nếu sau khi ta cuốn hình vuông theo chiều rộng hoặc chiều ngang tạo thành hình trụ thì hai ô ban đầu sẽ trở thành kề nhau trên hình trụ. Với qui ước trên ta thấy rằng hai ô kề nhau (theo nghĩa thông thường hay nghĩa rộng) khi và chỉ khi chùng biểu diễn hai phần tử của 𝐵4 chỉ khác nhau một thành phần.

Bây giờ để biểu diễn một hàm Bool 4 biến ƒ, ta sẽ gạch chéo các ô của hình vuông lớn tương ứng với các điểm của 𝐵4 ở đó ƒ bằng 1. Ta nói hình vẽ ấy là biểu đồ Karnaugh của hàm Bool ƒ. Ví dụ như hình vẽ dưới đây chỉ biểu đồ Karnagh của hàm Bool 4 biến:

ƒ =  𝑥𝑦𝑧𝑡 𝗏 𝑥𝑦𝑧𝑡̅ 𝗏 𝑥̅𝑦𝑧𝑡 𝗏 𝑥̅𝑦𝑧̅𝑡 𝗏 𝑥̅𝑦𝑧̅𝑡̅ 𝗏 𝑥̅𝑦̅𝑧̅𝑡

Nhận xét rằng hàm Bool ƒ chính là các hàm đặc trưng của tập hợp gạch chéo trong biểu đồ Karnaugh. Do đó sử dụng đẳng cấu giữa 2 đại số Bool 𝑃( 𝐵⁴) và 2𝐵⁴ ta có:

Mệnh đề 4.4.1:

Với mọi hàm Bool 4 biến ƒ, 𝑔:

i. Biểu đồ Karnaugh của ƒ là tập hợp con của biểu đồ Karnaugh của 𝑔 khi và chỉ khi ƒ ≺ 𝑔

ii. Biểu đồ Karnaugh của ƒ 𝗏 𝑔 (tương ứng ƒ 𝖠 𝑔) là hợp (tương ứng giao) của các biểu đồ Karnaugh của ƒ và 𝑔.

iii. Biểu đồ Karnaugh của ƒ̅ là phần bù của biểu đồ Karnaugh của ƒ.

Chú ý:

1. Sử dụng Mệnh đề 4.4.1 ta có thể vẽ được biểu đồ Karnaugh của một hàm Bool nếu biết bảng chân trị của nó hoặc nếu biết được một công thức biểu diễn hàm Bool dưới dạng một biểu thức theo các biến và các phép toán 𝗏,𝖠, −.

2. Ngược lại nếu biết được biểu đồ Karnaugh của hàm Bool ƒ, ta có thể đọc ngay từ đó dạng nối rời chính tắc: các từ tối tiểu trội bởi ƒ chính là các hàm đặc trưng của mỗi ô nằm trong biểu đồ Karnaugh. Hơn nữa, công thức cho từ tối tiểu như là tích của bốn từ đơn được đọc ngay triong biểu đồ Karnaugh khi xem các dòng và cột chứa ô đang xét:  ví  dụ như từ đơn ứng  với  ô  ở dòng  3  cột  2  là 𝑥𝑦𝑧̅𝑡 thì  các  dòng  và  cột  chứa  ô này là 𝑥, 𝑦, 𝑧̅ và 𝑡.

3. Hai từ tối tiểu ứng với hai ô kề nhau ( theo nghĩa thông thường hoặc nghĩa rộng) hỉ khác nhau một thừa số là từ đơn, nên ta có thể dùng luật phân bố để đặt thừa số chung trong tổng Bool của chúng và được một đơn thức có 3 thừa số là từ đơn. Ví dụ như:

𝑥𝑦𝑧𝑡 𝗏 𝑥𝑦𝑧𝑡̅ = 𝑥𝑦𝑧( 𝑡 𝗏 𝑡  = 𝑥𝑦𝑧

có biểu đồ Karnaugh là một hình chữ nhật theo nghĩa rộng gồm hai ô liên tiếp nhau 1110 và 1111.

Tổng quát hơn ta có:

Mệnh đề 4.4.2:

Biểu đồ Karnaugh của một đơn thức có dạng tích của 𝑝( 1 ≤ 𝑝 ≤ 4) từ đơn là một hình chũ nhật (theo nghĩa rộng) gồm 24−𝑝 ô, mà ta gọi là các tế bào.

Ví dụ:

Do Mệnh đề 4.4.1 và 4.4.2, các tiền đề nguyên tố của một hàm Bool 4 biến có biểu đồ Karnaugh là một tế bào tối đại nằm trong biểu đồ Karnaugh của ƒ. Ta nói các tế bào này là tế bào lớn của biểu đồ Karnaugh của ƒ. Như vậy việc tìm công thức đa thức tối tiểu của ƒ đưa về việc giải quyết hai vấn đề:

• Tìm tất cả các tế bào lớn nằm trong biểu đồ Karnaugh của ƒ.
• Tìm một phép phủ tối tiểu biểu đồ Karnaugh của ƒ bằng các tế bào lớn, nghĩa là một họ tế bào lớn có hợp là biểu đồ Karnaugh của ƒ sao cho khi rút bớt một tế bào lớn thì họ còn lại không phủ kín biểu đồ Karnaugh của ƒ. Từ đó ta được một thuật toán để tìm công thức đa thức tối tiểu.

Bước 1: chỉ ra tất cả các tế bào lớn của biểu đồ Karnaugh của ƒ.

Sau bước 1 ta sẽ phủ dần biểu đồ Karnaugh bằng các tế bào lớn cho đến khi phủ kín

Bước 2: Nếu tồn tại một ô chỉ nằm trong một tế bào lớn duy nhất, ta chọn ra tế bào này để phủ. Trong phần còn lại của biểu đồ Karnaugh, nếu có một ô chỉ nằm trong một tế bào lớn duy nhất, ta chọn ra tế bào này để phủ, và lặp lại bước 2 cho đến khi không còn ô nào có tính chất trên.

Bước 3: nếu các tế bào lớn chọn trong Bước 2 đã phủ kín biểu đồ Karnaugh của ƒ ta qua thẳng Bước 4. Nếu không, chọn ra một ô còn lại. Trong số các tế bào lớn chứa ô này ta chọn ra một ô tùy ý dể thêm vào phép phủ và cứ tiếp tục như trên cho phần còn lại cho đến khi phủ kín biểu đồ Karnaugh của ƒ.

Bước 4: ở bước này ta đã chọn được một số tế bào lớn phủ kín biểu đồ Karnaugh của ƒ. Do trong Bước 3 có sự lựa chọn tùy tế bào lớn chứa một ô , ta thường có nhiều hơn một phép phủ. Trong số phép phủ nhận được, loại bỏ các phép phủ không tối tiểu. Sau cùng các phép phủ còn lại cho ta một công thức đa thức của ƒ mà ta còn phải so sánh chúng theo Định nghĩa 4.3.1: loại bỏ những công thức có một công thức khác trong số đó thực sự đơn giản hơn nó. Các công thức còn lại chính là công thức đa thức tối tiểu phải tìm.

Chú ý:

1. Nếu Bước 3 được bỏ qua thì không có sự lựa chọn tùy ý. Trong trường hợp any2 ta được một phép phủ duy nhất tương ứng với công thức đa thức tối tiểu duy nhất.

2. Để thuận tiện cho việc xem xét ta gạch chéo mỗi tế bào lớn được chọn cho đến khi phần gạch chéo trùng với biểu đồ Karnaugh của ƒ. Đương nhiên hai cách chọn khác nahu sẽ dẫn đến hai quá trình phủ khác nhau và cho ta hai công thức khác nhau.

PHƯƠNG PHÁP THỎA THUẬN

Nhắc lại hai bài toán chính để tìm công thức đa thức tối tiểu của một hàm Bool ƒ:

• Tìm tất cả các tiền đề nguyên tố của ƒ
• Tìm cách biểu diễn ƒ như là tổng tối tiểu của các tiền đề nguyên tố Để giải quyết bài toán 5.1 ta sẽ dùng phương pháp thỏa thuận

Định nghĩa 4.5.1

Giả sử 𝑥 là một trong các biến Bool và 𝑚1, 𝑚2 là hai đơn thức không chia hết cho cả 𝑥 lẫn 𝑥̅. Khi ấy được nói là thỏa thuận giữa hai đơn thức 𝑥𝑚1 và 𝑥̅𝑚2.

Chú  ý:  nếu có một biến  thứ hai 𝑦  sao cho 𝑚₁ chia hết cho 𝑦  (hoặc 𝑦̅) và 𝑚₂  chia hết cho 𝑦̅ (hoặc 𝑦), khi ấy thỏa thuận 𝑚₁𝑚₂ rõ ràng bằng 0. Do đó cho trước 3 đơn thức có 3 trường hợp có thể xảy ra:

Trường hợp 1: không tìm được thỏa thuận của chúng vì không có biến 𝑥 nào như trong Định nghĩa 4.5.1

Trường hợp 2: thỏa thuận của chúng bằng 0 vì có ít nhất hai biến Bool thỏa Định nghĩa 4.5.1

Trường hợp 3: chỉ có một biến Bool thỏa Định nghĩa 4.5.1 và do đó thỏa thuận của hai đơn thức cho trước là một đơn thức (≠ 0)

Ví dụ:

1. 𝑥𝑧 𝑣à 𝑦𝑡̅ không có thỏa thuận

2. 𝑥𝑦̅𝑧 𝑣à 𝑦𝑧̅𝑡  có thỏa thuận bằng 0

3. 𝑥𝑦̅𝑧 𝑣à 𝑦𝑡 có thỏa thuận là 𝑥𝑧𝑡

Định lý 4.5.1

Thỏa thuận của haqi đơn thức luôn luôn đượ trội bởi tổng Bool của hai đơn thức ấy.

Chứng minh: Xét hai đơn thức 𝑥𝑚1 và 𝑥̅𝑚2 với thỏa thuận 𝑚1𝑚2 ta có:

𝑚1𝑚2 =  𝑚1𝑚2( 𝑥 𝗏 𝑥̅) =  𝑥𝑚1𝑚2 𝗏 𝑥̅𝑚1𝑚2

Suy ra:  

𝑚₁𝑚₂ 𝗏 𝑥𝑚₁ 𝗏 𝑥̅𝑚₂  =  ( 𝑥𝑚₁𝑚₂ 𝗏 𝑥𝑚₁) 𝗏 ( 𝑥̅𝑚₂ 𝗏𝑥̅𝑚₂𝑚₁)

= 𝑥𝑚₁ 𝗏 𝑥̅𝑚₂

Nghĩa là 𝑚₁𝑚₂ ≺ 𝑥𝑚₁ ≺ 𝑥̅𝑚₂ l đpcm

Với khái niệm thỏa thuận ta có phương pháp sau để xác định tất cả các tiền đề nguyên tố của một hàm Bool ƒ.

Bước 1: Viết ƒ dưới dạng công thức thu gọn tùy ý (dạng nối rồi chính tắc chẳng hạn):

Đặt ➚ = { 𝑚₁, 𝑚₂,…, 𝑚_𝑟}

ƒ = 𝑚₁ 𝗏 𝑚₂ 𝗏 …𝗏 𝑚_𝑟

Gọi ࣰ là danh sách các biến theo một thứ tự nhất định nhưng tùy ý.

Bước 2: Trong Bước 2 ta sẽ cập nhật dần ➚ theo từng biến trong ࣰ như sau:

i.  Giả sử 𝑥 là một biến trong ࣰ mà ta đã xét tới với ➚ đã được cập nhật theo các biến trước 𝑥. Ta phần hoạch ➚ thành 3 phần (rời nhau):

• 𝘗 gồm các đơn thức chia hết cho 𝑥
• 𝐵 gồm các đơn thức chia hết cho 𝑥̅
• gồm các đơn thức không chia hết cho 𝑥 lẫn 𝑥̅

ii. Nếu 𝘗 = ∅ hay 𝐵 = ∅ ta sẽ xét biến kế tiếp 𝑥. Nếu không, ta thêm vào ➚ tất cả các thỏa thuận của một đơn thức thuộc 𝘗 và một đơn thức thuộc 𝐵.

iii. Mỗi lẩn thêm một phần tử mới vào ➚ ta phải duyệt lại và loại bớt những phần tử được trội thực sự bởi một phần tử khác (kể cả phần tử mới thêm vào).

Bước 3: Sau khi đã duyệt tất cả các biến trong ࣰ ta có:

Định lý 4.5.2:

Tập hợp ➚ sau cùng trong Bước 3 chính là tập hợp tất cả các tiền đề nguyên tố của ƒ.

Chứng minh:

Gọi 𝜔 là số biến trong ࣰ, và một 𝑚 là một tiền đề nguyên tố bất kỳ của ƒ, ta chứng minh tập hợp ➚ sau cùng sẽ chứa 𝑚 bằng quy nạp trên 𝜔.

Gọi 𝑥 là biến đầu tiên trong danh sách ࣰ và 𝘗, 𝐵, ✔ là các tập hợp tương ứng như trong i).

Trường hợp 1: 𝑚 không chia hết cho 𝑥 lẫn 𝑥̅, ta có:

𝑚𝑥 ≺ ( Ç 𝑛) 𝑥 𝗏 (Ç𝑝𝑥) 𝗏 (Ç  𝑞) 𝑥

Ở đây kí hiệu Ç 𝑛 dùng để chỉ tổng Bool của tất cả các phần tử của A. Các ký hiệu khác cũng tương tự. để ý rằng nếu 𝑝 ∈ 𝐵 thì 𝑝 chia hia hết cho 𝑥̅ nên 𝑝𝑥 = 0. Do đó:

𝑚𝑥 ≺ (Ç 𝑛/ 𝑥) 𝑥 𝗏 (Ç 𝑞) 𝑥

Cho 𝑥 = 1 ta được

𝑚 ≺ (Ç 𝑛/ 𝑥) 𝗏 (Ç 𝑞)

Tương tự ta có

𝑚 ≺ (Ç𝑝/ 𝑥̅) 𝗏 (Ç  𝑞)

Suy ra

𝑚 ≺ ( Ç  ( 𝑛/ 𝑥) ( 𝑝/ 𝑥̅) )     𝑞∈✔

Giả sử ➚ đã được cập nhật theo biến 𝑥 như trong Bước 2 ở trên. Gọi ➚′ là tập hợp con của ➚ gồm các đơn thức không chia hết cho 𝑥 lẫn 𝑥̅. Gọi ƒ′ là tổng Bool của các đơn thức  trong ➚′  xem như hàm Bool theo các  biến  trong ࣰ′  =  ࣰ\ { 𝑥} .  Rõ ràng 𝑚  là một  tiền đề nguyên tố của ƒ′ nên theo giả thiết quy nạp, sau khi cập nhật theo biến cuối cùng trong

ࣰ′, ➚′ chứa 𝑚. Nhưng tập  hợp ➚′  sau  cùng  là  tậph  ợp  con  của  tập  hợp ➚  sau  khi  cập  nhật theo biến sau cùng của ࣰ′, vì trong quá trình cập nhật theo các biến của ࣰ′, các đơn thức của ➚ bị loại đi cũng chính là các đơn thức của ➚′ bị loại đi hoặc là các đơn thức chia hết cho 𝑥 hoặc 𝑥̅. Nói tóm lại ta đã chứng minh được tậph ợp ➚ sau cùng chứa 𝑚.

Trường hợp 2: 𝑚 chia hết cho 𝑥 hay 𝑥̅. Ta có thể giả sử 𝑚 chia hết cho 𝑥 vì trường hợp còn lại chứng minh tương tự.

Gọi 𝘗, 𝐵, ✔ là 3 tập hợp tạo thành phân hoạch của ➚ tương ứng với biến 𝑥 như trong Bước 2. Cho 𝑥 = 1 ta được:

𝑚/ 𝑥  ≺ (Ç( 𝑛/ 𝑥) ) 𝗏 (Ç  𝑞)

Suy ra

𝑚 ≺ (Ç 𝑛) 𝗏 𝑥 (Ç 𝑞)

≺ (Ç 𝑛) 𝗏 (Ç 𝑞) = ƒ

Ứng với mỗi hàm Bool 𝑔 theo các biến trong ࣰ, ta liên kết một hàm Bool 𝑔̅ với các biến trong ࣰ′  =  ࣰ\ { 𝑥}  bằng cách cho 𝑥 =  1. Đặt ➚′  =  𝘗 𝖴 ✔. Khi ấy 𝑔 ⟼ 𝑔̅  là một song ánh giữa ➚′ và  một tập hợp ➚̅′ các từ đơn theo các biến  trong ࣰ′ vì không  có phần  tử nào của ✔ là ước của một phần tử của 𝘗 (công thức đa thức ban đầu của ƒ là rút gọn).

Ta có công thức đa thức rút gọn:

ƒ   =  (Ç 𝑛̅) 𝗏 (Ç  𝑞)

𝑛∈𝘗                   𝑞∈✔

Hơn nữa tương ứng 𝑔 ⟼ 𝑔̅, nếu thu hệp trên tập ➚′ đã được cập nhật đối vối biến sau cùng, cũng là một song ánh giữa tập hợp này và tập hợp ➚̅′ đã được cập nhật theo biến sau cùng đối với hàm ƒ̅′, vì nếu có 𝑚̅1  =  𝑚̅2  với 𝑚1  ≠ 𝑚2  thì   một trong hai đơn thức 𝑚1, 𝑚2   là tích của đơn thức kia và 𝑥 nên đã được loại trong quá trình cập nhật.

Rõ ràng 𝑚̅  ≺ ƒ,

giả sử tồn tại đơn thức 𝑚̅′  theo các biến trong ࣰ′ sao cho:

𝑚̅  ≺ 𝑚̅′ ≺ ƒ̅′

Ta có:

𝑚 =  𝑥𝑚̅  ≺ 𝑥𝑚̅′  ≺ 𝑥ƒ̅′  =  (Ç 𝑥𝑛̅) 𝗏 𝑥 (Ç  𝑞) ≺ ƒ

                                           𝑛∈𝘗            𝑞                    

Suy ra 𝑚̅   =  𝑚̅′, nghĩa là 𝑚̅  là tiền đề nguyên tố của ƒ̅′

Như thế theo  giả thiết  quy  nạp, ➚̅′,  sau  khi  cập  nhật  theo  biến  cuối  cùng,  sẽ chứa 𝑚̅ . Tương tự như trong Trường hợp  1, ta thấy tập  hợp ➚  sau khi cập  nhật đối  với biến cuối cùng, sẽ chứa ➚′.

Suy ra 𝑚 ∈ ➚

Cuối cùng do cách cập nhật các đơn thức, trong đơn thức nào trong ➚ được trội thực sự bởi một đơn thức khác, nghĩa là các phần tử của ➚ đều là tiền đề nguyên tố của ƒ. l đpcm

Bài toán phủ:

Tìm một họ ➚0 các tiền đề nguyên tố của ƒ sao cho:

i. Mỗi từ tối tiểu trội bởi ƒ được trội bởi một tiền đề thuộc ➚0

ii. Họ ➚0 là từ tối tiểu, nghĩa là nếu rút bớt một phần tử thì phần còn lại không thỏa i)

Gọi ➚ = {𝑚₁,…, 𝑚_𝑝} là tập hợp tất cả các tiền dề nguyên tố của ƒ mà ta tìm được khi giải bài toán 5.1

Ta đưa vào các biến Bool 𝑎₁, 𝑎₂,…, 𝑎_𝑝 và tgiet61 lập một hệ phương trình Bool theo các biến Bool như sau:

Với mỗi từ tối tiểu ➚ trội bởi ƒ, gọi 𝑚_i1 , 𝑚_i2 ,…, 𝑚_ik là tất cả các tiền đề nguyên tố của ƒ trội 𝑡. Khi ấy ta có một phương trình: 𝑎_i1 𝗏 𝑎_i2 𝗏 …𝗏 𝑎_ik = 1

Cho 𝑡 chạy khắp các từ tối tiểu trội bởi ƒ, ta được một hệ 𝑞 phương trình trong đó 𝑞 là số các từ tối tiểu trội bởi ƒ. Giải hệ phương trình Bool trên ta được các nghiệm là bộ 𝑝:

$\left\{\begin{array}{l}\begin{array}{c}{a}_1=b_1\\ a_2=b_2\\ ⋮\end{array}\\ a_p=b_p\end{array}\right.$

Trong đó 𝑏₁, 𝑏₂,…, 𝑏_𝑝 là các giá trị cố định bằng 1 hoặc tùy ý. Với các 𝑏_i = 1 ta có 𝑎i = 1, nghĩa là tiền đề nguyên tố 𝑚_i được chọn để phủ ƒ. Để giải hệ phương trình Bool có dạng trên, ta thực hiên các bước sau:

Bước 1: loại bỏ các phương trình trùng lắp, nói cách khác giả sử có hai phương trình có dạng:

𝑎_i1 𝗏 𝑎_i2 𝗏 …𝗏 𝑎_ik  = 1

và  𝑎_j1 𝗏 𝑎_j2 𝗏 …𝗏 𝑎_jℎ = 1

sao cho { i1, i2,…, ik} ⊂ { j1, j2,…, jℎ}

Khi ấy phương trình thứ hai là hệ quả của phương trình đầu và do đó có thể được loại bỏ

Bước 2: Vì hệ phương trình đồng thời nghiệm đúng, ta thấy nó tương đương với một phương trình duy nhất có vế trái là tích của tất cả các vế trái và vế phải bằng 1 Dùng luật phân bố khai triển vế trái và đưa nó về dạng một công thức đa thức.