УП часть 2 ТА

Реализуем элементарные конъюнкции, соответствующие каждой фиктивной переменной и их дизъюнкции в соответствии с уравнениями (1.13) на логической схеме (рис.1.7):

Рис. 1.7 Реализация минимизированной системы функций на логической схеме

2. ФУНКЦИОНАЛЬНО ПОЛНЫЕ СИСТЕМЫ ЭЛЕМЕНТАРНЫХ ЛОГИЧЕСКИХ ФУНКЦИЙ

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

Система функций алгебры логики f1, f2, …, fm называется функционально полной, если любая логическая функция от произвольного числа n – аргументов может быть представлена суперпозицией функций f1, f2, …, fm.

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

Минимальным базисом называется такой базис из f1, f2, …, fm, для которого удаление хотя бы одной из функций fi, i=1,…,m входящих в этот базис, превращает систему функций f1, f2, …, fm в неполную.

Функциональной полнотой обладают следующие элементные базисы:

1.И, ИЛИ, НЕ (основной базис);

2.И, НЕ;

3.ИЛИ, НЕ;

4.И-НЕ;

5.ИЛИ-НЕ;

6.1, И, Å .

До определенного момента времени для доказательства функциональной полноты системы элементарных функций f1, f2, …, fm использовался следующий эвристический прием.

Требовалось доказать, что если с помощью элементарных функций f1, f2, …, fm могли быть реализованы логические функции основного базиса (И, ИЛИ, НЕ), то в этом случае система функций f1, f2, …, fm считалась полной. Суть этого доказательства рассмотрим на примере логического базиса, состоящего из элемента И-НЕ.

1. Докажем, что с помощью элемента И-НЕ может быть реализована операция НЕ.

Дано y = a × b ; пусть a=b, следовательно y = a × a = a - реализована операция НЕ.

a & a

2. Докажем, что с помощью элемента И-НЕ может быть реализована операция И.

Дано y = a × b ; рассмотрим функцию z = y = a ×b = a ×b - реализована операция И.

ИЛИ.

b &

Следовательно, базис И-НЕ является полным.

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

соотношение: f (0,0,...,0) = 0 , т.е. на нулевом наборе аргументов,

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

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

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

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

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

4.Свойство монотонности: функция обладает этим свойством, если для любой последовательности наборов, в каждом из которых аргументы не убывают, значения функции также не убывают, при этом полагаем, что 0<1.

5.Свойство линейности: данным свойством обладают те логические функции, которые могут быть представлены в следующем виде:

f (x1 , x2 ,..., xn ) = a0 Å a1 x1 Å a2 x2 Å ....Å an xn , где ai Î{0,1}.

В таблице 2.1 приведены элементарные логические функции одного и двух аргументов: таблицы истинности, представление в виде ДНФ или КНФ, названия наиболее используемых логических функций.

Рассмотрим наличие и отсутствие перечисленных выше пяти свойств у элементарных логических функций из таблицы 2.1. Результаты исследований занесем в таблицу 2.2. Если функция обладает исследуемым свойством, то в соответствующей ячейке поставим “x”.

Таблица 2.2

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

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

Из неубывающих значений аргументов логических функций строятся неубывающие наборы, состоящие из значений аргументов. Рассмотрим значения x1, x2 в таблице 2.2. Как видно из таблицы аргумент x1 не убывает, а аргумент x2 убывает. Для того, чтобы аргумент x2 не убывал, необходимо составлять наборы значений аргументов либо из 1,3,4 строк, либо из 1,2,4 строк таблицы 2.2. Выпишем эти наборы значений:

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

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

Далее рассмотрим, как определяется наличие или отсутствие у логических функций пятого свойства – свойства линейности.

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

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

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

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

Теорема Поста: Для того, чтобы множество N двоичных функций было базисом необходимо и достаточно, чтобы:

1.N содержало бы по крайней мере одну функцию, не сохраняющую ноль;

2.N содержало бы по крайней мере одну функцию, не сохраняющую единицу;

3.N содержало бы по крайней мере одну функцию, немонотонную;

4.N содержало бы по крайней мере одну функцию, несамодвойственную;

5.N содержало бы по крайней мере одну нелинейную

функцию.

3. ПРОГРАММИРУЕМЫЕ ЛОГИЧЕСКИЕ ИНТЕГРАЛЬНЫЕ СХЕМЫ

Интегральная (микро)схема (англ. microchip, silicon chip, chip — тонкая пластинка — первоначально термин относился к пластинке кристалла микросхемы) — микроэлектронное устройство — электронная схема произвольной сложности, изготовленная на полупроводниковом кристалле (или плёнке) и помещённая в неразборный корпус. Часто под интегральной схемой (ИС) понимают собственно кристалл или плёнку с электронной схемой, а под микросхемой (МС) — ИС, заключённую в корпус.

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

В 1958 году двое учёных, живущих в совершенно разных местах, изобрели практически идентичную модель интегральной схемы. Один из них, Джек Килби, работал на Texas Instruments, другой, Роберт Нойс, был одним из основателей небольшой компании по производству полупроводников Fairchild Semiconductor. Обоих объединил вопрос: «Как в минимум места вместить максимум компонентов?». Транзисторы, резисторы, конденсаторы и другие детали в то время размещались на платах отдельно, и учёные решили попробовать их объединить на одном монолитном кристалле из полупроводникового материала. Только Килби воспользовался германием, а Нойс предпочёл кремний. В 1959 году они отдельно друг от друга получили патенты на свои изобретения — началось противостояние двух компаний, которое закончилось мирным договором и созданием совместной лицензии на производство чипов. После того как в 1961 году Fairchild Semiconductor Corporation пустила интегральные схемы в свободную продажу, их сразу стали использовать в производстве калькуляторов и компьютеров вместо отдельных транзисторов, что позволило значительно уменьшить размер и увеличить производительность.