Восьмеричная система исчисления.

КОНСПЕКТ ЛЕКЦИЙ

по дисциплине

"Дискретная математика"

для студентов направления подготовки
09.03.02 «Информационные системы и технологии»

Рассмотрено на заседании кафедры «Автоматизированные системы управления»

Протокол № 6

от 19 января 2017 г.

Донецк

Конспект лекций по дисциплине "Дискретная математика" для студентов направления подготовки 09.03.02 «Информационные системы и технологии» профиля «Информационные системы и технологии в технике и бизнесе» / сост.: А. И. Секирин. – Донецк, ДОННТУ. 2017. –95 с.

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

Конспект лекций предназначен для студентов направления подготовки 09.03.02 «Информационные системы и технологии» очной и заочной форм обучения.

Составитель доц. Секирин А.И.

Ответственный за выпуск: доц. Привалов М.В.

СОДЕРЖАНИЕ

ВВЕДЕНИЕ. 3

СИСТЕМЫ ИСЧИСЛЕНИЯ. ПЕРЕВОД ИЗ ОДНОЙ СИСТЕМЫ СЧИСЛЕНИЯ В ДРУГУЮ. 5

ВОСЬМЕРИЧНАЯ СИСТЕМА ИСЧИСЛЕНИЯ. 6

ШЕСТНАДЦАТЕРИЧНАЯ СИСТЕМА. 7

ПОРЯДОК ПЕРЕВОДА ИЗ ОДНОЙ СИСТЕМЫ СЧИСЛЕНИЯ В ДРУГУЮ (АЛГОРИТМ ПЕРЕВОДА). ПЕРЕВОД ЦЕЛЫХ ЧИСЕЛ. 7

ДВОИЧНО-ДЕСЯТИЧНАЯ СИСТЕМА.. 9

АРИФМЕТИЧЕСКИЕ ОПЕРАЦИИ С ДВОИЧНЫМИ ЧИСЛАМИ (СЛОЖЕНИЕ, ВЫЧИТАНИЕ, УМНОЖЕНИЕ, ДЕЛЕНИЕ). 10

ЭЛЕМЕНТЫ ТЕОРИИ МНОЖЕСТВ. 13

АКСИОМЫ ТЕОРИИ МНОЖЕСТВ.. 15

ДОПОЛНИТЕЛЬНЫЕ ОПЕРАЦИИ НАД МНОЖЕСТВАМИ. 17

ЗАКОНЫ ДЛЯ ПЕРЕСЕЧЕНИЯ И ОБЪЕДИНЕНИЯ . 18

МИНИМИЗАЦИЯ ФУНКЦИОНАЛЬНОГО ПРЕДСТАВЛЕНИЯ.. 21

МНОЖЕСТВ. 21

СТАНДАРТНЫЕ ФОРМЫ ПРЕДСТАВЛЕНИЙ ФОРМУЛ.. 22

МНОЖЕСТВ. 22

МАТЕМАТИЧЕСКИЕ УТВЕРЖДЕНИЯ. 25

ГРАФИЧЕСКАЯ МИНИМИЗАЦИЯ ФУНКЦИИ ОТ.. 27

ТРЕХ ПЕРЕМЕННЫХ. 27

МИНИМИЗАЦИЯ ФУНКЦИИ ТРЕХ ПЕРЕМЕННЫХ ГРАФИЧЕСКИМ СПОСОБОМ. 29

МИНИМИЗАЦИЯ ФУНКЦИИ С ПОМОЩЬЮ КАРТ КАРНО. 29

МИНИМИЗАЦИЯ ФУНКЦИИ МЕТОДОМ КВАЙНА.. 33

СПОСОБЫ ПОКРЫТИЯ ТАБЛИЦЫ КВАЙНА.. 36

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

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

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

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

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

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

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

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

ЛИНЕЙНЫЕ ФУНКЦИИ И АЛГЕБРА ЖЕГАЛКИНА. 59

ФУНКЦИОНАЛЬНО – ПОЛНЫЕ СИСТЕМЫ И БАЗИСЫ В ШИРОКОМ СМЫСЛЕ. 61

ПОСТРОЕНИЕ БАЗИСА Р_a В ШИРОКОМ СМЫСЛЕ. 62

