§ 6.2. Применение ЭВМ для построения сокращенного базиса

В § 6.1 было показано, как при помощи ЭВМ, опираясь на сокращенный базис находить решение специальной логической задачи по определению следствий, вытекающих из некоторого заданного набора посылок. Изложим ряд алгоритмов, которые позволят применять ЭВМ также и для построения сокращенного базиса, связанного с исходными логическими зависимостями, наложенными на элементы

Алгоритм получения произведения двух булевых функций. Пусть требуется найти произведение функции на функцию Представим каждую из функций либо в ДНФ, либо в форме простейшей суммы произведений и трансформируем каждое слагаемое в колонку таблицы или соответственно, заполнив разряды колонок числами 0, 1 и знаком X по тем же самым правилам, которые использовались в § 6.1 при построении сокращенного базиса по функции Предположим, что таблицы и размещены в ЭВМ так, как показано на рис. 6.1. Пусть порядковые номера каких-либо колонок в таблицах соответственно. В соответствии с определением соотношения импликации условимся писать если в колонке все разряды, содержащие 0 или 1, совпадают с соответствующими

разрядами колонки а. Если то будем писать так как в этом случае колонки полностью совпадают. Проделаем следующие операции:

1. Колонку а таблицы поразрядно сравним с колонкой таблицы

Если то колонки вычеркиваются из таблиц и одновременно одна из этих колонок, например а, заносится в таблицу результатов далее переходим к сравнению колонки таблицы с первой колонкой таблицы

Если то колонка а вычеркивается из таблицы и заносится в таблицу результатов колонка сохраняется в таблице далее переходим к сравнению колонки таблицы с первой сохранившейся колонкой таблицы

Рис. 6.1

Если то колонка вычеркивается из таблицы и заносится в таблицу результатов колонка а сохраняется в таблице переходим к сравнению колонки с первой колонкой таблицы

Если то переходим к сравнению колонки а табл. с колонкой табл.

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

2. Перемножим таблицы Сначала умножается колонка а таблицы на колонку таблицы Если колонки а и несравнимы, т. е. хотя бы в одном из одинаковых разрядов колонок а и встречаются комбинации чисел 0 и 1 или .1 и 0, то их не перемножают и переходят к умножению колонки а таблицы на колонку таблицы Если колонки а и сравнимы, то их перемножают поразрядно по правилам: Результат умножения представляется в виде колонки, аналогичной колонкам-сомножителям, которая записывается в таблицу Далее умножается колонка а таблицы на колонку таблицы Операции повторяются до тех пор, пока каждая колонка таблицы не будет умножена на каждую колонку таблицы

Таблица результатов представляет произведение функций в ДНФ.

Алгоритм приведения булевой функции к тупиковой ДНФ. Для упрощения таблицы представляющей собой произведение двух булевых функций, каждую колонку а таблицы сравнивают с каждой последующей колонкой этой же таблицы по следующим правилам:

а) если сопоставляемые колонки полностью совпадают: то одна колонка, например колонка а, сохраняется в таблице, а другая колонка, например отбрасывается; переходим к сравнению колонки а с колонкой

б) если то колонка а отбрасывается, а колонка а Я сохраняется; переходим к срайнению колонки с колонкой

в) если то колонка отбрасывается, а колонка сохраняется; переходим к сравнению колонки а с колонкой а

г) если две сопоставляемые колонки совпадают во всех разрядах, кроме одного, и в этом разряде одна колонка содержит 0, а другая 1, то обе колонки отбрасываются и заменяются одной колонкой, которая совпадает в общей части разрядов со сравниваемыми колонками, а в том разряде, где содержались 0 и 1, ставится знак

д) если сопоставляемые колонки а и несравнимы только в разряде, а содержимое остальных разрядов таково, что для колонок и получающихся из и вычеркиванием разряда, выполняется , то колонки а и сохраняются, но в разряде колонки записывается знак переходим к сравнению колонки а с колонкой

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

Алгоритм получения отрицания булевой функции. Пусть требуется найти отрицание булевой функции записанной в ДНФ. Как и раньше, будем предполагать, что функция представлена в виде таблицы колонки которой образованы из чисел О, 1 и знака Проделаем следующие операции:

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

2. Пусть колонка таблицы содержит разрядов с числами 0 или 1, а в остальных разрядах этой колонки стоит знак -Преобразуем каждую колонку таблицы в таблицу из колонок. Все колонки таблицы имеют только один

разряд с числом 0 или 1 в соответствии с содержимым данного разряда в колонке таблицы а в остальных разрядах колонок таблицы стоит знак

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

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