Phân tích và tổng hợp các thiết bị logic. Các phương pháp giảm thiểu các hàm và mạch logic. Các phương pháp giảm thiểu hàm đại số logic

cho lần đầu tiên – X 3 X 4;

đối với giây – X 1 X 3;

đối với phần thứ ba – X 2 X 3;

đối với thứ tư – X 1 X 2 X 4;

đối với thứ năm – X 1 X 2 X 4;

Một DNF tối thiểu sẽ trông như thế này:

So sánh phương pháp bản đồ Karnaugh với các phương pháp giảm thiểu hàm khác, chúng ta có thể kết luận rằng phương pháp đầu tiên là phù hợp nhất để thực hiện thủ công. Thời gian tự lập giảm đáng kể (do đại diện trực quan chất dính dính). Triển khai phần mềm Phương pháp này có những khó khăn riêng của nó. Vì vậy sẽ rất khó thực hiện sự lựa chọn tối ưu hình chữ nhật thông thường, đặc biệt đối với một số lượng lớn các đối số.

1.3.5 Phương pháp hệ số bất định

Phương pháp này có thể được sử dụng cho bất kỳ số lượng đối số. Nhưng vì phương pháp này khá cồng kềnh nên nó chỉ được sử dụng trong trường hợp số lượng đối số không quá 5-6.

Phương pháp hệ số không xác định sử dụng các định luật về tập hợp phổ quát và tập rỗng và các định luật lặp lại. Lúc đầu, tất cả các hệ số đều không chắc chắn (do đó có tên của phương pháp).

Hãy xây dựng một ma trận các hệ số không chắc chắn cho bốn đối số. Trong trường hợp này, chúng ta sẽ có hệ thống gồm 16 phương trình.

Hệ thống được hiển thị trên trang tiếp theo.

Chúng ta hãy đánh đồng tất cả các hệ số bằng 0 trong các hàng tương ứng với 0 trong cột vectơ. Sau đó, chúng ta đánh đồng các hệ số tương ứng ở các hàng khác bằng 0. Sau những biến đổi này, hệ thống sẽ có dạng sau:

V = 1 VVVVVV = 1 VVV V VV = 1 V = 1 VVV = 1 VVVVVV = 1 VVV = 1 VVVVV = 1 VVV = 1

Bây giờ ở mỗi dòng, bạn cần chọn hệ số của thứ hạng tối thiểu và đánh đồng nó bằng 1, các hệ số còn lại bằng 0. Sau đó, gạch bỏ dòng giống hệt nhau, trong khi để lại một trong số chúng (những dòng có tất cả các hệ số bằng 0 cũng bị gạch bỏ).

= 1 = 1 = 1 = 1 = 1

Bây giờ chúng ta hãy viết ra các liên từ tương ứng với các hệ số bằng đơn vị. Chúng tôi sẽ nhận được DNF tối thiểu.

F(X 1 X 2 X 3 X 4) = X 1 X 3 V X 2 X 3 V X 3 X 4 V X 1 X 2 X 4 V X 1 X 2 X 4 .

Vì vậy, chúng tôi đã đạt được DNF tối thiểu theo nhiều cách, trong mọi trường hợp đều giống nhau, tức là bất kỳ phương pháp nào được mô tả đều có thể được sử dụng để giảm thiểu hàm. Tuy nhiên, các phương pháp này khác nhau đáng kể cả về nguyên tắc tìm MDNF và thời gian thực hiện. Phương pháp bản đồ Karnaugh rất thuận tiện cho việc tính toán thủ công. Nó là trực quan và không yêu cầu hoạt động thường lệ và việc chọn vị trí tối ưu của các hình chữ nhật chính xác không khó. Trong khi việc thực hiện phương pháp này bằng máy rất phức tạp do cần phải tìm cách sắp xếp tối ưu các hình chữ nhật. Đương nhiên, việc sử dụng các phương pháp khác (phương pháp Quine, phương pháp Quine-McCluskey, phương pháp hệ số không xác định) để tính toán thủ công là không phù hợp. Chúng phù hợp hơn cho việc triển khai máy vì chúng chứa một số lượng lớn các thao tác đơn giản lặp đi lặp lại.

Nhiệm vụ 2.

2.1 Sơ đồ thuật toán của phương pháp Quine

1. Bắt đầu.

2. Nhập ma trận DSNF của hàm ban đầu.

3. Kiểm tra các dòng thứ i (i=1,m-1: trong đó m là số dòng trong DSNF) và dòng thứ j (j=i+1, m) để dán. Nếu các dòng bị dính vào nhau thì chuyển sang bước 6, nếu không thì chuyển sang bước 5.

4. Tạo thành một mảng các hàm ý đơn giản, trước đó đã đánh dấu bằng ký hiệu '*' biến mà các chuỗi này được dán lại với nhau.

5. Chuyển sang bước 2.

6. Viết một dòng không gộp với bất kỳ dòng nào khác vào mảng cuối cùng.

7. Chuyển sang bước 2.

8. Đầu ra của ma trận kết quả.

Sơ đồ logic của thuật toán theo ký hiệu Lyapunov

V H V 1 Z 1 V. 2 ¯ V. 3 V. 4 V K

VH - bắt đầu.