ФУНКЦИОНАЛЬНО – ПОЛНЫЕ СИСТЕМЫ И БАЗИСЫ В УЗКОМ СМЫСЛЕ. 63

ВТОРАЯ ТЕОРЕМА О ФУНКЦИОНАЛЬНОЙ ПОЛНОТЕ. 64

СИНТЕЗ КОМБИНАТОРНЫХ СИСТЕМ. 68

МЕТОД КАСКАДОВ. 71

АЛГЕБРА ВЫСКАЗЫВАНИЙ И ЛОГИКА ПРЕДИКАТОВ. 81

ЭЛЕМЕНТЫ ТЕОРИИ АВТОМАТОВ. 87

ЭКВИВАЛЕНТНЫЕ СОСТОЯНИЯ И АВТОМАТЫ. 90

РЕАЛИЗАЦИЯ КА. 94

ВВЕДЕНИЕ.

Предлагаемый курс называется ОДМ - "основы дискретной математики" или в общем случае - математическая теория систем.

Дадим формальное определение системе.

Системой будем называть устройство преобразования информации.

Схематически систему можно представить следующим образом:

L

X(T)Þ Þ Y(T)

X(Y)-вектор входных информационных процессов, длины N, с компонентами Xi(T).

Y(T)-вектор выходных информационных процессов, длины N, с компонентами Yi(T).

T-множество моментов времени, в течение которого происходит работа системы.

Рассмотрим подробно информационные процессы, трансформируемые или

передаваемые системы:

1.Аналоговые системы в непрерывном времени.

Представляются функцией f(t) [a;b] - область значений функции принадлежит интервалу [a;b].

f(t)

_{t i t} t

tÎ [0, ]

2.Аналоговые процессы в дискретном времени.

Дискретным временем назовем множество определенных моментов времени. Такие процессы представляются функцией от дискретного аргумента f(idt),где dt - интервал между выбранными временными отрезками

(шаг дискретизации).

3.Квантованные процессы в непрерывном времени.

Эти процессы также представляются функцией f(t), но область значений функции является конечным множеством.

f(t)

df

_t t

df - шаг квантования.

4.Квантовые процессы в дискретном времени.

Представлены функцией от дискретного аргумента idt и проквантованы по уровню.

f(t)

_{t i t} t

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

цифр им соответствующих, так, например если a=1, а b=6, то представляемый цифровой процесс задается рядом:

2.5 3.5 5 5 3.5 2 2 4 5 .

Символы соответствующие цифровому процессу называются алфавитом

процесса.

В соответствие с выше указанным разделением информационных процессов

их можно классифицировать по системам.

Так системы, работающие с информационными процессами 1 и 2, называются аналоговыми системами с непрерывным и дискретным временем соответственно. Системы, использующие процесс 3, называются квантованными системами с непрерывным временем. Системы, использующие процесс 4, называются цифровыми или дискретными системами.

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

Если говорить о математическом аппарате, который используется

для изучения дискретных систем, то таким аппаратом является раздел математики, который называется дискретная математика.

В состав дискретной математики входят следующие основные разделы:

1.Теория множеств.

2.Булева алгебра.

3.Теория автоматов.

4.Теория алгоритмов.

1.Теория множеств изучает множества и отношения между ними.

2.Булева алгебра - изучает комбинаторные системы, системы имеющие

один оператор или системы с одним состоянием.

3.Теория автоматов - занимается системами с несколькими состояниями.

4.Теория алгоритмов - само говорит за себя.

СИСТЕМЫ ИСЧИСЛЕНИЯ.
ПЕРЕВОД ИЗ ОДНОЙ СИСТЕМЫ СЧИСЛЕНИЯ В ДРУГУЮ.

1.Десятичная и двоичная система счисления.

Числа могут быть записаны в любой системе. В десятичной системе основание 10. По такому принципу можно построить произвольную систему с произвольным основанием b. В общем случае любое число N можно представить в виде полинома:

N=P_nb_n+P_n-1b^n-1+…+P₁b¹+P₀b⁰+P_-1b^-1+…+P_-mb^-m

N= P_ibⁱ

