Способы покрытия таблицы квайна
При первом способе выделяются простые импликанты, без которых невозможно представление функции. Их характерной особенностью является то, что некоторые конституенты принадлежат только им. Для приведеннолго примера такими импликантами являются 0х1 1х0.
Объединение этих импликант называется ядром покрытия. Если ядро покрытия не перекрывает все конституенты функции, то к нему добавляются дополнительные импликанты до полного покрытия. Все минимальные покрытия отыскиваются с помощью простого перебора.
Так для нашего примера: ядро покрытия покрывает конституенты
0х1 - 001 и 011
1х0 - 100 и 110
Констутиента 111 осталась непокрытой ,следовательно к ядру нужно добавить еще одну импликанту. При этом получаем 2 минимальных покрытия:
{0х1 , 1х0 , х11}
{0х1 , 1х0 , 11х}
Первому покрытию соответствует тупиковая форма
f = 1М3 + М1
3 + М2 М3
а второму:
f = 1 М3 + М1М3 + М1М2
Такой способ образования минимальных покрытий для функций с большим числом переменных затруднен при применении.
Рассмотрим другой ,более эффективный способ.
Для этого каждую простую импликанту таблицы Квайна представим с помощью множества. При этом будем считать ,что для таблицы Квайна множество – малые латинские буквы.
0x1 | А | |||||
x11 | В | |||||
1x0 | С | |||||
11x | D |
В этом случае конституенты покрываются следующими множествами.
001 – P1=a
011 – P3=a+b
100 – P4=c
110 – P6=c+d
111 – P7=b+d
Из этого следует, что все возможные минимальные покрытия представляются множествам Р равным:
Р = а( а + b ) с ( с + d )( b + d)
Применяя, рассмотренные ранее, законы для операций над множествами:
Р = а( а + b ) c ( c + d )( b + d ) = ac ( b + d ) = acb + acd
acb – { 0x1, 1x0, x11 }
acd – { 0x1, 1x0, 11x }
f 1 = 1M2 + M1
3 + M2M3
f 2 = 1M2 + M1
3 + M1M2
Рассмотрим более сложный пример .
Функция от четырех переменных:
Kj | F |
Выпишем все образующие функцию конституенты, разбив на классы по количеству единиц.
0100 010x
0011 x100
0101 0x11
1001 x011
1100 01x1
0111 x101
1011 10x1
1101 1x01
110x
Объединяя их, получим: х10х х10х
x10x | A | ||||||||
0x11 | B | ||||||||
x011 | C | ||||||||
01x1 | D | ||||||||
10x1 | E | ||||||||
1x01 | F |
f 1 = M2 3 +
1M3M4 + M1
2M4
f 2 = M2 3 +
1M3M4 +
2M3 М4 + M1
3M4
f 3 = M2 3 +
2M3M4 +
1М2 М4 + M1
2M4
f 4 = M2 3 +
2M3M4 +
1М2 М4 + M1
3M4
Получены тупиковые формы. Их сложность соответственно:
S1 = 8, S2 = 11, S3 = 11, S4 = 11
Следовательно имеем одну минимизированную форму f1
P = a(b+c)(a+d)(e+f)a(b+d)(c+e)(a+f) = a(b+c)(e+f)(b+d)(c+e) = a(b+cd)(e+cf) =
(ab+acd)(e+cf) = abe + abcf + acde + acdf
БУЛЕВА АЛГЕБРА
Алгебра – это множество М, с заданными на нем функциями, обладающими свойствами замкнутости.
f (mi) Î Mi ; mi Î M.
Алгебра – некоторое множество М , с определенными на этом множестве операциями. Все функции ,заданные на М ,обозначаются буквой S –сигнатура алгебры. Множество М – носитель алгебры. Произв. алгебра А обозначается:
А < М, S >
ФУНДАМЕНТАЛЬНЫЕ АЛГЕБРЫ
1. Алгебра А = < М , f0 > ,где f0 - двуместная функция, называется группой. При этом f : a , b ® с , c = ab - обобщенное умножение
С обладает свойствами:
- если (а,b Î М, то результат обобщенного умножения так же принадлежит М
[(ab) Î M]
Это свойство замкнутости;
- (ab)c = a(bc) - свойство ассоциативности
- (ax) = b , ya = c - существованиеединственного решения уравнения
Группа , для которой выполнено условие:
ab = ba
называется коммутативной или абелевой группой.
ПРИМЕРЫ АЛГЕБРАИЧЕСКИХ СИСТЕМ
N - множество натуральных чисел
R - множество целых чисел
Z - множество действительных чисел
Определим алгебру вида:
А = < N, + , * , - >
Эта алгебра не является алгебраической системой
А = < N < + , * , > - алгебраическая система
Причем в данном примере содержится алфавит из бесконечного числа элементов.
Существуют алгебры с конечным алфавитом. Примером такой алгебры есть алгебра подстановок.
Образовывающаяся алгебра подстановок с помощью перестановок 3-х элементов х1, х2,х3 .
Отметим возможные варианты.
x1 | x2 | x3 | |
x1 | x3 | x2 | |
x3 | x2 | x1 | |
x2 | x1 | x3 | |
x2 | x3 | x1 | |
x3 | x1 | x2 |
Элементы носителя определяются следующим образом
a = x1 x2 x3 b = x1 x2 x3 c = x1 x2 x3
x1 x2 x3 x1 x3 x2 x2 x1 x3
d = x1 x2 x3 e = x1 x2 x3 c = x1 x2 x3
x2 x3 x1 x3 x1 x2 x3 x2 x1
Например элемент b означает,
что х1 переходит в х1
х2 переходит в х3
х3 переходит в х2
Определим групповую операцию, как общий переход:
![]() | |||
![]() | |||
bc = x1 x2 x3 x1 x2 x3 = x1 x2 x3 = d
x1 x3 x2 x2 x1 x3 x2 x3 x1
Составим мультипликативную таблицу:
a | b | c | d | e | f | |
a | a | b | c | d | e | f |
b | c | a | d | c | f | e |
c | c | e | a | f | b | d |
d | d | f | b | e | a | c |
e | e | c | f | a | d | b |
f | f | d | e | b | c | a |
Проверим выполняется ли закон ассоциативности для данного примера:
(bd)f = cf =d
b(df) = bc =d
то есть, закон выполняется.
Так же можно показать, что закон справедлив для любых элементов данной алгебры .Видно, что алгебра замкнута, но не выполнено свойство коммутативности.
Поэтому алгебра – мультипликативная некоммутативная группа.
Алгебра вида
А = < М , * , + >
Называется кольцом, если < М , + > есть аддитивная абелевая группа, выполняется закон дистрибутивности.
Если операция обобщ. умн. кольца < М, * > содержит 1, то имеет место кольцо с единицей.
Если умн. коммут. то кольцо – коммутат. Полем называется кольцо с единицей, ненулевые элементы которого образуют группу по умножению. Если эта группа имеет конечное число элементов и является абелевой, то такие поля называются полями Галуа.
Рассмотрим примеры :
1.Множество действительных чисел с опер. слож. и умноженные есть коммутативное поле.
2. Алгебра вида :
А = < М, 0 , + > ,где М {0,1,2,3,4,5} 0 , + по модулю 6.
Составим таблицу умножения и сложения.
с = а + в mod 6
+ | ||||||
с = ав mod 6
* | ||||||
Из таблиц видно, что эта алгебра есть коммут. кольцо с 1.
3. А = < М, 0 , + > М{0,1,2,3,4,5,6} c = a + b mod 7
+ | |||||||
* | |||||||
Для данного алфавита можно определить и обратную операцию вычитания.
а – в = а(-в)
Для данной алгебры составленна таблица :
а | -а |
По аналогии составляется таблица обратных элементов для деления.
1-1=1; 2-1=4; 3-1=5; 4-1=2; 5-1=3; 6-1=6;
Вышепреведенные алгебры являются полем Галуа.