V 1 – nhập ma trận DSNF của hàm ban đầu.

V 2 – tạo thành một mảng các hàm ý đơn giản, trước đó đã đánh dấu bằng ký hiệu '*' biến mà các chuỗi này được dán lại với nhau.

V 3 – một chuỗi không được hợp nhất với bất kỳ chuỗi nào khác được ghi vào mảng cuối cùng.

V 4 – đầu ra của ma trận kết quả.

Z 1 – nếu các đường được dán lại với nhau thì chuyển sang bước 3, nếu không thì chuyển sang bước 5.

V K – kết thúc.

Sơ đồ đồ thị của thuật toán.

Sự miêu tả máy móc thủ tục

Thủ tục bị kẹt(S1, S2: Diz; IndexS1, IndexS2: byte);

Thủ tục này gắn kết hai phần tách rời được truyền cho nó lại với nhau. Các khoản được quy định tại tham số S1, S2. Chỉ mục IndexS1, IndexS2 xác định chỉ mục của các mệnh đề này trong mảng làm việc chính. Thuật toán của quy trình như sau: đầu tiên, số lượng ký tự được dán lại với nhau sẽ được tìm kiếm. Nếu có 0 trong số chúng thì chúng giống nhau và chỉ một trong số chúng được ghi vào mảng cuối cùng. Nếu 1 thì vị trí của ký hiệu được xác định bằng cách gắn hai phần tách biệt này lại với nhau và chúng ta thay thế ký hiệu này bằng '*'. Tất cả các kết quả thu được được nhập vào mảng REZ.

Tất cả các chức năng và thủ tục khác của chương trình đều liên quan đến các hành động trên mảng, nghĩa là chúng không liên quan trực tiếp đến phương pháp tìm MDNF này. Vì vậy không có ích gì khi mô tả chúng.

2.2 Sơ đồ thuật toán của phương pháp Petrik

1. Bắt đầu.

2. Nhập ma trận DSNF của hàm ban đầu và các hàm ẩn đơn giản thu được theo phương pháp Quine.

3. Tạo bảng nhãn.

4. Sử dụng bảng nhãn, xây dựng một liên kết của các phép tách, mỗi phép tách là một tập hợp các hàm ý nằm trong cột này có dấu vết.

Thao tác được sử dụng phổ biến nhất khi thu nhỏ các hàm là thao tác dán.

AB+ ВB=B (A+ В)=B.

Chúng ta hãy xem xét ba phương pháp giảm thiểu phổ biến nhất.

1. Cho số tập hợp bốn biến, trên đó hàm logic lấy giá trị đơn vị: f (2,5,6,7,10,12,13,14)=1.

Hãy biểu diễn hàm logic này trong SDNF (chúng ta sẽ không viết ký hiệu kết hợp):

f(0010,0101, 0110, 0111, 1010, 1100, 1101, 1110) =

Ở giai đoạn giảm thiểu đầu tiên, SDNF ban đầu có thể được đơn giản hóa bằng cách sử dụng định luật dán, sau đó chúng ta thu được:

Chúng ta chú ý đến thực tế là cùng một thành phần (hàm ý) có thể được gắn kết với các thành phần khác (ẩn ý) nhiều lần, vì trong logic của Boole, luật bình thường được áp dụng:

do đó, bất kỳ thành phần nào cũng có thể được nhân lên.

Ở giai đoạn thứ hai, chúng ta sẽ sử dụng bảng Quine (Bảng 8), theo đó phương pháp này giảm thiểu có tên của nó - phương pháp Quine. Bảng liệt kê tất cả các hàm ý thu được ở giai đoạn đơn giản hóa đầu tiên theo chiều dọc và các thành phần ban đầu theo chiều ngang. Đơn vị trong bảng 8 là nơi hàm ý “bao phủ” thành phần. Thực tế là thành phần luôn có thể được thay thế bằng một thuật ngữ tiềm ẩn hoặc thậm chí là một thuật ngữ riêng biệt theo quy luật hấp thụ:

Bảng 8

Sau khi điền vào bảng Quine, chúng tôi thu được hai đơn vị ở hầu hết các cột; Trong khi đó, chỉ cần có một đơn vị trong biểu đồ là đủ. Vì vậy, bất cứ khi nào có thể, nên loại bỏ các đơn vị dư thừa. Việc lựa chọn các đơn vị được thực hiện dựa trên số lượng số hạng tối thiểu (các đơn vị được chọn sẽ được tô màu). Kết quả là, hóa ra chúng ta có thể vượt qua chỉ với ba yếu tố liên quan thay vì sáu:

Sử dụng bảng chân trị, có thể dễ dàng xác minh rằng hàm thu được trong MNF tái tạo tất cả các giá trị của hàm gốc. Lưu ý rằng trong trường hợp chung Có thể có một số giải pháp dựa trên tiêu chí về điều khoản tối thiểu.