b - основание системы;

P - целое число, называемое позиционной цифрой.

Степень и основание системы называются весами.

Пример:

547=5*10²+4*10¹+7*10⁰=500+40+7=547

В принципе персональные компьютеры могут быть построены на любой

системе счисления. Но используется двоичная система, потому что

имеет ряд достоинств:

1) имеет наименьшее кол-во цифр, необходимых для записи цифр (0 и 1)

2) наиболее экономична с точки зрения аппаратной реализации.

3) обеспечивает простоту выполнения элементарных арифметических операций.

Для перевода чисел в десятичную систему из двоичной используется

последовательность весов вида:

2³ 2² 2¹ 2⁰

Пример:

1. 101101₂=1*2⁵+0*2⁴+1*2³+0*2¹+1*2⁰=32+8+4+1=45₁₀

2. 10101,1101₂=1*2⁴+0*2³+1*2²+0*2¹+1*2⁰+1*2^-1+1*2^-2+0*2^-3+1*2^-4= =16+4+1+0.5+ +1/16=21,8125₁₀

ШЕСТНАДЦАТЕРИЧНАЯ СИСТЕМА.

Применяется для облегчения чтения записи двоичных кодов. Т.К. основанием является 16, что составляет 2⁴, то для перевода из двоичной в шестнадцатеричную двоичное число разбивается на 4-х битовые группы, называемые тетрадами.

b=10

b=16

a

b

c

d

e

f

Пример:

1011 1110 1111 1001 1101 1000 = bef9d8

b e f 9 d 8

ПОРЯДОК ПЕРЕВОДА ИЗ ОДНОЙ СИСТЕМЫ СЧИСЛЕНИЯ В ДРУГУЮ (АЛГОРИТМ ПЕРЕВОДА). ПЕРЕВОД ЦЕЛЫХ ЧИСЕЛ.

1. Поделить данное число на основание новой системы .

2. Перевести остаток от деления в новую систему исчисления.

Получится младший разряд нового числа.

3. Если частное от деления больше основания системы, то продолжить

деление, второй остаток от деления даст 2-й разряд и т.д.

Перевести 256 из 10-й в 8-ую.

256 8

24 32 8

16 32 4 256₁₀=400₈

16 0 400₈=4*8²=256₁₀

0

Перевести 397 из 10-й в 16-ую.

397 16

32 24 16

77 16 1 397₁₀=18D₁₆

64 8

13

18*d=1*16²+8*16¹+13*16⁰=256+128+13=397₁₀

Перевод дробной части

1.Умножить дробную часть на основание новой системы исчисления.

2.В полученном произведении выделить целую часть числа. Это будет старший разряд искомого числа.

3.Дробную часть произведения снова умножить на основание системы.

Целая часть будет следующим разрядом.

4.Выполнять умножение до получения необходимого количества разрядов.

Пример:

0,784₁₀ перевести в двоичную

0,784

2 0,784₁₀=0,11001₂

1,568

2

1,136

2

0,272

2

0,544

2

1,088

Перевести:

0,6125 в 8-ую

0,6125

8 0,6125₁₀=0,47146₈

4,9000

8

7,2000

1,6000

4,8000

Перевести: 0,378 в 16-ую

0,378

16 0,378₁₀=0,60c4₁₆

2,268

6,048

288

0,768

12,288

16

4,608

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

ДВОИЧНО-ДЕСЯТИЧНАЯ СИСТЕМА

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

Пример:

7 4 3 5 (7435₁₀)

0111 0100 0011 0101_10-2

Пример: перевести 01100101 в двоичный эквивалент.

Представим данное число через веса его разрядов:

0110*10¹ + 0101*10⁰=0110(8+2)+0101

Для упрощения умножения выразим весовой коэффициент 10 в виде (8+2). Учитывая, что умножение на 8 есть сдвиг на 3 разряда влево, а

на 2 - на 2 разряда влево, то получим.

1000001

1=1

2=2¹

8=2³

ЭЛЕМЕНТЫ ТЕОРИИ МНОЖЕСТВ.

Теория множеств является логической основой современного математического аппарата.

