Лекции в ворде (ДИСКРЕТКА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, где н – число аргументов.


Случайные файлы

Файл
153400.rtf
69246.rtf
12232.rtf
19112-1.rtf
20855-1.rtf




Чтобы не видеть здесь видео-рекламу достаточно стать зарегистрированным пользователем.
Чтобы не видеть никакую рекламу на сайте, нужно стать VIP-пользователем.
Это можно сделать совершенно бесплатно. Читайте подробности тут.