6 б) Иллюстрационные примеры
В каждом из следующих ниже двух иллюстрационных примеров представлены:
1) исходная КНФ;
2) полученная в результате преобразования
суперприведенная КНФ, эквивалентная исходной;
3) результат приведения КНФ в
форме ДНФ.
Под эквивалентностью понимается совпадение выполняющих наборов.
Для КНФ принято:
P – переменная;
S – инвертированная
переменная. Им предшествует индекс переменной, каждая строка– это
дизъюнкция.
Для ДНФ принято:
D – переменная;
N – инвертированная переменная.
Им предшествует индекс переменной, каждая строка – это конъюнкция.
Теперь отметим следующее: если в исходных КНФ определение Выполнимости является труднорешаемой задачей, то для суперприведенной КНФ – это уже легкая задача, то есть в ней факт выполнимости устанавливается за линейное время от размерности n * m задачи.
Сопоставление логических схем, реализующих КНФ и суперприведенную КНФ, говорит о пользе суперприведения.
Строго говоря, в практической деятельности применение программ суперприведения
позволяет на этапе проектирования системами CAD (computer-aided
design) получать лишь задачи сверхлегкорешаемые.
ПРИМЕР N 1
I Исходная КНФ:
0) 7S 8P 9P
1) 5P 6P 7S
2) 5P 6S 7P 9P
3) 4P 6S 7P
4) 4P 5P 6P 7P
5) 3S 4P 5P 9P
6) 3S 4S 6P 7P
7) 2P 5S 7S 9P
8) 2S 3P 7S 9P
9) 2P 3S 5S 7S
10) 2P 3P 6S 9P
11) 2S 3S 5S 6P
12) 2S 3P 7P 8P
13) 2S 6P 9P
14) 3S 6S 9P
15) 3P 4S 5S 7P
16) 1S 3S 4P 6S
17) 1P 4S 6S 9P
18) 1S 2P 5S 9P
19) 1S 2S 4P 7P
20) 1S 3P 5P 8P
21) 0P 3P 5S 9P
22) 0S 1P 4P 8P
23) 0P 1P 2P 8P
24) 0S 4S 6P 9P
25) 1S 3S 4S 8S
26) 2S 5S 7P 8S
27) 2S 6S 8S
28) 5S 6S 7S 8S
29) 4S 5S 6S 8S
30) 4P 6P 7P 8S
31) 5P 7P 8S
32) 2S 3S 9S
33) 3P 6P 8P 9S
34) 3P 6P 7S 9S
35) 1P 3P 7P 9S
36) 4S 8P 9S
37) 3P 4P 6S 9S
38) 2S 5S 6S 9S
39) 2P 4S 8S 9S
ПРИМЕР N 1
Результат суперприведения
I исходной КНФ:
0) 9P
1) 7P 8S
2) 7S 8P 9S
3) 6P 7S 9S
4) 6S 7P 8P 9S
5) 5P 6P 7P 8P 9S
6) 5S 6S 7S 8S
7) 4S 8P 9S
8) 4S 6S 8S 9S
9) 3P 6P 8P 9S
10) 3P 4P 6S 9S
11) 2S 6S 8S
12) 2S 3S 9S
13) 1S 3S 4P 6S
14) 0S 1P 4P 8P
ПРИМЕР N 1
Результат приведения
I КНФ к форме ДНФ:
0) 1N 2N 3D 4N 5N 6D 7D 8D 9D
1) 1D 2N 3D 4N 5D 6N 7N 8N 9D
ПРИМЕР N 2
II Исходная КНФ:
0) 1S 2S 7S 21S
1) 0P 13S 15S 23P
2) 4P 6P 7P 11P
3) 0S 14P 22S 29S
4) 10S 11S 26P 29P
5) 7P 20P 24P 27S
6) 1P 20P 21S 28S
7) 7S 14S 19S 26S
8) 0P 4P 7S 29S
9) 4P 8P 10S 18P
10) 8S 23P 28P 29P
11) 0P 4P 13P 24P
12) 4S 15S 19P 26S
13) 1S 11S 13P 26S
14) 1S 9P 28P 29P
15) 2P 5S 16P 22P
16) 0S 3S 26P 28P
17) 2S 11P 25S 28S
18) 3P 5P 9S 14S
19) 18S 19S 26S 28P
20) 7P 13S 27P 28P
21) 2S 10P 11P 12P
22) 15P 17S 19S 26P
23) 1P 8P 10P 23S
24) 2S 14P 15S 22P
25) 15P 22S 26P 28P
26) 0P 10P 13S 26S
27) 9S 20P 22P 23P
28) 6P 13P 23S 25P
29) 5P 12P 18P 19P
30) 2P 5S 19S 27P
31) 6S 15S 19P 24P
32) 0S 20S 22P 29P
33) 9S 14P 17S 19P
34) 5P 7P 15P 26P
35) 0S 2S 5P 8S
36) 2P 9S 10P 18S
37) 0P 5S 8P 9S
38) 2P 6S 18P 19P
39) 9P 22P 25P 28P
40) 11S 22S 23S 28P
41) 3S 6S 8P 22S
42) 9P 11P 25P 27P
43) 8S 15S 24S 27P
44) 1P 2S 11P 19S
45) 2S 6S 25S 28P
46) 9P 12P 20P 29P
47) 2P 6P 24P 26S
48) 3S 20P 24S 27P
49) 3P 18P 25S 28P
50) 2S 13P 15S 27S
51) 1P 4S 12P 16S
52) 1P 4S 8P 9S
53) 1P 2P 11P 16P
54) 1P 3S 12S 18P
55) 0P 9P 15P 26S
56) 7S 11S 15P 23S
57) 12S 21S 23S 28S
58) 0P 1P 16P 22P
59) 6S 7P 24S 27P
60) 0P 7S 9S 26P
61) 1S 12S 22S 23S
62) 6S 11S 20S 22P
63) 4P 9S 13P 27P
64) 1S 9P 10P 23S
65) 5P 15P 18S 26P
66) 9S 16S 19P 25S
67) 5S 18P 20S 22S
68) 1P 5P 12S 19S
69) 6P 15S 22S 23P
70) 12S 16S 21S 24P
71) 1S 6S 9P 10S
72) 7P 10S 11P 26P
73) 8P 12P 17S 18S
74) 3S 17P 26S 28P
75) 11P 14P 27P 29S
76) 0P 4S 14S 23S
77) 0P 1S 13S 27P
78) 4P 11P 12S 27P
79) 2P 11P 18P 19P
80) 4S 23S 25S 27P
81) 11S 16S 17S 20P
82) 11S 16P 22S 28S
83) 18P 21P 26S 27S
84) 1S 4P 26P 27P
85) 6S 18S 25S 29S
86) 1P 9S 15S 28P
87) 10S 11P 15S 24P
88) 11P 17S 25S 26P
89) 1P 13P 26P 28S
90) 0P 3S 5S 20P
91) 5P 6S 18S 28P
92) 2P 11S 15P 24S
93) 1P 13P 16S 23S
94) 2S 6S 10P 12P
95) 12S 15P 21P 24P
96) 4S 9S 14S 18P
97) 6P 10S 17P 21P
98) 1S 8S 19S 21P
99) 14P 15S 21P 24P
100) 6S 9P 11P 16S
101) 5S 18P 22S 27P
102) 2S 11S 18P 24S
103) 9S 10P 18S 22S
104) 10P 15P 27S 29P
105) 3P 9S 10P 27P
106) 4S 6P 16P 17S
107) 18P 23S 28P 29P
108) 1P 2P 9S 28S
109) 1P 4S 23S 28S
110) 1P 6S 15S 24S
111) 2P 12P 23S 28P
112) 1P 9S 17S 29S
113) 11S 14S 25P 27S
114) 13S 14S 15P 27S
115) 8S 10P 13S 26P
116) 1P 6P 9S 20S
117) 12S 14S 17P 21P
118) 9S 16S 19P 22P
119) 3P 5P 8S 12S
120) 3S 16P 19P 27S
121) 6P 14P 26S 28P
122) 7P 12S 15S 18P
123) 7S 12P 15S 26S
124) 8S 11S 12P 14P
125) 10P 20S 26S 29P
126) 16P 17S 19P 23S
127) 7S 13P 14S 20P
128) 8S 20P 21S 28S
129) 10P 11P 20P 24P
130) 3S 5S 8P 25S
131) 7P 9S 10P 12S
132) 15S 18S 20P 27P
133) 6S 7P 17S 23P
134) 17P 18P 21P 24P
135) 9S 12P 18S 19S
136) 0S 9S 10S 25S
137) 1P 5P 18P 27P
138) 2S 5P 10P 13S
139) 1P 2P 21S 27P
140) 2P 18P 21P 24S
141) 1P 4P 7S 17P
142) 10S 12P 22S 26S
143) 2P 8P 10S 19P
144) 5S 7P 9S 20P
145) 11P 19P 21S 22P
146) 4S 7S 18P 22S
147) 3S 7P 19P 29S
148) 6P 12S 18S 26S
149) 12S 14P 17S 18P
150) 5S 8P 24S 29P
151) 6S 12P 21P 23S
152) 3P 9P 15P 20S
153) 2P 11P 21P 22S
154) 14S 18S 19S 22P
155) 0P 16P 22P 27S
156) 9P 15P 18P 23P
157) 9P 11P 19S 21P
158) 0S 3S 27S 28P
159) 7P 13S 14P 28S
160) 5S 10S 11P 17P
161) 2P 3S 19P 25P
162) 10P 17P 24P 26P
163) 6S 7S 10P 21P
164) 22P 24P 26P 27S
165) 0S 5P 11P 25S
166) 2S 8P 14S 25S
167) 11S 12S 20S 25S
168) 10S 18S 21P 22P
169) 8S 17P 21P 27P
170) 0S 7P 26P 28P
171) 3P 13P 15S 22P
172) 9P 12P 22S 29S
173) 2S 6S 15S 19S
174) 8S 19S 23S 28P
175) 0S 7S 22S 29S
176) 5P 27S 28P 29S
177) 1S 8P 12S 14S
178) 2S 10P 22S 25P
179) 4S 7P 22S 28P
180) 4P 21P 23P 24S
181) 11P 15P 17P 20P
182) 5S 13P 21P 28P
183) 7P 15S 23P 29P
184) 2P 7P 17P 28P
185) 19S 21S 24P 27S
186) 0S 16S 18P 23S
187) 16S 21P 22P 28P
188) 2P 3P 25S 26S
189) 9P 10S 27S 29P
190) 0S 2P 13S 29P
191) 9P 12S 20S 25S
192) 9P 14S 17S 25P
193) 10P 11P 17S 25P
194) 11S 12S 13P 15P
195) 8S 19P 26P 27P
196) 3P 14S 26P 28P
197) 3S 20S 23S 27S
198) 0P 6S 21S 23S
199) 20P 22P 28S 29S
200) 0S 11P 18S 29S
201) 0S 17S 27S 29S
202) 4S 18P 24S 27P
203) 2P 3P 6S 20S
204) 12P 21S 24P 27S
205) 12P 15P 26S 29S
206) 5P 7P 24S 27S
207) 1S 17S 21P 23S
208) 18P 20P 21S 22P
209) 0P 1P 15P 16P
210) 9S 11S 12P 25P
211) 1S 3P 13S 28P
212) 4S 9S 19P 25S
213) 2S 20S 23P 28S
214) 12P 18P 19S 24S
215) 4S 5P 11S 17P
216) 6P 20S 22S 29P
217) 8P 16P 18P 27P
218) 21P 22P 24P 25S
219) 16P 18P 19P 25P
220) 7P 8S 11S 20P
221) 10P 20P 25P 29P
222) 24S 26S 28P 29P
223) 3S 10S 13P 26P
224) 1S 8S 23S 25P
225) 12P 13S 23S 25P
226) 0P 3S 11S 23P
227) 7P 9S 15P 22P
228) 4S 8S 14S 23P
229) 7S 8S 12P 21S
230) 1P 3P 4S 24S
231) 7S 12S 22P 24S
232) 5P 8S 20P 28S
233) 11S 17S 22S 29S
234) 10P 20P 26P 28S
235) 3P 11S 14P 16S
236) 2S 12P 13P 23P
237) 5S 7P 8P 15P
238) 1P 4P 7S 16P
239) 6S 8P 22P 27S
240) 2S 8S 14P 22S
241) 2P 4P 7P 15P
242) 9S 16P 24S 27P
243) 10P 12S 15P 25S
244) 3S 12S 14P 28S
245) 11S 20S 23P 27S
246) 0S 2S 3P 4S
247) 1P 7S 19P 26S
248) 1S 6S 8S 24P
249) 1P 10P 12P 15S
250) 5S 6P 14P 18S
251) 8S 9P 12P 21P
252) 4S 13S 24S 27P
253) 2P 6P 15P 16S
254) 5P 8P 11S 15S
255) 10S 20S 23P 25S
256) 7P 11S 16S 29P
257) 4S 11S 13P 21P
258) 8P 18S 21S 29S
259) 13P 16P 24P 29P
260) 1S 3P 4P 10P
261) 2P 18S 24P 27S
262) 1S 13S 20S 25P
263) 3P 16S 17P 22S
264) 6P 8P 23P 26P
265) 10S 12S 17P 22S
266) 7S 13S 22S 25P
267) 8S 16P 17S 28S
268) 2S 18P 19P 23S
269) 9S 11P 22S 24S 25P
270) 1P 3S 8P 19S 29S
271) 4P 11S 13S 24P 25S
272) 10S 13P 14P 20S 25S
273) 15S 19S 20P 21S 27S
274) 2P 6S 14P 15P 16S
275) 7S 19P 22P 24P 29P
276) 0S 1S 6P 7S 11S
277) 0P 4S 12P 15P 21P
278) 2P 3S 10P 12P 17S
279) 8S 12P 16P 18S 19S
280) 8P 9P 11P 20S 25S
281) 0P 3P 7P 13S 23S
282) 5S 14S 16P 19S 23S
283) 0S 4P 5S 13P 27S
284) 3P 6P 10S 17P 22S
285) 3P 10S 13P 16S 28P
286) 1S 4S 9P 19S 25P
287) 1P 8S 16P 17S 19S
288) 2P 12S 17P 25P 26S
289) 8P 10S 11P 16S 27S
290) 11P 14P 19S 21P 24P
291) 0S 6S 7S 14P 24S
292) 5P 9P 24S 27P 29S
293) 12P 21S 24S 26S 29S
294) 0P 6S 18P 19S 27S
295) 4S 6S 7P 10S 29P
296) 1S 3P 8S 10P 12P
297) 2S 10P 12P 16P 22P
298) 9P 17S 22S 24P 26S
299) 2S 11P 22S 25S 28P
300) 1P 7P 16S 24P 25P
301) 7S 8S 17S 18P 22P
302) 7P 20S 22P 26S 29S
303) 7P 10P 16S 27P 28S
304) 13S 15P 19S 22P 23P
305) 0P 5S 21P 22S 24P
306) 6S 17S 21P 24P 27P
307) 3S 4P 5P 10S 12P
308) 3S 9P 10S 18P 20P
309) 5S 14P 18P 20S 26S
310) 2P 8P 13P 14S 27S
311) 1S 10S 21S 22P 24S
312) 0S 13S 20S 26S 28P
313) 4P 6P 16S 18S 26S
314) 2S 11S 15S 23P 26S
315) 4P 5S 9S 19P 24S
316) 5S 9S 13P 15P 17P
317) 0P 4P 7P 23P 28P
318) 6P 8P 16S 22P 26S
319) 19P 21S 22P 24S 27S
320) 5S 6P 9P 17P 22P
321) 1P 5P 7S 10P 23P
322) 0P 13P 16S 22S 25P
323) 17S 20S 23P 25P 26S
324) 0P 5P 14S 20S 26P
325) 5P 18P 25S 28P 29P
326) 0P 8S 9P 12S 22S
327) 15S 17P 21S 23S 25P
328) 0S 3S 15P 20P 25S
329) 1P 7P 20S 24S 28S
330) 2S 4P 12S 21P 24S
331) 5S 13P 21S 22P 28S
332) 5P 8P 11P 12S 23S
333) 6P 7P 13S 14P 22P
334) 0S 3P 12S 19P 21P
335) 5S 12S 18P 21P 26P
336) 2S 7P 10P 13P 25S
337) 1S 9P 13P 18P 19S
338) 6P 14S 22P 28S 29S
339) 6S 14S 16S 24P 27P
340) 3S 8S 11S 12P 20S
341) 10P 12S 13P 15S 18P
342) 8S 10P 13S 23S 25S
343) 13S 15P 19S 26P 28S
344) 5S 9P 15P 24P 29P
ПРИМЕР N 2
Результат суперприведения
II исходной КНФ:
0) 28P
1) 27P
2) 26S
3) 25S
4) 24P
5) 23S
6) 22P
7) 21P
8) 20P
9) 19P
10) 18P
11) 17S
12) 16S
13) 15P
14) 14P
15) 13S
16) 12P
17) 11S
18) 10S
19) 9S
20) 8P
21) 7P
22) 6P
23) 5S
24) 4S
25) 3P
26) 2S
27) 1P
28) 0P
29) 29S
ПРИМЕР N 2
Результат приведения
II КНФ к форме ДНФ:
0) 0D 1D 2N 3D 4N 5N 6D 7D 8D 9N 10N 11N 12D 13N 14D
15D 16N 17N 18D 19D 20D 21D 22D 23N 24D 25N 26N 27D 28D 29N