Основатель теории множеств Г.Кантор определял множество следующим понятием : «под множеством понимают всякую совокупность определенных элементов, которое может быть связано с помощью некоторого закона." Множество обозначают большими буквами латинского алфавита.

Объекты, составляющие множество называются его элементами и обозначаются маленькими латинскими буквами.

Для того чтобы указать, что множество состоит из элементов X применяют, вот такую форму записи:

A={X}

Если нужно указать характеристическое свойство согласно которого

объекты объединяются во множества применяется следующая запись: A={X:...} где ... характеристическое свойство.

Например:

B={X:x²-1=0}

Элементами множества B является множество корней уравнения x²-1=0 КЛАССИФИКАЦИЯ МНОЖЕСТВ:

Условимся различать конечные и бесконечные множества.

Конечным множеством назовем множество, количество элементов которого

может быть выражено конечным числом, причем неважно, что это за число. Главное, что оно существует. Примерами конечных множеств может служить количество рук человека, количество букв на странице конспекта,

число букв во всех изданных книгах.

К конечным множествам мы также будем относить и пустое множество, не содержащее элементов.

К бесконечным множествам отнесем все множества, не являющиеся конечными. Примерами бесконечных множеств может служить множество

всех целых чисел, множество точек на плоскости.

Конечные множества могут быть заданы простым перечислением его

элементов.

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

Пример: C={X1,X2,X3,X4}

Введем некоторые основные понятия и обозначения.

Для того чтобы указать, что X есть элемент множества A пишут: X A

Чтобы указать, что X не принадлежит множеству A записывают таким образом: X A

Если множества A и B совпадают, то пишут: A=B

Это означает, что элементы этих множеств одни и те же.

Пример:

B-множество всех студентов в аудитории.

A-множество всех студентов мужского пола (горный факультет).

Если элементы множества A содержатся во множестве B, то записывается это следующим образом:

A B

и читается :"A содержится в B".

АКСИОМЫ ТЕОРИИ МНОЖЕСТВ

Существует 6 изначальных аксиом теории множеств:

1-Аксиома существования:

"существует хотя бы одно множество".

Все аксиомы мы будем сопровождать диаграммами Эйлера.

2-Аксиома эквивалентности:

"если множество A и B состоят из одних и тех же элементов,

то они равны"

A=B

3-Аксиома объединения:

"Для двух произвольных множеств A и B существует такое множество

C, элементами которого является каждый элемент содержащийся хотя бы в одном из этих множеств".

Аксиома обобщается на случай нескольких исходных множеств и звучит так:

"Для произвольных множеств A_i существует множество C, элементами которого является каждый элемент, содержащийся хотя бы в одном из этих множеств A_i".

Аналитическое выражение для двух множеств:

C =AÈB

Для операции объединения справедливы свойства:

1) AÈA=A

2) AÈI = I

3) A È Æ =A

Исходя из этих свойств бинарную операцию объединения обозначают следующим образом:

C=A+B

А множественную операцию обозначают:

M = M_i

4-Аксиома пересечения:

"Для двух произвольных множеств A и B существует множество C элементами которого является каждый элемент, принадлежащий как множеству A, так и множеству B".

Аналитически записывается C=A Ç B

читается множество C равно пересечению множеств A и B.

Для операции пересечения справедливы следующие соотношения:

1) A Ç A = A

2) A Ç I = I

3) A Ç Æ =Æ

Обобщенная аксиома на случай нескольких исходных множеств:

"Для произвольных множеств A_i существует множество C, элементами которого является каждый элемент, принадлежащий множествам A_i одновременно".

Далее бинарная операция будет обозначаться:

C=A*B

А множественная:

M= M_i

5-Аксиома универсального множества:

"Для произвольной группы множеств A_i всегда можно выбрать такое множество I, что A_i Ì I".

Множество I назовем единичным множеством универсальным.

6-Аксиома пустого множества:

"Всегда существует пустое множество - Æ, которому не принадлежит ни один элемент, иначе нулевое множество".

МНОЖЕСТВ.

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

С = f (A_i)

f – функция переводит элементы A_i во множество С.

Если пересечение множеств обозначать как функциональную операцию Р , то

Р (А,В) = АВ

