Funktsii_algebry_logiki

Федеральное агентство по образованию
Тверской государственный технический университет







Т.В. Асеева



Функции алгебры логики

Учебное пособие


Первое издание


























Тверь 2006



УДК 510(075.8)


ББК22.12я7



Асеева Т.В. Функции алгебры логики: учебное пособие, 1-е изд. Тверь: ТГТУ, 2006, 12 с.




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




















( Тверской государственный
технический университет, 2006

Содержание
13 TOC \o "1-3" \h \z \u 1413 LINK \l "_Toc152350342" 14Функции алгебры логики 13 PAGEREF _Toc152350342 \h 1441515
13 LINK \l "_Toc152350343" 14Булевы векторы и единичный n-мерный куб 13 PAGEREF _Toc152350343 \h 1441515
13 LINK \l "_Toc152350344" 14Функции алгебры логики (булевы функции) 13 PAGEREF _Toc152350344 \h 1441515
13 LINK \l "_Toc152350345" 14Элементарные булевы функции 13 PAGEREF _Toc152350345 \h 1451515
13 LINK \l "_Toc152350346" 14Теорема Шеннона о разложении булевых функций по переменным 13 PAGEREF _Toc152350346 \h 1461515
13 LINK \l "_Toc152350347" 14Частично определенные булевы функции 13 PAGEREF _Toc152350347 \h 1471515
13 LINK \l "_Toc152350348" 14Минимизация булевых функций в классе ДНФ 13 PAGEREF _Toc152350348 \h 1471515
13 LINK \l "_Toc152350349" 14Табличные методы минимизации булевых функций 13 PAGEREF _Toc152350349 \h 1481515
13 LINK \l "_Toc152350350" 14Диаграммы Вейча 13 PAGEREF _Toc152350350 \h 1491515
13 LINK \l "_Toc152350351" 14Минимизация булевых функций методом симметричных таблиц 13 PAGEREF _Toc152350351 \h 14101515
13 LINK \l "_Toc152350352" 14Метод таблиц различий 13 PAGEREF _Toc152350352 \h 14131515
13 LINK \l "_Toc152350353" 14Функциональная полнота системы булевых функций 13 PAGEREF _Toc152350353 \h 14161515
13 LINK \l "_Toc152350354" 14Операция замыкания и предполные классы 13 PAGEREF _Toc152350354 \h 14171515
13 LINK \l "_Toc152350355" 14Класс функций, сохраняющих 0, Т0 13 PAGEREF _Toc152350355 \h 14181515
13 LINK \l "_Toc152350356" 14Класс функций, сохраняющих 1, Т1 13 PAGEREF _Toc152350356 \h 14191515
13 LINK \l "_Toc152350357" 14Класс самодвойственных функций S 13 PAGEREF _Toc152350357 \h 14191515
13 LINK \l "_Toc152350358" 14Класс монотонных функций М 13 PAGEREF _Toc152350358 \h 14201515
13 LINK \l "_Toc152350359" 14Класс линейных функций L 13 PAGEREF _Toc152350359 \h 14221515
13 LINK \l "_Toc152350360" 14Теорема Поста 13 PAGEREF _Toc152350360 \h 14231515
13 LINK \l "_Toc152350361" 14Список литературы 13 PAGEREF _Toc152350361 \h 14241515
15 Функции алгебры логики
Булевы векторы и единичный n-мерный куб
Множество 13 EMBED Equation.3 1415 называется единичным n-мерным кубом. Упорядоченная последовательность (кортеж) длины n называется вершиной единичного n-мерного куба. Мощность множества вершин единичного n-мерного куба равна 13 EMBED Equation.3 1415 .
На множестве вершин единичного n-мерного куба задаются следующие характеристики:
Вес вектора, равный 13 EMBED Equation.3 1415;
Номер вектора, равный десятичному числу, записанному в двоичной системе счисления: 13 EMBED Equation.3 1415 если разряды двоичного вектора нумеруются справа налево, начиная с 0, т.е. 13 EMBED Equation.3 1415.
Расстояние Хемминга между двумя булевыми векторами, равное числу разрядов, в которых эти векторы различаются, определяемое как 13 EMBED Equation.3 1415. Два вектора 13 EMBED Equation.3 1415 называются соседними, если расстояние Хемминга между ними равно 1, и противоположными, если расстояние Хемминга между ними равно n.
На множестве булевых векторов длины n определено отношение предшествования: 13 EMBED Equation.3 1415. Нетрудно доказать, что отношение предшествования является отношением частичного порядка на множестве вершин единичного n-мерного куба.
Функции алгебры логики (булевы функции)
n-местной булевой функцией называется отображение13 EMBED Equation.3 1415, где n-местность (арность) функции. Это отображение может быть иначе записано как 13 EMBED Equation.3 1415. Переменные 13 EMBED Equation.3 1415 называются пропозициональными переменными.
Множество всех n-местных булевых функций равна 13 EMBED Equation.3 1415. n-местная булева функция может быть представлена таблицей, содержащей 13 EMBED Equation.3 1415 строк, расположенных по возрастанию сверху вниз номера строки. Таким образом, вектор n-местной булевой функции имеет длину 13 EMBED Equation.3 1415. Для задания функции достаточно указать ее вектор, так как последовательность кортежей, обозначающих строку, имеет всегда один и тот же вид. Вектор функции называется логическим значением функции или интерпретацией функции. На каждом наборе значений переменных функция может принять одно из двух значений. Если обозначить множество вершин единичного n-мерного куба, в которых функция равна 1, 13 EMBED Equation.3 1415, а множество вершин, в которых функция принимает значение 0, 13 EMBED Equation.3 1415, то очевидно, что 13 EMBED Equation.3 1415. Для задания полностью определенной булевой функции достаточно указать одно из этих множеств.
Переменная 13 EMBED Equation.3 1415 называется существенной, если выполняется условие: 13 EMBED Equation.3 1415, т.е. существует хотя бы одна пара наборов, соседних по переменной 13 EMBED Equation.3 1415, на которых значения функции различны. В противном случае переменная 13 EMBED Equation.3 1415 называется фиктивной. Фиктивную переменную можно исключить из обозначения функции. При этом длина вектора новой функции будет вдвое меньше длины исходной функции. В теории булевых функций рассматривается отношение равенства булевых функций с точностью до фиктивных переменных. Благодаря этому можно рассматривать при необходимости множество функций одинаковой местности.
Двойственные функции
Функция 13 EMBED Equation.3 1415, определенная как отрицание функции 13 EMBED Equation.3 1415 от отрицания ее аргументов называется двойственной функции 13 EMBED Equation.3 1415: 13 EMBED Equation.3 1415. Согласно определению таблица двойственной функции получается инвертированием столбца функции 13 EMBED Equation.3 1415 и последующим переворачиванием ее. Например,
13 EMBED Equation.3 1415.
Соответствующие таблицы представлены ниже.
x1
x2
x1(x2
13 EMBED Equation.3 1415
13 EMBED Equation.3 1415

0
0
1
0
0

0
1
1
0
1

1
0
0
1
0

1
1
1
0
0

Примеры элементарных двойственных функций:
f
Двойственна
13 EMBED Equation.3 1415

0

1

1

0

x

x

13 EMBED Equation.3 1415

13 EMBED Equation.3 1415

&

(

(

&

Очевидно выполнение тождественного равенства
13 EMBED Equation.3 1415.
Элементарные булевы функции
Элементарными булевыми функциями называются функции с арностью 0, 1 и 2. При этом нужно заметить, что множество функций двух переменных включают в себя все 0-местные и 1-местные функции, в описании которых присутствует две или одна фиктивная переменная соответственно. Множество всех элементарных булевых функций может быть представлено в виде таблицы, содержащей 4 строки и 16 столбцов. Каждый столбец определяет одну из элементарных булевых функций. Наиболее употребимыми являются двуместные функции: {&,(,(,(,(,(,(}, одноместные функции f(x)=x и f(x)=(x, и две 0-местные функции: константа 0 и константа 1, не имеющие ни одной существенной переменной (других таких функций в множестве элементарных булевых функций нет).
Элементарные булевы функции используются для аналитического задания булевых функций произвольной местности формулами. При этом используется принцип суперпозиции функций. Согласно этому принципу формула определяется индуктивно:
Пропозициональная переменная есть формула.
Если А и В формулы, то любое слово А(В – формула, если (({&,(,(,(,(,(,(}. Слово (А также является формулой.
Других формул нет.
Для формулы может быть построена таблица истинности, которая является ее интерпретацией. Говорят, что пропозициональная формула задает булеву функцию. Соответственно, булева функция реализует ту формулу, которая задает функцию. Очевидно, формула задает единственную булеву функцию. Обратное не справедливо.
Формулы, определяемые суперпозицией функций, могут преобразовываться как алгебраические выражения с использованием множества аксиом и тождеств. Основными из них являются аксиомы тождественности (идемпотентности), коммутативности, ассоциативности, дистрибутивности, поглощения, закон двойного отрицания, правило де-Моргана. Целью преобразования формул является приведение их к каноническому виду. В теории булевых функций используются канонические представления: дизъюнктивная нормальная форма (ДНФ), конъюнктивная нормальная форма (КНФ), полиномиальная нормальная форма. (ПНФ). Для выполнения преобразований используется правило подстановки, которое формулируется следующим образом: если формула образована суперпозицией функций над некоторым множеством функций, то замена вхождения какой-либо функции на равносильную ей не меняет логическое значение функции. Это можно представить как 13 EMBED Equation.3 1415, если 13 EMBED Equation.3 1415 с точностью до фиктивных переменных.
Теорема Шеннона о разложении булевых функций по переменным
Первичным термом называется функция
13 EMBED Equation.3 1415
Здесь 13 EMBED Equation.3 1415- пропозициональная переменная, 13 EMBED Equation.3 1415 - пропозициональная константа.
Свойства первичного терма:
13 EMBED Equation.3 1415,
13 EMBED Equation.3 1415.
Функция 13 EMBED Equation.3 1415 называется элементарной конъюнкцией ранга r. Функция 13 EMBED Equation.3 1415 называется элементарной дизъюнкцией ранга r. Элементарная конъюнкция ранга n над множеством всех n переменных называется минтермом или конституентой единицы. Элементарная дизъюнкция ранга n над множеством всех n переменных называется макстермом или конституентой нуля.
Произвольная булева функция n переменных может быть представлена разложением по любому числу 13 EMBED Equation.3 1415 переменных в следующем виде:
13 EMBED Equation.3 1415.
Здесь кратная дизъюнкция берется по всем наборам значений констант 13 EMBED Equation.3 1415, число которых равно 13 EMBED Equation.3 1415. Для упрощения записи разложение производится по m первым переменным функции, хотя теорема справедлива для произвольного выбора переменных.
Одним из следствий этой теоремы является разложение булевой функции по всем переменным:
13 EMBED Equation.3 1415.
Это разложение называется совершенной дизъюнктивной нормальной формой (СДНФ). СДНФ есть дизъюнкция всех конституент единицы данной функции.
Теорема: Произвольная булева функция, не равная тождественно 0, может быть представлена в СДНФ.
Теорема: Произвольная булева функция, не равная тождественно 1, может быть представлена в виде совершенной конъюнктивной нормальной формы (СКНФ), которая записывается как
13 EMBED Equation.3 1415
Теорема доказывается с использованием принципа двойственности. СКНФ есть конъюнкция всех конституент 0 данной функции.
Теорема Произвольная булева функция может быть представлена суперпозицией формул над множеством связок {&, (, (}.
Действительно, если функция не равна тождественно 0 или 1, ее можно представить в СДНФ или в СКНФ. Если функция есть константа 0, ее можно представить как 13 EMBED Equation.3 1415 или как 13 EMBED Equation.3 1415, т.е формулой над тем же множеством связок. Формула над множеством связок {&, (, (} называется булевой формулой.
Кроме двух указанных формул в теории булевых функций используется также совершенная полиномиальная нормальная форма, представляющая собой сумму по модулю 2 всех конституент единицы данной функции.
Например, для трехместной булевой функции, заданной вектором 13 EMBED Equation.3 1415,совершенные нормальные формы имеют вид:
СДНФ=13 EMBED Equation.3 1415;
СКНФ=13 EMBED Equation.3 1415;
СПНФ=((0,2,3,5,7)=13 EMBED Equation.3 1415.
Частично определенные булевы функции
n-местно частично определенной булевой функцией называется отображение 13 EMBED Equation.3 1415.
Множество частично определенных n-местных булевых функций обозначается 13 EMBED Equation.3 1415. Его мощность равна 13 EMBED Equation.3 1415. Частично определенная функция может быть задана указанием двух множеств из множества {N1,N0,Nud}, где N1 и N0(описанные выше единичное и нулевое множества вершин единичного n-мерного куба, а Nud(множество вершин, в которых функция не определена, им соответствует прочерк в векторе функции. При минимизации частично определенных булевых функций формируют единичное множество 13 EMBED Equation.3 1415, которое используют любым описанным выше способом. Затем из множества полученных максимальных интервалов отбирают неприводимые покрытия минимального ранга с помощью импликантной таблицы, в которой учитывают только единичные вершины из множества N1. Очевидно, МДНФ частично определенной функции является полностью определенной. В вершинах из множества N0 и N1 значения МДНФ совпадают со значениями исходной частично определенной функции. В вершинах, в которых функция не определена, МДНФ может принимать любые значения.
Минимизация булевых функций в классе ДНФ
Сложностью формулы называется число вхождений в эту формулу переменных. Например, сложность СДНФ можно определить как 13 EMBED Equation.3 1415. Как правило, булеву функцию можно задать с помощью формул, имеющих меньшую сложность. Построение таких формул является предметом минимизации булевых функций. Существуют различные методы минимизации булевых функций, использующих либо аналитические преобразования СДНФ, либо основанные на обработке булевых векторов из множества N1. В последнем случае мы имеем дело с алгоритмизируемыми процедурами, которые могут быть записаны в виде программы.
Теоретической основой минимизации булевых функций в классе дизъюнктивных нормальных форм (ДНФ) является использование правил склеивания, обобщенного склеивания и поглощения, представляемых формулами:
- Kx ( K(x = K,
- K1x (K2(x = K1x ( K2(x ( K1K2,
- K1K2 ( K2 = K2,
где К, К1, К2, ( элементарные конъюнкции произвольного ранга.
Аналитические преобразования СДНФ с использованием этих правил описывает метод Блейка. Правила склеивания, обобщенного склеивания и поглощения применяются к СДНФ до тех пор, пока это возможно. Результатом является множество элементарных конъюнкций, кратная дизъюнкция которых дает сокращенную ДНФ. Например, для функции, заданной вектором 13 EMBED Equation.3 1415=(11101011), СДНФ=((0,1,2,4,6,7) имеет сложность 3*6=18. Сокращенная ДНФ имеет вид 13 EMBED Equation.3 1415, а ее сложность равна 5.
Метод Квайна (алгоритмизируемый) состоит в следующем. Кортежи, входящие в множество N1, записываются в столбец в порядке возрастания их весов сверху вниз. При этом кортежи с одинаковым весом объединяются в ярусы. В соответствии с правилом склеивания кортежи соседних ярусов могут склеиваться, если они являются соседними наборами. Кортежам из множества N1 соответствуют интервалы ранга n. Результатом склеивания пар кортежей являются интервалы, ранг которых на единицу меньше ранга вершин единичного куба, так как они получаются вычеркиванием «мелькающей» переменной, по которой и происходит склеивание. Вместо этой переменной в обозначении интервала ставится прочерк или любой другой символ, отличный от 0 и 1.
Переменные интервала, которым соответствуют значения 0 и 1, называются связанными, а переменные, которым соответствуют прочерки, называются свободными переменными интервала. Если интервал содержит k прочерков, то ему соответствуют 2k вершин единичного n-мерного куба. Например, (01-0)={0100,0110}, (-1-0)={0100, 0110, 1100, 1110). Число связанных переменных интервала называется рангом интервала. Единичному интервалу функции ранга r соответствует элементарная конъюнкция ранга r, называемая импликантом функции.
Интервалы, полученные склеиванием кортежей из множества N1, записываются в столбец, правее первого столбца. В этом новом столбце отыскиваются смежные интервалы, которые также склеиваются, образуя новый столбец, справа от предыдущего. Если какие-либо интервалы не могут участвовать в склеивании, они переходят в правый столбец без изменения. Процедура продолжается до тех пор, пока не будут исчерпаны все возможности склеивания. Полученные в последнем столбце интервалы называются максимальными. Им соответствуют элементарные конъюнкции, называемые простыми импликантами. Дизъюнкция всех простых импликант образует сокращенную ДНФ.
Сокращенная ДНФ, вообще говоря, не является МДНФ. В ней могут присутствовать «лишние» импликанты, дублирующие покрытие некоторых единичных вершин из множества N1.
Следующим этапом является отбор в множестве максимальных интервалов неприводимых покрытий, из которых затем выбираются все неприводимые покрытия минимального ранга. Для отыскания всех неприводимых покрытий используются имликантные таблицы.
Табличные методы минимизации булевых функций
В практике проектирования дискретных вычислительных устройств для минимизации булевых функций «вручную» используют специального вида таблицы, представляющие собой разложение единичного n-мерного куба на плоскости, сохраняющее отношение смежности вершин. Такие таблицы известны для n({3,4-18}. Очевидно, с точки зрения здравого смысла таблицы для больших значений n (скажем, n>8) использовать не целесообразно (лучше написать программу). Для n-местной булевой функции такая таблица должна содержать 2n клеток, в каждую из которых записывается значение функции на том наборе значений переменных, номер которого совпадает с номером клетки. Нумерация клеток сохраняет отношение смежности вершин, так что любые две рядом расположенные клетки являются соседними и могут склеиваться друг с другом. В таблицах также возможно склеивание клеток, расположенных рядом по вертикали и по горизонтали, а также симметрично относительно некоторых осей симметрии таблицы. В склеивании могут участвовать 2k клеток, в которых k каких-либо переменных принимают все возможные наборы значений. Эти k переменных являются свободными переменными интервала, который содержит k свободных и n-k связанных переменных. Интервалу соответствует множество, содержащее 2k вершин единичного n-мерного куба {0,1}n
Процесс минимизации в классе дизъюнктивных нормальных форм (ДНФ) сводится к визуальному отысканию максимальных интервалов функции, покрывающих наибольшее число вершин единичного n-мерного куба. При этом отпадает необходимость в использовании импликантных таблиц.
Диаграммы Вейча
При небольшом числе переменных (n=3,4) для минимизации булевых функций используют диаграммы Вейча.
Для функции трех переменных нумерация клеток диаграммы Вейча приведена на Рис. 1.


x1










x2

6
7
3
2



4
5
1
0











x3


Рисунок 13 SEQ Рисунок \* ARABIC 14115 Диаграмма Вейча для 3-х переменных
Диаграмма содержит 23=8 клеток. В диаграмме указаны группы по 23-1=4 клеток, в которых каждая из переменных принимает значение 1.
Определим максимальные интервалы и соответствующую МДНФ для функции трех переменных, заданной вектором (f=(0111 1011).Изображение этой функции на диаграмме Вейча показано на рис.4 в предположении, что нумерация переменных в последовательности, задающей номер клетки, производится слева направо.
Из рис.4 видно, что множество единиц данной функции покрывается тремя максимальными интервалами, которым соответствует МДНФ = x2 ( x1(x3 ((x1x3.



1
1
1
1

1
0
1
0




Обозначенные на рис. 2 максимальные интервалы покрывают множество N1, образуя неприводимое покрытие, которому соответствует МДНФ
f (x1,x2,x3)=x1(x2 ( x2 ((x1x3
Для четырехместной булевой функции таблица содержит 24=16 строк. Соответственно, диаграмма Вейча такой функции содержит 16 клеток, расположение которых показано на Рис. 3, 4. Каждой клетке сопоставлена одна из вершин единичного 4-мерного куба, описанная кортежем 13 EMBED Equation.3 1415. Двоичные коды кортежей, соответствующие нумерации клеток, приведенной на Рис. 3, представлены на Рис. 4. Из последнего рисунка видно, что каждая переменная принимает значение 1 в 8 клетках таблицы, обозначенных соответствующим указателем.
12
13
9
8

14
15
11
10

6
7
3
2

4
5
1
0

Рисунок 13 SEQ Рисунок \* ARABIC 14315 Нумерация клеток при n=4


1100
1101
1001
1000

1110
1111
1011
1010

0110
0111
0011
0010

0100
0101
0001
0000




Примеры минимизации 4(местных булевых функций, заданных векторами ((f)=(1010101010101010) и ((f)=(1001100110011001) приведены на Рис. 5.
13 EMBED Word.Picture.6 1415
Рисунок 13 SEQ Рисунок \* ARABIC 14515 Пример определения МДНФ

При дальнейшем увеличении местности булевых функций их минимизация с использованием диаграмм Вейча становится затруднительной из-за громоздкости таблицы и уменьшения ее наглядности. Поэтому при n>4 используют метод симметричных таблиц.
Минимизация булевых функций методом симметричных таблиц
Симметричные таблицы обеспечивают наглядность процедуры минимизации булевых функций с числом переменных 13 EMBED Equation.3 1415. Громоздкость таблицы, неизбежная при увеличении местности функций, компенсируется регулярностью и наглядностью таблиц. Изложение этого метода можно найти в [2]. Симметричные таблицы позволяют:
быстро и легко заполнять таблицу значениями минимизируемой функции благодаря восьмеричной нумерации клеток;
легко находить максимальные интервалы функции благодаря свойству симметрии в структуре таблицы;
автоматизировать процесс минимизации, используя большую степень формализации алгоритма склеивания клеток.
При использовании этого метода значения минимизируемой функции нумеруются восьмеричными числами. Восьмеричный номер значения функции есть восьмеричное представление его двоичного набора xn,...,x1.Двоичный набор разбивается справа налево на группы по три разряда в каждой, и каждая группа заменяется соответствующей восьмеричной цифрой. При этом х1 имеет минимальный двоичный вес, равный 20, а xn - максимальный, равный 2 n-1.
Базовой структурой при использовании этого метода является таблица для минимизации функций, имеющих местность 2(n(6. Таблица, соответствующая максимальному числу переменных, содержит 26=64 клеток. Каждая клетка нумеруется двумя восьмеричными цифрами. Двоичный код этой последовательности при нумерации переменных справа налево(!) определяет значения шести двоичных переменных и имеет вид (x6x5x4x3x2x1). Для получения восьмеричного кода эта последовательность разбивается на тройки справа налево и каждая тройка замещается соответствующей восьмеричной цифрой. Восьмеричный код клетки обозначим (y2y1). В отмеченной симметричной таблице указываются группы по 2n-1 клетке, в которых указанная при отметке переменная принимает единичные значения. Определение зон прямого и инверсного значений переменных осуществляется следующим образом. Снизу всю горизонтальную строку клеток делят вертикальной линией пополам. Полученные половины также делят вертикальными линиями пополам. Далее, полученные части снова делят пополам до тех пор, пока в каждой части слева и справа от вертикальной линии не останется по одной клетке. Тогда для переменной х1 первая клетка слева представляет инверсное значение х1, следующие две клетки (удвоенное число)-прямое значение х1, затем чередуются по две клетки с прямым и инверсным значениями х1. В конце строки будет одна клетка, которой приписывается инверсное значение х1. Для переменной х2 инверсное значение, как и для остальных переменных, начинается слева, но для двух клеток, следующее прямое значение - для четырех клеток (удвоенное число) и т.д. до конца. Затем для переменной х3 - области инверсного и прямого вхождений удвоенной длины по сравнению с предшествующей переменной. Для трех старших переменных используется та же процедура справа от таблицы в направлении сверху вниз.
Три младшие двоичные переменные указываются снизу таблицы с возрастанием индекса в направлении сверху вниз, а три старшие переменные - справа от таблицы в направлении слева направо в порядке возрастания индекса переменной. Пример симметричной таблицы для n=6 приведен на Рис.6. Каждая клетка таблицы имеет свой восьмеричный номер (адрес) и в нее записывается значение функции из строки таблицы с тем же номером.
(Стрелками указаны группы клеток с единичными значениями отмеченных переменных)
Склеивание единиц в таблице осуществляют следующим образом. Любая единица может склеиваться по горизонтали: в группе из двух клеток с другой единицей или незаданным набором, образуя интервал с одной свободной переменной; в группе из четырех клеток, образуя интервал с двумя свободными переменными; в группе из 2к клеток, образуя интервалы с к свободными переменными, где к(2(n. Аналогично можно склеивать и клетки по вертикали. Склеиванию помогает визуальная симметрия возможных для склеивания клеток.

y1
y2
0
1
3
2
6
7
5
4

0









1
*



*


*

3
*

*
*
*


*

2


*


*
*


6





*
*


7









5









4














Рис. 9. Отмеченная симметричная таблица для минимизации булевых функций при n=6
На рис.6 звездочками и подсветкой отмечены клетки, которые можно склеивать. Номер клетки образуют две восьмеричные цифры-(у2у1), где у2 соответствует номеру строки таблицы, а у1 - номеру столбца. Клетки с номерами 23 и 33 образуют интервал (01-011) с одной свободной переменной х4. Клетки с номерами (25,27,65,67) - интервал (-101-1) с двумя свободными переменными х2 и х6. Клетки с номерами (10, 12, 14, 16, 30, 32,34,36) - интервал (0-1--0) с тремя свободными переменными х2, х3, х5. Интервалы, соответствующие группам склеиваемых клеток, отмечены выносками .
Основные оси симметрии таблицы выделены жирными линиями. Склеивание 2к клеток возможно только при условии их симметричного расположения относительно основных или дополнительных осей симметрии таблицы. Например, нельзя склеить четыре рядом расположенные клетки с номерами 62, 65, 66, 67.
y1
y2
0
1
3
2
6
7
5
4

0
0
1
1
*
*
*
*
0

1
*
*
*
*
*
*
*
*

3
*
*
*
1
1
*
*
*

2
*
*
*
1
1
*
*
*

6
*
0
0
*
*
0
0
*

7
*
0
0
*
*
0
0
*

5
*
*
*
*
*
*
*
*

4
0
1
1
*
*
*
*
0









Пусть, например, 6-местная частично определенная функция задана следующим образом:
N1=(-000-1)((01--10), N0=(11---1) ((-00-00). Соответствующая симметричная таблица и процедура отыскания максимальных интервалов показаны на Рис. 7.
Исходные интервалы функции помечены заливкой: единичные - более светлой, нулевые –
темнее. Для получения МДНФ склеивают клетки, в которых находятся 1 и *. Результаты склеивания отмечены контурами и выносками. Для данной функции МДНФ=(x1 x4(x6 ((x1 x2 .
При увеличении местности функций таблица строится из базовой таблицы из 64 клеток. При числе переменных 6(n(12 каждая часть из 26 клеток считается одной клеткой и нумеруется той же последовательностью чисел-0,1,3,2,6,7,5,4 по горизонтали и по вертикали, но каждая цифра в последовательности означает восьмеричную цифру третьего и четвертого разрядов соответственно восьмеричного кода клетки.

y3
y2

y1

0

1

3
0
2

6

7

5

4

4

5
1
7

6

2

3

1

0

0
0
*
*
*
*
0
*
0
*
*
*
*
*
*
*
0

1
0
*
*
*
*
0
*
*
0
*
*
*
*
*
*
*

3
0
*
1
1
*
0
0
*
*
0
0
*
1
1
1
*

2
*
*
1
1
*
0
0
*
*
0
0
*
1
1
*
0

6
*
1
1
1
*
*
*
0
0
*
0
*
1
1
1
0

7
*
1
*
*
*
*
*
0
0
*
*
*
*
*
*
*

5
0
*
*
*
*
*
*
*
*
*
*
*
*
*
*
0

4
0
*
*
*
*
*
*
*
*
*
*
*
*
*
*
0









Для 12 (n( 18 симметричная таблица строится аналогично предыдущей, но теперь базовой клеткой является таблица из 212 клеток, а их нумерация той же последовательностью восьмеричных цифр теперь соответствует пятому и шестому разрядам восьмеричного кода клетки.
Прямые и инверсные вхождения переменных в таблице записывают тройками: младшие три переменные записывают снизу, следующие три - справа, следующие три - снизу, следующие три -справа, и так далее. Для обеспечения «склеиваемости» соседних клеток "больших" таблиц нумерация в каждой следующей "большой " клетке должна быть зеркальной по отношению к предыдущей.
Составление карты для n=7 показано на Рис. 8. Каждая клетка нумеруется тремя восьмеричными цифрами, обозначаемыми (y3y2y1)

Приложенные файлы

  • doc 18333000
    Размер файла: 695 kB Загрузок: 1

Добавить комментарий