Определение минимального базиса

Рассмотрим на примере системы И, ИЛИ, НЕ удаление «лишних» функций из заданной системы логических функций, т.е. получение минимального базиса.

Обозначим:

– функцию НЕ символом a,

– функцию И символом b,

– функцию ИЛИ символом c.

Отсутствие свойств, заданных табл. 16, обозначим в табл. 17 символом 1.

Анализируя табл. 17, отмечаем:

Обеспечить свойство «не сохранять 0» может только функция a. На это указывает символ 1 в графе «Не сохраняющая 0» строки a и отсутствие 1 в этой графе в строках b и c.

Обеспечить свойство «не сохранять 1» может только функция a. На это указывает 1 в графе «Не сохраняющая 1» строки a и отсутствие 1 в этой графе в строках b и c .

Обеспечить свойство «не быть самодвойственной» может функция b или функция c. Помечено символами 1 в строках b и c.

Обеспечить свойство «не быть монотонной» может только функция a. Помечено символом 1 в строке a.

Обеспечить свойство «не быть линейной» может функция b или функция c. Помечено символами 1.

Приняв такие обозначения, условия полноты системы логических функций на основе табл. 17 можно сформулировать следующим образом.

Чтобы система функций была функционально полна, необходимо наличие всех пяти свойств:

1. «не сохранять 0», и

2. «не сохранять 1», и

3. «не быть самодвойственной», и

4. «не быть монотонной», и

5. «не быть линейной».

Используя номера свойств как логические переменные и заменив союз И символом конъюнкции, условие полноты системы функций можно записать так

= «1».

Если в таблице, аналогичной табл. 17, со свойствами функций, входящих в систему, в каком либо столбце нет 1, то это означает, что заданная система логических функций не является полной.

Для выявления «лишних» функций, заменив в рассуждениях союз ИЛИ символом логической операции, а логические функции их обозначениями, запишем условие полноты рассматриваемой системы логических функций в виде формулы

= = «1»

и проведем ее преобразование

= «1».

Здесь «1» означает «истину».

В результате преобразований получено тождество, левая часть которого содержит исходную формулу, а правая часть представляет собой дизъюнкцию двух конъюнкций, содержащих по две переменных. Правая часть будет равна 1 при равенстве 1 хотя бы одной любой конъюнкции, что происходит только тогда, когда в строках таблицы, соответствующих парам функций ( ) и ( ) имеются 1 во всех пяти столбцах. Следовательно, в качестве функционально полной системы можно рассматривать функции НЕ и И ( ) или НЕ и ИЛИ ( ). Каждая пара этих функций покрывает единицами все столбцы табл. 17, т.е. обладает всеми необходимыми свойствами.

Здесь мы рассмотрели типичную задачу о покрытии, которая в общем виде формулируется следующим образом:

Имеется таблица нулей и единиц, содержащая m строк и n столбцов.

Строки имеют имена a_i, i = 1,m, столбцы имеют имена b_j, j = 1,n.

Требуется определить минимальное число строк (и какие строки), единицы в которых покрывают все столбцы (содержатся во всех столбцах).

Решение этой задачи ищется следующим образом.

Составляется логическая формула в виде конъюнкции n дизъюнкций.

Если дизъюнкций меньше n, то покрытия (решения) не существует.

Каждая дизъюнкция соответствует отдельному столбцу таблицы и состоит из имен строк, имеющих единицы в данном столбце, соединенных символом дизъюнкции.

После раскрытия скобок и минимизации получается дизъюнктивная нормальная форма в виде дизъюнкции конъюнкций. Каждый терм этой формулы представляет решение задачи.

В нашем примере таблица получилась достаточно простой и никаких затруднений работа с ней не вызвала. При решении других задач, например, при построении тестов логических схем методом таблиц функций неисправностей приходится иметь дело с таблицами большой размерности, что заставляет искать средства для их сокращения.

Сокращение таких таблиц (их называют таблицами покрытий) производится из следующих соображений:

1. Исключаются столбцы, содержащие единицы во всех строках, – эти столбцы будут покрыты в любом случае.

2. Исключаются строки, не содержащие единиц, – эти строки не покрывают никаких столбцов.

3. Строка с единицами во всех столбцах – это решение задачи покрытия, поэтому все остальные строки можно исключить.

4. Из групп одинаковых столбцов оставить только по одному представителю.

5. Из групп одинаковых строк оставить только по одному представителю.

6. Строка, в которой в каком–либо столбце имеется единица, единственная в этом столбце, должна войти в решение, так как только она покрывает этот столбец; после ее включения в решение, исключаем другие столбцы, имеющие единицы в этой строке.

7. Перенося идею предыдущего пункта на множество единиц в столбцах, приходим к возможности исключения столбца j, множество единиц которого покрывает множество единиц столбца i. (Какая либо из строк с единицей в столбце i войдет в решение, но в этой же строке имеется единица и в столбце j.)

8. Количество единиц в строке может служить мерой ее эффективности. Если единицы какой–либо строки j покрываются единицами строки i, то строку j можно исключить, так как строка i более эффективна.

Если таблицу 16 преобразовать к виду таблицы 17, то окажется, что

– в строках функций f₁ и f₇ единицы во всех столбцах, следовательно, каждая из них является решением – полной системой функций;

– в строках функций f₁₀, f₁₂ нет ни одной единицы и их можно исключить;

– из пар функций f₂ – f₄ , f₃ – f₅, f₁₁ – f₁₃ и f₈ – f₁₄ следует оставить по одной функции, так как у функций каждой пары строки одинаковы.

В результате в таблице останется только 8 функций: f₀, f₄, f₅, f₆, f₉, f₁₃, f₁₄, f₁₅, (см. табл. 18) из которых можно получить 8 полных систем из двух функций.

Вот они: f₀ – f₁₃ , f₄ – f₅, f₄ – f₉, f₄ – f₁₃, f₄ – f₁₅ , f₅ – f₁₃, f₅ – f₁₄ и f₆ – f₁₃.

Таблица 18
Свойства функций двух переменных, разбивающие их на классы
Функция	Не сохраняет «0»	Не сохраняет «1»	Не само–двойственная	Не монотонная	Не линейная
	+			+	+
	+
			+		+
	+				+
		+			+
		+
	+	+		+
		+		+	+

(С учетом «двойников» можно получить 24 полных системы из двух функций двух переменных.)