解题报告逻辑范式化简

1、逻辑范式化简解题福建师大附中问题描述给出一张真值表，求出一个满足真值表的逻辑式，并使逻辑式的长度尽可能的短。问题分析该题若要求得准确的最短逻辑式，必须搜索。但使用近似算法，主要步骤如下：根据真值表，先写出所有的极小项，然后应用 Quine-McCluskey 方法求出这个逻辑式的极简多项式。求极小项对于一张真值表，找出所有结果为真的行，对于每一行，按照如下规则写出描述这一行的表达式：对于该行的每个变量，如果变量的值为F，则写下!，否则直接记下。每两个变量之间用&(且)连接。这样的表达式称为极小项(merm)。例如，第 4, 5, 6, 8, 10, 12, 13, 14 行的最终结果是真，由此

2、得到这些极小项(已列于表中)。Quine-McCluskey 方法将所有的极小项在左边排成一列，然后根据 (a & b) | (a & !b) = a 从而删去变量b 的 法则，两两检查所有极小项，看其是否能删掉一个变量，如果能删掉一个变量，则将所得的新项写在右边，并在使用过的两个极小项的旁边，打上记号 。然后，在对所有新得到的项做两两检查。以此类推，直到不能再删文字为止。于是，所有不带记号 的项，就称之为极简项(primeimplicants)。列表(prime implicant table)，将所有的极小项横向排列，所有极简项纵向排列。如果某个极简项完全出现在某些极小项中，则在该极简项所

3、在的行和这些极小项所在的列的交点上打上记号X。取最少个数的极简项，使得每列与这些极简项所在的行的交点上至少有一个X 号(满足条件的取法可能有好多种)。于是用|(或)连接这些极简项()，就得到了极简多项式(minimal expres)。由上表，极简多项式只有一个：b & !c | (!a & c & d) | (a & !b & d)。实际情况根据 Quine-McCluskey 方法，得出表后，需要搜索才能求出极简多项式。当然在搜索之前，判断，如果某一列只有一个X，则该X所对应的极简项在极简多项式中必须出现。但在极简项个数太多和X标记分布稀疏时，搜索无法得出极简多项式，所以使用贪心。先取能选

4、中最多的新的极小项的极简项，然后其次，以此类推，直至所有极小项的列都有X被选中。题目要求的是使范式的长度最短，所以在所有的(这当然是搜索求得的)极简多项式中找出长度最短的。部分改进前面，在求极小项时是选取结果为真的行，现在选取结果为行再求一遍极简多项式，然后整体取非。这样，对于部分数据，可以求得更短的逻辑范式。关于搜索前面，对于这题，Quine-McCluskey 方法只是近似的。在 Quine-McCluskey 方法得出较好的结果上考虑搜索。搜索化简的原则是：(A & B) | (A & !B) = A 和(A & B) | (A & C) = A | (B & C)，这里 A, B, C

