Чтобы система логических функций была функционально полной, необходимо и достаточно, чтобы эта система содержала хотя бы одну функцию, не сохраняющую ноль, хотя бы одну, не сохраняющую единицу, хотя бы одну нелинейную и хотя бы одну немонотонную.
Функция инверсии (отрицания), обозначаемая НЕ, является самодвойственной и линейной и не сохраняющей 0, не сохраняющей 1 и немонотонной. Упомянутая выше функция конъюнкции является кроме того функцией, сохраняющей 1 и монотонной, но несамодвойственной и нелинейной. Таким образом функция конъюнкции и функция инверсии вместе обладают всеми пятью необходимыми свойствами, то есть образуют функционально полную систему функций [2].
Одновременно всеми пятью свойствами обладает функция штрих Шеффера (отрицание конъюнкции), составленная из функций конъюнкции и отрицания 
Для упрощения записи функцию обозначают штрихом F=x|y. Второй функцией, обладающей такими свойствами, является функция отрицание дизъюнкции 
называемая иначе стрелка Пирса и обозначаемая f=x↓y.
Целью этой работы является ознакомление с методами синтеза логических схем с использованием схемы, реализующёй функцию И–НЕ[2] (штрих Шеффера).
Из сказанного выше следует, что любая схема, реализующая функцию алгебры логики может быть построена на однотипных логических элементов, реализующих функцию штрих Шеффера.
Функция штрих Шеффера справедлива для любого числа аргументов.
(1)
Для функции отрицания и функции штрих Шеффера справедливо соотношение 
(2)
Синтез схем на элементах И-НЕ удобно проводить исходя из минимальных дизъюнктивных нормальных форм логических[3] функций.
Рассмотрим правило перехода от дизъюнктивной нормальной формы (в частном случае минимальной) к представлению функции через операции Шеффера и отрицания. Правило гласит:
чтобы представить переключательную функцию через операции Шеффера и отрицания, достаточно в дизъюнктивной нормальной форме (ДНФ) этой функции заменить все операции дизъюнкции и логического умножения (конъюнкции) операциями Шеффера и группы букв, соответствующие дизъюнктивным членам, заключить в скобки.
Чтобы убедиться в справедливости этого правила, достаточно дважды взять отрицание от каждого дизъюнктивного члена заданное дизъюнктивной формой и применить вначале правило де Моргана, а затем соотношение (2).
Пример 1. Построить логическую схему, реализующую переключательную функцию, заданную в дизъюнктивной нормальной форме.
F(ABCD)= 
Применяя приведённое выше правило, получаем
F(ABCD)= 
Схема, реализующая это выражение, приведена на рис. 1.
Рис. 1. Логическая схема, реализующая функцию F(ABCD).
Если число входов универсального элемента x|y ограничено, то, пользуясь соотношениями (1) и (2), переключательную функцию следует преобразовать к функциям с ограниченным числом аргументов.
Пример 2. Построить логическую схему, реализующую переключательную функцию, заданную в минимальной дизъюнктивной нормальной форме.
Синтез провести на элементах И-НЕ с двумя и тремя входами.
Представим заданную функцию через операцию Шеффера и отрицание:
Применим соотношения (1) и (2): 
Логическая схема, реализующая полученное выражение, приведена на рис. 2.
Рис. 2.
Изложенные выше методы синтеза можно применять в любом случае, независимо от того выполняются ли логические элементы на транзисторах или на других физических приборах. При этом может оказаться нежелательным применение операции инверсии. Чтобы устранить эту операцию, достаточно в выражениях, которые содержат функцию Шеффера (или Пирса) и инверсию исключить отрицания с помощью выражения (1) или (2).
Интегральные логические элементы
Характерной особенностью современных цифровых вычислительных машин (ЦВМ) является применение логических элементов, выполненных на интегральных микросхемах.
Интегральная схема – ИС (микросхема) представляет собой микроминиатюрный функциональный узел электронной аппаратуры (триггер, логическая схема, усилитель и т. п.), в котором элементы и соединительные проводники, входящего в схему узла, изготавливаются в едином технологическом цикле на поверхности или в объёме полупроводникового материала основания (подложки) и имеют общую герметизацию и защиту от механических воздействий.
Применение интегральных микросхем способствует повышению надёжности, улучшению характеристик и снижению стоимости электронной аппаратуры.
Стоимость изготовления интегральной схемы, содержащей десяток или более транзисторов, при современной технологии можно сравнивать со стоимостью одного транзистора. При этом надёжность её выше аналогичного устройства на транзисторах. Основной задачей современной микроэлектроники, в первую очередь, является производство надёжных и дешевых интегральных микросхем, обладающих хорошими характеристиками. Это достигается методами массового производства, сопровождаемого автоматизацией технологических процессов.
Спецификой производства интегральных микросхем является то, что часто проще изготовить транзистор, чем создать резисторы с малым разбросом сопротивлений или резистор с большим сопротивлением. Поэтому обычно изготавливаются усложнённые варианты логических схем, где транзисторов применяется значительно больше, чем в соответствующих устройствах на дискретных компонентах. В подобных микросхемах транзисторами часто заменяют резисторы в цепи коллекторной нагрузки или в качестве сопротивления источника постоянного тока. При массовом изготовлении транзисторов на одном кристалле достигается большая идентичность пороговых напряжений транзисторов.
Классификация электрических схем микросхем логических элементов частично повторяет классификацию логических схем, изготовленных на дискретных компонентах. Однако в интегральной микросхемотехнике имеются решения, отличные от имеющихся в дискретной технике.
Интегральные логические элементы представляют собой схемы с непосредственными связями, то есть не содержат разделительных конденсаторов или трансформаторов. Поэтому от каскада к каскада происходит передача потенциала. Поскольку сигналом в рассматриваемом случае является изменение потенциала, то эти микросхемы называются схемами потенциального типа (в отличие от импульсных).
В настоящее время выпускаются логические микросхемы транзисторно-транзисторной логики – ТТЛ, в том числе с транзисторами Шоттки, микросхемы на переключателях тока с эмиттерными связями – ЭСТЛ. И те, и другие выполняются на биполярных транзисторах. Наряду с биполярными логическими схемами выпускаются логические микросхемы на полевых структурах.
Базовый элемент транзисторно-транзисторной логики
Схема базового элемента показана на рис.3. Входным элементом является биполярный многоэмиттерный транзистор.
Рис. 3.
Для пояснения работы базового элемента рассмотрим вариант ТТЛ с простым инвертором, рис.4 [5].
Рис. 4.
Пусть на обоих входах схемы на рис. 4 высокий потенциал. Этот случай представлен на рис. 5.
Рис. 5.
Тогда многоэмиттерный транзистор – МЭТ работает с открытым коллекторным переходом. Коллекторный переход работает, как открытый диод (включенный в прямом направлении), обеспечивающий ток базы Iб2, достаточный для насыщения Т2. Переходы база-эмиттер МЭТ закрыты. Таким образом транзистор Т1 работает в инверсном режиме.
Теперь пусть на одном из входов простого ТТЛ элемента появился низкий потенциал. В этом случае транзистор Т1 перейдёт в режим насыщения, рис. 6.
Рис.6.
Его переход база-эмиттер открывается. Между базой транзистора Т2 и «землёй» оказывается включённым малое сопротивление насыщения транзистора Т1.
Лабораторный макет
Лабораторный макет состоит из 12 элементов И-НЕ, и источников сигналов (потенциалов), снимаемых с выходов «Лог. 1» (потенциал +Еп), и «Лог. 0» (потенциал "земли").
Питание макета включается тумблером.
Порядок выполнения работы
1. После отчёта по теоретическому материалу выполнить на компьютере моделирование функции, заданной преподавателем. Для моделирования воспользоваться ППП Max+Plus II, Quartus II (например, воспользовавшись графическим редактором) или с помощью другого ППП[4]. Сначала функция должна быть промоделирована в виде, указанном в задании, а затем в виде, получившемся после реализации на элементах И-НЕ. По результатам моделирования убедиться, что получена та же функция в другой реализации. Продемонстрировать результаты моделирования.
2. Продемонстрировать работу синтезированной логической схемы на лабораторном макете.
3. Составить письменный отчёт.
Содержание отчёта
1. Письменный отчёт должен содержать название работы, фамилию студента, номер учебной группы и дату.
2. Исходную функцию и результат её реализации с помощью функции И-НЕ
3. Графический материал с результатами моделирования на компьютере.
4. Таблицу истинности снятую на лабораторном макете.
Литература
1. Каган Б.М. Электронные вычислительные машины и системы: Учеб пособие для вузов. – М.: Энергоатомиздат, 1991. – 592 с.
2. Ситников Ю.К. Основы цифровой вычислительной техники. Учебное пособие. Казань, 1992. – 168 с.
3. Вавилов Е.Н., Портной Г.И. Синтез схем электронных цифровых машин. – М.: Сов. радио. 1963. – 440 c.
4. Поспелов Д.А. Логические методы анализа и синтеза схем. – М.: «Энергия», 1964. –
5. Алексенко А.Г. Основы микросхемотехники. – М.: ЮНИМЕДИАСТАЙЛ, 2002.– 448 с.
6. Скарлетт Дж Транзисторно-транзисторные интегральные схемы и их применение. – М.: Мир, 1974. – 288 с.
7. Комолов Д.А., Мяльк Р.А., Зобенко А.А., Филиппов А.С. Системы автоматизированного проектирования фирмы Altera MAX+Plus II и Quartus II. Краткое описание и самоучитель. – М.: ИП РадиоСофт, 2002. – 352 с.
8. Алексенко А.Г., Шагурин И.И. Микросхемотехника: Учеб. Пособие для вузов. – 2-е изд. – М.: Радио и связь, 1990. – 496 с.
10. Точчи Рональд, Дж., Уидмер, Нил, С. Цифровые системы. Теория и практика. 8-е издание.: пер. с англ. – М.: Издательский дом "Вильямс", 2004. – 1024 с.
–
ПРИЛОЖЕНИЕ
Графический ввод схемы устройства
и функциональная симуляция с использованием САПР MAX+plusII
Программный продукт MAX+plusII представляет собой интегрированную систему автоматизированного проектирования (EDA - electronic design automation) цифровых систем, которая предполагает реализацию проекта с использованием программируемых логических интегральных схем (ПЛИС) Система позволяет описать проект несколькими способами: посредством ввода принципиальной схемы, текста на языке AHDL (Altera Hardware Description Language), в виде временных диаграмм функционирования, как машину состояний.
Система включает 11 программных модулей - приложений (applications), каждый из которых используется для выполнения определенного этапа обработки проекта. В список входят графический редактор, текстовый редактор, символьный редактор, редактор диаграмм, компилятор, монитор структуры проекта, симулятор, редактор конфигурации БИС, временной анализатор, программатор, процессор сообщений. Пользователь может пользоваться подсистемой помощи - Help, которая выдает информацию в виде гипертекста. Вид окна Manager системы MAX+plusII с открытым списком приложений приведен на рис. П.1.
Рис. П.1. Вид окна Manager системы Max+plusII с открытым списком приложений
ОПИСАНИЕ ПРОЦЕСА ПРОЕКТИРОВАНИЯ С ИСПОЛЬЗОВАНИЕМ ГРАФИЧЕСКОГО РЕДАКТОРА
Пусть проектируемое устройство определено булевым уравнением, а описание проекта в системе MAX+plusII предполагается с использованием библиотеки примитивов. Последовательность решения такой задачи следующая:
• исходя из уравнения необходимо определить количество переменных и построить таблицу истинности;
• используя графический редактор, ввести схему устройства. Начинать рекомендуется с входных портов, количество которых определяется количеством переменных в уравнении. Далее анализируется вид членов уравнения и вызываются соответствующие примитивы из библиотеки системы MAX+plusII. В завершение выполняются соединения (цепи и шины), вызывается примитив выходного порта;
• используя редактор временных диаграмм, на основе таблицы истинности формируются тестовые векторы для проверки (верификации) соответствия введенной схемы и первоначального уравнения. Для этого используется функциональная симуляция;
• выполняется трансляция проекта, вызывается симулятор, который на основе тестовых векторов формирует диаграмму выходной функции устройства;
• сравнивая диаграмму состояний функции с таблицей истинности делается заключение о правильности функционирования разработанного устройства.
При выполнении логического проектирования цифровых устройств следует иметь в виду, что для получения наиболее эффективного схемного решения во многих случаях целесообразно произвести определенные преобразования исходного алгебраического уравнения. В первую очередь следует произвести минимизацию заданной функции, используя один из методов дискретной математики (например, метод Квайна-МакКласки или метод, использующий карты Карно). Если многие импликанты в исходном выражении функции содержат общие логические переменные, целесообразно выполнить факторизацию - вынесение за скобки общих переменных. В результате получается скобочная форма представления функции, реализация которой обычно требует меньшего числа логических элементов (вентилей). В результате уменьшается число используемых элементов ПЛИС, поэтому можно реализовать на базе ПЛИС большее число требуемых функций. Другим методом получения скобочных форм является разложение функций по теореме Шеннона:
где xi - выделенная переменная, f0, f1 - логические функции, полученные из исходной функции 
подстановкой значений хi=0, хi = 1, соответственно. Данное соотношение позволяет реализовать функцию п переменных как композицию функций f0, f1, имеющих (п-1) переменную.
Выполнение такого рода преобразований в процессе схемотехнического проектирования цифровых устройств описано в учебном пособии [8] и ряде других монографий. Использование этих преобразований позволяет получить для заданной функции несколько эквивалентных выражений. При их схемотехнической реализации получаются различные варианты схем, выполняющие заданную функцию. Проектировщик имеет возможность провести анализ их характеристик и выбрать вариант схемы, в наибольшей степени соответствующий требованиям технического задания.
В качестве примера в данной работе будем рассматривать цифровое устройство, которое выполняет логическую функцию
Таблица истинности имеет следующий вид
| xl | x2 | x3 | f |
| 0 | 0 | ||
| 0 | 0 | ||
| 0 | |||
| 0 | |||
Осуществим ввод принципиальной схемы устройства с использованием графического редактора системы MAX+plusII, выполним трансляцию проекта с использованием приложения Compiler и проверим выполнение таблицы истинности, используя приложение Simulator.
ПОСЛЕДОВАТЕЛЬНОСТЬ МОДЕЛИРОВАНИЯ
Определение имени проекта. Разрабатываемое устройство представляется в системе MAX+plusII как проект. Вначале работы с системой необходимо определить текущий проект, т.е. указать его имя и директорию. Выберем директорию d:\max2work\tutorial, а в качестве имени проекта укажем graphic1. Из меню Manager выберите File→Project→Name, откроется диалоговое окно, приведенное на рис. 1.2. Имя тома и директория выбираются с помощью соответствующих меню, имя файла вводится в строке File Name. Завершается определение нажатием ОК. Имя проекта отобразится в титульной строке окна Manager.
Рис. 1.2. Вид диалогового окна определения имени проекта
Использование графического редактора. Для вызова графического редактора нужно в меню Manager выбрать Max+plusII→Graphic Editor. Откроется окно графического редактора, в титульной строке окна появится сообщение (Untitledl - Graphic Editor), говорящее о том, что текущим приложением системы MAX+plusII является графический редактор и открыт неименованный файл. Строка меню Manager содержит имена команд и набор инструментальных панелей, которых не было на рис. 1.1, то есть вид окна Manager зависит от текущего приложения. Чтобы узнать назначение каждой панели, нужно навести на нее указатель мыши, информация высветится под окном в строке состояния.
Графическому файлу со схемой узла необходимо присвоить имя с расширением .gdf (Graphic Design File).. Для этого выберите File→Save As и в строке File Name появившегося диалогового окна укажите имя graphic1.gdf, нажмите ОК.
Для ввода графических изображений элементов будем импортировать их из библиотеки, которая в этой системе называется Primitives. Дважды щелкните мышью в центре экрана графического редактора. Откроется диалоговое окно, в котором в меню Symbol Libraries указанная библиотека находится по адресу d:\maxplus2\max21ib\prim. Дважды щелкните мышью по этой строке, в меню Symbol Files появится список логических элементов. Двойной щелчок по имени and2 приводит к копированию элемента в окно графического редактора в позицию, определенную ранее курсором. Щелчок мышью по элементу производит его выбор, о чем свидетельствует окрашивание в красный цвет. После этого передвигая курсор мыши при нажатой кнопке 1 можно двигать элемент по окну редактора. Для определения положения элемента полезна сетка, которая появляется при активизации опции Option→Show guidelines.
Для реализации функции , рассматриваемой в этом примере, нужен еще один элемент and2, два элемента ог2 и элемент not. Введите эти элементы (примитивы) указанным выше образом. После того, как логические элементов введены, нужно ввести символы входных и выходных портов. Их примитивы находятся в той же библиотеке под именами input и output Введите три входных порта и один выходной, чтобы получить вид экрана, приведенный на рис.П.3.
Рис. П.3. Вид окна графического редактора с изображениями примитивов
Далее необходимо присвоить имена всем портам. Для этого дважды щелкните мышью по слову PIN_NAME на символе входного порта, находящегося в верхнем левом углу экрана. Слово засветится, позволяя прямо набрать имя порта. Нажатие Enter непосредственно после имени переводит курсор на следующий порт и так далее. Присвойте имена х2 и хЗ оставшимся двум входным портам и имя, например , выходному порту.
Следующим шагом является ввод линий, соединяющих логические элементы между собой и с портами.
Нажмите панель "Выбор объекта" - верхнюю в вертикальном меню слева от окна редактора (на ней изображена белая стрелка). Если после этого подвести курсор к концу линии вывода порта х1, его указатель приобретет вид креста, а после нажатия правой клавиши мыши потянет за собой соединительную линию, которая кончается при отпускании клавиши. Соединение выхода и входа двух элементов выполняется в виде горизонтальных и вертикальных отрезков прямых. Любой отрезок можно выделить, щелкнув по нему мышью (он станет красным), и стереть (например, клавишей Delete). Проведите все соединения, чтобы схема приобрела вид, соответствующий рис. П.4.
Рис. П 4. Вид окна графического редактора со схемой устройства graphic1
Работа с компилятором. После ввода схемы система проектирования анализирует ее и генерирует булевы уравнения для всех логических функций. Этот этап обработки выполняет приложение-компилятор, который вызывается выбором Max+PlusII→Compiler или щелчком по панели компилятора в меню инструментов. Перед компиляцией нужно выбрать тип микросхемы ПЛИС, на которой будет реализован проект. Наберите Assign→Device и в открывшемся окне укажите тип микросхемы ПЛИС (рекомендуется -EPF8282ALC84-2 из семейства (Family) Flex8000). Время перекомпиляции проекта сокращается, если установлена опция Smart Recompile (Processing→Smart Recompile). Если выбрать Processing→Design Doctor, специальная утилита проверит все файлы проекта на соответствие правилам реализации на выбранном типе ПЛИС. Для дальнейшей симуляции понадобится SNF-файл, для его генерации нужно указать Processing→Functional SNF Extractor. После установки опций щелчок по клавише Start запускает процесс компиляции, после окончания которого высвечиваются сообщения об ошибках errors) и предупреждения (warnings). После успешной трансляции закройте окно компилятора (кнопкой Х в верхнем правом углу окна).
Симуляция. Симуляцией обычно называют процесс функционального моделирования с использованием программно-логической модели. Перед проверкой функционирования схемы необходимо создать тестовые векторы, которые представляют значения входных сигналов. Мы будем использовать для их создания редактор диаграмм, который выбирается последовательностью команд Max+PlusII→Waveform Editor. Когда окно редактора откроется, создайте файл graphic.scf, последовательностью File→Save As и указанием graphicl.scf в строке File Name открывшегося диалогового окна.
Далее определим входные и выходные линии схемы для процесса симуляции. Для этого используем линии, занесенные в SNF-файл (Simulator Netlist File), созданный на этапе компиляции схемы. Введите Node→Enter Node from SNF. Откроется экран, в котором имеется два окна: Available Nodes & Groups и Selected Nodes & Groups. После нажатия List в первом окне появится список входных и выходных линий из SNF-файла. Нужно скопировать входные линии х1, х2, хЗ и выходную линию во второе окно. Для этого нужно отметить линии поодиночке или блоком и нажать панель => между окнами. Чтобы отметить одну линию, нужно щелкнуть по ней мышью. Чтобы отметить блок, нужно протащить указатель по списку при нажатой правой клавише мыши. В завершение нажмите ОК и вернитесь в окно редактора.
Определим параметры процесса симуляции, значения входных переменных для нашей схемы. Вначале вводом File→End Time откроем окно определения полного времени симуляции, введем значение, например 160ns, и щёлкнем ОК. Далее определим интервал сетки окна редактора, введя Options→Grid Size и набрав 20ns. После возврата в окно редактора (вводом ОК) экран системы выглядит так, как приведено на рис. 1.5. На входных линиях значения логического "О", а выходная линия заштрихована, что указывает на неопределенность значения выходной переменной.
Рис. 1.5. Вид окна редактора диаграмм (определены входные и выходные линии и сетка)
Для полной симуляции функционирования нашего устройства необходимо подать на входы все комбинации значений переменных. Поскольку переменных три, комбинаций 23 = 8. Длительность каждой комбинации при полном времени симуляции в 160ns равна 20ns. Таким образом, переменная х1 должна иметь значение логической " 1" в интервалы времени 20-40ns, 60-80ns, 100-120ns. Переменная х2 должна иметь значение логической "1" на интервалах 40-80ns, 120-160ns, а переменная хЗ на интервале 80-160ns.
Для редактирования временной диаграммы переменной х1 протащите указатель при нажатой правой кнопке мыши над линией логического "О" во втором интервале сетки. Этот интервал будет "залит" черным цветом, в окнах Ref: и Time: отобразятся значения 20ns и 40ns. Переведите указатель на панель установки значения "1" в левом вертикальном меню инструментов и щелкните мышью. Временная диаграмма х1 в указанном интервале примет значение "1", заливка исчезнет. Аналогичными действиями отредактируйте диаграммы переменных х1, х2, хЗ так, чтобы они приняли значения, указанные в предыдущем абзаце (рис. 1.6). Сохраните созданный файл (комбинация "горячих" клавиш Ctrl+S).
Рис. П.6. Окно редактора диаграмм с определенными для симуляции диаграммами входных переменных
Для вызова приложения-симулятора выберите Max+plusII→Simulator или нажмите соответствующую панель на верхнем меню инструментов. В открывшемся окне симулятора в заголовке указан режим функциональной симуляции, потому что на этапе компиляции была введена опция Processing Functional SNF Extractor. В качестве входного файла указан graphic1.scf. Укажите в качестве Start Time: значение 0.0ns, а в качестве End Time: значение 160.0 ns и щелкните по панели Start. После сообщения об отсутствии ошибок щелкните по ОК и вернитесь в окно симулятора. Результаты симуляции записаны в файл graphic1.scf и отображаются в окне редактора диаграмм (рис. П.7.).
Рис. П.7. Окно редактора диаграмм с результатами симуляции
Убедитесь, что значения функции f соответствуют таблице истинности. Закройте окно редактора диаграмм.
[1] В алгебре Буля нет полиномиальной записи функций, поэтому для проверки свойства линейности надо воспользоваться другой алгеброй логики, например алгеброй Жегалкина.
[2] В математических работах принято называть эту функцию НЕ И, в соответствии с выражение «отрицание конъюнкции».
[3] В технических дисциплинах вместо термина логические функции часто применяют термин «переключательные функции».
[4] Можно воспользоваться ППП MicroCAP, позволяющим моделировать, как аналоговые, так и цифровые устройства.