Главная страница
Образовательный портал Как узнать результаты егэ Стихи про летний лагерь 3агадки для детей
qrcode

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


Название2. элементарные булевы функции совершенные формы булевых функций алгебраическая минимизация Суперпозиция бф
Анкорраздел 2.doc
Дата27.09.2017
Размер357 Kb.
Формат файлаdoc
Имя файлараздел 2.doc
ТипДокументы
#20848
КаталогОбразовательный портал Как узнать результаты егэ Стихи про летний лагерь 3агадки для детей
Образовательный портал Как узнать результаты егэ Стихи про летний лагерь 3агадки для детей


2. ЭЛЕМЕНТАРНЫЕ БУЛЕВЫ ФУНКЦИИ.

совершенные формы БУЛЕВЫХ ФУНКЦИЙ.

алгебраическая минимизация
2.1. Суперпозиция БФ
Функция h(x) называется композицией функций f и g, если имеет место равенство h(x)=g(f(x)). Композиция f и g представляет собой последовательное применение этих функций, т. е. g применяется к результату f. Говорят, что функция h получена подстановкой f в g. Например, если в функции g(x1,x2,x3,x4) переменная x3=f(x1,x2), то порождается функция h от трех аргументов h(x1,x2,x4). Суперпозицией функций f1…fm называется функция f, полученная с помощью подстановок этих функций друг в друга с переименованием переменных. Например:
.
Подставляя в функцию y(x1,x2) вместо переменной х2 ее значения, получим новую БФ р(x1,z1,z2):
.
2.2. Основные элементарные булевы функции
Среди множества БФ существует ряд функций, называемых элементарными. Это БФ от двух аргументов. Они являются основой для формирования всех остальных БФ. Напомним, что БФ двух аргументов определяется на 22=4 наборах. Общее число таких БФ равно (22)2=16. Все эти БФ имеют свои имена и свойства. Они представлены в табл. 2.1 (некоторые из них записаны как суперпозиция функций И, ИЛИ, Не).

Рассмотрим БФ из табл. 2.1:

  • f0 – на любом наборе аргументов равна 0 и называется константой нуля, f15 на любом наборе аргументов равна 1 и называется константой единицы. Эти БФ не имеют СДНФ и СКНФ;

  • f1 – функция И описывает логическое произведение –конъюнкцию переменных x1x2;

  • f7 – функция ИЛИ описывает логическую сумму, или дизъюнкцию переменных x1+x2;

  • f6 – функция «сумма по модулю два», или неравнозначность, или исключающее ИЛИ. Эта функция принимает единичные значения только тогда, когда переменные противоположны. Ее можно записать как суперпозицию функций И, ИЛИ, Не в форме ДНФ:

;

  • f8 – стрелка Пирса или функция ИЛИ-Не: ;

  • f9 – функция эквивалентность или равнозначность, принимает единичные значения при равенстве переменных:

;

  • f14 – штрих Шеффера или функция И-Не: .

Остальные функции будут рассмотрены по мере их необходимости.

Все булевы функции могут быть представлены как суперпозиция элементарных БФ.

Таблица 2.1

Элементарные булевы функции


Обозначение логических операций

Таблица

истинности

Название операции

основные

дополнительные

X1

0

0

1

1

X2

0

1

0

1

-

-

f0

0

0

0

0

константа ноль

х1х2


x12

x1Λх2

f1

0

0

0

1

конъюнкция, логическое И,

логическое произведение,

логическое умножение






f2

0

0

1

0

запрет по X1,

отрицание импликации

-

-

f3

0

0

1

1

повторение Х1






f4

0

1

0

0

запрет по X2,

отрицание импликации

-

-

f5

0

1

0

1

повторение Х2







f6

0

1

1

0

сложение по модулю 2, функция неравнозначности, импликация,

исключающее ИЛИ





х12

f7

0

1

1

1

дизъюнкция, логическое ИЛИ,

логическое сумма








f8

1

0

0

0

стрелка Пирса, функция ИЛИ-Не

х1 х2


x1 ≡ x2


f9

1

0

0

1

Эквивалентность,