5、 均是布尔代数式。总结程序对 Quine-McCluskey 方法得出的结果进一步搜索。但大部分数据都可以得到 10 分，就是说对于该题 Quine-McCluskey 方法是一种有效的和相当好的方法。当然，标准并非最优。这题主要参赛者代数方面的知识。附录部分测试数据的更优：logic.st7!e&!d&b&a|(!e&c&!b&a)|(!e&c&b&!a)|(!e&d&!c&a)|(d&!c&b&!a)|(d&c&!b&!a)|(e&!d&!c&a)|(e&!d&b&!a)|(e&!d&c&!b)|(e&d&!c&!b)更好的结果：(d&!a&(!c&b)|(c&!b)|(e&(d&!c&!

6、b)|(!d&(c&!b)|(!c&a)|(b&!a)|(!e&(b&(!d&a)|(c&!a)|(a&(c&!b)|(d&!c)logic.st0!(!f&!e&d&!b&!a|(!f&e&!d&!b&!a)|(!f&!e&d&c&!a)|(!f&e&!d&c&!a)|(f&!e&!c&b&!a)|(f&!d&!c&b&!a)|(f&e&!c&!b&!a)|(!f&!d&c&b&a)|(!f&d&!c&b&a)|(!f&e&d&!b&a)|(f&!e&d&c&a)|(!e&!d&!c&b)|(f&!e&!d&!b)|(e&b&a)更好的结果：!(!e&!d&(!c&b)|(f&!b)|(e&

7、(b&a)|(!f&(d&!b&a)|(!d&!a&(!b|c)|(f&(!e&(!c&b&!a)|(d&c&a)|(!c&!a&(!d&b)|(e&!b)|(!f&(!d&c&b&a)|(d&(!e&!a&(!b|c)|(!c&b&a)参考文献Discrete Mathematics and Its Applications, 美Kenneth H.Rosen.参考程序 Logical ExpresSimplifying Using Quine-McCluskey Method constfilein = logic.in;fileout = logic.out;vartexp : arra

8、y1.1000of string6; merms, and used BFS while expanding sexp : array1.64of string6; the prime implicants g : array1.64, 1.64of 0.1; the prime implicant table nums, num : array1.1000of byte;n, nn, m : byte;base, best : set of byte;ans1, ans2 : string;error :;f : text;procedure outspel;beginassign(f, f

9、ileout); rewrite(f);wrin(f, !a&a);close(f);halt;end;procedure readdata1;var i, k : byte;s : string;beginassign(f, filein);reset(f);readln(f, n);k := 1; for i := 1to n do k:=k * 2;m := 0;for i := 1 to kdobeginreadln(f, s);i+ 1 =T thenbegin inc(m);texpm := copy(s, 1, n); numm := n; end;end;close(f);if

10、 m = 0 then outspel;end;procedure readdata2;var i, j, k : byte;s : string;beginfor i := 1 to 64 dobegintexpi:= ;sexpi:= ;end;assign(f,filein); reset(f);readln(f,n);k := 1; for i := 1 to n do k:= k * 2;m := 0;for i := 1 to kdobeginreadln(f, s);i+ 1 =F thenbegin inc(m);texpm := copy(s, 1, n); numm :=n

11、; end;end;close(f);end;procedure comp(s1, s2 : string; var s : string; var p: byte);var i : byte;begins := ; p := 0;for i := 1 to n doif abs(ord(s1i) - ord(s2i) = 14 thenbegins := s + -;inc(p);endelseif s1i =s2i thens := s +s1ielse beginp := 0; exit;end;end;procedure selsexp;vari, j : word;p : byte;

12、s : string;checked : array1.1000of;q1, q2, q3 : word;function same :;var l : word;beginsame := true;for l := q2 toq3 doif texpl =s then exit;same := false;end;beginerror:= false;nn :=0;q1 :=1; q2 := m; q3 := m;fillchar(checked, sizeof(checked),true);repeatfor i := q1 to q2 - 1 dofor j := i + 1 to q2

13、 dobegincomp(texpi, texpj, s, p);if p = 1 thenif not same thenbegincheckedi := false;checkedj := false;inc(q3); texpq3:=s;numq3:= numi -1;end;end;q1 := q2 + 1;q2 := q3;untilq1 q2;nn :=0;for i:= 1 to q3 doif checkedi thenbeginin);if nn 64 then beginerror:= true; exit; end;sexpnn := texpi; numsnn := n

14、umiend;end;function instr(s, t : string) :;var i :byte;begininstr:= false;for i:= 1 to n doif si - thenif si ti then exit;instr := true;end;proceduretableinit;var i, j,k : word;beginbase :=;fillchar(g, sizeof(g), 0);for i := 1 to nn dofor j := 1 to m doif instr(sexpi, texpj)thengi,j:= 1;for i := 1 t

15、o m dobegink := 0;for j := 1 to nn doifgj, i = 1 thenifk = 0 then k := j else begink :=0;break;end;if k 0 theninclude(base, k);end;end;procedure main;vardep : byte;chked : array1.64 of short;a : array0.64 of byte;sel : set of byte;min, use : word;procedure init;var i, j : byte;beginfillchar(chked, s

16、izeof(chked), 0);for i := 1 to nn doif i in base thenfor j := 1 to m doif gi, j =1 then chkedj:= -1;end;procedure check;var i : byte;beginfor i :=1 to mf chkedi = 0then exit;if use max then begax := count;seli:=i;end;end;if seli 0 thenbegininclude(base, seli);for j := 1 to m doif gseli, j = 1 thench

17、kedj :=1;changed := true;end;until not changed;end;procedure search(l : byte);var i, j : byte;beginif l dep then begin check;exit; end;for i := al - 1 + 1 to nn doif not (i in base) thenbegininclude(sel, i);al := i;for j := 1 to m doif gi, j = 1 thenif chkedj = 0 then chkedj := l;use := use+ numsi;s

18、earch(l +1);al := 0;for j := 1to m doif chkedj = l thenchkedj:=0;use := use - numsi;exclude(sel, i);end;end;begininit;dep := 1;best := ;min := 65525;fillchar(a, sizeof(a),0);if nn nn) or (best );base := best+ base;endelsegreedy;end;procedure out1;vari, j : byte;b:;s: string;beginans1 := ;b := false;

19、for i := 1 to nn doif i in base thenbegins := ;for j := 1 to n doif sexpij - thencase sexpij ofT : s := s + chr(j + 96) +&;F : s := s + ! + chr(j +96) +&;end;s := copy(s, 1, length(s) - 1);if not (length(s) =1) or(s1 = !)and (length(s) = 2)ornot b)then s:= ( + s+ );if not b thenbegin ans1 := ans1 +

20、s;b := true endelse ans1 := ans1 + | +s;end;end;procedure out2;var i, j : byte;b :;s : string;beginans2 := !(;b := false;for i := 1 to nn doif i in base thenbegins := ;for j := 1 to n doif sexpij - thencase sexpij ofT : s := s + chr(j + 96) + &;F : s := s + ! + chr(j + 96) + &;end;s := copy(s, 1, length(s) - 1);if not (length(s) =1) or(s1 = !)and