2. Không ít hơn cách hiệu quả Giảm thiểu các hàm logic là một phương pháp kết hợp các chỉ số. Để trình bày nó, hãy lập một bảng. 9, trong các cột ghi các tổ hợp chỉ số có thể có. Cột cuối cùng chứa các giá trị hàm. Việc phân tích bảng bắt đầu từ bên trái dọc theo các cột. Nguyên tắc loại trừ i, j_code như sau. Ví dụ, tại giao điểm của i_column với sự kết hợp của các chỉ số 23 và j_row, ví dụ 3_th, có mã 10, tương ứng với hàm ý. Do đó, trong cột này, bất cứ nơi nào mã 10 xuất hiện, tức là ở dòng 2, 3, 10 và 11, các mã này đều bị loại trừ vì giá trị của hàm ở dòng thứ 3 bằng 0. Bây giờ, hãy lấy một cột có sự kết hợp của các chỉ mục 124. Ở đây, mã 010 được để lại ở dòng thứ 2 và thứ 6, và mã 011 ở dòng thứ 10 và 14. Điều này được thực hiện vì các mã này chỉ được tìm thấy trên các dòng có giá trị hàm bằng một. Ngược lại, mã 110 của cùng một cột xảy ra với cả giá trị hàm đơn và giá trị 0.

Bảng 9

Vì vậy, tất cả các mã trên các dòng kết thúc bằng giá trị hàm null sẽ tự động bị loại trừ. Nếu các mã này nằm trên các dòng kết thúc bằng một giá trị hàm duy nhất thì chúng cũng không được tính đến. Chỉ những mã nằm trên các dòng có một giá trị hàm duy nhất còn lại (các mã này được làm tối).

Sau đó làm theo quy tắc sau. Để hàm nhận một giá trị, bằng một, chỉ cần một người hàm ý trên đường nhận giá trị đơn vị là đủ. Trước hết, chúng tôi để lại hàm ý tối thiểu, chồng lên các hàm ở dòng 2, 6, 10 và 14. Sau đó, tất nhiên, chúng tôi chuyển sang dòng thứ 12. Ở đây chúng tôi để lại mã duy nhất trên dòng, 011, tương ứng với người liên quan. Người liên quan tương tự chịu trách nhiệm về dòng thứ 13, dòng này cũng kết thúc bằng một đơn vị. Vẫn còn phải xem xét dòng thứ 5 và thứ 7. Điểm chung của chúng là hàm ý: . Do đó, với ba hàm ý, chúng tôi đã bao quát tất cả các giá trị đơn lẻ của hàm, trùng khớp với kết quả thu được trên cơ sở bảng Quine.

3. Tồn tại phương pháp đồ họa dán, được gọi là phương pháp bản đồ Karnaugh (được trình bày trong Bảng 10). Chúng tôi chọn các đơn vị liền kề, đây sẽ là các điều khoản về chức năng của chúng tôi.

Bảng 10

Chúng tôi có hai điều khoản

Mặc dù bảng 9 thì cồng kềnh hơn bàn. 8, phương pháp kết hợp các chỉ mục không được coi là phức tạp hơn phương pháp của Quine, nếu chúng ta nhớ rằng trước khi biên soạn các bảng của Quine, cần phải thực hiện nhiều phép nối các thành phần và hàm ý. Việc thực hiện thuật toán phương pháp kết hợp chỉ số trên máy tính tỏ ra tương đối đơn giản. Và ngược lại, sự đơn giản và rõ ràng bên ngoài của phương pháp thứ ba nhằm giảm thiểu hàm logic bằng bản đồ Karnaugh hóa ra lại là chương trình phức tạp khi thực hiện thuật toán trên máy tính.

Bảng 11

Bảng 12

Bản đồ Karnaugh cho bốn biến được trình bày dưới dạng bảng. 11. Mỗi ô của bản đồ tương ứng với một thành phần. Bản đồ hoàn chỉnh được trình bày trong Bảng. 12 (chức năng giống như trong hai phương pháp đầu tiên). Theo định luật dán, hai thành phần liền kề có giá trị đơn vị luôn có thể được kết hợp để thu được vật liệu tiềm ẩn tương ứng. Hơn nữa, những nơi nằm ở ranh giới của bản đồ cũng được coi là liền kề. Những đơn vị nào cần được kết hợp để có được vật liệu cấy ghép phù hợp có thể được xác định dễ dàng bằng trực quan. Cũng nên nhớ rằng theo quy luật bình thường, cùng một đơn vị của bảng. 12 có thể được dán vào hai hoặc ba đơn vị liền kề.

Tất cả các hàm logic được chỉ định dưới dạng công thức hoặc dưới dạng bảng giá trị. Đôi khi cần phải xác định hình thức đơn giản nhất ghi lại hàm này với số lượng tối thiểu các hàm logic cơ bản AND, OR, NOT để dễ sử dụng. Đối với điều này, tất cả các hoạt động được xem xét bắt đầu từ số 4 và các phương pháp Quine và Veitch đều được sử dụng.

Phương pháp Quine cho phép chúng ta tìm được chuẩn tắc đơn giản nhất hình thức phân biệt biểu thức logic, tức là viết ra biểu thức logicở dạng phân tách hoặc kết hợp, trong khi dấu đảo ngược chỉ có thể xuất hiện trên một đối số hoặc hoàn toàn không xuất hiện. Thuật toán được đưa ra trong tài liệu chuyên ngành.

Phương pháp Veitch (bản đồ Karnaugh)

