Một mã gồm 6 ký tự trong đó gồm 3 chữ cái tiếng Anh rời đến 3 chữ số hồi có bao nhiêu mà khác nhau

Thuật toán quay lui

procedure Try[i: integer];

var j:integer;

begin

for j=1 to 

if then

begin

;

if i= n then

else

Try [i+1];

end

end

begin

Try[1];

end

procedure Try[i:integer];

var j:integer;

begin

for j=0 to 1 do

begin

b[i]=j;

if i=n then Result else Try[i+1];

end

end

begin

Try[1];

end

Liệt kê các hoán vị từ 1 đến N

Biểu diễn hoán vị dưới dạng , , , , trong đó với i. Các giá trị từ 1 đến n

lần lượt đề cử cho , trong đó giá trị được chấp nhận nếu nó chưa được dung. Vì thế cần phải ghi nhớ đối với mỗi giá trị

xem nó được dùng hay chưa. Điều này thực hiện nhờ vào một dãy biến logic bằng true nếu chưa được

dùng. Các biến này cần phải được khởi gán giá trị true . Sau khi gán cho cần ghi nhận false cho và phải gán lại true

khi thực hiện xong Result hay Try[i+1].

procedure Try[i : integer];

var j: integer;

vegin

for j=1 to n do

if b[j] then { chấp nhận j }

begin

p[i] = j;

b[j] = false; {ghi nhận trạng thái mới }

if i= n then Result else Try[i + 1];

b[j]=true;

end

end

Liệt kê các tổ hợp chập m của {1, 2, …, n}

Biểu diễn tổ hợp dưới dạng … , trong đó  < … fopt

then branch_and_bound[i+1];

weight=weight –a[i]*x[i];

cost = cost –c[i] * x[i];

end

end

Bài toán người du lịch

Tìm cựu tiểu của hàm

