Учебно-методический комплекс по дисциплине основы схемотехники (стр. 4 )

Дополнительная литература: 11, 12

Лекция 4 Тема: Реализация логических функций в ЭВМ, логические элементы. Функционально-полные системы логических элементов.

Рассмотрим, какое смысловое содержание можно вложить в некоторые сложные высказывания на примере ФАЛ 2х аргументов.

Инверсия.Читается НЕ Х или 'Х' с чертой, отрицание Х.

Возьмем, например, такое высказывание: А=<Киев-столица Франции>, тогда сложное высказывание НЕ А означает: не верно, что А, т. е. не верно, что <Киев-столица Франции>.

Из простых высказываний можно строить более сложные, применяя так называемые связи.

Логические связи – это ФАЛ, аргументами которых являются простые высказывания

Конъюнкция. Возьмем 2 высказывания:

А=<Москва – столица РФ>

В=<дважды два - четыре>

тогда сложное высказывание: А & В будет истинным, так как истинны оба этих высказывания.

Поскольку таблица истинности для конъюнкции совпадает с таблицей умножения, если истинному высказыванию приписать значение '1', а ложному - '0', то сложное высказывание можно назвать произведением.

X1	X2	f1(X1,X2)
0	0	0
0	1	0
1	0	0
1	1	1

Функция конъюнкции истинна тогда, когда истинны одновременно оба высказывания.

Дизъюнкция. Это сложное высказывание истинно тогда, когда истинно хотя бы одно высказывание, входящее в него.

X1	X2	f1(X1,X2)
0	0	0
0	1	1
1	0	1
1	1	1

Читается X1 ИЛИ X2: Некоторое отличие от смысла союза «или», принятого в русском языке: в данном случае этот союз употребляется в смысле объединения, а не разъединения.

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

Естественно возникает вопрос, какое количество связок необходимо, чтобы построить произвольную ФАЛ. Ответ на этот вопрос не однозначен. Мы видим, что, например, с помощью только функции f0 (константа 0), f15 (константа 1) произвольную ФАЛ построить нельзя. Нельзя ее построить и с помощью только инвертора. Однако очевидно (теорема), что это можно сделать с помощью f7, f1, f10 или f7, f1, f12.

Эта совокупность элементарных ФАЛ называется базисом конъюнкции, дизъюнкции и отрицания. Это наиболее распространенный базис при математическом построении ФАЛ. Существуют и другие базисы: , +, 1, |

Есть также одноэлементные базисы: f8 – стрелка Пирса, f14 – штрих Шеффера, И-НЕ, ИЛИ-НЕ.

Технически синтез устройства означает, что нужно иметь некоторый набор элементов, ФАЛ которых образуют базис, чтобы можно было построить реальное устройство.

Однако, как было отмечено, задача синтеза ФАЛ – идеальная модель. В действительности, для построения реальных устройств пользуются несколько более расширенным набором элементов усиления и коррекции сигналов.

Основная литература: 1, 2, 3, 4, 8

Дополнительная литература: 11, 12,13

Лекция 5 Тема: Минимизация функции алгебры логики и ограничения при ее рассмотрении.

Покажем на примере, что СДНФ не является экономной формой записи:

f(Х1, Х2)= Х1Х2 Х1Х2 Х1Х2 =Х1Х2 Х1 на основании полного склеивания по Х2 мы видим, что запись стала короче, т. к. содержит меньшее число связок и букв. Физически это означает, что устройство, которое реализует эквивалентную, но более простую функцию, будет иметь в своем составе меньшее количество оборудования, а следовательно, будет работать надежнее.

Итак, задача синтеза устройства должна быть дополнена задачей уменьшения оборудования в нем. С математической точки зрения это задача построения минимальной ФАЛ.

Под минимальной ФАЛ понимается такая форма, в которой содержится меньшее количество букв, чем в ее исходной форме.

Если на каком-либо наборе f принимает значениа а1, а – значение а2, то говорят, что f своим значением а1 покрывает значение а2 функции .

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

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

Так, каждое элементарное произведение, входящее в СДНФ, покрывает только одну единицу функции.

Порядок получения Сок. ДНФ может быть следующим:

Провести все операции неполного склеивания конституент единицы исходной СДНФ. Получатся произведения (n-1) ранга; оставшиеся несклеенные конституенты единицы не могут участвовать в дальнейших склеиваниях. Провести покрытие всех полученных произведений и конституент единицы. Часть некоторых конституент единицы будет устранена. продолжить, пока возможны операции 1) и 2).

Пример 1:

f(Х1, Х2)= Х1Х2 Х1Х2 Х1Х2

Если применим операцию полного склеивания, то получим:

или

f(Х1, Х2)= Х1 Х1Х2

или

f(Х1, Х2)= Х1Х2 Х2

т. е. у нас нет возможности далее провести операцию.

Применим теперь операцию неполного склеивания:

f(Х1, Х2)= Х1 Х1Х2 Х1Х2 Х1Х2 Х2 = Х1 Х2 Х1Х2 Х1Х2 Х1Х2

Простые импликанты: Х1, Х2

Конституенты единицы: Х1Х2, Х1Х2, Х1Х2

Теперь можем провести операции поглощения:

Х1 поглощает: Х1, Х1Х2, Х1Х2

Х2 поглощает: Х2 , Х1Х2, Х1 Х2