Определение. Будем говорить, что строка таблицы Квайна покрывает столбец, если она содержит единицу в этом столбце.
Пример. Строка H покрывает второй, третий, шестой и восьмой столбцы таблицы Q. •
Определение. Покрытием таблицы Квайна назовем подмножество таких ее строк, которые в совокупности покрывают все столбцы таблицы.
Примеры. Покрытиями таблицы Q являются: все восемь ее строк; семь строк: A,B,C,D,F,G,H, первые шесть строк; первые пять строк; однако не удается найти ни одного четырехстрочного покрытия. •
Любое покрытие таблицы Квайна функции f(x1, …, xn) задает ее достаточное подмножество максимальных интервалов. Другими словами, любое покрытие таблицы Квайна задает ДНФf. В частности, покрытие, состоящее из всех строк таблицы, задает сокращенную ДНФ.
Определение. Длиной покрытия назовем количество строк, образующих покрытие.
Примеры. Длины покрытий из предыдущего примера равны соответственно 8, 7, 6 и 5. •
Определение. Покрытие таблицы Квайна называется безызбыточным, если при удалении из него хотя бы одной строки оно перестает быть покрытием.
Примеры. Множество из первых шести строк таблицы Квайна Q не является безызбыточным покрытием, поскольку при удалении шестой строки оно остается покрытием. Первые пять строк образуют безызбыточное покрытие, и оно не единственное – шесть строк A,B,C,D,F,G тоже образуют безызбыточное покрытие. •
В общем случае таблица Квайна функции f(x1, …, xn) имеет несколько безызбыточных покрытий, и любое безызбыточное покрытие задает безызбыточную ДНФf, так как из нее нельзя выбросить ни одной конъюнкции (из безызбыточного покрытия нельзя выбросить ни одной строки) и ни одной буквы из какой-либо конъюнкции (строкам приписаны простые импликанты) так, чтобы полученная ДНФ оставалась равносильной исходной ДНФ.
Определение. Кратчайшим покрытием таблицы Квайна назовем покрытие минимальной длины.
Примеры. Первые пять строк таблицы Квайна Q, а также пять строк A,B,F,G,H образуют ее кратчайшие покрытия. •
Очевидно, что каждое кратчайшее покрытие таблицы Квайна функции f(x1, …, xn) задает кратчайшую ДНФf.
Определение. Рангом строки таблицы Квайна назовем ранг приписанной ей простой импликанты.
Пример. Ранг строки H (конъюнкции c d) таблицы Квайна Q равен двум, ранги остальных строк равны трем. •
Определение. Минимальным покрытием таблицы Квайна назовем покрытие с минимальной суммой рангов строк.
Пример. Строки A,B,F,G,H таблицы Квайна Q образуют минимальное покрытие, так как сумма их рангов равна 14, а все остальные покрытия имеют больший суммарный ранг строк. •
Нетрудно видеть, что минимальное покрытие таблицы Квайна функции f(x1, …, xn) задает минимальную ДНФf.
Таким образом, задача минимизации булевой функции решается построением таблицы Квайна и поиском ее кратчайших или минимальных покрытий (в зависимости от постановки задачи).
Отвлечемся на время от задачи минимизации и покажем, что совсем иные задачи сводятся к поиску тех или иных покрытий булевых матриц.
Задача 1. Пусть в некотором устройстве возможны 10 неисправностей, и пусть имеется 8 тестов, каждый из которых обнаруживает свое подмножество неисправностей:
| Тесты: | A | B | C | D | E | F | G | H |
| Неисправности: | 1, 2 | 3, 4 | 5, 6 | 8, 9 | 7, 10 | 5, 7 | 9, 10 | 2, 3, 6, 8 |
Требуется подобрать кратчайший полный тест, то есть набор из минимального числа тестов, обнаруживающих все неисправности.
Построим матрицу, строкам которой припишем тесты, а столбцам – неисправности. Элемент матрицы, стоящий на пересечении i-й строки и j-го столбца, положим равным единице тогда и только тогда, когда i-й тест обнаруживает j-ю неисправность.
Матрица полностью совпадает с таблицей Q, а ее кратчайшее покрытие является решением задачи о кратчайшем полном тесте.
Пусть теперь проверка каждого теста требует определенных временных затрат, например, тест H требует двух единиц времени, а остальные – трех. Тогда имеет смысл искать минимальный полный тест, то есть набор тестов, который обнаруживает все неисправности за минимальное время. Решение задачи сводится к поиску минимального покрытия той же матрицы, если рангом строки считать временные затраты на проверку теста.
Задача 2. Имеется группа переводчиков с иностранных языков на русский. О каждом переводчике известно, какими иностранными языками он владеет. Требуется выбрать минимальное число переводчиков, знающих в совокупности все языки. И снова мы приходим к мысли о построении булевой матрицы и поиске ее кратчайшего покрытия.
Учитывая это, будем абстрагироваться от задач, породивших матрицы, и говорить лишь об их строках, столбцах и элементах.