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

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₁₃ + M₂M₃

f ₂ = ₁M₂ + M₁₃ + M₁M₂

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

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

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

0100 010x

0011 x100

0101 0x11

1001 x011

1100 01x1

0111 x101

1011 10x1

1101 1x01

110x

Объединяя их, получим: х10х х10х

f ₁ = M₂₃ + ₁M₃M₄ + M₁₂M₄

f ₂ = M₂₃ + ₁M₃M₄ + ₂M₃ М₄ + M₁₃M₄

f ₃ = M₂₃ + ₂M₃M₄ + ₁М₂ М₄ + M₁₂M₄

f ₄ = M₂₃ + ₂M₃M₄ + ₁М₂ М₄ + M₁₃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-х элементов х₁, х₂,х₃.

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

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

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₁

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

Проверим выполняется ли закон ассоциативности для данного примера:

(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;

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

СИСТЕМЫ УРАВНЕНИЙ И ПОЛЯ ГАЛУА.

Как и в обычной алгебре можно решать системы уравнений и в полях Галуа.Возьмем следующую систему:

X₁+3x₂+6x₃=2

4x₁+5x₂+2x₃=1

2x₂+x₃=5

Будем решать систему по методу Гаусса:

1 3 6

= 4 5 2 mod 7 = (5+48–4–12) mod 7=37 mod 7 = 2

0 2 1

2 3 6

₁ = 1 5 2 mod 7 = (–109) mod 7=(140-109) mod 7 = 31 mod 7 = 3

0 2 1

₂ = 103 mod 7 = 5 ₃ = (27-21) mod 7 = 0

x₁=3*2^-1=3*4=5

x₂=5*2^-1=5*4=6

x₁=0*2^-1=0*4=Æ

5+3*6+6*Æ=5+4+Æ=2+Æ=2

4*5+5*6=6+2=1

2*6=5

БУЛЕВЫ АЛГЕБРЫ.

Изоморфизмом между алгебрами называется взаимооднозначное соответствие j между носителями и сигнатурами.

f_i(x₁,…x_n) =x_k Þ j (f_i)[j (x₁),…j (x_n)] = j (x_k)

Алгебры для которых существует изоморфизм j называют изоморф-ми.

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

Булевы алгебры – алгебры вида:

A = < M, +, *, - > для которых справедливы следующие отношения:

" х_i Î M

1. x_i + x_j = x_j + x_i

2. x_i * x_j = x_j * x_i

3. (x_i + x_j) + x_k = x_i + (x_j +x_k)

4. (x_i * x_j) * x_k = x_i * (x_j *x_k)

5. (x_i + x_j) * x_k = x_i *x_k+ x_j*x_k

6. x_i + x_j * x_k = (x_i + x_j)(x_i+x_k)

7. x_i+x_j Î M, x_i x_j Î M

8. x E = x; xÆ = Æ; x + E = E; x + Æ = x;

9. x * = E; x * = Æ;

Множество вида М = {I_j, E, Æ}

I_j – интервалы пораждающих множеств;

E – единичное множество;

Æ - пустое множество;

и определенные на нем операции +, *, - есть булева алгебра или алгебра множеств. Булевы алгебры есть частный случай фундаментальных видов алгебр.

АЛГЕБРА БУЛЯ.

Булевой переменной является переменная, которая принимает значение 0 или 1. Будем обозначать такую переменную Х. Если в некоторой алгебре Буля определены функции от к переменных, то будем называть её к-значной, а сигнатуру обозначать как Р_к .

Операция обобщ-го сложения в случае булевых алгебр называют дизъюнкцией, а операция обобщ-го умножения – конъюкцией.

Групповая операция обобщ. сложения:

х₁х₂ ~ x₁ + x₂

Операция обобщенного умножения:

x₁&x₂

0 0 = 0 0 & 0 = 0

0 1 = 1 0 & 1 = 0

1 0 = 1 1 & 0 = 0

1 1 = 1 1 & 1 = 1

Установим выполдняется ли для данной алгебры законы теории множеств:

1. Дистрибутивный закон

х₁(х₂х₃)=х₁х₂х₁х₃

Составим таблицу:

x1	x2	x3	х1(х2х3)	х1х2х1х3

1^-й закон дистрибутивности применим к алгебре Буля. Аналогичная таблица для 2^-го закона дистрибутивности.

(х₁х₂) (х₁х₃) = x₁(x₂ & x₃)

x1	x2	x3	(х1х2) (х1х3)	x1(x2 & x3)

2. Проверим закон де Моргана.

Отрицание конъюкции есть дизъюнкция отрицания.

₁& ₂ = ₁₂

x1	x2	1& 2	12

Отрицание дизъюнкции равно конъюкции отрицания.

₁₂ = ₁&₂

x1	x2	12	1&2

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

ПРИОРИТЕТЫ АЛГЕБРЫ БУЛЯ.

1. –

2. &

3. Å

4.

ОСНОВНЫЕ ОПЕРАЦИИ АЛГЕБРЫ БУЛЯ.

(АЛГЕБРЫ ЛОГИКИ).

ТАБЛИЦЫ ИСТИННОСТИ ЭТИХ ОПЕРАЦИЙ.

1. «НЕ» - х

0 1

1 0

2. х₁х₂ «ИЛИ»

х1 х2	х1х2
0 0
0 1
1 0
1 1

3. Конъюкция х₁& х₂ «И»

4. Импликация х₁® х₂ «ЕСЛИ ТО»

5. Эквиваленция х₁ ~ х₂ «ТОГДА И ТОЛЬКО ТОГДА»

ПРЕДСТАВЛЕНИЕ ФУНКЦИИ В АЛГЕБРЕ БУЛЯ.

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

Кроме табличного задания алгебры логики применяются различные аналитические методы. К ним относятся – дизъюктивная и коньюктивная форма. Для представления в дизъюктивной соверш. норм. форме (ДСНФ) вводится фар-кая функция единицы, которая соответствует конституентам, в которых функция принимает значение = 1.

Единичная функция записывается,как элементарная конъюнкция, содержащая n – переменных и называется минитермом. Алгоритм представления функции алгебры логики в виде ДСНФ записывается в виде:

1) Выбрать в таблице функции все наборы аргументов, на которых функция обращ. в единицу