Trong phương pháp này, để mô tả một hàm gồm n biến, một bảng đặc biệt được vẽ chứa 2n ô. Mỗi ô tương ứng với một trong các bộ n biến. Ô ghi lại giá trị được hàm chấp nhận cho tập hợp đối số này. Tất cả các ô tương ứng với các tập hợp chứa một số biến không có dấu đảo ngược tạo thành diện tích 2 n -1 ô. Khu vực này được gọi là diện tích của một biến nhất định(ví dụ: phạm vi của biến x). Các ô còn lại tạo thành vùng của biến nghịch đảo này. Các tập hợp đối số có thể được phân bổ giữa các ô theo cách sao cho ranh giới của các vùng của tất cả các biến và sự đảo ngược của chúng rõ ràng và việc thuộc về bất kỳ ô nào đối với một khu vực cụ thể đều được xác định dễ dàng bằng trực quan.

1) Hàm một biến:

2) Hàm hai biến:

3) Sơ đồ phân ly:

4) Sơ đồ kết hợp:

5) Đối với ba đối số:

6) Đối với bốn đối số:

Bạn có thể giảm thiểu một biểu thức Boolean nhất định bằng cách nhóm đứng gần đóđơn vị, đồng thời loại trừ biến chuyển từ trạng thái trực tiếp sang trạng thái nghịch đảo. Bạn có thể kết hợp không chỉ theo chiều dọc và chiều ngang mà còn có thể dọc theo các cạnh, vì trong trường hợp chung, bản đồ Karnaugh tạo thành một hình xuyến. Ví dụ:

Đại số logic

3.3.1. Giảm thiểu FAL bằng ma trận Carnot

Ma trận Carnot là một loại bảng chân lý FAL, được chia thành các ô. Số lượng ô ma trận là 2 N, Ở đâu N– số đối số FAL. Các cột và hàng của ma trận được chỉ định bởi các tập đối số. Mỗi ô của ma trận tương ứng với một thành phần của đơn vị FAL (số nhị phân). Số nhị phân của ô bao gồm một tập hợp các đối số hàng và cột. Ma trận Carnot cho FAL, tùy thuộc vào hai đối số, được trình bày dưới dạng bảng 3.3., từ ba đối số trong bảng 3.4. và từ bốn đối số bảng 3.5.

Bảng 3.3.

Bảng 3.5.

X 3 X 4 X 1 X 2
	0 0 0 0	0 0 0 1	0 0 1 1	0 0 1 0
	0 1 0 0	0 1 0 1	0 1 1 1	0 1 1 0
	1 1 0 0	1 1 0 1	1 1 1 1	1 1 1 0
	1 0 0 0	1 0 0 1	1 0 1 1	1 0 1 0

Các ô của ma trận (Bảng 3.3., 3.4. và 3.5.) được đánh số bằng số thập phân tương đương với số nhị phân của các ô. Các ô ma trận liền kề, theo cả chiều ngang và chiều dọc, chứa các số nhị phân liền kề. Ngoài ra, các số nhị phân liền kề được tìm thấy trong tất cả các cột của hàng trên cùng và dưới cùng, cũng như trong tất cả các hàng của cột ngoài cùng.

Quá trình giảm thiểu FAL bằng ma trận Carnot dựa trên định luật dán các số nhị phân liền kề. Bạn có thể dán các số nhị phân của các ô liền kề lại với nhau, nhưng nên dán các bộ đối số biểu thị các hàng và cột của ma trận lại với nhau. Hãy xem xét việc dán các số nhị phân của các ô của cột đầu tiên của ma trận (Bảng 3.5.).

Ô 0 và 4, số nhị phân lần lượt là 0000 và 0100, kết quả dán là 0-00.

Ô 8 và 12, số nhị phân 1000 và 1100, kết quả là 1-00. Các vật liệu tiềm ẩn được tạo thành được dán lại với nhau, bởi vì Dấu gạch ngang ở cùng một vị trí và các số nhị phân liên quan liền kề nhau, kết quả cuối cùng là - 00.

Ô 8 và 12

Do đó, nếu tất cả các số nhị phân của một cột được dán lại với nhau thì những bit chỉ ra các hàng đó sẽ biến mất. Tương tự, nếu tất cả các số nhị phân của một hàng được dán lại với nhau, ví dụ 4, 5, 7, 6, thì tất cả các chữ số biểu thị các cột sẽ biến mất, tức là. kết quả sẽ như sau 01- -.

Nếu các số nhị phân của chỉ hai ô bất kỳ được dán lại với nhau thì một dấu gạch ngang được đặt thay cho chữ số đó của số nhị phân của một hàng hoặc cột sẽ thay đổi khi các ô di chuyển từ dòng này sang dòng khác (hoặc từ cột này sang cột khác) . Ví dụ số ô 5 và 13 ghép lại với nhau ta được kết quả -101, hoặc ô 7 và 6 kết quả là 011-.

Khi dán số nhị phân của 8 ô liền kề thì 3 biến biến mất, ví dụ đối với các ô 3, 7, 15, 11, 2, 6, 14, 10 thì biến biến mất X 1 , X 2 , X 3. Biến X 1 , X 2 biến mất vì tất cả các ô của cột được dán lại với nhau và X 3 vì hai cột cuối cùng được dán lại với nhau.

Trước khi xem xét các ví dụ về giảm thiểu FAL bằng ma trận Carnot, cần phân loại các tập hợp đối số để xác định các hàm đại số logic.