, …., ] = c[1, + c[, + ….+ c[, + c[, 1

Với điều kiện , …., ] là hoán vị của các số 2, 3, …,.

Ký hiệu 

Giả sử ta có phương án bộ phận []. Phương án này tương ứng với hành trình bộ phận qua thành phố

… 

Vì vậy, chi phí phải trả theo hành trình bộ phận qua thành phố

c[1, + c[, + ….+ c[, 

Cận dưới phương án bộ phận g[]= + 

Giải bài toán người du lịch      

    

    

    

    

procedure Try[i:integer];

var j: integer;

begin

for j=2 to n do

if chuaxet[j] then

begin

a[i]=j;

chuaxet [j] = false;

chuaxet[j] = false;

can = can + c[a[i-1], a[i]];

if i=n then Ghinhan

else

if Can + [n-i+1]*then Try [i+1];

 

chuaxet [j] = true;

end

end

Bài toán lập lịch trên hai máy

Thuật toán JOHNSON

1. Chia các chi tiết thành 2 nhóm:  

2. Sắp xếp các chi tiết theo chiều tăng của các và sắp xếp chi tiết theo chiều giảm 

3. Nối vào đuôi . Dãy thu được sẽ là lịch gia công tối ưu.

Các kết quả được tính sau:

•Chia nhóm = {,} = {, }

•Sắp xếp các chi tiết theo chiều tăng của các và sắp xếp chi tiết theo chiều giảm 

= {, } = {, }

•,,

Định nghĩa 1. Đơn đồ thị vô hướng

G= 

Định nghĩa 2. Đa đồ thị vô hướng

G= 

được gọi là cạnh lặp nếu chúng cùng tương ứng với một cặp đỉnh.

Định nghĩa 3. Giả đồ thị vô hướng G=[V, E] bao gồm V là tập đỉnh, và E là họ các cặp không có thứ tự gồm hai phần tử [ không

nhất thiết phải khác nhau] của V gọi là các cạnh. Cạnh được gọi là khuyên nếu nó có dạng 

Định nghĩa 4. Đơnđồ thị vô hướng G=[V, E] bao gồm V là tập đỉnh, và E tập các cặp có thứ tự gồm hai phần tử khác nhau của

V gọi là các cung.

Định nghĩa 5. Đa đồ thị có hướng

 . Hai

cung 

Các thuật ngữ cơ bản

Định nghĩa 6. Hai đỉnh và của đồ thị vô hướng G được gọi là kề nhau nếu [] là cạnh của đồ thị G. Nếu e=[u, v] là

cạnh của đồ thị thì ta nói cạnh này là liên thuộc với 2 đỉnh u và v, hoặc cũng nói là cạnh e là nối đỉnh u và đỉnh v, đồng thời

các đỉnh u và v sẽ được gọi là các đỉnh đầu của cạnh [u, v].

Định nghĩa 7. Ta gọi bậc của đỉnh v trong đồ thị vô hướng là số cạnh liên thuộc với nó và sẽ kí hiệu là deg[v]

Xét đồ thị trong hình 1, ta có

deg[a] = 1, deg[b] = 4, deg[c] = 4, deg[f] = 3, deg[d] = 1, deg[e] = 3, deg[g] = 0

Định lý 1. Giả sử   





Chứng minh. Rõ ràng mỗi cạnh

e  

Thí dụ 2

Đồ thị n đỉnh và mỗi đỉnh có bậc là 6 có bao nhiêu cạnh ?

Giải: Theo định lý 1, ta có 2m=6n. Từ đó suy ra số cạnh của đồ thị là 3n.

Hệ quả. Trong đồ thị vô hướng, số đỉnh bậc lẻ[ nghĩa là có bậc là số lẻ] là một số chẵn.

Chứng minh. Thực vậy, gọi 

=+ 

Định nghĩa 8.

N  

   

Định nghĩa 9

Ta gọi bán bậc ra [bán bậc vào] của đỉnh v trong đồ thị có hướng là số cung của đồ thị đi ra khỏi nó [đi vào nó] và kí hiệu

là  

Định lý 2. Giả sử là đồ thị có hướng. Khi đó



 



Đường đi, chu trình. Đồ thị liên thông

Định nghĩa 10. Đường đi độ dài n từ đỉnh u đến đỉnh v, trong đó n là số nguyên dương, trên đồ thị vô hướng  

, …, 

Trong đó , [, ]  

Đường đi nói trên có thể biểu diễn dưới dạng dãy các cạnh

[, ], [, ],…., [, ]

Đỉnh u gọi là đỉnh đầu, còn đỉnh v gọi là đỉnh cuối của đường đi. Đường đi có đỉnh đầu trùng với đỉnh cuối [tức là u=v]

được gọi là chu trình. Đường đi hay chu trình được gọi là đơn nếu nhưkhông có cạnh nào được lặp lại.

Định nghĩa 11.

Đường đi độ dài n từ đỉnh u đến đỉnh v, trong đó n là số nguyên dương, trên đồ thị có hướng  

,…., 

Trong đó , ,  

Đường đi nói trên còn có thể biểu diễn dưới dạng dãy các cung: , , , , …., , 

Đỉnh u được gọi là đỉnh đầu, còn đỉnh v gọi là đỉnh cuối của đường đi. Đường đi có đỉnh đầu trùng với đỉnh cuối [tức là

u=v] được gọi là chu trình. Đường đi hay chu trình được gọi là đơn nếu nhưkhông có cung nào bị lặp lại.

Định nghĩa 12.

Đồ thị vô hướng  

Định nghĩa 13. Ta gọi đồ thị con của đồ thị là đồ thị  

Trong đó  

Định nghĩa 14.

Đỉnh v được gọi là đỉnh rẻ nhánh nếu việc loại bỏ v cùng với các cạnh liên thuộc với nó khỏi đồ thị làm tang số thành phần

liên thông của đồ thị. Cạnh e được gọi là cầu nếu việc loại bỏ nó khỏi đồ thị làm tăng số thành phần liên thông của đồ thị.

Định nghĩa 15.

Đồ thị có hướng   được gọi là liên thông mạnh nếu luôn tìm được đường đi giữa hai đỉnh bất kì của nó.

Định nghĩa 16.

Đồ thị có hướng   được gọi là liên thông yếu nếu đồ thị vô hướng tương ứng với nó là đồ thị vô hướng liên thông.

Định lý 3.

Đồ thị vô hướng liên thông là định hướng được khi và chỉ khi mỗi cạnh của nó nằm trên ít nhất một chu trình.

Một số dạng đồ thị đặc biệt

Đồ thị hai phía.

Đơn đồ thị   

của đồ thị chỉ nối một đỉnh nào đó trong X với một đỉnh nào đó trong Y. Khi đó ta sẽ sử dụng kí hiệu   

hai phía với tập đỉnh X.

Định lý 4

Đơn đồ thị là đồ thị hai phía và chỉ khi nó không chứa chu trình độ dài lẻ.

Đồ thị hai phía.

Đơn đồ thị

 

. Cách vẽ như vậy sẽ được gọi là biểu diễn phẳng của đồ thị.

Định lý 5[Kuratovski]

Đồ thị là phẳng khi và chỉ khi nó không chứa đồ thị con đồng cấu với 

Định lý 6 [công thức Euler]

Giả sử G là đồ thị phẳng liên thông với n đỉnh, m cạnh. Gọi m là số miền của mặt phẳng bị chia bởi biểu diễn phẳng của G. Khi đó

= –+2

Thí dụ

Cho G là đồ thị phẳng liên thông với 20 đỉnh, mỗi đỉnh đều có bậc là 3. Hỏi mặt phẳng bị chia làm bao nhiêu phần bởi biểu diễn

phẳng của đồ thị G.

Giải. Do mỗi đỉnh của đồ thị đều có bậc là 3, nên tổng bậc của đỉnh là 3x20=60. Từ đó suy ra số cạnh của đồ thị m=60/2=30. Vì

vậy theo công thức Euler, số miền cần tìm là = 30- 20 +2 =12

BIỂU DIỄN ĐỒ THỊ TRÊN MÁY TÍNH

  



A= {

=0 nếu  và =1, nếu   















Tùy từng trường hợp cụ thể c[i , j] = 

Tìm kiếm theo chiều sâu trên đồ thị

procedure DFS[v];

[* Tìm kiếm theo chiều sâu bắt đầu từ đỉnh v, các biến Chuaxet, Ke là biến toàn cục *]

begin

Thăm_đỉnh[v];

Chuaxet[v] = false;

for 

if chuaxet[u] then DFS[u];

end

begin

for do chuaxet[v]=True;

for do

if Chuaxet[v] then DFS[v];

end

Tìm kiếm theo chiều rộng trên đồ thị

procedure BFS[v];

[* Tìm kiếm theo chiều sâu bắt đầu từ đỉnh v, các biến Chuaxet, Ke là biến toàn cục *]

begin

QUEUE= 

QUEUE ;

Chuaxet[v]=false;

while QUEUE 

begin

p 

thămđỉnh[p];

` for kề[p] do

if Chuaxet[u] then

begin

QUEUE ;

Chuaxet [u] = false;

end

end

end

ĐỒ THỊ EULER VÀ ĐỒ THỊ HAMILTON

Đồ thị Euler và các kết quả liên quan đã được nhà toán học Thụy Sĩ Leonhard Euler [1707-1783] nghiên cứu từ thế kỉ 18

khi ông tiến hành giải quyết bài toán nổi tiếng có tên gọi “Bài toán 7 chiếc cầu ở thành phố Kónigsberg”. Có thể đi dạo

qua hết tất cả các cầu mỗi cầu chỉ qua một lần rồi trở về nơi xuất phát được không.

Bài toán xuất phát từ những bức thư của người dân vùng Kónigsberg [Nga] gửi cho Euler vào năm 1736 khi ông sang Nga

làm việc. Euler đã chứng minh được rằng, một cuộc đi dạo nhưvậy không thể nào xảy ra. Euler đã biểu diễn bài toán trên

bằng đồ thị và khẳng định, đồ thị nhưvậy không thể vẽ được một đường liền nét đi qua tất cả các cạnh sao cho mỗi cạnh

chỉ vẽ một lần.

Hình chiếc cầu ở thành phố Kónigsberg và biểu diễn thành đồ thị

ĐỒ THỊ EULER VÀ ĐỒ THỊ HAMILTON

Đồ thị Euler

Định nghĩa 1. Chu trình đơn trong G đi qua mỗi cạnh của nó một lần được gọi là chu trình Euler. Đường đi đơn trong G đi

qua mỗi cạnh của nó một lần được gọi là đường đi Euler. Đồ thị được gọi là đồ thị Euler nếu nó có chu trình Euler và gọi

là đồ thị nữa Euler nếu nó có đường đi Euler.

Định lý 1[Euler]. Đồ thị vô hướng liên thông G là đồ thị Euler khi và chỉ khi mọi đỉnh của .

Hệ quả . Đồ thị vô hướng liên thông và chỉ khi nó không quá 2 đỉnh bậc lẻ.

Định lý 2. Đồ thị có hướng liên thông mạnh là đồ thị Euler khi và chỉ khi

 

procedure Euler_cycle;

begin

STACK= ;

CE=;

chọn u là một đỉnh nào đó của đồ thị;

STACK u;

while STACK do

begin

x= top [STACK];

if Ke[x] then

begin

y=đỉnh đầu tiên trong danh sách Kề[x];

STACK u;

[* Loại bỏ cạnh [x,y] khỏi đồ thị *]

Ke[x] = Ke[x] \ {y};

Ke[y]= Ke[y]\{x};

end else

begin

x STACK;

CE u;

end

end

end

Đồ thị Hamilton

Định nghĩa 2

Đường đi qua tất cả các đỉnh của đồ thị mỗi đỉnh đúng một lần được gọi là đường đi Hamilton. Chu trình bắt đầu từ đỉnh v

nào đó qua tất cả các đỉnh còn lại mỗi đỉnh đúng một lần rồi quay trở về v được gọi là chu trình Halmilton. Đồ thị G được gọi

là đồ thị Halmilton nếu nó chứa chu trình Hamilton, và gọi là nửa Hamilton nếu nó chứa đường đi Hamilton.

Định lý 3[Dirak 1952]

Đơn đồ thị vô hướng với n>2 đỉnh, mỗi đỉnh có bậc không nhỏ hơn n/2 là đồ thị Hamilton.

Định lý 4

Giả sử G là đồ thị có hướng liên thông mạnh với n đỉnh. Nếu

,  

Thì G là Hamilton

Đồ thị Hamilton

Định lý 5 [tổng quát hơn Dirac]

Giả sử đồ thị G gồm mọi cặp đỉnh của nó đều có tổng bậc không bé hơn n. Khi đó G là đồ thị Halmilton.

Định lý 6[Ore, 1960] Giả sử G gồm đỉnh và mọi cặp đỉnh không kề nhau của

là đồ thị Halmilton.

Định lý 7.

Giả sử G là đồ thị Halmilton. Khi đó

a. Mọi đỉnh của nó phải có bậc lớn hơn hoặc bằng 2.

b. Nếu một đỉnh có bậc bằng 2 thì hai cạnh của nó phải nằm trên một chu trình Halmilton

c. Nếu một đỉnh có bậc lớn hơn 2 và có hai cạnh của nó nằm trên một chu trình Hamilton thì các cạnh còn lại của nó

không nằm trên chu trình Hamilton

Thuật toán liệt kê các chu trình Hamilton của đồ thị

procedure Hamilton[k];

[* Liệt kê các chu trình Hamilton thu được bằng việc

Phát triển dãy đỉnh [ X[1],…, X[k-1]]

Của đồ thị  

begin

for y  

if [k=n+1] and [] then Ghinhan[X[1],…,X[n], ]

else

if chuaxet[y] then

begin

X[k]=y;

Chuaxet[y]=false;

Hamilton[k+1];

Chuaxet[y]=true;

end

end

begin

for do chuaxet[v]=true;

X[1]= ;

chuaxet[;

Hamilton[2];

end

CÂY VÀ CÂY KHUNG CỦA ĐỒ THỊ

Định nghĩa 3

Ta gọi cây là đồ thị vô hướng liên thông không có chu trình. Đồ thị không có chu trình được gọi là rừng.

Định lý 8. Giả sử là đồ thị vô hướng đỉnh. Khi đó các mệnh đề sau đây là tương đương:

1.

là cây

2.

không chứa chu trình và có 

3.

liên thông và có 

4.

liên thông và mỗi cạnh của nó là cầu

5. Hai đỉnh bất kì của được nối với nhau bởi đúng một đường đi đơn

6.

không chứa chu trình nhưng hễ cứ thêm vào nó một cạnh ta thu được đúng một chu trình

CÂY VÀ CÂY KHUNG CỦA ĐỒ THỊ

Định nghĩa 4. Giả sử là đồ thị vô hướng liên thông. Cây T=[V, F] với E được gọi là cây khung của đồ thị .

Định nghĩa 5 [Cayley]. Số cây khung của đồ thị 

Thuật toán xây dựng cây khung của đồ thị

procedure cay_khung_DFS[];

// Đồ thị 

begin

chuaxet[v]= false;

for do

if chuaxet[u] then

begin  

Cay_khung_DFS[

end

end

begin   

;

Cay_khung_DFS 

;

end

Thuật toán xây dựng cây khung của đồ thị

procedure cay_khung_BFS[];

// Đồ thị 

begin

Queue=;

Queue 

chuaxet[v]=false;

while Queue do

begin

Queue

for kề [v] do

if chuaxet[u] then

begin

Queue 

chuaxet[u]=false;

 

end

end

end

begin   

;

Cay_khung_BFS 

;

end

BÀI TOÁN CÂY KHUNG NHỎ NHẤT

procedure Kruskal [1956];

begin ;

while  do

begin

Chọn ;

{e};

if không chứa chu trình then ;

end

if  

end

BÀI TOÁN CÂY KHUNG NHỎ NHẤT

Thuật toán Prim [1957]

Thuật toán Kruskal làm việc kém hiệu quả đối với những đồ thị dày [ đồ thị với số cạnh 

] .

Trong trường hợp đó thuật toán Prim tỏ ra hiệu quả hơn. Thuật toán Prim còn được gọi là phương pháp lân cận. Trong

phương pháp này, bắt đầu từ một đỉnh tùy ý của đồ thị 

•, chẳng hạn là đỉnh 

•Tìm cạnh có độ dài nhỏ nhất trong số các cạnh kề với hai đỉnh 

•Quá trình này tiếp tục cho đến khi được cây  C    

    

    

    

     

     

procedure Prim;

 ;

;

for =1 to -2 do

begin

Chọn là cạnh có trọng số nhỏ nhất trong và liên thuộc với ;

if   ;



end

BÀI TOÁN TÌM ĐƯỜNG ĐI NGẮN NHẤT TRÊN ĐỒ THỊ

Bài toán 1.

Cho một đồ thị đơn vô hướng liên thông. Tìm đường đi ngắn nhất theo số cạnh từ đỉnh 

Đồ thị của bài toán này không có trọng số hay trọng số của các cạnh là bằng nhau, và đường đi ngắn nhất giữa hai đỉnh trên

đồ thị được hiểu là số cạnh của đường đi này là bé nhất.

Có thể giải bài toán này bằng thuật toán BFS.

Bài toán 2. [Thuật toán tìm đường đi ngắn nhất trong đồ thị có trọng số cạnh không âm – Thuật toán Dijkstra]

Cho đồ thị đơn vô hướng liên thông có trọng số dương. Tìm đường từ đỉnh đến của sao cho tổng trọng số của

đường đi này là nhỏ nhất.

•Đặc điểm của phương pháp này là cực tiểu hóa nhãn cho các đỉnh

Ký hiệu nhãn của đỉnh   

Ký hiệu là trọng số của cạnh . Giả sử 

BÀI TOÁN TÌM ĐƯỜNG ĐI NGẮN NHẤT TRÊN ĐỒ THỊ

sv









={d[],d[]+a[,]}

• 

•

;

for v 

begin

d[v] = a[s, v];

truoc[v]=s;

end

d[s] = 0; H= V\{s};

while H do

begind[u]=min{d[z]:z};

H=H\{u};

for v 

if d[v] > d[u] + a[u,v] then

begin d[v]=d[u] + a[u,v];

truoc[v]=u;

end

end



BÀI TOÁN TÌM ĐƯỜNG ĐI NGẮN NHẤT TRÊN ĐỒ THỊ

BÀI TOÁN TÌM ĐƯỜNG ĐI NGẮN NHẤT TRÊN ĐỒ THỊ

Thuật toán FLOYD

procedure Floyd;

begin

for i=1 to n do

for j=1 to n do

begin

d[i,j]=a[i,j];

p[i, j]=i;

end

for k=1 to n do

for i=1 to n do

for j= 1 to n do

if d[i, j] > d[i ,k] + d[k, j] then

begin

d[i, j] = d[i, k] + d[k, j];

p[i, j] = p[k, j];

end

end

BÀI TOÁN LUỒNG CỰC ĐẠI

Đồ thị tăng luồng

Đồ thị trạng thái của luồng

Luồng cực đại, đỉnh phát và đỉnh thu

    

   

   

Algorithm



1: Xây dựng đồ thị tăng luồng

2: Chọn đường tăng luồng với giá trị 

3: Tiến hành tăng luồng trên đường đã xét.

Until mạng đạt trạng thái cực đại của luồng;

ưng ý







Bài toán lập lịch cho hội nghị

Một hội nghị có tiểu ban và phòng họp, mỗi tiểu ban cần sinh hoạt trong một ngày tại phòng họp phù hợp với tiểu

ban đó. Cho biết = 1 [hoặc 0] cho biết tiểu ban

 . Hãy bố trí các phòng họp sao cho hội

nghị kết thúc sớm nhất.

ĐẠI SỐ BOOLE VÀ ỨNG DỤNG

Định nghĩa đại số Boole

Định nghĩa 1. Cho tập cộng ‘.’ nhân và một phép

toán một ngôi ‘ ’ [bù] thỏa mãn các tính chất sau:

1. Tính kết hợp: , b, c  

   

2. Tính giao hoán: , b  

 a.b=b.a

3. Tính phân phối:  

   

4. Phần tử trung hòa   

  

5. Phần tử bù:   {0,1} sao cho

 =0

Bộ sáu[B, +,., ‘ ’,0, 1] thỏa 5 tính chất trên gọi là một đại số Boole. Thay vì viết a.b, người ta viết ab.

ĐẠI SỐ BOOLE VÀ ỨNG DỤNG

a. Xét tập B gồm các mệnh đề toán học có giá trị false, true với các phép toán logic or, and, not. Khi đó bộ sáu [{true,

false}, or, and, not, false, true] là một đại số boole.

b. Giả sử ‘ là phép lấy bù của một tập hợp con của . Ta có 

‘,

c. Bộ sáu {B={0,1}, +, ., ‘, 0, 1 }, trong đó phép + được hiểu theo phép + [mod 2] trong số học, phép ‘.’’ là phép nhân

thông thường trong số học, phép bù ‘ thỏa mãn Là một đại số boole.

Các tính chất cơbản

Từ định nghĩa trên có thể chứng minh các tính chất sau đây của một đại số Boole B={0,1},  

1. Luật đồng sức: 



2. Luật nuốt:  

3. Luật bù kép: 

4. Luật De Morgan: ==

Biểu thức Boole và hàm Boole

Với tập hợp  

hợp thành bởi các biến boole với các phép toán cộng, nhân và bù, các dấu ngoặc [,].

Một cách đệ quy:

Nếu , thì 



là biểu thức boole.

Định nghĩa 2

Ký hiệu là tập các phần tử  , . Một hàm boole n biến là một ánh xạ 

Hàm boole nhận một trong hai giá trị 0 hoặc 1 ứng với mỗi bộ biến . Vì   .

Nên số hàm boole của n biến là Với n=3, số hàm Boole 3 biến khác nhau là 256.

Ví dụ hàm boole ba biến  

Một môn thi trắc nghiệm gồm 4 câu hỏi với số điểm lần lượt 2, 3, 5, 4. Nếu trả lời đúng mỗi câu sinh viên sẽ được điểm tối đa, trả lời sai

chỉ được không điểm. Sinh viên thi đạt kết quả từ 10 điểm trở lên. Xác định hàm boole cho biết sinh viên thi đạt [=1] hay không đạt [=0].

Từ bảng chân trị này ta xác định biểu thức của 

  +zt + + 

CÁC DẠNG KHÁC NHAU CỦA MỘT HÀM BOOLE

1. Tích cơbản

Để tiện cho việc trình bày, ta đưa vào quy tắc sau đây: giả sử biến   

 



Giả sử cho n biến 





với {0, 1}

,…, nếu  

Định lý 1

Mọi tích có thể đưa về 0 hoặc về một tích căn bản

Xét trên gồm các biến x, y, z, t. Ta có tích cơ bản của 3 biến: , yzt và các tích cơ bản của 3 biến: y,  

Cho nếu mọi biến và bù của biến đều có mặt trong .

Từ định nghĩa trên dễ dàng chứng minh được rằng, nếu chứa trong thì

[luật nuốt]

Chẳng hạn, với =x là tích cơ bản của hai biến x, z và =xchứa trong

và =x 

Dạng tổng chuẩn tắc của hàm Boolean

Một hàm Boolean



tích nào khác.

+xyz+ 

 

Mọi hàm Boole [khác 0] đều có thể đưa về dạng tổng chuẩn tắc:

1. Dùng luật De Morgan và bù kép đưa biểu thức về dạng trong đó phép bù chỉ áp dụng trên các biến.

2. Luật phân phối đưa biểu thức về dạng tổng của các tích.

3. Dùng luật giao hoán, luật đồng sức và luật bù để đưa mỗi tích trong biểu thức về 0 hoặc là tích cơbản.

4. Dùng luật nuốt để đưa về dạng tổng chuẩn tắc.

Ví dụ. Biểu diễn tổng chuẩn tắc của hàm Boole   

Giải

  

=[xy + ][+yz] [Luật De Morgan]

= +0 [luật phân phối + luật bù]

= 

DẠNG TỔNG CHUẨN TẮC CỦA HÀM BOOLE

Định nghĩa 3. Một hàm boole



có đủ .

Ví dụ

Hàm  + + là dạng tổng chuẩn tắc hoàn toàn.

Hàm  

Định lý 2. Một hàm boole ,…, ] khác 0 đều có một dạng tổng chuẩn tắc hoàn toàn và duy nhất

Thuật toán

1. Biến đổi về dạng tổng chuẩn tắc.

2. Nhân tích cơbản nào vắng mặt biến với [+

3. Lặp lại bước 2 cho đến khi trong ,,…, 

Ví dụ Biểu diễn hàm boole sau đây ở dạng tổng chuẩn tắc hoàn toàn

  +

Ta có biểu thức đã cho ở dạng tổng chuẩn tắc, tiếp tục với bước 2 và 3

       ++ +

Dạng thu gọn và dạng tối thiểu của hàm Boole

Consensus của hai tích cơbản

Định nghĩa 4. Cho   có chứa hoặc . Ta gọi consensus 

của , là tích của , và và xóa các biến theo luật đồng sức 

Ví dụ: với =, ta có . ,  , ta có .

Định lý 3. Nếu . Thì + + 

Chứng minh. Do có consensus nên giả sử ==với  

Xét hai trường hợp: Nếu 

= + = A+ = + 

Nếu = , thì 

+B= = 

Với =xyzt,  

+Q= 

Nguyên nhân nguyên tố của hàm boole.

Tích cơbản [implicant] của hàm : 

  +

Thật vây, viết , 

=x  [ 

   

+xy +

Dễ thấy :+ 

Định nghĩa 5

Giả sử 

nguyen nhân nguyên tố của f.

Dễ dàng kiểm tra  là nguyên nhân nguyen tố 

+ 

Dạng thu gọn và tối thiểu của hàm Boole

Định nghĩa 6. Ta gọi độ phức tạp của một dạng tổng chuẩn tắc là số lần các biến xuất hiện trong nó.

Chẳng hạn, 

Định nghĩa 7. Dạng tổng chuẩn tắc của hàm 

Hàm  có dạng tương đương



Định nghĩa 8.

Hàm Boole

Hàm +  

Định nghĩa 9.

Một dạng tổng chuẩn tắc của hàm hạng của nó là các nguyen nhân nguyên tố cốt yếu của

.

Lập bảng cho dạng thu gọn của   này, mọi nguyên nhân nguyên tố của



Tối thiểu hóa hàm Boole

1. Phương pháp biến đổi đại số

Đưa 

.

Xuất phát từ dạng thu gọn của , chọn các nguyên nhân nguyên tố cốt yếu, ta được dạng tối thiểu cần tìm.

Tối thiểu hóa hàm boole     

Giải

Bước 1:   ++ [ luật nuốt của số hạng thứ 2 và thứ 5]

=   +z [nhóm số hạng thứ 1 và thứ 3]

=   z + xy [Cộng them Q= 

=  +   [luật nuốt của số hạng thứ 2 và thứ 4]

   

Đến đây ta thu được dạng tối thiểu của    

Tuy nhiên nếu cộng thêm 

   

Bước 2: Trong hai biểu thức ở trên của , có thể xóa số hạng       

   + 

 + 

Phương pháp Karnaugh

Trường hợp hai biến 

Mỗi tích cơbản ,   



Xác định tối thiểu của hàm sau đây

      +

 

Trường hợp 3 biến 

Tìm dạng tối thiểu của hàm

   

 + 