Способы покрытия таблицы Квайна

При первом способе выделяются простые импликанты, без которых невозможно представление функции. Их характерной особенностью является то, что некоторые конституенты принадлежат только им. Для приведеннолго примера такими импликантами являются 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} + М₂ М₃

а второму:

f = ₁ М₃ + М₁М₃ + М₁М₂

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

Рассмотрим другой,более эффективный способ.

Для этого каждую простую импликанту таблицы Квайна представим с помощью множества. При этом будем считать,что для таблицы Квайна множество – малые латинские буквы.

 

0x1						А
x11						В
1x0						С
11x						D

 

В этом случае конституенты покрываются следующими множествами.

001 – P₁=a

011 – P₃=a+b

100 – P₄=c

110 – P₆=c+d

111 – P₇=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 ₁ = ₁M₂ + M_{1 3} + M₂M₃

f ₂ = ₁M₂ + M_{1 3} + M₁M₂

Рассмотрим более сложный пример.

Функция от четырех переменных:

 

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 ₁ = M_{2 3} + ₁M₃M₄ + M_{1 2}M₄

f ₂ = M_{2 3} + ₁M₃M₄ + ₂M₃ М₄ + M_{1 3}M₄

f ₃ = M_{2 3} + ₂M₃M₄ + ₁М₂ М₄ + M_{1 2}M₄

f ₄ = M_{2 3} + ₂M₃M₄ + ₁М₂ М₄ + M_{1 3}M₄

Получены тупиковые формы. Их сложность соответственно:

S₁ = 8, S₂ = 11, S₃ = 11, S₄ = 11

Следовательно имеем одну минимизированную форму f₁

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 (m_i) Î M_i; m_i Î M.

Алгебра – некоторое множество М, с определенными на этом множестве операциями. Все функции,заданные на М,обозначаются буквой S –сигнатура алгебры. Множество М – носитель алгебры. Произв. алгебра А обозначается:

А < М, S >

 

ФУНДАМЕНТАЛЬНЫЕ АЛГЕБРЫ

1. Алгебра А = < М, f₀ >,где f₀ - двуместная функция, называется группой. При этом f: a, b ® с, c = ab - обобщенное умножение

С обладает свойствами:

- если (а,b Î М, то результат обобщенного умножения так же принадлежит М

[(ab) Î M]

Это свойство замкнутости;

- (ab)c = a(bc) - свойство ассоциативности

- (ax) = b, ya = c - существованиеединственного решения уравнения

Группа, для которой выполнено условие:

ab = ba

называется коммутативной или абелевой группой.

ПРИМЕРЫ АЛГЕБРАИЧЕСКИХ СИСТЕМ

N - множество натуральных чисел

R - множество целых чисел

Z - множество действительных чисел

Определим алгебру вида:

А = < N, +, *, - >

Эта алгебра не является алгебраической системой

А = < N < +, *, > - алгебраическая система

Причем в данном примере содержится алфавит из бесконечного числа элементов.

Существуют алгебры с конечным алфавитом. Примером такой алгебры есть алгебра подстановок.

Образовывающаяся алгебра подстановок с помощью перестановок 3-х элементов х₁, х₂,х₃.

Отметим возможные варианты.

	x1	x2	x3
	x1	x3	x2
	x3	x2	x1
	x2	x1	x3
	x2	x3	x1
	x3	x1	x2

 

Элементы носителя определяются следующим образом

a = x₁ x₂ x₃ b = x₁ x₂ x₃ c = x₁ x₂ x₃

x₁ x₂ x₃ x₁ x₃ x₂ x₂ x₁ x₃

d = x₁ x₂ x₃ e = x₁ x₂ x₃ c = x₁ x₂ x₃

x₂ x₃ x₁ x₃ x₁ x₂ x₃ x₂ x₁

 

Например элемент b означает,

что х₁ переходит в х₁

х₂ переходит в х₃

х₃ переходит в х₂

Определим групповую операцию, как общий переход:

bc = x₁ x₂ x₃ x₁ x₂ x₃ = x₁ x₂ x₃ = d

x₁ x₃ x₂ x₂ x₁ x₃ x₂ x₃ x₁

 

Составим мультипликативную таблицу:

 

	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,1,2,3,4,5} ₀ , + по модулю 6.

Составим таблицу умножения и сложения.

с = а + в mod 6

+

 

с = ав mod 6

*

 

Из таблиц видно, что эта алгебра есть коммут. кольцо с 1.

3. А = < М, ₀, + > М{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;

Вышепреведенные алгебры являются полем Галуа.