2) Вычислить конъюкцию, соответствующей этим наборам аргументам. При этом аргумент x_i входит в данный набор как 1, он вписывается без изменения в конъюнкцию, соответствующую данному набору. Если х_i входит как 0,то в конъюнкцию вписывается его отриц.

3) Все полученные конъюнкции соединены между собой знаками дизъюнкции.

Для примера запишем ДСНФ

f(х₁,х₂, х₃) = _{1 2 3 1} x_{2 3 1 2} x₃ x_{1 2 3} x_{1 2} x₃

x₁ x_{2 3}

Для представления функции алгебры логики в КСНФ вводится хар-кая

функция О,которая соответствует набору, на котором функция принимает значение О. Функция нуля записывается как элементарная дизъюнкция, содержащая n-переменных и называется макситермом.

Алгоритм построения КСНФ:

1) Выбрать в таблице функции все наборы аргументов, на которых функция обращается в О.

2) Выписать дизъюнкции, соответствующие этим наборам. При этом если х_i входит как О, он вписывается без изменений в дизъюнкцию, если х_i входит как 1, то в дизъюнкцию вписывается его отрицание.

Для примера запишем КНФ

f(х₁,х₂, х₃) = (x₁ x₂₃) & (_{12 3})

По аналогии с теорией множеств при минимизации:

ДСНФ ® ДНФ

КСНФ ® КНФ

ДНФ,КНФ – обозначения для сокращения макситермами и минитермами. Номера мини- и макситермов являются дес-ными экв-ми соответствующего набора, на котором функция принимает 1 или 0 соответственно, то есть

(ДСНФ) f(х₁,х₂,х₃) = m₀ m₂ m₃ m₄ m₅ m₆

(КСНФ) f(х₁,х₂,х₃) = m₁ & m₇