функция равнозначности

-

-

f10

1

0

1

0

нет имени

-

-

f11

1

0

1

1

нет имени

-

-

f12

1

1

0

0

нет имени

x1 → x2



f13

1

1

0

1

импликация


x1 │ x2




f14

1

1

1

0

штрих Шеффера, функция И-Не

-

-

f15

1

1

1

1

константа единица
2.3. Совершенные формы булевых функций
Наборы логических переменных х1х2…хn, на которых БФ принимает единичные значения f(х12,…,хn)=1, называют единичными наборами. Наборы логических переменных х1х2…хn, на которых БФ принимает нулевые значения f(х12,…,хn)=0, называют нулевыми наборами.

Конъюнкцией называется логическое произведение произвольного числа аргументов. Конъюнкция называется элементарной, если она содержит любое количество попарно различимых букв в прямой или инверсной форме. Например, конъюнкция является элементарной, а вот конъюнкция не является элементарной. Назовем рангом R элементарной конъюнкции количество входящих в нее букв. Две конъюнкции назовем соседними, если они зависят от одних и тех же аргументов, имеют одинаковый ранг и отличаются знаком инверсии только одного аргумента (например, ). Длиной функции L назовем сумму рангов всех входящих в функцию конъюнкций (т. е. количество букв в формуле). Дизъюнктивной нормальной формой (ДНФ) БФ назовем дизъюнкцию (логическую сумму) конечного множества попарно различимых элементарных конъюнкций:


Функция ДНФ не является.

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

Дизъюнкцией называется логическая сумма произвольного числа аргументов. Дизъюнкция называется элементарной, если она содержит любое количество попарно различимых букв в прямой или инверсной форме. Например, дизъюнкция является элементарной, а вот дизъюнкция не является элементарной. Назовем рангом R элементарной дизъюнкции количество входящих в нее букв. Две дизъюнкции назовем соседними, если они зависят от одних и тех же аргументов, имеют одинаковый ранг и отличаются знаком инверсии только одного аргумента (например, ). Длиной функции L назовем сумму рангов всех входящих в функцию дизъюнкций, т. е. количество букв в формуле. Конъюнктивной нормальной формой (КНФ) БФ назовем конъюнкцию (логическое произведение) конечного множества попарно различимых элементарных дизъюнкций:

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


2.4. Переход от табличного способа задания БФ

к аналитическому
Пусть БФ f1 и f2 заданы табл. 2.2:

Таблица 2.2

Таблица истинности функций f1,f2,f3

X1

X2

X3

f1

f2

f3

0

0

0

1

0

1

0

0

1

0

0

1

0

1

0

0

1

1

0

1

1

1

0

0

1

0

0

0

1

1

1

0

1

1

1

1

1

1

0

1

0

1

1

1

1

1

0

0


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

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

  2. конституента единицы записывается как логическое произведение переменных, причем, если переменная в наборе имеет значение 1, то она записывается в прямом виде, а если 0, то в инверсном, например СДНФ f1 будет иметь вид:


.
БФ f2 из табл. 2.2 представим в КНФ. Из таблицы можно получить только СКНФ. БФ записывается как логическое произведение конституент нуля. Для получения аналитического выражения БФ:

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

  2. конституента нуля записывается как дизъюнкция переменных, причем, если переменная в наборе имеет значение 0, то она записывается в прямом виде, а если 1, то в инверсном, например f2 будет иметь вид:


.
Следует уяснить, что СДНФ и СКНФ это просто разные формы БФ, и одна и та же БФ может быть записана в любой из них. Например, пусть БФ Z задана табл. 2.3.
Таблица 2.3

Таблица истинности функции Z

X1

X2

Z

0

0

0

0

1

1

1

0

1

1

1

0


Запишем эту функцию в обеих формах:


В формуле СКНФ раскроем скобки и применим закон поглощения:

т. е. совпадает с СДНФ.

Если функция задана алгебраически, то может быть восстановлена таблица истинности. Например, задана функция Р:

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

Вычисленные значения функции заносятся в таблицу (табл. 2.4).
Таблица 2.4

Восстановленная таблица истинности функции Р

