ДИСКРЕТКА105 (Лекции в ворде)

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

Любая система исчисления должна обеспечивать: -1. Возможность представления любого числа -2. Единственность представления, то есть каждой комбинации должна соответствовать только одна величина -3. Простота оперирования с числами

Система исчисления делится на позиционную (п.с. характеризуются основанием, под которым понимается количество знаков или цифр, используемых для изображения чисел (например: десятичная 0,1,…9)) и непозиционную (н.с. значение символа (цифры) не зависит от положения в числе (римская XIX=19)).

Для п.с. справедливо выражение сумма от (n-1) до (i=-m) АиКУвстепении=Аку, где Аку - произвольное число, записанное в системе исчисления с основанием ку. Аи – цифры системы исчисления. n-1 – число целых разрядов числа. M – число дробных разрядов числа.

Под длиной числа понимается количество цифр или разрядов в его записи. В технике длина числа ставится в соответствие длине разрядной сетки ЭВМ. В системах с различным основанием длина числа также будет различной: 96(10)=140(8)=1100000(2)

Пусть длина разрядной сетки задана и равна n тогда максимальное число: Акуmax=кувстепениn-1 Акуmin=-(кувстепениn-1)

Введем показатель экологичности системы исчисления в виде произведения С=nку Пусть один разряд числа фиксируется ку элементами. Каждый, из которых имеет одно устойчивое состояние. Тогда параметр С покажет условное количество оборудования, которое необходимо затратить на представление числа в заданной системе исчисления. Из этого соотношения следует, что n=logку(Акумах+1) Тогда С=куlogку(Акумах+1)

Для сравнения двух систем исчисления можно ввести относительный показатель: F=Cку/С2, тогда F=куlogку(Акумах+1)/2log2(Акумах+1) позволяет сравнить любую систему исчисления с двоичной.

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

Основа булевой алгебры. Рассмотрим набор переменных, где Хи может принимать только 0 и 1. Число всех наборов, сочетаний 0 и1 конечно. Л=2встепениН Ф(Х1,Х2,…Хн) – булева, переключательная функция алгебры логики. Если она сама, как и ее аргументы может принимать только 2 значения 0 и 1.

Две функции Ф(Хи) и Ф(Уи) называются равными, если они на всех возможных наборах значений аргументов принимают одинаковые значения. Функция Ф(Х1…Хн) существенно зависит от аргумента Хи, если выполняется услдовие: Ф(Х1…0…Хн)не=Ф(Х1…1…Хн) В противном случае говорят, что функция от Хи зависит несущественно. Число булевых функций от Н аргументов конечно и определяется из соотношения К=2встепени2встепениН Так как набор аргументов есть двоичное число, то принято к каждому набору приписывать десятичный номер равный соответствующему двоичному числу.

Булевы функции можно задавать с помощью таблицы истинности. В таблицах истинности наборы записываются в порядке их возрастания. 000-0й набор … 111-7й набор. А функции приписывается номер равный двоичному числу соответствующего набора, записанного слева направо. В связи с тем, что в булевой алгебре область определения функции и область определения её аргументов совпадают между собой, в булевой алгебре допустимы операции перестановки аргументов и суперпозиции функций.

Под операцией подстановки аргумента понимается замена одних аргументов другими или их перестановка. Под операцией суперпозиции функции понимается подстановка в функцию вместо её аргументов других функций. Н=2 – К=16 функций Н=3 – К=256. В связи с этими свойствами функции и её аргументами в булевой алгебре особое значение имеет функция одного и двух аргументов.

Основные соотношения булевой алгебры. 1. Коммутативный (перестановочный закон) АВ=ВА, А+В=В+А 2. Ассоциативный закон (ХУЗ)=Х(УЗ)=..=ХУЗ 3. Дистрибутивный закон (А+В)С=АС+ВС. Согласно этим законам логические выражения, содержащие функции конъюнкции и дизъюнкции можно преобразовывать, то есть раскрывать скобки, выносить за скобки общий множитель и т.д. по правилам обычной алгебры, формально считая операцию инверсии доминирующей над всеми другими, а затем операции логического умножения и сложения.

Соотношения для инверсии. Не0=1, не1=0, ненех=х.

Соотношения для конъюнкции. х1=х, х0=0, хнех=0, хх…х=х

Соотношения для дизъюнкции. Х+1=1, х+0=х, х+нех=1, х+х…х=х

Правило склеивания. ху+хнеу=х

Правило поглощения. х+ху=х

Правило де Моргана. не(АВ)=неА+неВ, не(А+В)=неАнеВ

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

Минтермом или конституентой единицы называется элементарное произведение, в котором каждый аргумент функции входит один раз в прямой или инверсной форме. Ми – минтерм обозначается, где индекс равен десятичному эквиваленту двоичного набора аргументов, на котором он равен 1. Как булева функция, минтерн=1 только на одном наборе значений аргументов.

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

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