Согласно теореме Шеннона функция в ДСНФ имеет вид:

f(х₁,…,х_k) = f(d₁,…,d_k) & x₁^d1* x₂^d2… x_k^dk

Функция трех переменных задана таблично:

f(х₁,х₂, х₃) = _{1 2 3 1} x_{2 3 1}x₂ x₃ x₁ x₂ x₃ (ДСНФ)

Выясним каково количество возможных булевых функций к-значных.

Если мы имеем к переменных, то из них можно составить m=2^к комбинаций, а так как для каждой комбинации может быть задана своя функция, то общее число возможных функций V=2^m=2^{2^k}

Теорема:

Алгебра множеств с к-порожденными множествами изоморфна к-значной алгебре Буля.

Доказательство:

Изоморфизм строится следующим образом:

j (М_i)=x_i - для алгебры множеств

j (f_i)=y_i - для алгебры Буля

Тогда согласно представлению Булевых функций в ДСНФ и представлению функций от порождающих множеств в СНФК следует следующее:

f_j(M_i) = M_v^dv ;

y_j(x_i) = x_v^dv ;

Основным следствием этой теоремы является возможность применения всех методов минимизации из теории множеств для алгебры Буля.

Метод Квайна для функции Буля:

0 0 0

0 1 0 0х0

0 1 1 х11

1 1 1

Строим таблицу Квайна:

Y(x₁, x₂, x₃) = ₁₃x₂x₃

Минимизация по методу Карно:

х1 х2х3

f(x₁, x₂, x₃) = ₁₃x₂x₃

ФУНКЦИОНАЛЬНО ПОЛНЫЕ СИСТЕМЫ ФУНКЦИЙ.

Запишем таблицу функций 1-й перем.:

y₁ – функция константы О;

y₂ – переменная х;

y₃ – отриц. переменная х;

y₄ – конст-ты 1.

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

Некоторые из этих функций встречались ранее:

F₁(x₁, x₂) = x₁ * x₂ - дизъюнкция

F₆(x₁, x₂) = x₁ Å x₂ - слож. по модулю 2

F₇(x₁, x₂) = x₁ x₂ - конъюкция

Сведем в таблицу:

Функция	Название	Предназначение
F0	конст-та 0	Æ
F1	конъюкция	Логич. умнож. х1х2
F2	отрицание по х2	х1 2
F3	повт-ль х1	х1
F4	запрещение по х1	1х2
F5	повт-ль х2	х 2
F6	сумма по mod 2	х1Åх2
F7	дизъюнкция	логич. сложен. х1х2
F8	стрелка Пирса	х1 ¯ х2
F9	эквив-ти	х1 ~х2
F10	отрицание х2	2
F11	импликация по х2	х2®x1
F12	отрицание х1	1
F13	импликация по х1	x1 ® х2
F14	отр. конъюкции	1 2
F15	конст-та 1

Функционально-полной системой алгебры Буля – набор функций Р_к, с помощью которых может быть выраженна любая функция из Р_к.

Тривиальной функционально-полной системой является весь набор функций из Р_к.

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

Примером алгебры с функционально-полной системой, но не являющейся базисом является функция вида:

А = < M, , &, - >

На основании законов де Моргана из неё можно получить алгебры с базисами.

А₁ = < M, , - >, А₂ = < M, &, - >

Принцип нахождения функционально-полных систем и базисов для Р_к.

Будем искать такой набор из Р_к, с помощью которого можно представить функции дезъюнкции, конъюкции, отрицания, а следовательно и все остальные функции. Для изучения свойств пространства Р₂, т. е. Функция от двух переменных, представим все функции с помощью операций дезъюнкции, конъюкции и отрицания.

F1 = х1*х2

F2 = х1*2

F4 = 1*х2

F6 = х1Åх2 = 1*х2х1*2

F7 = х1 х2

F8 = 1*2 = 12

F9 = 12 х1х2 = х1Åх2

F10 = 2

F11 = 12 х12 х1х2 = x12

F12 = 1

F₁₃ = _{12 1}х₂ х₁х₂ = ₁ х₂

