Основной базис алгебры логики

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

Логические функции, представляющие собой дизъюнкции от­дельных членов, каждый из которых, в свою очередь, есть неко­торая функция, содержащая только конъюнкции и инверсии, называются логическими функциями дизъюнктивной формы. Форма представления дизъюнктивной функции, в которой инверсия при­меняется лишь непосредственно к аргументам, но не к более сложным функциям этих аргументов, называется дизъюнктивной нор­мальной формой (ДНФ) представления функций. Если же каждый член ДНФ от п аргументов содержит все эти п аргументов (с инверсией или без нее), то такая форма представления функции называется совершенной дизъюнктивной нормальной формой (СДНФ).

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

Возможность записи функций в дизъюнктивных и конъюнк­тивных формах определяется исходя из следующего. Рассмотрим произвольную логическую функцию от п аргументов типа кон­ституенты единицы. Как указывалось ранее, конституента едини­цы полностью определяется заданием набора, обращающего ее в 1. В этом наборе некоторые аргументы могут быть равны 1, а осталь­ные равны 0. Составим конъюнкцию от всех п аргументов, причем те из аргументов, которые в указанном наборе равны 0, возьмем с инверсией, а аргументы, равные 1, — без инверсии. Если все аргументы будут соответствовать заданному набору, то при нем функция обратится в конъюнкцию п единиц и будет равна 1. Для всех остальных наборов хотя бы один член конъюнкции, а зна­чит, и вся конъюнкция обратится в 0. Таким образом, произволь­ная функция от п аргументов типа конституенты единицы может быть выражена через конъюнкцию и инверсию.

Переход от табличного задания функции к записи в виде СДНФ выполняется в такой последовательности:

в таблице задания функции выбираются все наборы аргумен­тов, при которых функция обращается в 1;

выписываются конъюнкции, соответствующие этим наборам аргументов. Если аргумент х,- входит в данный набор как 1, то он вписывается без изменения в конъюнкцию, соответствующую данному набору; если же х,- входит в данный набор как 0, то в соответствующую конъюнкцию вписывается его отрицание;

все полученные конъюнкции соединяются между собой знака­ми дизъюнкции.

Аналогично выполняется переход от табличного задания функ­ции к записи в виде СКНФ:

в таблице задания функции выбираются все наборы аргумен­тов, при которых функция обращается в 0;

выписываются дизъюнкции, соответствующие этим наборам аргументов. Если аргумент х,- входит в данный набор как 0; он вписывается без изменения в дизъюнкцию, соответствующую дан­ному набору; если же х, входит в данный набор как 1, то в соот­ветствующую дизъюнкцию вписывается его отрицание;

все полученные дизъюнкции соединяются между собой знака­ми конъюнкции.

Выбор той или иной формы аналитической записи определя­ется видом таблицы заданной функции. Если большинство значе­ний данной функции 0, то выгодно записывать ее в СДНФ, в противном случае более экономную запись дает СКНФ.

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

Базис из дизъюнкции, конъюнкции и инверсии не является минимальным. Поскольку конъюнкцию можно представить через инверсию и дизъюнкцию, то можно получить минимальный ба­зис из дизъюнкции и инверсии. С другой стороны, дизъюнкцию можно представить через инверсию и конъюнкцию, т.е. получить минимальный базис из конъюнкции и инверсии.

Возможны и другие минимальные базисы, например из конъ­юнкции и инверсии. Каждая из функций Пирса и Шеффера также составляет полную систему и представляет собой минимальный базис. Благодаря тому, что любую, сколь угодно сложную логи­ческую функцию можно реализовать с помощью малого числа типов логических операций (например, только дизъюнкции и инверсии), самые сложные электросхемы могут быть постро­ены из однотипных элементов. Таких элементов потребуется очень много, но при массовом производстве они будут очень дешевы. К тому же наладить массовое производство всего одного или двух типов элементов значительно дешевле, чем большого числа ти­пов. Особенно это важно при производстве больших интеграль­ных схем.

Поиск по сайту: