"逻辑范式化简"解题报告
福建师大附中 李翼
[问题描述]
给出一张真值表，求出一个满足真值表的逻辑式，并使逻辑式的长度尽可能的短。
[问题分析]
该题若要求得准确的最短逻辑式，必须搜索。但我们使用近似算法，主要步骤如下：根据真值表，先写出所有的极小项，然后应用Quine-McCluskey方法求出这个逻辑式的极简多项式。
[求极小项]
对于一张真值表，找出所有结果为真的行，对于每一行，按照如下规则写出描述这一行的表达式：对于该行的每个变量 ，如果变量的值为F，则写下!，否则直接记下。每两个变量之间用"&"(且)连接。这样的表达式称为极小项(minterm)。例如，
第4, 5, 6, 8, 10, 12, 13, 14行的最终结果是真，由此我们得到这些极小项(已列于表中)。
[Quine-McCluskey方法]
将所有的极小项在左边排成一列，然后根据 (a & b) | (a & !b) = a从而删去变量b的 法则，两两检查所有极小项，看其是否能删掉一个变量，如果能删掉一个变量，则将所得的新项写在右边，并在使用过的两个极小项的旁边，打上记号 。
然后，在对所有新得到的项做两两检查。
以此类推，直到不能再删文字为止。于是，所有不带记号的项，就称之为极简项(prime
implicants)。
列表(prime implicant table)，将所有的极小项横向排列，所有极简项纵向排列。如果某个极简项完全出现在某些极小项中，则在该极简项所在的行和这些极小项所在的列的交点上打上记号X。取最少个数的极简项，使得每列与这些极简项所在的行的交点上至少有一个X号(满足条件的取法可能有好多种)。于是用"|"(或)连接这些极简项()，就得到了极简多项式(minimal
expression)。
由上表，极简多项式只有一个：b & !c | (!a & c & d) | (a & !b
& d)。
[实际情况]
根据Quine-McCluskey方法，得出表后，需要搜索才能求出极简多项式。当然在搜索之前，我们判断，如果某一列只有一个"X"，则该"X"所对应的极简项在极简多项式中必须出现。但在极简项个数太多和"X"标记分布稀疏时，搜索无法得出极简多项式，所以我们使用贪心。先取能选中最多的新的极小项的极简项，然后其次，以此类推，直至所有极小项的列都有"X"被选中。
题目要求的是使范式的长度最短，所以我们在所有的(这当然是搜索求得的)极简多项式中找出长度最短的。
[部分改进]
前面，我们在求极小项时是选取结果为真的行，现在我们选取结果为假的行再求一遍极简多项式，然后整体取非。这样，对于部分数据，可以求得更短的逻辑范式。
[关于搜索]
前面说过，对于这题，Quine-McCluskey方法只是近似的。
我们在Quine-McCluskey方法得出较好的结果上考虑搜索。搜索化简的原则是：
(A & B) | (A & !B) = A和(A & B) | (A & C) = A | (B
& C)，这里A, B, C均是布尔代数式。
[总结]
我的程序对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&!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&((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 Expression Simplifying Using Quine-McCluskey Method }
const
filein = 'logic.in';
fileout = 'logic.out';
var
texp : array[1..1000]of string[6]; { minterms, and used BFS while
expanding }
sexp : array[1..64]of string[6]; { the prime implicants }
g : array[1..64, 1..64]of 0..1; { the prime implicant table }
nums, num : array[1..1000]of byte;
n, nn, m : byte;
base, best : set of byte;
ans1, ans2 : string;
error : boolean;
f : text;
procedure outspecial;
begin
assign(f, fileout); rewrite(f);
writeln(f, '!a&a');
close(f);
halt;
end;
procedure readdata1;
var i, k : byte;
s : string;
begin
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 k do
begin
readln(f, s);
if s[n + 1] = 'T' then
begin inc(m); texp[m] := copy(s, 1, n); num[m] := n; end;
end;
close(f);
if m = 0 then outspecial;
end;
procedure readdata2;
var i, j, k : byte;
s : string;
begin
for i := 1 to 64 do
begin
texp[i] := '';
sexp[i] := '';
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 k do
begin
readln(f, s);
if s[n + 1] = 'F' then
begin inc(m); texp[m] := copy(s, 1, n); num[m] := n; end;
end;
close(f);
end;
procedure comp(s1, s2 : string; var s : string; var p : byte);
var i : byte;
begin
s := ''; p := 0;
for i := 1 to n do
if abs(ord(s1[i]) - ord(s2[i])) = 14 then
begin
s := s + '-';
inc(p);
end
else
if s1[i] = s2[i] then
s := s + s1[i]
else begin p := 0; exit; end;
end;
procedure selsexp;
var
i, j : word;
p : byte;
s : string;
checked : array[1..1000]of boolean;
q1, q2, q3 : word;
function same : boolean;
var l : word;
begin
same := true;
for l := q2 to q3 do
if texp[l] = s then exit;
same := false;
end;
begin
error := false;
nn := 0;
q1 := 1; q2 := m; q3 := m;
fillchar(checked, sizeof(checked), true);
repeat
for i := q1 to q2 - 1 do
for j := i + 1 to q2 do
begin
comp(texp[i], texp[j], s, p);
if p = 1 then
if not same then
begin
checked[i] := false;
checked[j] := false;
inc(q3); texp[q3] := s; num[q3] := num[i] - 1;
end;
end;
q1 := q2 + 1;
q2 := q3;
until q1 > q2;
nn := 0;
for i := 1 to q3 do
if checked[i] then
begin
inc(nn);
if nn > 64 then begin error := true; exit; end;
sexp[nn] := texp[i]; nums[nn] := num[i]
end;
end;
function instr(s, t : string) : boolean;
var i : byte;
begin
instr := false;
for i := 1 to n do
if s[i] <> '-' then
if s[i] <> t[i] then exit;
instr := true;
end;
procedure tableinit;
var i, j, k : word;
begin
base := [];
fillchar(g, sizeof(g), 0);
for i := 1 to nn do
for j := 1 to m do
if instr(sexp[i], texp[j]) then g[i, j] := 1;
for i := 1 to m do
begin
k := 0;
for j := 1 to nn do
if g[j, i] = 1 then
if k = 0 then k := j else begin k := 0; break; end;
if k <> 0 then
include(base, k);
end;
end;
procedure main;
var
dep : byte;
chked : array[1..64] of shortint;
a : array[0..64] of byte;
sel : set of byte;
min, use : word;
procedure init;
var i, j : byte;
begin
fillchar(chked, sizeof(chked), 0);
for i := 1 to nn do
if i in base then
for j := 1 to m do
if g[i, j] = 1 then chked[j] := -1;
end;
procedure check;
var i : byte;
begin
for i := 1 to m do if chked[i] = 0 then exit;
if use < min then
begin
min := use;
best := sel;
end;
end;
procedure greedy;
var i, j, seli, count, max : integer; changed : boolean;
begin
best := [];
repeat
changed := false;
max := 0;
seli := 0;
for i := 1 to nn do
if not (i in base) then
begin
count := 0;
for j := 1 to m do
if (g[i, j] = 1) and (chked[j] = 0) then inc(count);
if count > max then begin max := count; seli := i; end;
end;
if seli <> 0 then
begin
include(base, seli);
for j := 1 to m do
if g[seli, j] = 1 then chked[j] := 1;
changed := true;
end;
until not changed;
end;
procedure search(l : byte);
var i, j : byte;
begin
if l > dep then begin check; exit; end;
for i := a[l - 1] + 1 to nn do
if not (i in base) then
begin
include(sel, i);
a[l] := i;
for j := 1 to m do
if g[i, j] = 1 then
if chked[j] = 0 then chked[j] := l;
use := use + nums[i];
search(l + 1);
a[l] := 0;
for j := 1 to m do
if chked[j] = l then chked[j] := 0;
use := use - nums[i];
exclude(sel, i);
end;
end;
begin
init;
dep := 1;
best := [];
min := 65525;
fillchar(a, sizeof(a), 0);
if nn <= 20 then
begin
repeat
sel := []; use := 0;
search(1);
inc(dep);
until (dep > nn) or (best <> []);
base := best + base;
end
else
greedy;
end;
procedure out1;
var i, j : byte;
b : boolean;
s : string;
begin
ans1 := '';
b := false;
for i := 1 to nn do
if i in base then
begin
s := '';
for j := 1 to n do
if sexp[i][j] <> '-' then
case sexp[i][j] of
'T' : 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
(s[1] = '!') and (length(s) = 2) or
not b)then s := '(' + s + ')';
if not b then
begin ans1 := ans1 + s; b := true end
else ans1 := ans1 + '|' + s;
end;
end;
procedure out2;
var i, j : byte;
b : boolean;
s : string;
begin
ans2 := '!(';
b := false;
for i := 1 to nn do
if i in base then
begin
s := '';
for j := 1 to n do
if sexp[i][j] <> '-' then
case sexp[i][j] of
'T' : 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
(s[1] = '!') and (length(s) = 2) or
not b)then s := '(' + s + ')';
if not b then
begin ans2 := ans2 + s; b := true end
else ans2 := ans2 + '|' + s;
end;
ans2 := ans2 + ')';
end;
procedure finalout(s : string);
begin
assign(f, fileout); rewrite(f);
writeln(f, s);
close(f);
end;
begin
readdata1;
if m = 1 then
begin
nn := 1; sexp[1] := texp[1]; base := [1];
out1;
finalout(ans1);
halt;
end;
selsexp;
if not error then
begin
tableinit;
main;
if base <> [] then out1;
end
else
ans1[0] := chr(255);
{ inverse the minterms }
readdata2;
selsexp;
if not error then
begin
tableinit;
main;
if base <> [] then out2;
end
else
ans2[0] := chr(255);
if length(ans2) < length(ans1) then finalout(ans2) else finalout(ans1);
end.
{
Comment:
In this code, we record minterm !a&b&!c&d&e as 'FTFTT',
!a&c&!e as 'F-T-F', etc.
}
|
