Булева алгебра (1023551), страница 4

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

Текст из файла (страница 4)

наборы

х₀ → х₁ = f

1) 0 → 0 = а₀ ⊕ а₁ 0 ⊕ а₂ 0 ⊕ а₃ 0 0 = а₀ = 1;

2) 0 → 1 = а₀ ⊕ а₁ 0 ⊕ а₂ 1 ⊕ а₃ 0 1 = а₀ ⊕ а₂= 1;

3) 1 → 0 = а₀ ⊕ а₁ 1 ⊕ а₂ 0 ⊕ а₃ 1 0 = а₀ ⊕ а₁= 0;

4) 1 → 1 = а₀ ⊕ а₁ 1 ⊕ а₂ 1 ⊕ а₃ 1 1 = а₀ ⊕ а₁ ⊕ а₂ ⊕ а₃ = 1.

из 1) а₀ = 1; из 2) 1⊕ а₂ = 1⇒а₂ = 0; из 3) 1 ⊕ а₁ = 0 ⇒ а₁ = 1;

из 4) 1 ⊕ 1 ⊕ 0 ⊕ а₃ = 1 ⇒ а₃ = 1.

Построение полинома Жегалкина по ДНФ и КНФ

В ДНФ или КНФ исключаются операции дизъюнкции и отрицания по правилам:

x v y = x y xy; ;

раскрываются скобки и удаляются некоторые члены по правилам:

Пример.

Построение полинома Жегалкина по СДНФ

• Вместо v записываем ⊕.

• Исключаем отрицания, полагая .

• Раскрываем скобки.

• Приводим подобные члены.

Почему v заменяем ⊕?

в СДНФ всегда есть члены и или или т.д.

Поэтому при преобразовании дизъюнкции AvB = A B AB получаем в произведении АВ такое выражение = 0.

Классы логических функций

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

Первый класс составляют функции, сохраняющие константу 0,

то есть функции y=ƒ(x_n-1; x_n-2;…; x₀)= ƒ(0;0;…;0)=0.

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

Второй класс составляют функции, сохраняющие константу 1, то есть функции y=ƒ(x_n-1; x_n-2;…; x₀)= ƒ(1;1;…;1)=1. Как и в предыдущем случае, имеется булевых функций, сохраняющих константу 1. В табл. 2 таковыми являются все функции с нечетными индексами.

Третий класс составляют самодвойственные функции.

Булевы функции

и

называются двойственными друг другу, если

и, разумеется,

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

Если логическая единица кодируется более высоким (более положительным) потенциалом, то такой способ кодирования называется положительной логикой. (Такой способ кодирования применяется для схем, выполненных на биполярных n-p-n, n-МОП или КМОП-транзисторах.) Если же логическая единица кодируется менее высоким (менее положительным) потенциалом, то такой способ кодирования называют отрицательной логикой. (Такой способ кодирования применяется для схем, выполненных на элементах ЭСЛ.)

Пусть мы имеем логический элемент, выполняющий функцию y´=x₁x₀ в положительной логике. Какую функцию он будет выполнять в отрицательной логике? Очевидно, что это будет или

являются двойственными по отношению друг к другу функциями.

Булева функция называется самодвойственной, если она двойственна по отношению к себе самой, то есть выполняется соотношение

Если, например, при n = 3, наборы 010 и 101 называть противоположными (инверсными) наборами, то тогда можно дать следующее определение самодвойственной функции: булева функция называется самодвойственной, если на любых противоположных наборах она принимает противоположные значения. При расположении наборов в естественном (линейном, лексикографическом) порядке, как в табл. 2, противоположные друг другу наборы расположены симметрично относительно середины столбцов. Следовательно, столбец значений самодвойственной функции должен быть антисимметричен своей середины. Для ‘n’ переменных существует таких столбцов значений функций и, следовательно, столько же будет самодвойственных функций.

При n = 2 существует четыре самодвойственные функции. В табл. 2 таковыми являются y₃; y₅; y₁₀ и y₁₂ .

Четвертый класс составляют линейные функции. Булева функция называется линейной, если ее полином Жегалкина можно представить в виде:

где могут принимать значения 0 и 1, а так как всего этих коэффициентов n + 1, то может существовать 2ⁿ⁺¹ наборов коэффициентов и соответственно линейных булевых функций от ‘n’ переменных. В табл. 2 таковыми являются:

П
ятый класс булевых функций составляют монотонные функции. Булева функция называется монотонной, если для любых пар наборов для которых выполняется отношение предшествования, справедливо неравенство

При n = 2 существуют следующие последовательности наборов с отношением предшествования: 00-01-11 и 00-10-11, а наборы 01 и 10 несравнимые.

Любая монотонная ФАЛ может быть представлена в форме, которая не содержит переменных с отрицанием.

Для рассмотренных выше четырех классов легко вычисляется число всех функций, принадлежащих к данному классу. Определение же числа всех монотонных функций от ‘n’ переменных оказывается очень сложным. Эта задача в общем случае, по-видимому, не решена до сих пор. Известна формула для вычисления числа F_m монотонных функций только для n ≤ 3: F_m=2+n∙n!. При n = 2 F_m=6. В табл. 2 таковыми функциями являются: .

При n = 4 F_m = 168 (точное значение), при n =5 F_m = 7581 (оценочное значение), при n =6 F_m = 7828354.

Теорема о функциональной полноте

Теперь сформулируем основную теорему булевой алгебры – теорему о функциональной полноте.

Для того чтобы система булевых функций была функционально полной необходимо и достаточно, чтобы эта система содержала

хотя бы одну функцию, не сохраняющую константу 0,

хотя бы одну функцию, не сохраняющую константу 1,

хотя бы одну несамодвойственную функцию,

хотя бы одну нелинейную функцию и

хотя бы одну немонотонную функцию.

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

Табл. 4 подтверждает, что каждая из систем функций

И, ИЛИ, НЕ;

И, НЕ;

ИЛИ, НЕ

является функционально полной, причем первая система избыточна.

Минимальная функционально полная система, то есть такая полная система функций, удаление из которой любой функции делает систему неполной, называется базисом.

ЭВМ первого и второго поколений строились в базисе И, ИЛИ, НЕ. Начиная с ЭВМ третьего поколения, кроме базиса И, ИЛИ, НЕ; широко используются базисы И‑НЕ и ИЛИ‑НЕ.

Таблица 4

Минимизация функций алгебры логики

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

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

Пример. ФАЛ, заданную таблицей истинности (табл. 5), можно представить следующими выражениями

, (9)

Характеристики

Список файлов книги