Теорема Жегалкина. Эта теорема гласит, что любую функцию можно представить в виде многочлена вида: Ф(Х0,Х2,…Хн)=а0+а1х1+…анх1х2хн, где аи=0или1, Хи – только в прямой форме. Такой многочлен называется каноническим полиномом Жегалкина.

Классы замечательных функций. Из всех возможных булевых классов выделяют 5, которые называются замечательными. Они называются потому что любое преобразование функции, входящей в класс приводит к получению функции того же самого класса. 1. Функция сохраняющая constу К0. 2. Функция сохраняющая constу К1. 3. Монотонная функция М 4. Линейная функция Л 5. Самодвойственная функция С.

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

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

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

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

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

Th-a Поста-Яблонского. Для того, чтобы система булева функций была функционально полной, необходимо и достаточно, чтобы эта система содержала хотя бы одну функцию не сохраняющую const 0, const 1, не монотонную, не линейную, не самодвойственную.

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

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

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

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

Синтез логических схем в основном базисе. Минимизация булевых функций: конъюнкция И, дизъюнкция ИЛИ, инверсия.

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

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

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

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

Под собственной частью импликанты принимается любое сочетание аргументов, входящих в эту импликанту. Если ХнеУЗ – импликанта х, не у, з, ху, хз, неуз следовательно нахождение минимальной формы булевой функции состоит из двух этапов: 1. Нахождение всех простых импликант функций 2. Выбор из множества простых импликант таких их подмножеств, которое бы своими единицами накрывали бы все единицы функции.

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

Алгоритм метода. 1. Записать функцию в СДНФ 2. Нанести полученный минтерм функции на карту Вейча 3. Проанализировать все отметки о вхождении минтерма в карту на наличие их склейки, проанализировать склеивающиеся минтермы во всех комбинациях. 4. Выбрать такие комбинации, при которых большее число, в результате таких склеиваний получается простые импликанты функции. 5. Из полученных простых импликант выбирают те, которые обеспечивают получение минимальных форм функций.

Метод Квайна минимизации булевых функций. Алгоритм метода. 1. Функцию представить в СБНФ. 2. Провести все возможные склеивания минтермов. 3. Над полученными элементарными конъюнкциями, у которых в результате склеивания сократилось на единицу, производятся дальнейшие возможные склеивания. 4. Процесс заканчивается, когда дальнейшее склеивание не возможно. 5. Полученная в результате склеивания импликанта является простой функцией, а дизъюнкция импликант ДНФ этой функции (сокращенно).

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

Метод импликантных матриц (таблиц). Путем преобразования из функции мы получили минимальную формулу – простая импликанта, которую нельзя исключить из сокращенной ДНФ называют существенной.

Дизъюнкция всех существенных импликант булевых функций называют её тупиковой формой. Функция может иметь несколько тупиковых форм. Тупиковая ДНФ называется минимальной (МДНФ), если количество аргументов, которое она содержит, будет не более, чем в любой другой ДНФ. Для поиска ДНФ применяют метод импликантных матриц. Такая матрица представляет собой прямоугольную таблицу, строки которой соответствуют простым импликантам функции, а столбцы всем минтермам функции. На пересечении строки и столбца ставится отметка, если соответствующая импликанта есть собственная часть минтерма. Таким образом, в каждой строке будут стоять отметки против всех минтермов, которые покрываются соответствующей импликантой. Простые импликанты, которым соответствуют строки с единственной отметкой в своем столбце называются ядром функции. Простые импликанты входящие в ядро функции обязательно входят в любую тупиковую форму этой функции. Следовательно, эта задача является в математике, как задача покрытия.

Минимальные конъюнктивные нормальные формы (МКНФ). МДНФ не всегда дают лучшие решения, в некоторых случаях ищут МКНФ, … только вместо понятия импликанта вводят понятие имплищента. Наиболее простой способ получения МКНФ основан на получении инверсных МКНФ обратной функции. Алгоритм метода: 1. Найти СДНФ заданной функции 2. Найти СДНФ обратной функции 3. Найти МДНФ обратной функции 4. Инверсия полученной МДНФ обратной функции после преобразования по правилам Моргана будет представлять МКНФ заданной функции. Обратная функция имеет значение равной 1 на тех наборах, на которых исходная функция равна 0. Следовательно в СДНФ обратной функции входят те минтермы, которые отсутствуют в исходных СДНФ функций.

Минимизация частичных (не полностью) определенных булевых функций. Частичные булевы функции называются функция, значения которой на некоторых наборах аргумента неопределенны; наборы, на которых функция неопределенна, называются избыточными наборами. Минимизация таких функций существенно зависит от выбранных значений функции на избыточных наборах. Для получения минимальных форм таких функций выписываются все наборы аргументов, на которых функция = 1 и наборы, на всех которых неопределенна. Применяя один из методов минимизации находят простые импликанты функции, а затем из множества полученных импликант выбирают те, которые лучшим образом покрывают все единицы функции.

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

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

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

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