На единичном множестве 1 заданы множества А,В,С. В этом случае с помощью известной операции над множествами переводим исходное множество в какое-либо другое.

f (А,В,С) = АВС È А С È В È È АВ È AС È С È В;

Записанное выражение назовем формулой. Определим сложность формулы, как количество, содержащихся в ней исходных множеств. Для приведенного примера сложность =20. При аналазе формул первым вопросом является: «Можно ли уменьшить сложность формулы?» Сделаем это на примере применяя законы дистрибутивности и поглощения

f(А,В,С) = АВС È А È В È È А(В È С) È (В È С) =

= АВС È А È B È È В È С = ВÈ А È È С =

= È В È С = È =1

f(А,В,С) = АС È С È ВС È АВС È АВ È В = АС È С È В È АВ =

=В È АС È С;

Или :

F(А,В,С) = АС È С È ВС È АВС È АВ È В = АС È С È ВС È АВ È È В = АС È С È ВС È В = С È В

Как видно из примеров минимизация одних и тех же функций может дать разные результаты при применении одних и тех же законов.

МНОЖЕСТВ.

На 1 определении М₁,М₂,М₃ совокупность М_i назовем порожд-ми множествами пространства и определим М_i по универсальной формуле:

М_i ; d_i =1;

M_i^di = d_i={0;1}

_i ; d_i =0;

Мi = i = {0,1}

Mi; i=0;

M_i, d_i – первичный термом

K_i = _i^di - конституентой

n - число порожденных множеств.

Перечислим все конституенты нашего примера:

К₀ = _{1 2 3} К₁ = _{1 2}М₃ К₂ = ₁М_{2 3} К₃ = ₁М₂М₃

К₄ = М_{1 2 3} К₅ = М_{1 2}М₃ К₆ = М₁М_{2 3} К₃ = М₁М₂М₃

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

К₀ = 000; К₁ = 001; К₂ = 010; К₄ =011; К₅ = 100; К₆ = 110; К₇ = 111.

Если учесть,что каждой конституенте длины П можно сопоставить n разр.

двоичное число, то общее количество конституент равно:

N = 2ⁿ

1) Выражения, заданные с помощью формул ,могут быть упрощены.

2) Необходимые шаги для упрощения не всегда очевидны и сложность упрощения находится в прямой зависимости от числа аргументов в формуле.

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

Пересечение двух различных конституент - пустое множество.

Пересечение двух конституент – есть пересечение всех первичных термов их составляющих, если конституенты не равны , то найдется хотя бы 1 разряд с несовпадающими первичными термами.

Обозначим этот разряд через i.

M_i^di *M_i^di*= Æ

Объединение всех коституент,порожденных множествами M_i на универсальном множестве равно самому универсальному множеству:

I= (M_i È _i)

n=1 M₁, ₁ M₁+ ₁=I

n=k _j = I

С помощью конституент, образованных множествами M_i ,можно представить исходное универсальное множество.

1. Проиллюстрируем на графическом примере:

(универсальное множество I, внутри М₁-квадрат, М₂-треугольник, М₃-круг).

В дополнение к рассматриваемым свойствам ,рассмотрим сколько множеств на I можно образовать из конституент.

Для этого произвольному множеству сопоставим m-разрядное двоичное число,где m-длина конституент. При этом 0-отсутствие конституенты, 1-присутствует.

Так например, двоичному числу

01101001 соответствует множество, из объединенных 0,3,5,и 6 конституент.

Вместо двоичных чисел можно использовать их десятичный эквивалент:

d = 1+2³+2⁵+2⁶ = 1+8+32+64 = 40+ 65 = 105

Если любому, образованному из конституент, множеству соответствует m-разрядное двоичное число, то таких множеств может быть 2^m,а так как число конституент = 2ⁿ , где n-число образованных множеств,то общее число, которое образуется из конституент = 2^{2^n}

Для иллюстрации это количество -256.

Рассмотрев понятие конституент зададимся вопросом:»Как конституенты связаны с функциями от образующих множеств?»

МАТЕМАТИЧЕСКИЕ УТВЕРЖДЕНИЯ.

Множество M_i равно объединению всех конституент ,содержащих M_i

Рассмотрим равенство:

I = _j-1

