UVA1179 Minimal Cover of Prime Implicants
题目描述
### 题意翻译
在组合逻辑设计中，布尔函数通常表示为最小项的和。
例如，$F(x,y,z)=xyz+xyz+xyz+xyz$是一个布尔函数，其中$xyz$、$xyz$、$xyz$和$xyz$是函数的小项$（MT）$。通常，小项使用它们的二进制或十进制表示。如小项$xyz$可以表示为$001$（二进制）或简单地表示为$1$（十进制）并且小项$xyz$可以表示为$011$（二进制）或$3$（十进制）。通过这个小项的数字表示，上述函数可以表示为$F(x,y,z)=S(1,3,6,7)$或$F(x,y,z)=S(001011110111)$。小项的二进制一般是计算机处理布尔函数是所用。
利用布尔代数定理$Ax+Ax=A$，我们可以将两个乘积项组合起来生成一个降积项。如，$xyz+xyz=xz$和$xyz+xy z=xy$。函数的降积项也称为函数的素蕴涵项。所以布尔函数可以表示为素数蕴涵的和。比如，上述函数可表示为$F(x,y,z)＝xz+xy$。一般来说，函数中的素数蕴涵项是用二进制表示法表示，其中缺少的变量用“$-$”表示。也就是说，素数蕴涵$xz$表示为$0-1$，$xy$表示为$11-$。则最初说的$F(x,y,z)$函数即可表示为$F(x,y,z)＝S(0-1,11-)$。
大多数素数蕴涵生成算法生成的前者都超过了最小要求。例如对于上述函数，小项$001$和$011$生成素蕴涵$0-1$，小项$110$和$111$生成素蕴涵$11-$，并且小项$011$和$111$生成素蕴涵$-11$。但是素蕴涵$-11$不是表示函数所必要的。因此，给定一个函数的一组小项和一组素数蕴涵，需要找到覆盖该函数所有小项的素数蕴涵的极小子集。事实上这是一个优化问题。对于这个问题，存在一种覆盖大多数算法，下面将对此进行深入的讨论。
素数蕴涵的代价是素数蕴涵中$0$和$1$的个数。如素数蕴涵项$0-1$的代价是$2$。素蕴涵覆盖一个小项当且仅当此素蕴涵可以被展开以产生该小项。比如说素数隐含项$0-1$覆盖了小项$001$和$011$。
在覆盖大多数算法中，第一个选择是覆盖最多数量小项的素数蕴涵。如果一个以上的素蕴涵包含相同数量的小项，则选择具有最小代价的素蕴涵。通过按顺序选择第一个素数蕴涵来打破关系。
下面使用下表说明了上述函数的算法。表中的“$x$”意味覆盖。
| MT PI | 001 | 011 | 110 | 111 | Cost| No of minterms covered |
| :----------: | :----------: | :----------: | :----------: | :----------: | :----------: | :----------: |
| $0-1$ | $X$ | $x$ | | | $2$ | $2$ |
| $11-$ | | | $X$ | $x$ | $2$ | $2$ |
| $-11$ | | $x$ | | $x$ | $2$ | $2$ |
第一个选择是素数隐含项$0-1$。之后问题就归结为下表。
| MT PI| 110 | 111 | Cost | No of minterms covered |
| :----------: | :----------: | :----------: | :----------: | :----------: |
| $11-$ | $x$ | $X$ | $2$ | $1$ |
| $-11$ | | $X$ | $2$ | $1$ |
下一个选择是素数蕴涵$11-$。然后问题变为为零，并且给定素数蕴涵的最小覆盖为$0-1$和$11-$。
你需要写一个程序找到给定的一组素数蕴涵和一个函数的一组小项的素数蕴涵集最小覆盖。你还需要确定给定的素数蕴涵集是否涵盖函数的所有小项。如果给定的素数蕴涵集不覆盖所有的小项，则该算法产生的最小覆盖将不覆盖给定的函数。
输入格式
输入包含多个测试样例。每个测试样例的第一行三个整数表示函数变量的数量$n(2\le n\le20)$、小项的数量$m(m\le200)$和素数蕴涵项的数量$h(h\le200)$。第二行的整数表示小项。后面一行表示素数蕴含项。输入以三个零结束。
输出格式
对于输入中的每个测试用例，输出测试样例的编号，后跟“$No of required PIs$”$=$或“$PIs don't cover all MTs$”。
### 输入输出样例
#### 输入#1
```
4 7 5
0001 0010 0101 0110 1001 1101 1110
--01 -11- 0-1- 0--1 -1-1
4 8 5
0000 0010 0100 1000
1010 1011 1100 1101
---0 -10- 101- 01-- 0-0-
4 9 5
0000 0010 0011 0100 1000 1010 1011 1100 1101
---0 -10- 101- 01-- 0-0-
5 15 6
00110 00100 01110 01100 11000 11010 11110 11100 10110 10100
01111 01101 11111 11101 10001
-11-- --1-0 001-- 11--0 10001 01-11
0 0 0
```
#### 输出#1
```
Test #1: No of required PIs = 3
Test #2: No of required PIs = 3
Test #3: PIs don't cover all MTs
Test #4: No of required PIs = 4
```