Được biết, với mỗi FAL có 2 bộ đối số N, Ở đâu N– số đối số mà hàm hoặc biểu thức logic phụ thuộc vào.

Bộ đối số được chia thành ba loại

1. Các tập hợp đối số mà hàm bằng một được gọi là làm việc.

2. Các tập hợp đối số mà hàm bằng 0 được gọi là tập hợp bị cấm.

3. Các tập hợp đối số mà hàm có thể bằng 1 hoặc 0 được gọi là không quan tâm.

Nếu một FAL nhất định không có các tập trung tính thì nó có thể được biểu diễn dưới dạng biểu thức nghĩa đen dưới dạng SDNF. Nếu có các tập trung lập trong một FAL nhất định, biểu diễn của nó có thể có dạng sau.

số thập phân tương đương ở đâu bộ công việc,

– số thập phân tương đương của các bộ bị cấm.

Những lập luận không nằm trong số những lập luận có tác dụng và bị cấm sẽ trở nên thờ ơ.

Ví dụ 3.3. Giảm thiểu FAL đã cho dưới dạng SDNF bằng ma trận Carnot.

Do đó, hàm này chỉ được xác định bởi các tập hợp làm việc. Phần còn lại sẽ bị cấm. Hàm này chỉ phụ thuộc vào ba đối số. Chúng tôi xây dựng ma trận Carnot và đặt các ma trận vào các ô tương ứng với tập hợp làm việc và đặt các số 0 vào các ô còn lại.

Bảng 3.5.

X 2 X 3 X 1
	0

Để giảm thiểu, các ô ma trận chứa các ô đó được kết hợp thành các đường viền. Mạch có thể bao gồm hai ô, bốn hoặc tất cả tám ô. TRONG trong ví dụ nàyđường viền bao gồm bốn ô liền kề của cùng một hàng. Hàm ý của đường viền đã cho sẽ là 1 - -. Kết quả của việc giảm thiểu như sau, tức là đã có sự giảm bớt hàm đã cho trong SDNF với 11 chữ cái.

Ví dụ 3.4. Giảm thiểu biểu thức Boolean được đưa ra bởi các tập hợp làm việc và tập hợp bị cấm bằng cách sử dụng ma trận Carnot.

Chúng tôi xây dựng ma trận Carnot cho bốn biến và điền vào các ô bằng số 1 và số 0 tương ứng cho các tập hợp làm việc và tập hợp bị cấm.

Bảng 3.6.

X 3 X 4 X 1 X 2	00
		(1)

	(1)	(1)

Khi kết hợp các ô với các đơn vị thành các đường viền, điều mong muốn là mỗi đường viền bao gồm số lớn nhất tế bào từ mức tối đa có thể. Để làm điều này, chúng ta sử dụng các ô của một số tập hợp trung lập làm ô của các tập hợp làm việc, thay thế các ô trong ngoặc đơn vào chúng. Kết quả là chúng ta có được ba đường viền, mỗi đường chứa 4 ô. Trong mã mạch tổng quát, bao gồm tất cả các ô của một dòng, các biến sẽ biến mất X 2 X 3 (10 - -). Trong mã mạch tổng quát, bao gồm tất cả các ô của một cột, các biến sẽ biến mất X 1 X 2 (- - 11) và đối với đường viền chứa hai ô của hai dòng, các biến sẽ biến mất X 2 (khi di chuyển từ đường này sang đường khác trong đường viền) và X 3 (khi di chuyển từ cột này sang cột khác). Kết quả là chúng tôi thu được DNF tối thiểu trong mẫu sau

Tùy chọn có thể sự kết hợp các ô ma trận Carnot thành các đường viền được thể hiện trên Hình 3.4.

X 3 X 4 X 1 X 2

A = 0 - 0 -

Z = - 0 - 0

B = 1 - 1 -

K = - - - 1

B = - - 0 0

L = - 1 - -

Г = 1 0 - -

M = - - - 0

D = - 0 0 1

H = - 0 - -

E = - 0 1 -

F = - 1 - 1

Cơm. 3.1. Các tùy chọn khả thi để kết hợp các ô ma trận Carnot thành các đường viền

3.3.2. Giảm thiểu các hàm đại số logic bằng ma trận năm biến

Ma trận tối thiểu hóa cho năm biến được xây dựng tương tự như ma trận Carnot, tức là trong ma trận này, các cột và hàng liền kề phải được chỉ định liền kề số nhị phân bộ biến

Trong ma trận 5 biến (Bảng 3.7.), các hàng tương ứng với các tập biến X 1 X 2 X 3, và các cột là tập hợp các biến X 4 X 5 . Mỗi ô của ma trận tương ứng với một số nhị phân 5 bit. Các ô của ma trận (Bảng 3.7.) chứa số thập phân tương đương của các số nhị phân tương ứng.

Bảng 3.7.

X 4 X 5 X 1 X 2 X 3

Giảm thiểu FAL bằng cách sử dụng ma trận năm biến bao gồm việc kết hợp các ô với bộ làm việc (bao gồm, nếu cần, các ô có bộ không phân biệt) thành các đường viền và lấy mã tổng quát tương ứng với các đường viền này.