Х1

Х2

Х3

Р

0

0

0

0

0

0

1

0

0

1

0

0

0

1

1

0

1

0

0

1

1

0

1

1

1

1

0

1

1

1

1

0



По табл. 2.4 можно записать СДНФ:

Для функции R, заданной в конъюнктивной форме
,
вычислены значения функции, которые занесены в табл. 2.5:

Таблица 2.5

Восстановленная таблица истинности функции R

Х1

Х2

R

0

0

1

0

1

0

1

0

0

1

1

0




2.5. Применение законов склеивания для минимизации

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

  1. склеиванию подлежат только соседние конституенты единицы. В результате склеивания образуется конъюнкция, называемая импликантой. Импликанта, полученная склеиванием двух конъюнкций, ранг которых равен R, имеет ранг R-1;

  2. одна и та же конституента единицы может принимать участие в нескольких операциях склеивания;

  3. к полученным импликантам опять применяется операция склеивания (до тех пор, пока это возможно);

  4. БФ записывается, как дизъюнкция полученных импликант.

Исходя из этого для БФ f1 из табл. 2.2
:


  • первая конъюнкция не склеивается ни с одной другой;

  • вторая склеивается с пятой ;

  • третья – с пятой ;

  • четвертая – с пятой ;

  • полученные конъюнкции больше не могу быть склеены.

БФ f1 запишется как:
,
т. е. очевидно, что полученная ДНФ короче, чем исходная СДНФ.

Алгоритм минимизации БФ, заданной в форме СКНФ:

  1. склеиванию подлежат только соседние конституенты нуля. В результате склеивания образуется дизъюнкция, которая имеет ранг R-1;

  2. одна и та же дизъюнкция может принимать участие в нескольких операциях склеивания;

  3. к полученным дизъюнкциям опять применяется операция склеивания (до тех пор, пока это возможно);

  4. БФ записывается, как произведение полученных дизъюнкций.

Минимизация БФ f2 из табл. 2.2


  • первая дизъюнкция склеивается со второй

;

  • вторая склеивается с третьей ;

  • четвертая – с пятой ;

  • к полученным дизъюнкциям операция склеивания уже не применима, поэтому БФ f2:


,
т. е. очевидно, что полученная КНФ короче, чем исходная СКНФ.

Для f2 операции склеивания можно выполнить и по-другому:

  • первую – со второй, четвертую – с пятой, как и в первом случае;

  • а вот третью можно склеить не со второй, а с пятой





  • полученные дизъюнкции не могу быть склеены, поэтому можно записать:


.
Оба варианта функции f2 имеют одинаковую длину L=6, поэтому они равноценны.

2.6. Применение законов поглощения для минимизации

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

Применим закон склеивания к первой и второй конъюнкции:


В соответствии с законом поглощения (переменная х1 поглощает все конъюнкции, содержащие х1):

Для функции P:

2.7. Понятие фиктивной переменной
Любая переменная Хк в БФ называется несущественной, или фиктивной, если выполняется условие:
,
т. е. переменная изменяет свое значение на любом наборе остальных аргументов, но это не сказывается на значении БФ. Фактически, такая БФ, зависит от n -1 аргументов. В таблице истинности столбец несущественной переменной можно удалить. Например, БФ f3 (табл. 2.2) имеет следующую СКНФ:
.
После выполнения склеивания по х1 она будет иметь вид:
,
т. е. f3 не зависит от переменной х1.

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

Умножая каждую конъюнкцию на сумму той переменной и ее инверсии, которые отсутствуют в данной конъюнкции, можно получить СДНФ функции В от переменных х123:

Такие же преобразования можно выполнить и с БФ, заданной в КНФ. Например, КНФ функции сначала преобразована в СКНФ, а затем в нее добавлена переменная х3:

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

Однако введем в первую конъюнкцию недостающую переменную х1 и проведем склеивание:






перейти в каталог файлов

Образовательный портал Как узнать результаты егэ Стихи про летний лагерь 3агадки для детей

Образовательный портал Как узнать результаты егэ Стихи про летний лагерь 3агадки для детей