Конспект лекций по дискретной математике - реферат

Приложение Булевой алгебры к синтезу комбинационных схем

Двоичная система логики:

1. Элементы Булевой алгебры:

а) числа

b) переменные

с) операции

d) выражения

e) функции

f) законы

А) Числа:

Два числа: логический ноль и логическая единица в Булевой алгебре отождествляются с понятиями “правда” и ”ересь”.

В) Переменные:

Булевы (логические, двоичные) переменные именуются переменными, принимающими значение из огромного количества Конспект лекций по дискретной математике - реферат - ноль и единица.

С) Операции:

1. Отрицание (инверсия).

2. Конъюнкция (логическое умножение).

3. Дизъюнкция (логическое сложение).

Унарной является операция отрицания.

Обозначения:

1. Отрицание , ù x

2. Конъюнкция a&b, a·b, ab, aÙb

3. Дизъюнкция aÚb

D) Выражения:

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

Ценность задается порядком операции.

Е) Функции:

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

Областью определения Булевой функции является совокупа 2n двоичных наборов ее аргументов. Набор аргументов можно рассматривать как n-компонентный двоичный вектор.

Формы задания Булевой функции:

1. Аналитическая (в виде логического выражения Конспект лекций по дискретной математике - реферат)

2. Табличная (в виде таблицы истинности)

3. Графическая

4. Таблично-графическая (в виде карты Карно)

5. Числовая

6. Символическая форма

1) Аналитическая:

_ _

y=(x1 Ú x2 ) x3

_ _ _ _ _ _

y=x1 x2 x3 Ú x1 x2 x3 Ú x1 x2 x3

2) Табличная:

x1

x2

x3

_

x1 Ú x2

y

0 0 0 1 1
0 0 1 1 0
0 1 0 1 1
0 1 1 1 0
1 0 0 0 0
1 0 1 0 0
1 1 0 1 1
1 1 1 1 0

Переход от аналитической к табличной однозначен! Оборотный переход не является конкретным.

Главные законы (тождества Конспект лекций по дискретной математике - реферат)

1) ab=ba

aÚb=bÚa

2) Ассоциативный:

a(bc)=(ab)c

aÚ(bÚc)= (aÚb) Úc

3) Дистрибутивный:

a(bÚc)=abÚac

aÚ(bc)=(aÚb)(aÚc)

4) Закон двойного отрицания:

=

a=a

5) Тавтологии:

aa=a

aÚa=a

6) Законы нулевого элемента:

a0=0

aÚ0=a

7) Законы единичного элемента:

а1=а

аÚ1=1

8) Законы дополнительного элемента:

_

В Булевой алгебре дополнительным элементом к Конспект лекций по дискретной математике - реферат а является а.

_ _

аÚа=1; аа=0

9) Двойственности (деМоргана):

__ _ _

ab=aÚb

___ _ _

aÚb=a b

Cледствия: ab=aÚb; aÚb=a b

10) Поглощения:

aÚab=a

a(aÚb)=a

11) Сокращения:

_

аÚаb=aÚb

_

a(aÚb)=ab _ _ _ _

Cледствия: aÚab=aÚb; a(aÚb)=ab

12) Склеивания:

_ _

abÚab=a Конспект лекций по дискретной математике - реферат; (aÚb)(aÚb)=a

Комменты:

1) Для подтверждения законов можно использовать:

а) Способ совершенной индукции.

б) Внедрение одних законов для подтверждения других законов.

Способ совершенной индукции состоит в подтверждении эквивалентности левой и правой части на всем огромном количестве наборов аргументов. Для этого составляется таблица истинности.

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

3) Некие законы можно распространять на случайное число частей Конспект лекций по дискретной математике - реферат.

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

5) Законы используются для упрощения Булевых функций.

Обилие Булевых функций.

1. Булева функция от одной переменной.

Обозначение аргумента и функции

Значения аргумента и функции

Наименование функции
x 0 1
0 0 Логический ноль
0 1 Повторение x
1 0 Инверсия x
1 1 Логическая единица

2. Вероятные функции от 2-ух переменных.

Обозначение аргументов и функций

Значение аргументов и функций

Обозначение функций Наименование Вырожденность Представление функции в Конспект лекций по дискретной математике - реферат булевом базисе
0 0 0 0 “0” Логический ноль + -
0 0 0 1 x1 &x2 Конъюнкция - x1 x2
0 0 1 0 x1 D x2 Запрет x1 по x2 - x 1 2
0 0 1 1 x1 Повторение x1 + -
0 1 0 0 x2 D x1 Запрет x2 по x1 - x 2 1
0 1 0 1 x2 Повторение x2 + -
0 1 1 0 x1 Å x2 Сумма по модулю 2 неравнозначная (исключительное либо) XOR - 1 x2 Ú x1 2
0 1 1 1 x1 Ú x2 Дизъюнкция - x1 Ú x2
1 0 0 0 x1 ¯ x2 Функция Конспект лекций по дискретной математике - реферат Вебба - x1 Ú x2
1 0 0 1 x1 º x2 Равнозначность - 1 2 Ú x1 x2
1 0 1 0 2 Отрицание x2 + -
1 0 1 1 x2 ® x1 Импликация от x2 к x1 - 2 Ú x1
1 1 0 0 1 Отрицание x1 + -
1 1 0 1 x1 ® x2 Импликация x1 к x2 - 1 Ú x2
1 1 1 0 x1 | x2 Штришок Шеффера -
1 1 1 1 “1” Логическая единица + -

Определение: Булева функция от n аргументов fn (x) именуется вырожденной по аргументу Конспект лекций по дискретной математике - реферат xi , если ее значение не находится в зависимости от этого аргумента, другими словами для всех наборов аргументов имеет место равенство:

f(x1 , x2 , ... , xi-1 , 0, xi+1 , ... , xn ) = f(x1 , x2 , xi-1 , 1, xi+1 , ... , xn ).

Функция запрета x1 Dx2 воспринимает значение, равное нулю при равенстве запрещающей переменной (x2 ) единице и повторяет значение аргумента Конспект лекций по дискретной математике - реферат x1 при равенстве запрещающей переменной нулю.

Понятие импликации в Булевой алгебре отождествляется с выражением следования (если ... то ... ).

Пример: Имеют место два обычных выражения.

А. На небе тучи.

В. Идет дождик. В®А

А В В®А
f f t
f t f
t f t
t t t

Из правды не может следовать ересь!

Некие функции от 3-х переменных.

Значение аргументов

Значение функций

Сумма по модулю 2 Исключающее Либо Функция мажоритарности
x Конспект лекций по дискретной математике - реферат1 x2 x3 x1 Åx2 Åx3 XOR (x1 ,x2 ,x3 ) x1 #x2 #x3
0 0 0 0 0 0
0 0 1 1 1 0
0 1 0 1 1 0
0 1 1 0 0 1
1 0 0 1 1 0
1 0 1 0 0 1
1 1 0 0 0 1
1 1 1 1 0 1

Функция - сумма по модулю 2 и исключающее Либо являются эквивалентными только для 2-ух аргументов.

n

Общее обилие функций от n аргументов равно 22

В самом малогабаритном виде всякую Булеву функцию можно представить символически: , где n-количество аргументов, а N Конспект лекций по дискретной математике - реферат-десятичный эквивалент двоичного набора значений функции на упорядоченном огромном количестве аргументов.

Пример:

f3 (x)=x1 Åx2 Åx3 =

Невырожденные функции от 2-ух переменных с добавлением функции отрицания принято именовать функциями Булевой алгебры. С учетом обращаемости неких базисных функций к неким аргументам, их полное количество равно 9.

Обычные формы Булевых функций

Обычные Конспект лекций по дискретной математике - реферат формы - это особенный класс аналитических выражений, применяемых при решении задачки минимизации Булевых функций и для перехода от табличной формы задания к аналитической. Обычные формы строятся на основании операций конъюнкции, дизъюнкции и отрицания, при этом отрицание только единственной переменной.

Определение: Простой конъюнкцией (дизъюнкцией) именуется конъюнкция (дизъюнкция) конечного числа Конспект лекций по дискретной математике - реферат попарно различимых переменных либо их отрицаний.

Простую конъюнкцию (дизъюнкцию) принято именовать конъюнктивным (дизъюнктивным) термом.

В личном случае терм, как конъюнктивный так и дизъюнктивный может состоять из единственной буковкы (литерала). Под буковкой будем осознавать аргумент Булевой функции и его отрицания.

Примеры конъюнктивных термов:

_ _

x1 , x2 , x1 x3 , x2 x Конспект лекций по дискретной математике - реферат4 x5 (терм)

___ _

x1 x2 , x1 x2 x3 (не терм)

Рангом терма именуется количество букв входящих в него.

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

Каноническая обычная форма.

Конституентой единицы (нуля) именуется конъюнктивный (дизъюнктивный) терм наибольшего ранга. Т.е. для Булевой функции Конспект лекций по дискретной математике - реферат от n переменных конституента содержит в себе n букв.

Свойство конституенты: Конституента единицы (нуля) воспринимает значение единицы (нуля) на одном и только одном наборе аргументов.

Пример: _ _

n=4 x1 x2 x3 x4 (1010)=1

_ _ _

x1 Úx2 Úx3 Úx4 =0

Определение: Дизъюнктивная (конъюнктивная) обычная форма именуется канонической, если все ее дизъюнктивные (конъюнктивные) термы Конспект лекций по дискретной математике - реферат представляют собой конституенты единицы (нуля). Время от времени канонические формы именуют совершенными.

Пример получения канонических форм:

y=x1 Åx2

x1 x2 y Конституента единицы Конституенты нуля
0 0 0 - x1 Úx2
0 1 1 1 x2 -
1 0 1 x1 2 -
1 1 0 - 1 Ú 2

КДНФ - каноническая дизъюнктивная обычная форма:

_ _

y=x1 x2 Úx1 x2

ККНФ - каноническая конъюнктивная обычная форма:

_ _

y=(x1 Úx2 )(x1 Úx2 )

1) При помощи канонических форм Конспект лекций по дискретной математике - реферат более просто осуществляется переход от табличной формы задания Булевой функции к аналитической.

2) При помощи канонических форм можно выполнить преобразование хоть какой функции в Булев базис.

3) Неважно какая Булева функция кроме логического нуля и логической единицы имеет единственные КДНФ и ККНФ. Логическую единицу можно представить в виде КДНФ и Конспект лекций по дискретной математике - реферат логический ноль в виде ККНФ.

4) Правило перехода от табличной формы задания Булевой функции к аналитической:

а) в таблице истинности выделяются все наборы аргументов, при которых функция равна единице (нулю).

б) для каждого из этих наборов составляют конституенты единицы (нуля).

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

Пояснение: при составлении конституент единицы (нуля) употребляют последующее правило:

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

5) КДНФ и ККНФ представляют собой две разные, но эквивалентные аналитические формы Конспект лекций по дискретной математике - реферат булевой функции. Это значит, что из одной формы можно получить другую, используя законы Булевой алгебры.

_ _ _ _ _ _ _ _ _ _

y=(x1 Úx2 )(x1 Úx2 )=x1 x1 Úx1 x2 Úx2 x1 Úx2 x2 =x1 x2 Úx2 x1 =x1 x2 Úx1 x2 (КДНФ)

6) Принципно существует другой метод получения ККНФ:

а) составляется КДНФ, но не для самой Конспект лекций по дискретной математике - реферат, а для ее отрицания.

б) берется отрицание над приобретенной КДНФ, которое снимается с применением закона двойственности.

_ _ _ = ------------ ----- ---- _ _

y=x1 x2 Úx1 x2 , y=y=x1 x2 Úx1 x2 =x1 x2 x1 x2 =( x1 Úx2 )(x1 Úx2 )

Обилие двоичных алгебр

В связи с тем, что всякую сколь угодно сложную Булеву функцию Конспект лекций по дискретной математике - реферат можно представить в канонических формах, другими словами записать ее при помощи операций отрицания, конъюнкции и дизъюнкции эта система Булевых операций обладает свойством многофункциональной полноты, т.е. образует так именуемый базис. Естественно представить, что система Булевых операций является не единственной, при помощи которой можно образовать некий базис.

В принципе Конспект лекций по дискретной математике - реферат всякую из базисных функций можно отождествить соответственной операцией и на базе совокупы этих операций выстроить двоичные алгебры, хорошие от Булевой. К более всераспространенным двоичным алгебрам относятся: алгебра Жигалкина (Å, &); алгебра Вебба (Пирса) (¯); алгебра Шеффера ( | ). В каждой из этих алгебр действуют собственные законы. Естественно есть взаимно конкретные переходы от операций Конспект лекций по дискретной математике - реферат 1-го базиса к операциям другого.

Числовое представление Булевых функций

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

f3 (x)= (0,2,6,7) - от этой числовой формы просто перейти к КДНФ методом подмены каждого из наборов в перечислении конституенты единицы Конспект лекций по дискретной математике - реферат.

_ _ _ _ _ _ _ _ _ _ _

y=x1 x2 x3 Úx1 x2 x3 Úx1 x2 x3 Úx1 x2 x3 =x1 x3 (x2 Úx2 )Úx1 x2 (x3 Úx3 )=x1 x3 Úx1 x2 (ДНФ)

f3 (x)= &(1,3,4,5)

_ _ _ _ _ _

y=(x1 Úx2 Úx3 ) (x1 Úx2 Úx3 ) (x1 Úx2 Úx3 ) (x1 Úx2 Úx3 ) (*)

Преобразование случайной аналитической формы Булевой Конспект лекций по дискретной математике - реферат функции в нормальную

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

Пример:

_ _ _ _ _ _

y=f4 (x)=(x1 x2 Úx2 x3 )(x1 |x4 )=(x1 x2 Úx2 x3 )(x1 x4 )=(x1 x2 Úx2 x3 )(x1 Úx4 )=

_ _ _ _ _ _ _ _ _ _

=x Конспект лекций по дискретной математике - реферат1 x2 Úx1 x2 x4 Úx1 x2 x3 Úx2 x3 x4= x1 x2 Úx1 x2 x3 Úx2 x3 x4 =x1 (x2 Úx2 x3 )Úx2 x3 x4 =

_ _ _ _

=x1 (x2 Úx3 ) Úx2 x3 x4 =x1 x2 Úx1 x3 Úx2 x3 x4 (КДНФ)

Замечания:

1) В общем случае неважно какая Булева функция может иметь несколько Конспект лекций по дискретной математике - реферат КДНФ, отличающихся или количеством термов, или количеством букв в этих термах.

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

3) По сопоставлению со схемой, построенной по ДНФ, схема, построенная по скобочной Конспект лекций по дискретной математике - реферат форме (*), является более предпочтительной т.к. при одном и том же числе логических частей (И, Либо) содержат наименьшее число входов (9 заместо 10).

Задачка преобразования обычной формы Булевой функции в скобочной форме именуют задачей фактеризации.

4) Суть конструктивного подхода при получении ДНФ состоит в следуюшем:

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

б) снятие отрицаний над выражениями с применением законов двойственности

в) раскрытие скобок с применением дистрибутивного закона

г) упрощения выражения с применением закона поглощения

Приведение случайных обычных форм Булевой функции к каноническим

Для приведения случайной ДНФ к КНФ нужно использовать правило дизъюнктивного развертывания применительно к каждому из неполных Конспект лекций по дискретной математике - реферат конъюнктивных термов.

_ _

P=P(xi Úxi )=Pxi ÚPxi, где P-неполный конъюнктивный терм (ранг этого терма

меньше n), а xi - недостающий в терме аргумент.

Пример:

_ _ _ _ _ _ _ _ _ _

y=x1 Úx2 x3 (ДНФ)=x1 (x2 Úx2 )(x3 Úx3 ) Úx2 x3 (x1 Úx1 )=x1 x2 x3 Ú x1 x2 x3 Ú

_ _ _ _ _ _ _ _ _

Úx1 x Конспект лекций по дискретной математике - реферат2 x3 Úx1 x2 x3 Ú x1 x2 x3 Ú x1 x2 x3 (КДНФ)

Замечание:

После раскрытия скобок могут получиться однообразные термы, из которых необходимо бросить только один.

y= (0,1,2,3,5)=f3

Преобразование КНФ к ККНФ реализуется методом внедрения правила конъюнктивного развертывания к каждому неполному дизъюнктивному терму.

_ _

P=PÚxi xi =(PÚxi )(P Конспект лекций по дискретной математике - рефератÚxi )

_ _ _ _ _ _ _ _ _ _

y=x1 Úx2 x3 (ДНФ)=(x1 Úx2 )(x1 Úx3 )(КНФ)=(x1 Úx2 Úx3 x3 )(x1 Úx3 Úx2 x2 )=

_ _ _ _ _ _ _ _

=(x1 Úx2 Úx3 )(x1 Úx2 Úx3 )(x1 Úx2 Úx3 )(x1 Úx2 Úx3 )(ККНФ)

y= (4,6,7)


Минимизация булевых функций на картах Карно(см . Практику) .

Способ Квайна-МакКласски базируется на кубическом представлении булевых функций Конспект лекций по дискретной математике - реферат.

Кубическое представление булевых функций .

В кубическом представлении булевой функции от n переменных все огромное количество из 2n наборов ее аргументов рассматривается как огромное количество координат вершин n-мерного куба с длинноватой ребра равной 1. В согласовании с этим наборы аргументов, на которых булева функция воспринимает значение равное 1 принято именовать существенными верхушками Конспект лекций по дискретной математике - реферат.

Значительные верхушки образуют так именуемые ноль-кубы (0-кубы). Меж 0-кубами существует отношение соседства и определена операция склеивания. Два 0-куба именуются примыкающими если они отличаются только по одной координате.

Пример :n=4 0101

0001 - два примыкающих 0-куба

итог склеивания : 0x01 (*)

Склеивание 2-х примыкающих 0-кубов дает в итоге 1-куб. Координата, отмечаемая эмблемой Конспект лекций по дискретной математике - реферат х, именуется свободной (независящей, несвязанной), а другие (числовые) координаты именуются зависимыми (связанными). Аналогичное отношение соседства существует меж 1-кубами, в итоге склеивания которых выходит 2-куб.

0х01

0х11 - 0хх1 (**)

В продолжении аналогии два r-куба именуются примыкающими если они отличаются только по одной (естественно зависимой) координате.r-куб содержит r независящих и n-r Конспект лекций по дискретной математике - реферат зависимых координат. В итоге склеивания 2-х примыкающих r-кубов появляется (r+1)-куб содержащий r+1 независимую координату.

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

_ _ _ _ _ _ _

х1 х2 х3 х4 Ú х1 х2 х3 х4 = х1 х3 х4

(0101) (0001) (0х01)

_ _ _ _

для (**) х1 х Конспект лекций по дискретной математике - реферат3 х4 Ú х1 х3 х4 = х1 х4

(0х01) (0х11) (0хх1)

Определения .

Кубическим комплексом K0 (f) булевой функции f именуется огромное количество 0-кубов этой функции. В общем случае кубическим комплексом Kr (f) булевой функции f именуется объеденение множеств кубов всех размерностей этой функции

m

k(f)=UKr (f) m-максимальная размерность кубов Конспект лекций по дискретной математике - реферат функции f.

r=0

Пример получения кубических комплексов

f3 (x)=V(1,2,3,6,7) |001 (1) |0x1 (1-3) (1)

(f=1) |010 (2) |01x (2-3) (2)

K0 (f)=|011 (3) K1 (f)=|x10 (2-4) (3) K2 (f)=|x1x (2-5)

|110 (4) |x11 (3-5) (4)

|111 (5) |11x (4-5) (5)

K3 (f)=пустому огромному количеству

K(f)=K0 (f)UK1 (f)UK2 (f)

Для получения кубического комплекса K(f) нужно провести различные операции склеивания над 0-кубами, 1-кубами и т Конспект лекций по дискретной математике - реферат.д. до того времени пока на следующем шаге не получится Kr+1 (f)=пустому огромному количеству. При склеивании 1-кубов 2-кубы представлены в 2-х экземплярах как результаты склеивания 2-х разных пар 1-кубов.

Распространяя этот принцип можно утверждать, что r-кубы как итог склеивания (r-1)-кубов получаются в r-кратном количестве Конспект лекций по дискретной математике - реферат экземпляров.

Куб, входящий в состав кубического комплекса K(f) именуется наибольшим, если он не вступает ни в одну операцию склеивания.

В приведенном примере наивысшими кубами являются х1х и 0х17.

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

Схожий подход носит ограниченный нрав и обычно является приятным для Конспект лекций по дискретной математике - реферат булевых функций от 2-х и 3-х переменных.


F3 (x)=V(1,2,3,6,7)

(f=1)

Геометрическим местом 0-куба является точка, представляющая существенную верхушку.

Два примыкающих 0-куба являются концами какого-нибудь ребра.

Геометрическим местом 1-куба является ребро, замыкаемое склеивающимися 0-кубами, образующими данный 1-куб.

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

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

Покрытия булевых функций .

Меж кубами различной размерности, входящих в кубический комплекс K(f), существует отношение включения либо покрытия. Принято гласить, что куб А наименьшей размерности покрывается кубом Б большей размерности, если Конспект лекций по дискретной математике - реферат куб А врубается в куб Б. Это значит, что при образовании куба Б хотя бы в одном склеивании принимает участие куб А.

Отношение включения (покрытия) меж кубами принято обозначать АÌБ. В теории множеств отношение включения связывает меж собой некое огромное количество и его подмножества.

Для рассмотренного примера дела включения имеют Конспект лекций по дискретной математике - реферат место меж 001Ì0х1; 011Ìx11Ìx1x... хоть какой 1-куб покрывает 2 0-куба, 2-куб - 4 0-куба и 2 1-куба, 3-куб покрывает 8 0-кубов, 12 1-кубов и 6 2-кубов.

Покрытием булевой функции f именуется такое подмножество кубов из кубического комплекса K(f), которое покрывает все значительные верхушки функции.

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

Личным случаем покрытия булевой функции является кубический комплекс K0 (f), покрытие c0 (f)=K0 (f). Этому покрытию соответствует КДНФ.

Для примера покрытием является также

|0x1

|01x

c1(f)=K1(f)=|x Конспект лекций по дискретной математике - реферат10

|x11

|11x

этому покрытию соответствует ДНФ вида

_ _ _ _ _ _ _ _ _ _

f=x1 x3 vx1 x2 vx2 x3 vx2 x3 vx1 x2 приведенная ДНФ не является малой.

В качестве малой еще 1-го покрытия можно использовать огромное количество наибольших кубов

|0x1

c2 (f)=|x1x

Вправду, куб 0х1 покрывает значительные верхушки 0х1É(001, 011), а куб Конспект лекций по дискретной математике - реферат x1xÉ(010, 011, 110, 111).

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

Покрытие c2 (f) соответствует ДНФ вида х1 х3 vx2 . Эта ДНФ является малой. Покрытие булевой функции, которое соответствует малой ДНФ именуется наименьшим покрытием.

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

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

Пример : f3(x)=V(0,1,4,6,7)

(f=1)

|000 (1) |00x (1-2)

|001 (2) |x00 (1-3)

K0 (f)=|100 (3) K1 (f)=|1x0 (3-4)

|110 (4) |11x (4-5)

|111 (5)

Для данного примера огромное количество наибольших кубов совпадает Конспект лекций по дискретной математике - реферат с комплексом K1 (f). Z(f)=K1 (f)

Наименьшими покрытиями являются

|00x |00x

с1 (f)=|11x c2 (f)=|11x

|x00 |1x0

Из анализа покрытия существенных вершин наивысшими кубами из комплекса K1 (f) следует :

1) Куб 00х должен непременно врубаться в покрытие, потому что только он покрывает существенную верхушку 001, аналогично 11х покрывает 111.

Огромное количество Конспект лекций по дискретной математике - реферат наибольших кубов без которых не может быть образовано покрытие булевой функции именуется ядром покрытия T(f)=|00x

|11x

2) Потому что ядром покрытия не считая существенных вершин 001 и 111 покрываются также значительные верхушки 000 и 110, то не покрытой ядром остается только значимая верхушка 100. Для ее покрытия довольно взять 1 из оставшихся наибольших Конспект лекций по дискретной математике - реферат кубов (х00 либо 1х0).

Выводы :

Задачка получения малой ДНФ сводится к задачке получения малого покрытия.

Получение малого покрытия реализуется в таком порядке : а) Находится огромное количество наибольших кубов б) Выделяется ядро покрытия в) Из наибольших кубов, не вошедших в ядро, выбирается такое малое подмножество, которое покрывает значительные верхушки, не покрытые Конспект лекций по дискретной математике - реферат ядром.

Стоимость покрытия .

Стоимость r-куба представляет собой количество несвязанных координат. Sr=n*r

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

m

1) Sa =åSr Nr , где Nr - количество r-кубов, входящих в по-

r=0

крытие,m- наибольшая размерность куба. Стоимость Sa представляет собой сумму цен кубов, входящих в покрытие Конспект лекций по дискретной математике - реферат.

2) Sb =Sa +k, где k - количество кубов, входящих в покрытие

m m

Sa =å(n-r) Nr ; Sb =å(n-r)(Nr +1)

r=0 r=0

Под наименьшим покрытием понимают покрытие, владеющее малой ценой Sa по сопоставлению с хоть каким другим покрытием этой функции.

Можно показать, что покрытие, владеющее малой ценой Sa обладает также и малой Конспект лекций по дискретной математике - реферат ценой Sb .

Пример : f3 (x)=V(0,1,4,6,7)

(f=1)

C0 (f)=K0 (f) ; Sa =5*3=15 ; Sb =Sa +5=20

C1 (f)=K1 (f) ; Sa =4*2=8 ; Sb =Sa +4=12

Cmin (f) : Sa =3*2=6 ; Sb =9

Стоимость покрытия Sa представляет собой количество букв, входящих в ДНФ, которая соответствует данному покрытию.

Стоимость Sb представляет для ДНФ сумму количества букв и количества термов Конспект лекций по дискретной математике - реферат.

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

Для приведенной схемы стоимость по Квайну SQ =9=Sb (9-число входов).

В принципе, меж SQ и ценами Sa и Sb существует соотношение Sa £ SQ £ Sb Это неравенство имеет место при последующих Конспект лекций по дискретной математике - реферат допущениях по комбинационной схеме :

1) Схема строится по обычной форме (ДНФ либо КНФ).

2) Схема строится на элементах булевого базиса (И, Либо).

3) На входы схемы можно подавать как прямые, так и инверсные значения входных переменных, представляющие из себя значения аргументов булевой функции (схема с парафазными входами). Элементы НЕ (инвертора в схеме Конспект лекций по дискретной математике - реферат отсутствуют.


Нулевое покрытие булевой функции и получение малой КНФ .

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

Такие покрытия можно именовать единичными. Вместе с единичными покрытиями есть и нулевые, для которых покрываются наборы аргументов, на которых функция равна нулю, другими словами покрытие реализуется Конспект лекций по дискретной математике - реферат для существенных вершин, но не самой функции, а ее отрицания (инверсии).

Нулевое покрытие строится также как и единичное, но только для отрицания начальной функции.

f3 (x)=V(0,1,4,6,7) f3 (x)=&(2,3,5)

(f=1) (f=0) _ |010

K0 ( f )=|011

_ _ |101

C0( f )= K0 ( f ) Sa =9 Sb =12

_ _ _

K1( f )=|01x Z( f )=Cmin ( f )=|01x Sa =5 Sb =7

|101

Стоимость Конспект лекций по дискретной математике - реферат малого нулевого покрытия оказалась меньше цены малого единичного покрытия.

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

Импликанты булевой функции .

Системы Конспект лекций по дискретной математике - реферат импликант .

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

Определение : Булева функция g(x) именуется импликантой булевой функции f(x), если для хоть какого набора аргументов, на которых g(x)=1, f(x) также равна единице.

~ ~~

g( x Конспект лекций по дискретной математике - реферат )=1 => f( x )=1, где х - некий набор аргументов.

Характеристики импликант :

1) Меж импликантой и самой функцией существует отношение включения g(x)Ìf(x).

2) Можно утверждать, что для хоть какого набора аргументов, на котором функция равна нулю, ее импликанта также равна нулю.

3) Если g(x) и j(x) являются импликантами функции f(x), то их Конспект лекций по дискретной математике - реферат дизъюнкция также является импликантой этой функции.

Простейшими примерами импликант могут служить конъюнктивные термы, входящие в ДНФ данной функции.

Пример : для f3 (x)=V(0,1,4,6,7) (#)

(f=1) _ _ _

импликантами являются х1 х2 х3 ; х1 х2 х3 ; х1 х2 ;...

Случайная дизъюнкция этих термов также является импликантой функции.

Определение : Обычный (первичной) импликантой булевой функции именуется Конспект лекций по дискретной математике - реферат конъюнктивный терм, который сам является импликантой этой функции, но никакая его собственная часть уже не является импликантой этой функции.

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

Для данного примера функции (#) ординарными импликантами являются : _ _ _

х1 х2 х3 ; х1 х2 х3 ; х1 х Конспект лекций по дискретной математике - реферат2 ;...

Огромному количеству обычных импликант можно поставить в соответствие огромное количество наибольших кубов.

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

Для функции (#) из приведенного примера

_ _ _ _ _

СДНФ : y= х1 х2 v х1 х2 vх2 х3 v х1 х3

Понятие «сокращенное» присвоено ДНФ в Конспект лекций по дискретной математике - реферат том смысле, что она, обычно, содержит наименьшее количество букв и термов по сопоставлению с КДНФ. Для нашего примера КДНФ содержит 15 букв и 5 термов, а СДНФ - 8 букв и 4 терма.

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

Хоть какому кубу из К(f) можно поставить в соответствие конъюнктивный терм который Конспект лекций по дискретной математике - реферат можно рассматривать как импликанту булевой функции .Хоть какой обычной импликанте булевой функции соответствует наибольший куб ,и в свою очередь огромное количество всех обычных импликант соответствует огромному количеству Z(f) всех наибольших кубов К(f).

Таким макаром можно провести некую аналогию меж сокращенной СДНФ и Z(f).

В отношении импликант Конспект лекций по дискретной математике - реферат булевой функции также как и в отношении кубов соответственных им существует отношение покрытия.

Принято считать ,что импликанта покрывает некую существенную верхушку либо в общем случае некий куб из К(f) ,если значение импликанты на наборе аргументов представляющем данную существенную верхушку равно 1 либо в общем случае значение импликанты Конспект лекций по дискретной математике - реферат равно 1 для всех существенных вершин покрываемых кубом из К(f).

ПРИМЕР : импликанта х1 х2 покрывает значительные верхушки(110,111) и в свою очередь покрывает куб 11х.

Определение :огромное количество импликант булевой функции образует полную систему импликант ,если неважно какая значимая верхушка булевой функции покрывается хотя бы одной импликантой этого огромного количества Конспект лекций по дискретной математике - реферат.

Если считать ,что в полную систему импликант врубаются импликанты исключительно в виде конъюнктивныхтермов и не включает импликанты в виде дизъюнктивных термов ,то полной системе импликант можно поставить в соответствие некое огромное количество кубов из К(f) образующих покрытие булевой функции f .

Так к примеру ,кубам из кубического комплекса К Конспект лекций по дискретной математике - реферат°(f) соответствует полная система импликант ,представляющая собой огромное количество конституент 1 данной функции f. В свою очередь огромному количеству наибольших кубов Z(f),естественно образующих покрытие булевой функции ,соответствует полная система обычных импликант.

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

Для функции y= x 1 x 2 Ú 1 2 Ú 2 3 Ú x 1 3 (*)

система обычных импликант

{ x 1 x 2 , 1 2 , 2 3 , x 1 3 }

является полной ,но не является приведенной ,т.к. из нее можно исключить одну из импликант не нарушая полноты системы .{ 2 3 либо x1 2 }

Определение: Дизъюнкция всех обычных импликант ,образующих некую приведенную систему именуется тупиковой ДНФ булевой Конспект лекций по дискретной математике - реферат функции либо ТДНФ

Для функции (*)есть две ТДНФ

1) у= x 1 x 2 Ú 1 2 Ú 2 3

2) у= x 1 x 2 Ú 1 2 Ú x 1 3

В этом случае они совпадaют с малой ДНФ. Но в общем случае это утверждение не справедливо. Т.е. малая ДНФ непременно является ТДНФ но не неважно какая ТДНФ является МДНФ. Таким макаром огромное количество МДНФ является подмножеством Конспект лекций по дискретной математике - реферат ТДНФ.

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

Огромное количество существенных импликант соответствует наибольшим кубам образующим ядро покрытия.

ПОСЛЕДОВАТЕЛЬНОСТЬ действий для решения канонической задачки минимизации способом Квайна-Мак-Класки.

1)Нахождение огромного количества наибольших кубов либо обычных импликант функции Конспект лекций по дискретной математике - реферат.

2)Выделение ядра покрытия.

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

Исходя из убеждений поочередного преобразования ДНФ булевой функции с целью их упрощения каноническая задачка минимизации может быть представлена в виде КДНФ Конспект лекций по дискретной математике - реферат.

КДНФÞСДНФÞ{ТДНФ}Þ{МДНФ}

Распространение терминологии в отношении нулевого покрытия определяется на понятии импликанта как соответствие импликанте и на системе импликант.

ПРИМЕР: (минимизация булевой функции способом Квайна-Мак-Класки)

1) f4 (x)=V(0,1,5,7,8,10,12,14,15)

(f=1)

f4 (x)=&(2,3,4,6,9,11,13)

(f=0)

На шаге получения огромного количества наибольших кубов целенаправлено поделить огромное количество Конспект лекций по дискретной математике - реферат ноль - кубов (К°(f)) на ряд подмножеств ,отличающихся количеством единиц .

В операцию склеивания в данном случае могут вступать только кубы ,относящиеся к примыкающим подмножествам ,другими словами отличающиеся на единицу

ì000X ü

ï X000 ÷ K°(f)=C°(f)

ï 0X01 ÷

Z(f)= í 01X1 ý Sa =36

ê X111 ú Sb =45

ê 111Xú

î 1XX0 þ

K1 (f)=C1 (f) Sa =10*3=30

Sb =40

Z(f Конспект лекций по дискретной математике - реферат)=C3 (f) Sa =20

Sb =27

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

2) Определение ядра покрытия .

Выполнение этого шага реализуется при помощи таблицы покрытий .

Kаждая строчка таблицы - наибольший куб(обычная Конспект лекций по дискретной математике - реферат импликанта).

Каждый столбец - значимая верхушка булевой функции (безразличные наборы не врубаются).

Элементы этой таблицы отражают отношение покрытия ,другими словами на скрещении i-ой строчки и j-ого столбца ставится некая отметка в этом случае если i-ый наибольший куб покрывает j-ую верхушку .

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

единицы(нуля).

Значительные верхушки

макс.

Кубы

0000 0001 0101 0111 1000 1010 1100 1110 1111
A 000X * * | | | |
B X000 * | * | | |
C 0X01 * * | | | |
D 01X1 * * | | | |
E X111 * | | | | *
F 111X | | | | *
1XX0 | * | * | * | *
a b c d | | | | e

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

Т(f)={1XX0}

3) Определение огромного количества малых покрытий .

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

Реализацию этого шага целенаправлено создавать с внедрением облегченной таблицы.

В облегченной таблице вычеркнуты все кубы принадлежащие ядру и верхушки покрываемые ядром.

Для решения задачки 3-го Конспект лекций по дискретной математике - реферат шага можно использовать один из 3-х способов либо их комбинацию:

1) Способ обычного перебора

2) Способ Петрика

3) Предстоящее упрощение.

1)На данном шаге целенаправлено ввести обозначение наибольших кубов и существенных вершин.

Наибольшие кубы обозначены в таблице А...F

1-ый методцелесообразно использовать для облегченной таблицы маленького объема .Этот способ не дает гарантии получения всех наибольших покрытий.

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

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

ì Tüì Tü

C min 1 (f)= êAú Cmin 1 (f)= êBú,...

ïCúêC Конспект лекций по дискретной математике - рефератú

îE þîE þ

2)Достоинство этого метода-получение всех малых покрытий.

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

Y=(AvB)(AvC)(CvD)(DvE)(EvF)=(AvBC)(DvCE)(EvF)=

=(AvBC)(DEvCEvDFvCEF)=

=(ADEvACEvADFvBCDEvBCEvBCDF)

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

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

3) Предстоящее упрощение состоит в применение 2-ух операций : а)Вычеркивание излишних строк.

б)Вычеркивание излишних столбцов.

Если огромное количество меток i Конспект лекций по дискретной математике - реферат-й строчки является подмножеством меток j-й строчки и куб i имеет маленькую размерность, чем куб j, то из таблицы можно вычеркнуть i-ю строчку потому что значительные верхушки покрываемые i-м кубом будут с гарантией покрыты j-м кубом.

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

В отношении новейшей Конспект лекций по дискретной математике - реферат таблицы можно использовать один из 3-х способов: 1) Способ обычного перебора.

2)Способ Петрика.

3)Предстоящее упрощение.

Многофункциональная полнота системы булевых функций .

Система булевых функций S={y1 ,y2 ,...,ym }называется функционально полной ,если при помощи функций этой системы можно выразить всякую сколь угодно сложную булеву функцию с внедрением способа суперпозиции, может Конспект лекций по дискретной математике - реферат быть неоднократно.

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

Примерами полных систем являются :

1)S1 ={ù,&,Ú}(булев базис)

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

Система S1 ={ù,&,Ú}является лишней потому что из нее можно удалить одну из функций (& либо Ú) без нарушения многофункциональной полноты.

Получаемые при всем этом системы S2 ={ù,&}иS3 {ù,&,Ú}обычно именуют сокращенным булевым базисом .

Недостающие операции(Úв системе S2 и & в системе S3 ) могут быть выражены при Конспект лекций по дискретной математике - реферат помощи следствий из законов

____

Де Моргана : x1 V x2 = 1 2

_____

x1 x2 = 1 v 2

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

Системы из одной функции S4 =¯(стрелка Пирса)

S5 =|(штришок Шеффера)

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

2)Базис Жегалкина S6 = {&, Å, 1}

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

Эта связь заключается в последующем :

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

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

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

булевых функций можно производить одним из 2-ух методов:

1) С внедрением аксиомы о многофункциональной полноте .

2) С внедрением Конспект лекций по дискретной математике - реферат конструктивного подхода .

Аксиома о многофункциональной полноте (Пост - Яблонского).

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

1) cохраняющую константу ноль

2) cохраняющую константу единица

3) линейную функцию

4) однообразную функцию

5) самодвойственную функцию.

Примечательные классы булевых функций.

1. Булева функция именуется сохраняющей константу ноль , если на нулевом наборе аргументов Конспект лекций по дискретной математике - реферат она воспринимает значение равное нулю, другими словами f(0,0,0,...,0) = 0;

В неприятном случае функция относится к классу не cохраняющих константу ноль.

К функциям ,сохраняющим константу ноль относятся

f(x1 ,x2 )= x1 v x2

f(x1 ,x2 )= x1 * x2

К функциям не cохраняющим константу ноль относятся

f(x)= и f(x Конспект лекций по дискретной математике - реферат1 ,x2 )=x1 ~x2

2.Булева функция именуется сохраняющей константу единица , если на единичном наборе аргументов она воспринимает значение равное единице, другими словами f(1,1,1,...,1)= 1;

В неприятном случае функция относится к классу не cохраняющих константу единица.

К функциям ,сохраняющим константу единица относятся

f(x1 ,x2 )= x1 v x2

f(x1 ,x2 )= x1 * x2

К функциям Конспект лекций по дискретной математике - реферат не cохраняющим константу единица относятся

f(x)= и f(x1 ,x2 )=x1 Åx2

3. Булева функция именуется линейной если она представима полиномом Жегалкина первой степени.

В булевой алгебре доказывается аксиома о способности представления хоть какой булевой функции от n переменных при помощи полинома Жегалкина n-ой степени.

В общем Конспект лекций по дискретной математике - реферат случае полином имеет вид :

fn (x)= K0 ÅK1 x1 Å...ÅKn xn Å...

...ÅKn+1 x1 x2 ÅKn+2 x1 x3 Å...ÅKn+l xn-1 xn Å...

...

...ÅKn+m x1 x2 ...xn

K0 ,K1 ,Kn+m -являются коэффициентами и представляют собой логические константы нуля либо единицы.

В алгебре Жегалкина одноименной полином можно считать канонической обычной формой Конспект лекций по дискретной математике - реферат для булевой алгебры.

Полином Жегалкина является линейным (1-ой степени) если все коэффициенты общего полинома ,начиная с Kn+1 =Kn+2 =...=Kn+m =0

В отношении функции от 2-х переменных полином Жегалкина имеет вид (линейный): f2 (x)=K0 ÅK1 x1 ÅK2 x2

Примерами линейных функций являются:

y= x1 Åx2 (K0 =0,K1 =K Конспект лекций по дискретной математике - реферат2 =1)

_____

y= x1 ~x2 =x1 Åx2 =1Åx1 Åx2 (K0 =K1 =K2 )

y= =1Åx1 (K0 =K1 =1 ,K2 =0)

Примеры нелинейных функций:

y= x1 *x2

____

y= x1 lx2 =x1 *x2 =1Åx1 *x2

4.Булева функция именуется однотонной если при возрастании наборов аргументов она воспринимает неубывающие значения.

A=(a1 ,a2 ,...,an )>B=(b Конспект лекций по дискретной математике - реферат1 ,b2 ,...,bn )

f(A)³f(B)

Меж наборами аргументов А и В имеет место отношение возрастания в том и только том случае , если имеет место отношение не убывания для всех компонент этого набора:

___

ai ³bi (i=1, n )

и по последней мере для одной составляющие имеет место отношение Конспект лекций по дискретной математике - реферат возрастания.

Примеры наборов ,для которых имеет место отношение возрастания: (1011)>(0011)

(1011)>(0001)

(0001)>(0000)

Пример несопоставимых наборов (1011)и (0111)

В отношении функции от 2-х переменных несопоставимыми являются наборы (01) и (10)

Пример немонотонных функций: y=

y= x1 Åx2

5.Две булевы функции fn (x) и gn (x) именуются двоякими если для всех наборов аргументов производится равенство

____

fn (x) =gn (x) другими Конспект лекций по дискретной математике - реферат словами функции f и g на обратных наборах аргументов х и воспринимает обратные значения .

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

x=(0101) =(1010)

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

Примером самодвойственной функции является : у=

Примеры не самодвойственных функций: у=х1 *х2

у=х1 vх2

у=х1 Åх2

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

К0 + сохраняет константу ноль ,- не сохраняет константу ноль

К1 + сохраняет константу единица ,- не сохраняет константу

Кл + линейная ,- нелинейная Конспект лекций по дискретной математике - реферат

Км + однообразная , - не однообразная

Кс + самодвойственная ,- не самодвойственная

Функция К0 К1 Кл Км Кс
0 + - + + -
1 - + + + -
-
х1 *х2 + + - + -
х1 vх2 + + + -
х1 Åх2 + - + - -
х1 ~х2 - + -
х1 Dх2 + -
х1 ®х2 -
х1 |х2 - -
х1 ¯х2 -

Конструктивный подход к подтверждению многофункциональной полноты некой системы булевых функций .

Подход основан на подтверждении реализуемости функций булева базиса при помощи функций этой Конспект лекций по дискретной математике - реферат системы.

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

Пример :S5 =

_ ____

x =x * x= x|x

====

x1 *x2 = x1 *x2 =( x1 |x2 )|( x1 |x2 )

______

x1 vx2 = 1 * 2 =( x1 |x1 )|( x2 |x2 )

Синтез комбинационных схем .

Понятие логического элемента .

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

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

Хоть какой логический элемент характеризуется :

1) Наличием 1-го либо нескольких входов на которые подаются входные сигналы( входные переменные).

2) Наличием выхода ,на котором формируется выходной сигнал

(выходная переменная).

3) Определенной функцией ,которая показывает зависимость выходного сигнала от Конспект лекций по дискретной математике - реферат входных.

К главным типам логических частей относятся:

1) Инвертор( НЕ)

2) Дизъюнктор (Либо)

3) Конъюнктор (И)

4) Дизъюнкторс отрицанием (Либо - НЕ)

5) Конъюнкторс отрицанием (И - НЕ)

6) Исключительное Либо

(единичный сигнал на выходе имеет место в том и только том случае если на

одном и только одном входе находится единичный сигнал)

7) Сумматор по модулю 2

1)Элементы Конспект лекций по дискретной математике - реферат 1,2,3 образуют булев базис.

2)Элементы 1 и 2 либо 1 и 3 образует сокращенный(неполный)

булев базис.

3)Элементы 4 либо 5 образуют универсальный базис.

4)Элементы 3 и 7 образуют базис Жегалкина.

Функции частей 6 и 7 совпадают при наличии только 2-ух входов.

Понятие двоичного сигнала .

Методы его кодировки .

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

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

1)Положительное Конспект лекций по дискретной математике - реферат кодирование (положительное)

высший уровень сигнала - 1 ,низший - 0

2)Негативное кодирование (отрицательное)

высший уровень сигнала - 0 ,низший - 1

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

Понятие логической системы .

Типы логических систем .

Логическая схема представляет собой совокупа логических частей и связей меж ними Конспект лекций по дискретной математике - реферат.

Соединения логических частей в рамках единой логической системы должны удовлетворять последующим правилам:

1)К хоть какому входу логического элемента могут быть подключены:

a) выход хоть какого другого логического элемента( в личном случае ,такого же самого)

б) входной сигнал (входная переменная)

в) логическая константа(0 либо 1)

В реальных электрических схемах подача логической константы Конспект лекций по дискретной математике - реферат на вход элемента реализуется или заземлением или подключением этого входа непременно через резистор к шине питания.

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

Логические схемы делятся на два Конспект лекций по дискретной математике - реферат типа :

1)Комбинационные

2)Последовательносные

В комбинационных схемах значение выходного сигнала в хоть какой момент времени зависит только от композиции входных сигналов (в тот же момент времени с учетом задержки распространения сигнала по элементам схемы)

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

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

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


Пример комбинационной схемына элементах булева базиса :

В последовательносных схемах выходные сигналы в Конспект лекций по дискретной математике - реферат хоть какой момент времени зависят не только лишь от композиции входных сигналов на этот момент времени ,да и от предыстории их конфигурации ,другими словами от последовательности входных сигналов во времени. Обычно последовательносные схемы характеризуются неким внутренним строением ,от которого зависит значение выходного сигнала(ов).

Внутреннее состояние таковой схемы Конспект лекций по дискретной математике - реферат сохраняется на запоминающих элементах (триггерах) ,в связи с чем ,схемы этого типа именуются схемами с памятью.

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

Пример последовательносной схемы: (универсальный базис И-НЕ)

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

Главные характеристики комбинационной схемы.

Основными параметрами комбинационных схем (КС) является цена и быстродействие ,обычно при построении абстрактных КС не привязанных к определенной системе частей стоимость схемы определяется в смысле Квайна. Быстродействие схемы ,обычно оценивается задержкой распространения сигналов от входов схемы к ее Конспект лекций по дискретной математике - реферат выходу. Для абстрактных КС эту задержку принято считать в виде : Т=кt,t-задержка на одном логическом элементе,к-максимальное количество логических частей ,через которые проходит сигнал от входов к выходу.

Обычно задержка схемы сопоставляется с числом уровней этой схемы. Для этой цели все элементы схемы распределяются по уровням. Уровень Конспект лекций по дискретной математике - реферат элемента ,на выходе которого формируется выходной сигнал схемы совпадает с количеством уровней схема и как следует с ее задержкой.

Для приведенной схемы элементы 1,2,3 относятся к первому уровню.

Элементы 4,5 ко второму уровню.

Элемент 6 к третьему уровню.

Элемент 7 к четвертому уровню.

Задачки анализа и синтеза комбинационных схем .

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

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

__

y=y1 v y2 = 4 v y3 y6 =x1 x2 v(y4 v y5 )x4 x5 =

___

=x1 x2 v(x1 x2 v 3 )x4 x5

Определим Конспект лекций по дискретной математике - реферат реакцию схемы на входной набор.

К примеру (00000) у=1

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

При решении этой задачки нужно учесть последующие моменты:

1) Синтезируемая схема должна по способности содержать минимум оборудования. В связи с этим животрепещущей задачей является минимизация данной булевой функции. При решении этой Конспект лекций по дискретной математике - реферат задачки целенаправлено получить как МДНФ так и МКНФ.

2) Обычно ,синтезируемая схема строится на логических элементах ,принадлежащих некому базису. Естественно ,что применяемая система частей должна владеть свойством многофункциональной полноты ,другими словами быть достаточной для построения на ее базе комбинационной схемы ,реализующую всякую наперед заданную булеву функцию. Такими функционально Конспект лекций по дискретной математике - реферат полными системами логических частей являются: 1.{И,Либо,НЕ} 2.{И,НЕ} 3.{ИЛИ,НЕ} 4.{И-НЕ} 5.{ИЛИ-НЕ} 6.{И,М2}

3) Обычно при решении задачки синтеза стараются достигнуть экстремального значения 1-го из характеристик схемы :минимум цены либо максимум быстродействия (минимум задержки).В тех случаях ,когда аспектом эффективности схемы является минимум цены по Конспект лекций по дискретной математике - реферат Квайну над наименьшими формами проводят дополнительные преобразования ,методом решения задач факторизации и может быть декомпозиции булевой функции. Обычно малая форма не дает абсолютного минимума цены ,чего можно достигнуть решением задач факторизации и декомпозиции. Если аспектом эффективности схемы является малая задержка ,то следует подразумевать ,что факторное преобразование и декомпозиция Конспект лекций по дискретной математике - реферат булевой функции в общем случае уменьшает стоимость схемы и наращивает ее задержку. В более сложном случае схема оптимизируется по одному из характеристик при наличии ограничения на 2-ой. Примером схожей постановки задачки синтеза является: Синтезировать схему с малой ценой по Квайну ,чтоб ее задержка не превосходила 4t.

4) Нужно учесть ,в каком виде Конспект лекций по дискретной математике - реферат представлены входные сигналы схемы: исключительно в прямом либо и в прямом и в оборотном. В первом случае строится комбинационная схема с однофазовыми входами. Во 2-м случае с парафазными. Вреальных комбинационных схемах входные сигналы представляют собой значение выходов регистров. К примеру при построении комбинационного сумматора входные сигналы снимаются с Конспект лекций по дискретной математике - реферат регистров слагаемого. При интегральной реализации регистров в виде СИС в целях минимизации числа выходов выходные сигналы регистров обычно представляются исключительно в прямом виде ,что делает животрепещущими схемы с однофазовыми входами.

5) При построении схем в реальной системе частей нужно учесть ряд конструктивных ограничений ,основными из которых являются:

а) Коэффициент объединения по Конспект лекций по дискретной математике - реферат входу, который представляет собой ограничение на число входов в элемент. Может принимать значения 2,3,4,8,16.

б) Коэффициент разветвления по выходам который определяет наибольшее число логических частей, которые можно подключить к выходу элемента в критериях его обычного функционирования. Этот коэффициент определяет нагрузочную способность. Варьируется от 10 до 30.

6) В реальных системах частей однотипные Конспект лекций по дискретной математике - реферат элементы соединяются воединыжды в модули ,реализуемые одной интегральной схемой с малым уровнем интеграции(МИС). В связи с этим при построении схем в реальной системе частей нужно минимизировать не столько число частей и входов в их сколько число модулей ,из которых компонуется схема.

7) Обычно в большинстве реальных систем частей вместе Конспект лекций по дискретной математике - реферат с ординарными логическими элементами употребляются также сдвоенные элементы реализующие составную булеву функцию. Обычным примером может служить элемент И-ИЛИ-НЕ.

8) В реальных системах частей обычно употребляется существенное обилие логических частей, относящихся к различным базисам. Все же построение схемы в рамках определенного базиса является довольно животрепещущей задачей, потому что позволяет уменьшить номенклатуру Конспект лекций по дискретной математике - реферат применяемых частей.

Построение комбинационных схем (КС) по наименьшим обычным формам в разных базисах .

1) Булев Базис (И, Либо, НЕ)

_ _ _ _ _ _ _

y=x1 x2 x3 vx1 x2 x4 vx1 x5 vx6 (МДНФ)

-------- ------- -----

и (3) и (3) и (2)

Схема с парафазными входами

SQ =3+3+2=12 Sa

В общем случае задержка Т=2t (схема 2-х Конспект лекций по дискретной математике - реферат уровневая).

При построении схемы по МКНФ элементами 1-го уровня будут Либо, а 2-го И.

Схема с однофазовыми входами

SQ =16 T=3t

В общем случае задержка схемы с однофазовыми входами составляет 3t.

При построении схемы с однофазовыми входами целенаправлено выбирать такую наименьшую форму (если она не единственная) которая содержит Конспект лекций по дискретной математике - реферат меньшее число инверсий над различными элементами.

При наличии единственной малой обычной формы можно выполнить ее преобразование с внедрением закона двойного отрицания и двойственности (Де Моргана)

ººº===ºººº==º===ººººº=--ºººº-º==-ºº

y=x1 x2 x3 v x Конспект лекций по дискретной математике - реферат1 x2 x4 v x4 x5 v x6 = x1 x2 x3 * x1 x2 x4 * x4 x5 * x6 =

-------------------------------------------

=( x1 v x2 v x3 )( x1 v x2 v x4 )( x4 v x5 )* x6

Для реализации этой схемы пригодятся три инвертора.

По сравне6нию с предшествующей схемой стоимость миниатюризируется на единицу (SQ =15). Но Конспект лекций по дискретной математике - реферат наличие выходного инвертора приведет к повышению цены схемы T=4t.

2) Сокращенный булев базис (И, НЕ).

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

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

Схема с Конспект лекций по дискретной математике - реферат парафазными входами :

SQ =16 T=4t

При построении схемы на элементах базиса И, НЕ по МДНФ задержка схемы в общем случае составляет 4t. А при использовании однофазовых входов 5t.

3) Универсальные базисы И-НЕ и ИЛИ-НЕ (см. Практику).

Задачка факторизации (факторного преобразования) булевой функции .

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

_ _ _ _ _ _ _ _ _ _ _ _

y=x1 x2 x3 v x1 x2 x4 v x4 x5 v x6 = x1 x2 (x3 v x4 )v x4 x5 v x6 =

SQ =12 SQ =10 T=3t

_ _ _ _ _ _ _ _ _

= x1 (x2 x3 v x2 x4 v x5 )vx6 = x Конспект лекций по дискретной математике - реферат1 (x2 (x3 v x4 )v x5 )vx6

T=4t SQ =11 T=5t SQ =10

Решение задачки факторизации приводя к уменьшению цены схемы наращивает ее задержку.

_ _ _ _ _

1) y= x1 x2 (x3 v x4 )v x4 x5 v x6 SQ =10 T=3t

_ _ _ _

2) y= x1 (x2 (x3 v x4 )v x5 )vx6 T=5t Конспект лекций по дискретной математике - реферат SQ =10

В тех случаях, когда схема синтезируется при ограничении на число входов в элементы, равное 2, предпочтение следует отдавать скобочной форме 2.

1)

SQ =10 T=3t

T=3t SQ =10 Квх =2

2)

T=5t SQ =10 Квх =2

Схема построенная по схеме 2 удовлетворяет ограничению на число входов и является более предпочтительной по сопоставлению со схемой 1 по аспекту цены схемы Конспект лекций по дискретной математике - реферат, а по аспекту малой задержки - лучше схема 1.

Пример факторного преобразования для МКНФ

_ _ _ _

y=(x1 vx2 vx3 )(x1 vx2 vx4 )(x1 vx5 )= SQ =11

_ _ _

=( x1 vx2 vx3 x4 )(x1 vx5 )= SQ =9

_

=x1 v(x2 vx3 )( x2 vx4 ) x5 = SQ =9

_ _

= x1 v(x2 vx3 x4 ) x5 = SQ =8

Оценка эффекта факторизации .

Этот эффект характеризуется разностью Конспект лекций по дискретной математике - реферат цен схемы до и после факторизации.

Можно показать, что для однократной факторизации ее эффект определяется выражением :

DSQ = SQ до - SQ после =m(k-1)+q-D ,

где m - количество букв, выносимых за скобки;

k - количество термов, из которых происходит вынесение. q -количество термов, в каких после вынесения осталась одна буковка Конспект лекций по дискретной математике - реферат (q£k);

D=1, если вынесение осуществляется из всех термов;

D=2, если не из всех.

Для действенного решения задачки факторизации нужно учесть последующий момент :

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

2) При минимизации не вполне определенной Конспект лекций по дискретной математике - реферат булевой функции возможно окажется, что наибольший эффект за счет факторизации дает обычная форма, не являющаяся малой.

Пример :

|10x1 _ _

cmin (f)=|xx10 МДНФ y=x3 x4 vx1 x2 x4 SQ =7

|10x1 _ _ _

cmin (f)=|101x ДНФ y= x1 x2 x4 vx1 x2 x3 = x1 x2 (x3 v x4 ) SQ =5

В неких Конспект лекций по дискретной математике - реферат случаях наибольшего эффекта за счет факторизации можно достигнуть методом расширения термов МНФ с применением законов товтологии

МДНФ y=x1 x2 x3 vx1 x2 x4 vx1 x3 x5 x6 vx2 x4 x5 x6 = SQ =18

= x1 x2 (x3 v x4 )v x5 x6 (x1 x3 v x2 x4 )= SQ =16

= x1 x Конспект лекций по дискретной математике - реферат2 (x1 x3 v x2 x4 )v x5 x6 (x1 x3 v x2 x4 )= SQ =20

=(x1 x3 v x2 x4 )( x1 x2 v x5 x6 ) SQ =14

Построение одновыходных схем .

Декомпозиция булевых функций .

Задачка декомпозиции булевой функции в общем случае состоит в таком разделении огромного количества ее аргументов на Конспект лекций по дискретной математике - реферат ряд подмножеств, при котором можно выразить начальную функцию f(x) через вспомогательную промежную функцию j(z), где zÌx.

В личном случае имеет место так именуемая обычная разделительная декомпозиция, при которой огромное количество аргументов x делится на два непересекающихся подмножества (z,w®(zÇw=j;zÈw=x)) и приведение Конспект лекций по дискретной математике - реферат начальной функции к виду f(x)=f(j(z,w)).

Пример :f3 (x)=V(1,2,4,7)

(f=1)

z=(x2 x3 ) W={x1 }

_ _

j(z)=x2 x3 vx2 x3

_ _

f(x)=x1 j(z)vx1 j(z) SQ =13

SQ =13 T=5t

Схема базиса Жигалкина .

SQ =4 T=2t

Применение декомпозиции там, где он уместно, в Конспект лекций по дискретной математике - реферат почти всех случаях позволяет уменьшить стоимость синтезируемой схемы.

_ _ _ _ _ _ _ _ _ _

МДНФ y=x1 x2 x3 x4 vx2 x5 vx3 x5 vx4 x5 =x1 x2 x3 x4 vx5 (x2 vx3 vx4 )

SQ =14

_

j(z)=x2 vx3 vx4

___ _

f(x)=x1 *y(z)vx5 *j(z) SQ =10

Синтез многовыходных комбинационных схем .

МКС представляется в виде Конспект лекций по дискретной математике - реферат обобщенного «черного ящика»

Закон функционирования МКС представляется в виде системы булевых функций

|y1 =f1 (x1 ...xn )

|y2 =f2

|.

|.

|.

|yn =fn

Естественным образом, при решении задачки синтеза МКС используются способы факторизации и вероятной декомпозиции, применительно не к одной функции, а к системе.

Минимизация системы Булевых функций

Задачка минимизации применительно к системе Конспект лекций по дискретной математике - реферат Булевых функций решается аналогично как для одной функции и сводится к получению малого покрытия. Для решения этой задачки система приводится к одной функции методом дополнения огромного количества агументов подмножеством вспомогательных переменных, при помощи которых выделяются отдельные функции системы. Количество вспомогательных переменных k³log2 m, m - количество функций.

Пример:

Раздельная Конспект лекций по дискретной математике - реферат минимизация:

y1 Cmin (y1 )=

y2 Cmin (y2 )=

МДНФ:

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

Совместная минимизация

Пусть V=0 для у1 ; V=1 для y2

Cmin(y1 ,y2 )= ;

Z= (общий терм)

Пример:

V1 V2 =00 y1

V1 V Конспект лекций по дискретной математике - реферат2 =01 y2

V1 V2 =10 y3

V1 V2 =11 y4

Cmin(S)=

Общие термы:

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

После получения малого покрытия при записи малых форм с начала выделяются термы, общие для нескольких Конспект лекций по дискретной математике - реферат функций и обозначаются вспомогательными функциями (Z1 -Z4 ).

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

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

Пример:

Сmin(S)=

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

1. Применение машинных способов

2. Раздельная минимизация и внедрение карт Карно.

3. Выделение подмножеств из функций системы для их совместной минимизации.

Факторизация системы Булевых функций

Применительно к Конспект лекций по дискретной математике - реферат системе задачка факторизации состоит в выделении общих термов либо их частей для отдельных функций системы с целью уменьшения цены схемы. Схожая задачка уже решается при совместной минимизации функций системы, но совместная минимизация не исключает применение предстоящей факторизации. В особенности животрепещущей задачей факторизации становятся при раздельной минимизации функций системы. Совместная Конспект лекций по дискретной математике - реферат факторизация не исключает рпаздельной минимизации в рамках каждой функции.

МДНФ:

Порядок проведения 2-ух видов факторизации совместной и раздельной почти всегда безразличен.

Декомпозиция системы Булевых функций

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

Пример:

a b p s q
0 0 0 0 0
0 0 1 1 0
0 1 0 1 0
0 1 1 0 1
1 0 0 1 0
1 0 1 0 1
1 1 0 0 1
1 1 1 1 1

Однофазовые входы

Раздельная минимизация

Раздельная факторизация

Совместная факторизация

,

Совместная минимизация

Cmin=

V=0, S

V=1, q

Арифметические базы ЭВМ .

Представление Конспект лекций по дискретной математике - реферат чисел в ЭВМ.

Вопросы:

1) Понятие системы счисления.

2) Позиционная и непозиционная системы счисления их отличия и примеры.

3) Понятие основания системы счисления.

4) Понятие веса разряда.

5) Подход к выбору рационального основания системы счисления (по Савельеву).

6) Обоснования использования в ЭВМ двоичной системы счисления.

7) Правила перевода целых и дробных чисел из одной системы счисления Конспект лекций по дискретной математике - реферат в другую.

8) Двоичная, восьмеричная, шеснадцетиричная системы счисления.

На самостоятельную проработку.

Систематизация данных применяемых в ЭВМ.

Информация с которой работает ЭВМ в принципе можно поделить на три вида:

1) Команды.

2) Адреса.

3) Данные.

Обычно адресная информация представлена в самих командах ,но прикосвенной адресации адресок может находиться или в регистре или в Конспект лекций по дискретной математике - реферат ячейке памяти.

Дерево систематизации данных.

Довольно обширно употребляется термин аппаратная поддержка данных. Принято считать что данные некого типа и определенных форматов являются аппаратно поддерживаемыми в определенной ЭВМ если в системе команд микропроцессора имеются команды для обработки данных данного типа в соответственных форматах. Для нечисловых данных главных типов поддержка осуществляется на уровне Конспект лекций по дискретной математике - реферат системных команд. Для логических значений в каких смысловое содержание относится к каждому биту поддержка осуществляется на уровне логических команд: AND,OR,XOR,NOT.

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

В ПЭВМ символьные данные представляются в коде ASCII. Сам по Конспект лекций по дискретной математике - реферат для себя этот код является 7 битным ,но для удобства он расширен до восьми битного с добавлением в голо букв государственного алфавита.

Числовые данные естественно поддерживаются на уровне арифметических команд. В связи с разделением чисел на двоичные и десятичные для их обработки употребляется соответственная математика. Зависимо от формы представления двоичных Конспект лекций по дискретной математике - реферат чисел употребляется два вида двоичной математики.

1) Двоичная целочисленная математика.

2) Математика с плавающей запятой.

Десятичные числа представляются в двоично-кодированном виде ,в каком неважно какая десятичная цифра представляется в естественном двоичном коде, который принято именовать :

8-4-2-1

9 - 1001,8 - 1000,7 - 0111,...,1 - 0001.

В упакованном формате в каждом б содержится две десятичные числа ,в не упакованном одна. В Конспект лекций по дискретной математике - реферат ПЭВМ неупакованный формат представляется ASCII-кодом десятичных цифр ,в каком фактически цифра помещается в младшую тетраду ,а старшая тетрада имеет вид 0011.

Пример : 985

1) Упакованный формат 0000|1001 1000|0101

2) Не упакованный формат 0011|1001 0011|1000 0011|0101

Десятичные числа употребляются в ЭВМ на шаге ввода данных и вывода результатов. После ввода они преобразуются в двоичную систему ,в какой реализуется обработка данных Конспект лекций по дискретной математике - реферат. На шаге вывода двоичный итог за ранее преобразуется в десятичную форму. Преобразования десятичных чисел в двоичные и назад может быть реализовано как на аппаратном так и на программном уровне. На аппаратном уровне подразумевается наличие в системе команд микропроцессора соответственных команд преобразования. Так к примеру в IBM/370 имеется Конспект лекций по дискретной математике - реферат две команды : CBD - преобразование двоичного числа в десятичное , CDB - преобразование десятичного в двоичное. В ПЭВМ схожих команд нет и преобразование реализуется на программном уровне, с внедрением стандартных процедур. Общей тенденцией в вычислительной технике при решении вопроса о реализации той либо другой функции на аппаратном либо программном уровне является: аппаратный уровень ,владея большей Конспект лекций по дискретной математике - реферат ценой реализации, обеспечивает и огромную скорость реализации этой функции. Традиционная схема обработки - десятичный ввод, преобразование в двоичную систему, двоичная обработка, преобразование в десятичную, десятичный вывод - смотрится неоправданной при решении задач с огромным объемом обрабатываемых данных и малым объемом обработки. Более целесообразный путь десятичный ввод, десятичная обработка, десятичный Конспект лекций по дискретной математике - реферат вывод. Для реализации схожей схемы поддерживаемой на аппаратном уровне нужно внедрение в системе команд микропроцессора десятичной математики.

Двоичные числа с фиксированной запятой .

Зависимо от местоположения фиксированной запятой (справа либо слева от числа ) числа с фиксированной запятой делятся на целые и дробные. Дробные числа с фиксированной запятой как таковые Конспект лекций по дискретной математике - реферат в современных ЭВМ не употребляются ,а употребляются как часть числа с плавающей запятой в виде его мантиссы . Целые числа делятся на два типа: знаковые и беззнаковые. Это разделение определяется методом интерпретации старшего разряда числа. В знаковых он интерпретируется как символ, а в без знаковых числах как старшая цифра числа Конспект лекций по дискретной математике - реферат. В почти всех случаях интерпретация целого числа ,как знакового либо без знакового возлагается на программера, хотя на аппаратном уровне может поддерживаться тот либо другой метод интерпретации. Примером подтверждающим это может употребляться парные команды умножения MUL,IMUL и деления DIV,IDIV в микропроцессорах INTEL 80X86. 1-ая команда из этих пар интерпретирует операнды и Конспект лекций по дискретной математике - реферат итог как без знаковое целое ,а 2-ая как знаковое. Особенностью представления знаковых целых чисел является внедрение дополнительного кода. Под дополнительным кодом знакового n- разрядного целого числа понимается последующие выражение:ìx, при x³0

[x] дк = í

î2x -|x|, при x<0

К примеру n=6 число 30 представиться в виде [30] дк Конспект лекций по дискретной математике - реферат =011110

[-30] дк =1.000000

011110

100000

В связи с тем ,что значение 2n не представимо в n - разрядном формате можно производить вычитание из нуля. На этом принципе поддерживаются на аппаратном уровне операция конфигурации знака числа (NEG) с преобразованием его в дополнительный код. В терминологии по поводу прямого и дополнительного кода есть некие разногласия. Создатели неких Конспект лекций по дискретной математике - реферат монографий считают что положительные числа представлены в прямом коде ,а отрицательные в дополнительном. Для общности представления ,как положительных ,так и отрицательных чисел в дополнительном коде вернее считать что дополнительный код положительного числа совпадает с его прямым кодом. Для отрицательных чисел это несправедливо, потому что прямой код отрицательного числа в Конспект лекций по дискретной математике - реферат знаковом разряде содержит единицу ,а в цифровых модуль числа. [-30]пр = 111110

Внедрение конкретно дополнительного кода в представлении знаковых целых чисел можно разъяснить простотой реализации в этом коде операции сложения и вычитания которые являются самыми массовыми при решении задач научного комплекса. Что касается операций умножения и деления то при использовании дополнительного Конспект лекций по дискретной математике - реферат кода по сопоставлению с прямым усложняет метод их реализации но все же разработаны способы для выполнения этих операций в дополнительном коде.

Спектр предоставления чисел

Спектр представления знаковых n-разрядных чисел определяется в виде

-2 n-1 £ Х £ 2n-1 -1

1 000...0 0 111...1

n-1 n-1

Для стандартного байтного формата (n=8) спектр :

-128 £ Xц зн £127

Наибольшее по модулю Конспект лекций по дискретной математике - реферат отрицательное число оказывается по модулю на единицу больше наибольшего положительного числа.

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

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

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

Спектр представления беззнаковых целых чисел в n- разрядном Конспект лекций по дискретной математике - реферат формате имеет вид :

0£Хц б . зн £2n -1

Для стандартного байтного формата (n=8) спектр :

0£ Xц зн £255

Спектр представления дробных чисел .

Для правильной n-разрядной двоичной дроби спектр представления имеет вид

2- n £Aдр пр £1-2-n

Некорректная дробь содержит неотклонимую двоичную единицу в целой части. Для неверной n-разрядной двоичной дроби спектр представления имеет вид

1£Aдр Конспект лекций по дискретной математике - реферат непр £2-2- ( n -1)

Числа с плавающей запятой .

В формате представления чисел с плавающей запятой выделяются 3 части : символ числа (представляется очень левым битом формата); мантисса числа (представляется в виде правильной либо неверной двоичной дроби); порядок числа (представляется в общем виде как целое число со знаком). Значение числа А с плавающей Конспект лекций по дискретной математике - реферат запятой представляется в виде :

Апз =(sign A)-1 *Ma *SPa

где sign A - символ 0 - «+», 1 - «-»

SPa - порядок числа А, S - основание порядка.

Число с плавающей запятой именуется нормализованным, если старшая цифра его мантиссы означающая (не 0), в неприятном случае число именуется не нормализованным.

Основными особенностями представления чисел с плавающей запятой в современных ЭВМ Конспект лекций по дискретной математике - реферат являются :

1) Мантисса числа независимо от его знака представляется в прямом коде

2) Порядок числа представляется не в очевидном виде как знаковое целое, а со смещением в виде беззнакового целого числа.

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

3) В качестве основания порядка употребляется значение S=16 (ЕС ЭВМ) либо S=2 (СМ ЭВМ, IEEE).

4) В подавляющем большинстве случаев принято внедрение нормализованных чисел с целью увеличения их точности.

5) При использовании основания порядка, равного двум, нормализованное число содержит неотклонимую единицу в старшем разряде Конспект лекций по дискретной математике - реферат мантиссы.

Это позволяет не представлять его в очевидном видев формате, что позволяет прирастить точность числа. Схожее сокрытие старшего разряда мантиссы именуется сокрытым разрядом (сокрытой единицей).

6) В ЭВМ хоть какого класса для представления чисел с плавающей запятой принято использовать несколько форматов (обычно, чтоб удовлетворить противоречивым требованиям увеличения точности чисел Конспект лекций по дискретной математике - реферат и увеличения скорости их обработки).

Эти форматы употребляют наименования :

а) маленький (одинарной точности) - 32 бита;

б) длиннющий (двойной точности) - 64 бита;

в) расширенный (расширенной точности) - 80 бит для РС и 128 бит для огромных ЭВМ.

Переход от недлинного формата к расширенному может сопровождаться или расширением только разрядности мантиссы (ЕС ЭВМ) или расширением разрядности как Конспект лекций по дискретной математике - реферат мантиссы так и порядка (IEEE).

Спектр представления чисел с плавающей запятой .

Его принято определять в отношении модуля нормализованного числа. В общем случае этот спектр представим в виде :

М а мин норм *SРа мин £½А пл норм ½£М Ра макс *SРа макс

Особенности представления чисел с плавающей запятой в Конспект лекций по дискретной математике - реферат ЭВМ разных классов :

1) ЕС ЭВМ (IBM/370) - ЭВМ общего предназначения (Main Frame) числа представляются в 3-х форматах :

0 1 7 8 21(63, 127)

символ черта мантисса

В огромных ЭВМ принято нумерацию разрядов в формате создавать слева вправо. В мини компьютерах и индивидуальных ЭВМ - справа влево.

ХА =РА +d ; d=64

0£XA £127

-64£PA £63

В связи с тем, что в качестве Конспект лекций по дискретной математике - реферат основания порядка употребляют S=16 признаком нормализации числа является наличие означающей шестнадцатиричной числа в старших разрядах мантиссы. Таким макаром признаком нормализации числа является наличие хотя бы одной единицы в старшей тетраде мантиссы.

Спектр представления нормализованной мантиссы

1/16£МА норм £1-2-m<1

m - число разрядов мантиссы

В общем случае спектр представления нормализованной мантиссы в виде Конспект лекций по дискретной математике - реферат правильной дроби при основании порядка S имеет вид :

1/S£MA H <1

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

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

В Конспект лекций по дискретной математике - реферат терминологии эталона IEEE последняя ситуация именуется антипереполнением.

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

2) СМ ЭВМ (РДР-11, VAX-11)

КФ 31 30 23 22 0

sign черта мантисса

В качестве основания порядка S=2. Смещенный порядок (черта) занимает 8 разрядов, величина смещения равна весу старшего разряда Конспект лекций по дискретной математике - реферат смещения. В мантиссе употребляется сокрытый разряд.

0£xa £255

-128£Pa £127

-1£Ma H £1

IEEE

КФ (КВ) 31 30 23 22 0

sign черта мантисса

ДФ (ДВ) 63 62 52 51 0

sign черта мантисса

РФ (РВ) 79 78 64 63 0

sign черта мантисса

Сокрытая единица имеет место в маленьком и длинноватом форматах, в расширенном формате она представляется в очевидном виде. Величина смещения определяется как вес старшего разряда свойства, уменьшенная на единицу Конспект лекций по дискретной математике - реферат.

КФ: d=27 -1=127; ДФ: d=210 -1=1023; РФ: d=214 -1=16383

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

Наибольшее значение свойства, представленное всеми единицами при положительном знаке зарезервированно для представления значения +¥ (нулевая мантисса) и представление так именуемых “не чисел” (NAN Конспект лекций по дискретной математике - реферат). Наибольшее значение свойства употребляется для преставления -¥,¤, (неопределенность) в старшем разряде единица, в других - ноль.

Малое значение свойства, представленное всеми нулями зарезервированно для представления “денормализованных” чисел (положительных и отрицательных) и нуля (всеми нулями формата).

КФ:

1£xa £254

-126£Pa £127

1£Ma H £2

ДФ: 10-308 <|Ап.з. |<10308

РФ: 10-4932 <|Ап.з. |<104932

Точность представления чисел

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

Абсолютная погрешность: А=А-А* , где А - четкое значение

А* - машинное представление

А - знаковая величина

Относительная погрешность:

, время от времени

Погрешность двоичной дроби

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

верная дробь:

(n-разрядная)

1 1 1 …

Наибольшая абсолютная погрешность правильной дроби равна весу ее Конспект лекций по дискретной математике - реферат младшего разряда.

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

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

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

Точность представления для маленьких форматов Конспект лекций по дискретной математике - реферат в ЭВМ разных типов

ЕС ЭВМ

СМ ЭВМ

IEEE

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

Способы округления чисел с плавающей запятой

Употребляются для роста точности представления чисел и используются в тех случаях, когда итог операции представленный в Конспект лекций по дискретной математике - реферат ДФ либо РФ переписывается из сопроцессора либо FPU в память в более маленьком формате. Способы округления в РС оговариваются интернациональным эталоном IEEE-754(854). К ним относятся:

1. Округление усечением (разряды не вмещающиеся в формат отбрасываются)

2. Округление к наиблежайшему (реализуется на базе старшего из отбрасываемых разрядов), непомещающихся в формат, если этот разряд Конспект лекций по дискретной математике - реферат равен единице, то к младшему уровню мантиссы добавляется единица, в неприятном случае мантисса остается без конфигураций.

3. Округление к наиблежайшему большему (к +¥)(для положительных чисел реализуется добавлением единицы к младшему уровню мантиссы; для отрицательных мантисса остается без конфигураций).

4. Округление к наиблежайшему наименьшему (к -¥) (для положительных -мантисса Конспект лекций по дискретной математике - реферат не изменяется; для отрицательных чисел - к ней добавляется единица).

Внедрение хоть какого способа округления, исключая округление усечением, позволяет уменьшить наивысшую относительную погрешность до значения . При всем этом наибольшая относительная погрешность мантиссы становится равной весу старшего из отбрсываемых разрядов. По дефлоту употребляется способ округления к наиблежайшему. Способы округления (к Конспект лекций по дискретной математике - реферат -¥) и (к +¥) употребляются в “интервальной” математике для определения границ приобретенных результатов в смысле их точности.

Принципы выполнения арифметических операций в ЭВМ.

Базы двоичной математики.

Операция сложения целых чисел.

Сложение n- разрядных целых чисел реализуется на базе n- разрядного комбинационного сумматора который может быть построен из модулей одноразрядных сумматоров методом Конспект лекций по дискретной математике - реферат их соединения по цепям переноса.

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

Для беззнаковых чисел переполнение фиксируется при появлении переноса из старшего Конспект лекций по дискретной математике - реферат разряда .Этот перенос в микропроцессорах 80Х86 фиксируется во флаге CF-carry flag.

Для знаковых чисел фиксация фиксируется во флаге OF-overflow flag.

Таким макаром при программировании на Ассемблере после выполнения сложения беззнакового нужно инспектировать CF, а после знакового OF.

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

Примеры сложения: n=6

-32<=Aз<=31

0<=Aб<=63

A+B=C

A= -11 1.10101

B= -20 +1.01100

----------

C= -31 1.00001

зн. беззн.

A=11 0.01011 11 11

B=-20 1.01100 -20 44

-----------

C= -9 1.10111 -9 55(55)

Переполнение при знаковом сложении и методы его фиксации.

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

зн. беззн.

A=17 0.10001 17 17

B=19 0.10011 19 19

----------

C= 1.00100 -28? 36(36)

зн. беззн Конспект лекций по дискретной математике - реферат.

A= -17 1.01111 -17 47

B= -19 1.01101 -19 45

-----------

C= 0.11100 28? 28?(92)

Переполнение при сложении знаковых целых чисел можно фиксировать одним из 2-ух методов:

1) Сопоставлением символов операндов и результата (при наличии ++ либо - - символов операндов и - либо + соответственно в знаке результата фиксируется переполнение).

2) Сопоставление переносов из 2-ух старших разрядов (при наличии 1-го и только 1-го переноса фиксируется переполнение).Конкретно этот Конспект лекций по дискретной математике - реферат метод употребляется в микропроцессорах компании INTEL для установки флага OF.

Операция вычитания целых чисел.

При использовании знаковых чисел операция может быть реализована одним из 2-ух методов:

1) Сведением к сложению методом подготовительного конфигурации знака второго операнда. При использовании дополнительного кода изменение знака подразумевает операцию дополнения над ним ,другими словами invert Конспект лекций по дискретной математике - реферат,+1.

2) Выполнение прямого(конкретного) вычитания по аналогии со сложением вычитание производится поразрядно начиная с младших разрядов с учетом возникающих межразрядных заемов.

Таблица истинности одноразрядного двоичного вычитателя имеет вид:

ai bi zi-1 ri zi

0 0 0 0 0

0 0 1 1 1

0 1 0 1 1

0 1 1 0 1

1 0 0 1 0

1 0 1 0 0

1 1 0 0 0

1 1 1 0 1

a i - i-й разряд уменьшаемого.

b i - i-й разряд вычитаемого.

z i-1 - заем из Конспект лекций по дискретной математике - реферат предшествующего разряда.

z i - заем в следующий разряд.

Примеры: n=6

зн. беззн.

A= -13 1.10011 -13 51

B= -28 1.00100 -28 36

-----------

C= 0.01111 15(15) 15(15)

A= -28 1.00100 -28 36

B= -13 1.10011 -13 51

-----------

C= 1.10001 -15(-15) 49?

Для беззнакового вычитания итог не корректный .Факт получения не корректного числа разъясняется вычитанием из наименьшего большего другими словами итог должен быть отрицательным. О факте получения отрицательного беззнакового результата свидетельствует заем в старший Конспект лекций по дискретной математике - реферат разряд .Этот заем при выполнении вычитания фиксируется во флаге CF. Если от приобретенного результата взять дополнение то выходит верный итог равный 15. В связи с этим при наличии заема в старший разряд приобретенный итог можно интерпретировать как беззнаковый дополнительный код.

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

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

Пример: n=6

зн. беззн.

A= -13 1.10011 -13 51

B= 24 0.11000 24 24

----------

C= 0.11011 27(-37) 27(27)

A= 24 0.10011 24 24

B= -13 1.10011 -13 51

-----------

C= 1.00101 -27? 37?

По аналогии со знаковым сложением фиксация переполнения при вычитании может реализоваться 2-мя методами:

1) Анализ символов операндов и результата. Если знаки операндов различные и символ результата отличен от Конспект лекций по дискретной математике - реферат знака первого операнда то фиксируется переполнение.

2) Сопоставление заемов в два старших разряда. Если один и только один из заемов имеет место то фиксируется переполнение. При наличии обоих заемов либо их отсутствии итог вычитания является корректным.

В микропроцессорах INTEL реализован 2-ой метод в согласовании с которым осуществляется установка флага OF.

Сложение Конспект лекций по дискретной математике - реферат и вычитание чисел с плавающей запятой.

Пример:

А=0,527*103 Pa=3

B=0,923*102 Pb=2 B=0,0923*103

C=Ma+Mb=0.6193*103

Операция сложения чисел с плавающей запятой реализуется в виде поочередных шагов:

1) Сопоставление порядков.

2) Выравнивание порядков.

3) Сложение мантисс.

4) Нормализация результата.

Некие этапы могут быть опущены при выполнении соответственных критерий для прошлых шагов.

1) Сопоставление порядков реализуется Конспект лекций по дискретной математике - реферат по средством вычитания. При всем этом в целях однозначности принято из Ра вычитать Рb при использовании смещенных порядков осуществляется вычитание свойства как беззнаковых целых чисел. Естественно что разность черт имеет тоже значение что и разность порядков если при вычитании черт имеет место заем в старший разряд то Конспект лекций по дискретной математике - реферат итог вычитания отрицательный и представлен в дополнительном беззнаковом коде. Для второго шага нужно его преобразование в прямой код.

2) Этот шаг опускается при равенстве порядков операндов другими словами если: Xa-Xb=0

При выполнении этого шага всегда операнд с наименьшим порядком приводится к большему порядку. Это реализуется сдвигом мантиссы на право на количество Конспект лекций по дискретной математике - реферат разрядов равное |Xa-Xb| .В данной трактовке понятие разряда находится в зависимости от основания порядка. Для ЕС ЭВМ при |Xa-Xb|=2 мантисса двигается на 2-а шестнадцатеричных разряда другими словами на 8 двоичных. При сдвиге мантиссы операнда с наименьшим порядком происходит утрата ее младших разрядов ,что приводит к уменьшению точности в общем Конспект лекций по дискретной математике - реферат случае.

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

При большенном модуле разности порядков возможно окажется что мантисса с наименьшим порядком стопроцентно выйдет за границы формата. Данный факт можно учитывать для ускорения выполнения операций последующим образом на первом шаге |Xa-Xb Конспект лекций по дискретной математике - реферат| сравнивается с числом разрядов мантиссы и если он оказывается больше то операция заканчивается методом присвоения результату значения операнда с огромным порядком.

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

Единственный момент возникающий при сложении мантисс в прямых кодах это возможность переполнения. Переполнение если оно имеет место устраняется на четвертом шаге. Для операндов с различными знаками сложение мантисс подменяют их вычитанием в Конспект лекций по дискретной математике - реферат принципе заместо прямого вычитания можно выполнить их сложение с представлением одной мантиссы в дополнительном коде. Факт выбора мантисс уменьшаемого и вычитаемого при прямом их вычитании либо выбора мантиссы представляемой в дополнительном коде при их сложении определяется типом ЭВМ и в рамках 1-го типа находится в зависимости от модели. В принципе могут Конспект лекций по дискретной математике - реферат употребляться последующие подходы: a) Уменьшаемым является мантисса положительного операнда. б) Уменьшаемым является мантисса первого операнда. в) Уменьшаемым является мантисса операнда с огромным порядком ,а при равенстве порядков мантисса первого операнда.

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

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

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

4) Нормализация

Этот шаг имеет место только при получении не нормализованного результата.

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

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

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

Если порядок результата равный порядку большего операнда был наибольшим то повышение на Конспект лекций по дискретной математике - реферат единицу даст особенный случай "переполнение порядка".

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

Нормализация делается сдвигом мантисса на лево с целью удаления ведущих нулей .Этот сдвиг сопровождается уменьшением порядка что может повлечь "исчезновение порядка Конспект лекций по дискретной математике - реферат"(анти-переполнение).

Вычитание

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

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

Операция умножения целых чисел и

принципы ее реализации Конспект лекций по дискретной математике - реферат в ЭВМ

Главные положения двоичного умножения

А=13 x 1101

В=11 1011

---------

1101

+ 1101

1101

-------------

10001111=(143)10

Другой способ:

x 1101

1011

--------

1101

+ 1101

1101

------------------

10001111=(143)10

1. Умножение двоичных чисел (как и десятичных) состоит в поочередном умножении множимого на отдельные разряды множителя с суммированием результатов умножения. Итог умножения множимого на один разряд множителя принято именовать частичным произведением. Итог умножения 2-ух чисел представляет собой сумму Конспект лекций по дискретной математике - реферат всех личных произведений.

2. Каждое личное произведение или совпадает с множимым, или равно 0.

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

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

5. В общем случае для результата умножения требуется количество Конспект лекций по дискретной математике - реферат цифр равное сумме количества цифр операндов. При схожей разрядности операндов: 2n - разрядов.

Особенности реализации умножения в ЭВМ

1. В операционном устройстве для умножения двоичных чисел должен употребляться многоразрядный двоичный сумматор, что предназначает умножение в виде поочередного многошагового процесса, на каждом шаге которого проводится умножение на один разряд множителя Конспект лекций по дискретной математике - реферат. Сумма личных произведений: СЧП.

Для фиксации этой суммы на каждом шаге нужно использовать 2n-разрядный микропроцессор, n-разрядного операнда.

До операции нужно выполнить сброс этого регистра (установить в “ноль”).

2. На каждом шаге умножения анализируется определенный разряд множителя, и если он равен единице, то на этом шаге делается сложение СЧП с множимым Конспект лекций по дискретной математике - реферат. Если разряд множителя равен нулю, то сложения на данном шаге делается.

3. Хоть какой шаг умножения должен сопровождаться сдвигом множимого относительно недвижной СЧП: принципно вероятен и подход, при котором множимое остается недвижным, но происходит сдвиг СЧП.

4. Реализацию умножения принципно можно начинать как от младшего, так и от Конспект лекций по дискретной математике - реферат старшего разряда множителя.

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

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

6. Для фиксации момента окончания операции, в операционном устройстве умножения должен быть применен Конспект лекций по дискретной математике - реферат счетчик (суммирующий либо вычитающий).

7. Потому что в реализации умножения можно использовать разные подходы, связанные с тем, от какого разряда множителя начинается умножение, а так же с тем относительно чего двигается, можно использовать четыре метода (схемы) умножения.

Методы (схемы) реализации умножения

1. Умножение, начиная с младших разрядов множителя со сдвигом множимого на лево Конспект лекций по дискретной математике - реферат.

2. Умножение, начиная с младших разрядов множителя со сдвигом СЧП на право.

3. Умножение, начиная со старших разрядов множителя со сдвигом множимого на право.

4. Умножение, начиная со старших разрядов множителя со сдвигом СЧП на лево.

Анализ схем:

1. В схемах умножения со сдвигом множимого для его представления требуется 2n-разрядный регистр.

2. А Конспект лекций по дискретной математике - реферат в схеме умножения, начиная с младших разрядов множителя со сдвигом СЧП на право для представления множимого требуется n-разрядный регистр.

3. А в схеме умножения, начиная со старших разрядов множителя со сдвигом множимого на право нужно использовать 2n-разрядный сумматор, связанный по входу с регистром множителя.

4. 4-ая схема просит Конспект лекций по дискретной математике - реферат 2n-разрядного сумматора.

5. 2-ая схема - n-разрядного.

В целях минимизации оборудования целенаправлено использовать схему 2, на базе которой реализуется умножение фактически во всех ЭВМ.

Облегченная схема операционного устройства для реализации умножения по второму методу


Операция деления и ее реализация в ЭВМ

Особенности двоичного деления

Пример: 130/10

А= 10000010 | 1010

1010 |--------

------------- |01101

0110010

1010

-------------

001010

1010

-----------

1010

1010

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

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

2) На подготовительном шаге делитель совмещается со старшими разрядами делимого ,а потом на каждом шаге двигается на право Конспект лекций по дискретной математике - реферат на одну цифру относительно недвижного остатка На последнем шаге делитель совмещается с младшими разрядами остатка.

3) Числа личного вырабатываемые каждом шаге определяются знаком текущего остатка ,для остатка >= 0 цифра личного равна единице ,для остатка < 0 цифра равна нулю.

Особенности реализации деления в ЭВМ.

(по отношению к целым числам)

1) Делимое по сопоставлению с Конспект лекций по дискретной математике - реферат делителем представляется в удвоенном формате.

2) В качестве результата деления формируется как личное так и остаток .При всем этом обычно остаток замещает старшие разряды ,а личное младшие.

3) В целях экономии оборудования на каждом шаге осуществляется не сдвиг делителя на право относительно остатка ,а сдвиг остатка на лево относительно Конспект лекций по дискретной математике - реферат недвижного делителя. При всем этом делитель совмещается со старшими разрядами делимого ,а дальше остатка.

4) При получении отрицательного остатка на каком или шаге для перехода к последующему шагу требуется восстановление остатка методом сложения с делителем. Схожий способ именуется делением с восстановлением остатка .В целях экономии времени деление обычно реализуется в ЭВМ Конспект лекций по дискретной математике - реферат с применением способа без восстановления .В согласовании с этим способом при получении отрицательного остатка он не восстанавливаясь двигается на лево так же как и положительный но при всем этом на последующем шаге делается не вычитание делителя ,а сложение с делителем.

Подтверждение:Допустим на i-м шаге получен отрицательный остаток Конспект лекций по дискретной математике - реферат тогда по способу с восстановлением :Ri+1=2(Ri+B)-B

Ri+1 =2Ri +2B-B=2Ri+B

5) При неких соотношениях меж делимым и делителем возможно окажется что личное не помещается в отводимый формат. Схожая ситуация появляется также при делении на 0. Этот особенный случай распознается на исходном шаге деления и приводит к прерыванию выполняемой программки Конспект лекций по дискретной математике - реферат из-за ошибки деления.

Деление беззнаковых.

А/В<2^n А-В*2^n<0 из этого неравенства следует что для проверки правильности деления нужно отнять делитель из старших разрядов делимого. Если итог вычитания положителен либо равен 0 то операция прекращается выходом на прерывание. В остальном беззнаковое деление реализуется по описанным выше принципам потому Конспект лекций по дискретной математике - реферат что цифра личного вырабатываемая на каждом шаге деления определяется знаком текущего остатка ,поточнее представляет собой инверсию его знакового разряда, целенаправлено расширить n-разрядный сумматор дополнительным разрядом для очевидного представления знака остатка.

Если по окончанию всех шагов деления остаток является отрицательным то требуется его восстановление методом сложения с делителем Конспект лекций по дискретной математике - реферат.

Деление знаковых.

IDIV

По аналогии с операцией умножения знаковое деление может быть реализовано одним из 2-ух способов:

1) Способ деления в прямых кодах .

2) Способ деления в дополнительных кодах.

При использовании первого способа отрицательные операнды за ранее преобразуются в прямой код и дальше над ними делают деление по аналогии с беззнаковым Конспект лекций по дискретной математике - реферат .Символ личного формируется отдельным действием как сумма по модулю два символов операндов. Символ остатка совпадает со знаком делимого. Исключением из этого правила является нулевой остаток содержащий в знаковом разряде 0.

Отрицательные результаты в конце операции конвертируют из прямого в дополнительный код.

Значимым различием деления модулей операндов в прямых кодах от беззнакового деления Конспект лекций по дискретной математике - реферат является проверка правильности деления. Вправду модуль n-разрядного знакового числа располагается в (n-1)-разряде в связи с этим условие правильности для деления в прямых кодах имеет вид |A|/|B|<2^(n-1) ; |A|-|B|^(n-1)<0

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

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

Деление в дополнительных кодах .

Основное отличие этого способа от прошлых заключается в том, что операнды вступают в операцию в коде собственного представления вкупе со знаком. Но при всем этом появляется ряд аспектов :

1) Числа личного, в том числе и символ, создаваемые на каждом шаге, определяются не только лишь остатком Конспект лекций по дискретной математике - реферат, да и знаком делителя. При их совпадении цифра личного равна единице, по другому - нулю.

2) Действие выполняемое над текущим остатком на каждом шаге определяется не только лишь этим остатком, да и знаком делителя. При их совпадении производится вычитание делителя из старших разрядов делителя,при не совпадении производится Конспект лекций по дискретной математике - реферат сложение делителя со старшими разрядами делителя.

3) Корректировка остатка делается в конце операции в этом случае, если его символ не совпадает со знаком делимого. Эта корректировка осуществляется действием над остатком, аналогичным основному циклу деления.

4) Корректировка личного производится только при отрицательном делимом и нулевом остатке деления и состоит в инкременте (повышение на Конспект лекций по дискретной математике - реферат единицу) положительного личного и декременте отрицательного.

5) Проверка правильности деления производится также как при делении прямых кодов исключительно в случае положительных операндов.

1) A>0, B>0 => A/B<2n-1 A-B*2n-1 <0

2) A<0, B A/B<2n-1 A-B*2n-1 >0

3) A0 => A/B³-2n-1 A/B>-2n-1 A+B*2n-1 +B>0

4) A>0, B>0 => A/B>-2n-1 -1 A+B*2n Конспект лекций по дискретной математике - реферат-1 +B<0

При схожих знаках операндов для проверки правильности деления нужно двинуть делимое на 1 разряд на лево а потом отнять делитель из его старших разрядов.

Проверка правильности осуществляется сопоставлением знака первого остатка со знаком делимого. Если они НЕ совпадают деление корректно, в неприятном случае - не корректно.

При различных знаках пробное Конспект лекций по дискретной математике - реферат вычитание практически заменяется сложением.

В этом нет ничего необыкновенного, потому что для первого шага в качестве остатка для первого шага бытует само делимое и его символ не совпадает со знаком делителя в согласовании с действиями для основного цикла над текущим остатком в данном случае нужно делать сложение с остатком Конспект лекций по дискретной математике - реферат.

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

1) Сложение делимого с делителем, совмещенным с его младшими разрядами. При всем этом производится знаковое расширение делимого на старшие разряды делителя Конспект лекций по дискретной математике - реферат.

2) Сдвиг приобретенного остатка на один разряд на лево.

3) Сложение с делителем, совмещенным со старшими разрядами остатка.

4) Сопоставление знака остатка со знаком делимоговыполняется также как и для операндов с схожими знаками.

В связи с тем, что при проверке правильности деления употребляется символ делимого нужно при схемной реализации предугадать его сохранение до конца Конспект лекций по дискретной математике - реферат операции. По результату пробного вычитания формируется старшая цифра личного, интерпретируемая как символ.

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

Пример :A=-168 B=-14 n=5

A=1101011000 ; B=10010

Выполняемые деяния

N шага обозначения A/R (старшие) A/C (младшие)
0

A

¬

A

B

R0

11010

-10101

10010

¾¾¾

00011

­

sign R0 ¹sign B®

11000

10000

1000|0

­

®®

1

¬

R0

B

R1

+00111

10010

¾¾&frac Конспект лекций по дискретной математике - реферат34;

11001

sign R1 =sign B

000|00

000|01

2

¬

R1

B

R2

+10010

10010

¾¾¾

00000

­

sign R2 ¹sign B®

00|010

00|010

­

®®

3

¬

R2

B

R3

+00000

10010

¾¾¾

10010

sign R3 =sign B

0|0100

0|0101

4

¬

R3

B

R4

-00100

10010

¾¾¾

10010

sign R3 =sign B

01010

01011

псевдо-

корректировка

R4

B

R

-10010

10010

¾¾¾

00000

корректировка личного

+01011

1

¾¾¾

01100

Приведенный пример иллюстрирует ряд дополнительных аспектов деления в дополнительных кодах :

На четвертом Конспект лекций по дискретной математике - реферат шаге при сдвиге остатка вышло искажение его знака. Выполняемое действие над остатком должно определяться его знаком для предшествующего шага (до сдвига). В схемной реализации данный факт нужно учесть методом внедрения измененного кода с двойным знаковым разрядом. В связи с этим разрядность регистра для хранения остатка и личного должна быть Конспект лекций по дискретной математике - реферат 2n+1, а разрядность сумматора (сумматора вычитателя) n+1. При получении нулевого остатка на коком или шаге деления для последующего шага остаток будет равен делителю. При его сдвиге на лево он станет равен удвоенному делителю. И после вычитания делителя на последующем шаге он опять станет равен делителю. Таким макаром в Конспект лекций по дискретной математике - реферат конце операции после выработки всех цифр личного остаток будет не нулевым, а равным делителю. Если при всем этом его символ совпадает со знаком делимого, то в согласовании с главным методом деления он не подлежит корректировки.

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


konspekt-uroka-fiziki-dlya-8-klassa-po-teme-istochniki-sveta-rasprostranenie-sveta.html
konspekt-uroka-immunitet.html
konspekt-uroka-istorii-v-8-klasse-osvoenie-sibiri-i-dalnego-vostoka.html