Возьмем пересечение левых и правых частей с M_i

Mi = _j-1M_i

Рассмотрим выражение К_j,M_i. Для него возможны два случая:

1.K_j не содержит в себе M_i, Ki*Mi = Æ

2.K_j Ì M_i , K_j*M_i =K_j

Следовательно, M_i можно представить в виде:

М_i = _l

k_l -конституенты,содержащие M_i.

ТЕОРЕМА.

Любая функция от порождающих множеств представима в виде объединения конституент.

Из аксиоматичного построения следует,что все операции представимы через операции объединения и отрицания.

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

Для доказательства рассмотрим объединение произвольно образованных множеств M_i и М_к.

Согласно утверждению (M_i È М_к) ,записывающихся в виде:

М_i È М_к = _j+ _l М_i È М_к = _j

при этом М – различно,так как различно число совпадающих конституент в представлениях множеств M_i иМ_к.

Остается доказать,что дополнения к объединению конституент в свою очередь есть объединение конституент .

Так как универсальльное множество является объединением всех конституент, ясно ,что если взять объединение некоторых из них, то оставшиеся конституенты будут дополнительными к исходному объединению.

Рассмотрим пример:

Функция от множеств А,В,С

f(A,В,С) = А(В È ((С А)\В)) = А(В È ((С È С )\В)) = А(В È (С È А) ) =

А(В È С È А ) = АВ È А = А È АВС È АВ

Из пересечения АВ получена АВС È С. Ясно ,чтобы получит трех-разрядную конституенту, необходимо до термов АВ добавить С, а так как произв-но множество М:

М(С È ) = МС È М АВ = АВС È АВ

то просто получим из АВ трехразрядную конституенту.

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

Если в представлении функции участвовали конституенты меньшей длины, то оно называется норм. формой Кантора (НФК).

Для получения РФК нужно минимизании СНФК любым (аналитическим, графическим,графо-аналитическим способом).

Назовем интервалами универсального пространства ранга n все коституенты длина l =1, n

Если какая-либо С₁ (интерв.) = С₂È С₃, то говорят что С₁ включает в себя С₂ и С₃ или С₁ покрывает С₂ и С₃

Из этого следует , что функция ,представленная в СНФК равна:

f (A,В,С) = _j= _l

где C_l - интервалы,покрывающие все конституенты К_j .

Если рассмотреть предыдущий пример,то можно заметить ,что f(А,В,С):

f (A,В,С) = АВ È А

где, АВ покрывает АВС и АВ , а втор. совпадает с А .

ТРЕХ ПЕРЕМЕННЫХ.

Введем геометрическое представление интервалов при n=3.

Для этого каждой из 8 конституент , сопоставив вершину трехмерного куба и двоичный эквивалент. При этом расположим вершины так,чтобы их двоичные представления отличались лишь в одном разряде.

Сопоставим коституенты с их двоичным эквивалентом:

000 – ; 001 – C; 010 – В ; 011 – ВС; 100 – А ;

101 – А С; 110 – АВ ; 111 – АВС.

Рассмотрим более сложные интервалы:

È В =

О – О , где — - отсутствие разряда

Геометрически - сопоставляется ребро соединения вершины 000 и 010.

Запишем соответствие ребер интервала:

-00 = ; -01 = С; -10 = В ;

0-0 = ; 0-1 = С; 1-0 = А ;

00- = ; 01- = В; 10- = А ;

-11 = ВС; 1-1 = АС; 11- = АВ.

По аналогии ребра конституенты можно объеденить в грань.

АВ È В È В È ВС = В

Соответствия граней:

--0 = ; --1 = С

-0- = ; -1- = В;

0-- = ; 1-- = А.

Для представления функции на кубе ,участвующие интервалы выделяются.

111 110

_{101 100}

001 000

f(A,В,С) = С È В

111 B 110

В этом примере видно,что конституенты В и

ВС покрытые В

^{101 100} и В и АВ покрытые В можно покрыть одним

_{001 000} интервалом В.

f(A,В,С) = С È В

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

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

Алгебра – это множество М, с заданными на нем функциями, обладающими свойствами замкнутости.

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 < + , * , > - алгебраическая система

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

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