Điều đặc biệt ở đây là trong các cột của ma trận năm biến, bạn chỉ có thể kết hợp bốn ô thành đường viền hoặc bốn ô ở trên cùng hoặc bốn ô ở dưới cùng hoặc bốn ô ở giữa. Ví dụ: đối với cột cuối cùng của ma trận, các đường viền có thể bao gồm các ô 2, 6, 14, 10 hoặc 26, 30, 22, 18 hoặc 14, 10, 26, 30.

Ví dụ 3.6. Sử dụng ma trận năm biến để giảm thiểu biểu thức logic sau

Chúng tôi xây dựng một ma trận gồm năm biến và điền vào các ô của tập làm việc bằng các biến và các ô của tập hợp bị cấm bằng số 0.

Chúng tôi kết hợp các ô với các tập hợp làm việc thành các đường viền, bao gồm các ô cần thiết của các tập hợp không quan tâm. Đối với mỗi mạch, chúng tôi xác định một mã tổng quát.

Bảng 3.8.

X 4 X 5 X 1 X 2 X 3
	(1)	(1)	(1)
	(1)
	(1)	(1)
		(1)	(1)
	(1)		(1)
			(1)
	(1)		(1)

Chúng tôi nhận được DNF tối thiểu

Câu hỏi kiểm soát

1. Xác định DNF viết tắt.

2. DNF ngõ cụt là gì?

3. DNF tối thiểu được chọn từ DNF cụt như thế nào?

4. Bảng hàm ý dùng để làm gì và nó được xây dựng như thế nào?

5. Giải thích phương pháp phân tích để giảm thiểu FAL Quine-McClassky.

6. Ma trận Carnot được xây dựng cho ba và bốn biến như thế nào?

7. Giảm thiểu một cách phân tích các biểu thức logic sau chỉ được đưa ra bởi các tập hợp làm việc

8. Sử dụng ma trận Carnaugh, tối thiểu hóa các biểu thức logic được chỉ định bởi tập hợp làm việc và tập hợp bị cấm

Thông tin liên quan.

Khi thiết kế máy tự động kỹ thuật số, các phương pháp giảm thiểu hàm Boolean được sử dụng rộng rãi để thu được các mạch hiệu quả về mặt chi phí. Nhiệm vụ chung Việc giảm thiểu các hàm Boolean có thể được xây dựng như sau: tìm một biểu thức phân tích cho một hàm Boolean nhất định ở dạng chứa số lượng chữ cái tối thiểu có thể có.

Các phương pháp giảm thiểu dựa trên thao tác dán (thuật toán kết hợp các số nhị phân liền kề):

trong đó A là một liên kết sơ cấp.

Trong biểu thức, các số hạng là các số nhị phân liền kề, chỉ khác nhau một chữ số. Khi thực hiện thao tác dán trên hai số liền kề, một biến sẽ bị loại khỏi tập hợp, giúp phân biệt số này với số khác, trên bốn số liền kề theo cặp - hai biến, trên tám - ba biến, v.v.

Dạng chuẩn phân biệt tối thiểu (MDNF) của hàm Boolean là DNF chứa số lượng chữ cái nhỏ nhất (so với tất cả các DNF khác biểu thị một hàm Boolean nhất định).

Bạn có thể thu nhỏ hàm, tức là tìm biểu thức đơn giản nhất cho hàm gốc Các phương pháp khác nhau. Tất cả chúng thực tế chỉ khác nhau ở giai đoạn đầu tiên - giai đoạn có được DNF viết tắt. Cần lưu ý rằng, thật không may, việc tìm kiếm MDNF luôn gắn liền với một số tìm kiếm giải pháp. Chúng ta hãy nhìn vào một số trong số họ.

Giảm thiểu các biểu thức Boolean phức tạp bằng ma trận Carnot

Để thực hiện thuật toán hợp nhất, cần phải tìm các thuật toán lân cận từ toàn bộ tập hợp các thành phần bắt buộc ở dạng chuẩn phân biệt hoàn hảo của hàm đại số logic. Để tìm các thành phần lân cận, ma trận Carnot, một mạng các số lân cận và bảng các thành phần lân cận được sử dụng.

Nên sử dụng ma trận Carnot để giảm thiểu FAL trên các bộ 2,3,4,5 và 6 biến. Số cột trong ma trận Carnot tạo thành các chữ số có ý nghĩa nhỏ nhất và số hàng tạo thành các chữ số có ý nghĩa nhất trong tập hợp. Số ô được tạo thành từ số hàng và số cột và tương ứng với các tập hợp biến.

Xét ma trận Carnot cho hàm đại số logic trên bộ 4 biến (Bảng 1).

Bảng 1. Ma trận Carnot

Các cột và hàng trong ma trận này được ký hiệu bằng các số nhị phân liền kề: 00-0I-II-I0. Do đó, số ô liền kề theo chiều ngang và chiều dọc cũng như các ô ngoài cùng trong hàng và cột đều là số liền kề, ví dụ:

các ô có số và;

các ô có số;

các ô có số.

Để cực tiểu hóa một hàm đại số logic xác định ở dạng chuẩn phân biệt hoàn hảo sử dụng ma trận Carnot, cần: chuẩn bị ma trận Carnot bằng cách ghi đơn vị vào các ô tương ứng với các thành phần bắt buộc, gộp các ô có đơn vị thành các “khối con”, viết số rút gọn hàm đại số logic ở dạng chuẩn phân biệt.