F₁₄ = _{12 1}х₂ х₁₂ = _{1 2} = ₁₂

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

Изобразим эти элементы.

F₁ = x₁x₂ F₂ = x₁₂ F₄ = ₁x₂

x₁ x₁ x₁

x₂ & y₁ x₂ & y₂ x₂ & y₄

F₆ = х₁Åх₂ F₇ = х₁ х₂ F₈ = ₁₂

x₁ x₁ x₁

x₂ y₆ x₂ 1 y₇ x₂ 1 y₈

F₉ = х₁Åх₂ F₁₀ = ₂ F₁₁ = x₁₂

x₁ x₁ x₁

x₂ y₉ x₂ 1 y₁₀ x₂ 1 y₁₁

F₁₂ = ₁ F₁₃ =₁ х₂ F₁₄ = ₁₂

x₁ x₁ x₁

x₂ 1 y₁₂ x₂ 1 y₁₃ x₂ & y₁₄

На основании этих элементов можно синтезировать любую логическую функцию.

f(х₁,х₂,х₃) = х₁х₂х_{3 1}х₂ х_{1 2 123}

_{02 07}

^{x1 00 1}

^{x2 01 &} ₀₃ ⁰⁴ ₁₂

₀₄ ⁰⁵ ₀₉ ¹

^{x3 02 &} ₀₆ ^& _{08 09 1 14 f}

⁰⁰ ₁ ^{07 &}

⁰⁵ ₁₀ ¹⁰

₀₁ ^{01 &} ₁₁ ¹

¹ ₀₀

_& ¹¹

₀₆

Реализуем функцию вида f(х₁,х₂,х₃):

f(х₁,х₂,х₃) = х₁₂х₃ & ₁х₃

^{x1 00} ₀₄

^{x2 01 &} _{03 04 1} ⁰⁶

_{x3 02 &} ⁰⁴

^& _{08 1} ^{f 09}

⁰⁵ ₀₇

_& ^{05 05 1}

f(х₁,х₂,х₃) = х₁₂х_{3 1}х₃ = ₁х₂₃x₁₃

_{x1 00 00}

_{x2 01 00} ^{1 03 03} _{1 05}

_{x3 02} ⁰¹

_{04 1 06}

₀₈

₀₂ ^{00 1 10 f}

_{02 1} ^{04 04 1} _{07 1} ⁰⁹

СВОЙСТВА БУЛЕВЫХ ФУНКЦИЙ.

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

Функциональный класс замкнутый,если суперпозиция этого класса принадлежит этому же классу.

Например, класс функций, полученных с помощью дизъюнкции аргументов замкнут.

y(x₁,x₂) = x₁x₂ ,где x₂(z₁,z₂) = z₁z₂

y(x₁,x₂(z₁,z₂)) = y(x₁,z₁,z₂) = x₁z₁z₂

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

Набор – фиксируемое значение аргументов функции d, t d = {0110}

Между различными наборами установим соотн. сравнения:

d₁ > d₂, если любой элемент набора d₁ ³ соответственно элементу из набора d₂

d₁ = (11010)

d₂ = (01010) Þ d₁ > d₂

t₁ = (01001)

t₂ = (10100) Þ 2 набора несравнимы

d = (d₁, d₂, …,d_n)

t = (t₁, t₂, …,t_n) наборы знач. перем. знач. и считается d > t, если d_i > t_i

ТЕОРЕМА.

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

ДОКАЗАТЕЛЬСТВО.

Возьмем произвольные значения d и t, причем d £ t. В этом случае условию теоремы удовлетворяют следующие возможности:

у(d) = 0, у (t) = 0

у(d) = 0, у (t) = 1

у(d) = 1, у (t) = 1

Откуда следует, что для доказательства теоремы достаточно доказать следующее утверждение:

если d £ t, то у (d) = 1 у (t) = 1

Докажем это утверждение.

Если у(d) = 1, то всегда найдется интервал, для которого выполняется следующее условие:

x_j1, x_j2 … x_jk|_d = 1, где d_j1 = d_j2 = d_jk