Các “khối con” kết hợp:

- hai ô chứa các số là các số liền kề, trong khi một biến bị loại trừ;
- bốn ô (hàng, cột, ô vuông, ô góc), trong khi hai biến bị loại trừ;
- tám ô (hai hàng liền kề hoặc cực (cột)), với ba biến bị loại trừ.

Để cung cấp một ngoại lệ có thể hơn các biến, kích thước của các “khối con” phải càng lớn càng tốt và số lượng của chúng Càng ít càng tốt. Với mục đích này, bạn có thể sử dụng cùng một ô với một đơn vị nhiều lần, bao gồm ô đó trong các “khối con” khác nhau. Số lượng thuật ngữ trong hàm đại số logic tối thiểu bằng số lượng khối con và ô có đơn vị không được kết hợp thành các khối con.

Giả sử cần cực tiểu hóa hàm đại số logic sau:

Ma trận Carnot, được điền theo công thức này, có thể được trình bày dưới dạng Bảng 2:

Bảng 2. Ma trận Carnot

Trong ma trận này, có thể phân biệt hai khối con hai ô. Kết quả của việc giảm thiểu, sẽ thu được hàm đại số logic sau:

phương pháp Quine

Để thu được dạng tối thiểu của một hàm logic, cần phải thực hiện tất cả việc dán và hấp thụ có thể ở dạng chuẩn phân biệt hoàn hảo của hàm (SDNF) để kết quả là một hàm phân biệt rút gọn. dạng bình thường chức năng. (DNF). DNF giảm trong trường hợp chung có thể chứa các hàm ý chính bổ sung, phải được xác định ở giai đoạn giảm thiểu thứ hai.

Ở giai đoạn đầu tiên, quá trình chuyển đổi được thực hiện từ chức năng được chỉ định ở dạng DNF sang DNF rút gọn. Bản chất của phương pháp này là thực hiện tuần tự tất cả các quá trình dán có thể và sau đó là tất cả các quá trình hấp thụ, dẫn đến giảm DNF. Phương pháp này có thể áp dụng cho DNF hoàn hảo. Từ hệ thức hấp thụ, suy ra rằng một sản phẩm cơ bản tùy ý được hấp thụ bởi bất kỳ phần nào của nó. Để chứng minh điều đó, chỉ cần chỉ ra rằng một số nguyên tố tùy ý p = x là đủ i1 x i2... x TRONG có thể được nhận. Thật vậy, áp dụng phép toán khai triển ( hoạt động ngược lại dán):

cho tất cả các biến bị thiếu x ik , ..., x Tôi hàm f ban đầu, ta thu được tập S gồm các phần tử của sự thống nhất. Bằng cách dán tất cả các thành phần từ S lại với nhau, chúng ta thu được p tiềm ẩn. Điều thứ hai là hiển nhiên, vì thao tác dán là nghịch đảo của thao tác trải ra. Tập S gồm các thành phần nhất thiết phải có mặt trong một DNF hoàn hảo của hàm f vì p là hàm ý của nó.

Kết quả của việc dán, thu được kết hợp cấp n-1 và các kết hợp vẫn giữ nguyên biểu thức ban đầu và tham gia so với các thành viên khác của SDNF. Vì vậy, có thể giảm thứ hạng của các thuật ngữ.

Việc dán và hấp thụ được thực hiện miễn là có các thành viên không tham gia so sánh theo cặp. Các thuật ngữ đã trải qua quá trình dán sẽ được đánh dấu. Các thuật ngữ không được đánh dấu là các thuật ngữ chính và được bao gồm trong DNF viết tắt. Tất cả các liên từ được đánh dấu thuộc hạng n-1 lại phải chịu thao tác dán cho đến khi thu được các số hạng thuộc hạng n-2, v.v. cho đến khi số lượng liên từ không được đánh dấu lớn hơn 2. Kết quả của giai đoạn đầu tiên là DNF giảm được thu được.

Biểu thức logic thu được không phải lúc nào cũng tối thiểu. Ở giai đoạn thứ hai, họ chuyển từ DNF giảm sang DNF cuối cùng và chọn MDNF trong số đó.

Để hình thành các DNF cuối cùng, một bảng hàm ý (ma trận) được xây dựng, các hàng trong đó được đánh dấu bằng các hàm ý đơn giản của DNF viết tắt và các cột có các thành phần của đơn vị SDNF ban đầu. Trong dòng đối diện với mỗi vật tiềm ẩn đơn giản, một dấu được đặt dưới các tập hợp (thành phần của đơn vị) mà nó nhận giá trị 1. Các thành phần tương ứng được hấp thụ (bao phủ) bởi vật tiềm ẩn đơn giản này.

Từ Tổng số những người cấy ghép chính cần phải chọn số lượng tối thiểu của chúng, loại bỏ những số lượng dư thừa. Sự hình thành các dạng ngõ cụt và việc lựa chọn phạm vi bao phủ tối thiểu bắt đầu bằng việc xác định các hàm ý chính bắt buộc, nghĩa là các hàm ý (và chỉ chúng) bao trùm một số tập hợp ban đầu. Hãy xem ví dụ về việc giảm thiểu hàm logic:

f SDNF = V(1,2,5,6,7)=x 1 x 2 x 3 + x 1 x 2 x 3 + x 1 x 2 x 3 + x 1 x 2 x 3 + x 1 x 2 x 3

1 2 3 4 5

Hãy thực hiện thao tác dán:

1 - 3 (x 1 ) x 2 x 3 1
2 - 4 (x 1 ) x 2 x 3 2
3 - 5 (x 2 ) x 1 x 3 3
4 - 5 (x 3 ) x 1 x 2 4

Kết quả của bước gắn kết đầu tiên là chúng ta thu được bốn liên từ mới; không có hàm ý đơn giản nào được xác định. Các liên từ kết quả không còn dính vào nhau và tạo thành DNF rút gọn.

f abbr SDNF =x 2 x 3 + x 2 x 3 + x 1 x 3 + x 1 x 2

Để xác định các hàm ý đơn giản bắt buộc và xây dựng phạm vi bao phủ tối thiểu dựa trên chúng, một bảng hàm ý đơn giản được xây dựng (Bảng 3). Các hàm ý đơn giản được viết vào các hàng của bảng hàm ý, và các thành phần của sự thống nhất được viết vào các cột. Dấu hoa thị được đưa ra nếu hàm chính bao phủ thành phần.

Bảng 3. Bảng hàm ý

x 1 x 2 x3	X 1 x 2 x3	x 1 x 2 x3	x 1 x 2 x3	x 1 x 2 x3

Các hàm ý chính là bắt buộc vì chúng chỉ bao gồm các thành phần và được bao gồm trong phạm vi bảo hiểm tối thiểu. Vẫn còn một thành phần x chưa được khám phá 1 x 2 x 3 có thể được bao phủ bởi một trong hai hàm ý chính còn lại. Điều này dẫn đến hai hình thức ngõ cụt.

Phương pháp Blake-Poretsky

Phương pháp này cho phép người ta thu được DNF rút gọn của hàm Boolean f từ DNF tùy ý của nó. Dựa vào việc áp dụng công thức dán tổng quát:

tính đúng đắn của nó dễ dàng được chứng minh. Thật sự,

Kể từ đây,

Phương pháp này dựa trên tuyên bố sau: nếu trong một DNF tùy ý của hàm Boolean f, chúng ta thực hiện tất cả các phép dán tổng quát có thể có và sau đó thực hiện tất cả các phép hấp thụ, thì kết quả là DNF giảm của hàm f.

Hãy xem một ví dụ. Giả sử hàm Boolean f được cho bởi một DNF tùy ý.

Cần phải thu được DNF rút gọn của hàm f bằng phương pháp Blake-Poretsky. Chúng tôi thực hiện dán chung. Dễ dàng nhận thấy rằng phần tử thứ nhất và thứ hai của DNF ban đầu thừa nhận việc dán tổng quát đối với biến x 1 . Kết quả của việc dán chúng ta nhận được:

Phần tử thứ nhất và thứ ba của DNF ban đầu thừa nhận việc dán tổng quát đối với cả biến x 1 và x 2 . Sau khi dán dọc theo x 1 chúng ta có:

Sau khi dán theo x 2 ta có:

Phần tử thứ hai và thứ ba của DNF thừa nhận việc dán tổng quát đối với biến x 2 . Sau khi dán ta được:

Sau khi thực hiện lần dán tổng quát cuối cùng, chúng tôi đến DNF:

Sau khi thực hiện hấp thụ, chúng tôi nhận được:

Những nỗ lực tiếp tục áp dụng hoạt động dán và hấp thụ tổng quát không mang lại kết quả. Do đó, thu được DNF giảm của hàm f. Tiếp theo, vấn đề tìm DNF tối thiểu được giải quyết bằng cách sử dụng ma trận hàm ý theo cách giống hệt như trong phương pháp của Quine.

Giảm thiểu các FAL được xác định không đầy đủ

Nếu trong quá trình tổng hợp mạch logic, thực hiện một số FAL của n biến, hóa ra một số bộ tổng số 2 N không bao giờ có thể xuất hiện ở đầu vào của mạch thì hàm logic này không được xác định trên các bộ này. Sau đó 2 N tập hợp các biến có thể được chia thành ba nhóm: tập hợp mà hàm số nhận một giá trị L, giá trị null D và một nhóm các tập hợp mà hàm số không được xác định N (các tập hợp không xác định). FAL chứa các tập hợp không xác định được gọi là được xác định không đầy đủ hoặc được xác định một phần. Các tập hợp không xác định có thể được sử dụng để cải thiện chất lượng tối thiểu hóa. Trong trường hợp này, các tập hợp không chắc chắn (ví dụ như khi được thu nhỏ bằng bản đồ Veitch, Carnaugh) có thể tham gia vào việc hình thành các đường viền với cả tập đơn vị và tập 0. Điều này dẫn đến việc hình thành một hàm logic tối thiểu hóa đơn giản hơn.

Một phương pháp giảm thiểu phổ biến là sử dụng các định luật và quan hệ của đại số logic, cho phép giảm thiểu FAL cho bất kỳ số lượng biến nào.