Для получения Минимальной Конъюнктивной Нормальной Формы (МКНФ), используя метод Куайна, вводятся слудующие критерии:
· для минимизации берётся не СДНФ, а СКНФ функции;
· склеиваемые пары членов меняются на: 
или 
;
· правило операции поглощения выглядит следующим образом:
| Синякина Г.Е. МММММММММММММММммухамедшиной. |
| Монтаж, наладка и эксплуатация САУ |
12. Функции алгебры логики
Радиоэлектроника в настоящее время во многом определяет научно- технический прогресс и объединяет ряд отдельных областей науки и техники, развившихся из радиотехники и электроники.
Радиотехника - область науки и техники, связанная с разработкой устройств и систем, обеспечивающих генерирование, усиление, преобразование, хранение, а также излучение и прием электромагнитных колебаний радиочастотного диапазона, используемых для передачи информации.
В современных радиотехнических системах и комплексах до 90% разрабатываемых устройств реализуется на элементах цифровой и вычислительной техники и используются цифровые методы обработки сигналов.
В настоящее время бурно развивается по экспоненциальному закону вычислительная техника и ее элементная база. А не так давно первые интегральные микросхемы (1958 год) содержали до десяти транзисторов. Сегодня современные микропроцессоры содержат до 10 миллионов транзисторов на один кристалл, и менее чем через десять лет это число достигнет 100 миллионов транзисторов.
Уже отошла в историю дискретная схемотехника, когда различные узлы строились на печатных платах с использованием отдельных навесных радиоэлектронных компонентов: транзисторов, резисторов, конденсаторов и других элементов. Ранее соединения выполнялись с помощью внешнего печатного монтажа, теперь соединения и монтаж осуществляется внутри кристалла. Поэтому современный инженер электронной техники должен владеть передовыми методами и технологиями, чтобы уметь приспособить их завтра к вычислительной технике будущих поколений, овладеть практическими приемами проектирования устройств на программируемых логических интегральных схемах.
Логические выражения n двоичных переменных с помощью конечного числа логических операций можно рассматривать как некоторую функцию, отражающую взаимную связь между входными и выходными переменными. Логические операции конъюнкции 
и дизъюнкции 
можно представить простейшими функциями вида: 
и 
. Эти функции называются аналогично логическим операциям – функциями И и ИЛИ.
Такие ФАЛ подобно логическим выражениям могут быть заданы аналитическим и табличным способами.
При аналитическом способе ФАЛ задается в виде логических выражений, получаемых путем логических преобразований с помощью законов и правил Булевой алгебры.
При табличном способе ФАЛ задается таблицей истинности, где число всех возможных наборов (комбинаций) аргументов конечно. Если число аргументов ФАЛ равно n, то число их возможных наборов 
, а число различных функций 
, тогда при n=2, F=16. Составим таблицу истинности для функций двух аргументов.
Таблица 1.
В таблице 1 приведены элементарные ФАЛ 
двух аргументов. В левой части таблицы перечислены все возможные наборы аргументов 
и 
, в правой части приведены значения ФАЛ на соответствующих входных наборах. Значения всей совокупности этих наборов переменных представлены в таблице последовательностью чисел в двоичной системе счисления.
Каждая ФАЛ обозначает одну из 16 возможных логических операций над двумя переменными и , имеет свою таблицу истинности, собственное название и условное обозначение.
Основные сведения об элементарных функциях даны в таблице 2. Таблицы истинности для каждой ФАЛ составляются отдельно по таблице 1.
Таблица 2
 Функция | Операционные символы | Обозначения, названия | Зарубежные аналоги |
 | | Константа 0 | Const 0 |
 |  |  И – лог. умножитель |  AND – Conjunctor |
 |  |  Запрет |  Inhibition |
 |  |  Повторитель |  BF – Buffer |
 |  |  Запрет  |  Inhibition |
 |  |  Повторитель |  BF – Buffer |
 |  |  Исключающее ИЛИ |  Exlusive – OR |
 |  |  ИЛИ – лог. сумматор |  OR – Disjunctor |
 |  |  ИЛИ – НЕ, функция Пирса |  NOR, Peers F. |
 |    |  Исключ. ИЛИ – НЕ |  EX – NOR |
 |  |  НЕ – инвертор |  NOT – Invertor |
 |  |  Импликатор |  Implicator |
 |  |  НЕ – инвертор |  NOT – Invertor |
 |  |  Импликатор | Implicator  |
 |  |  И – НЕ, функция Шеффера |  NAND, Shaffer F. |
 | |  Генератор 1 |  Generator 1 |
В таблице 2 часто применяемыми являются функции:
-повторители 1-го и 2-го аргументов;
– инверсии 1-го и 2-го аргументов;
– функция И (конъюнкция), логическое умножение;
– функция И-НЕ (базис Шеффера);
– функция ИЛИ (дизъюнкция), логическое сложение;
– функция ИЛИ-НЕ (базис Пирса);
– функция неравнозначности, реализуется ЛЭ “Исключающее ИЛИ” (сумматор по модулю два);
– функция равнозначности реализуется ЛЭ “Исключающее ИЛИ-НЕ”.
Рассмотренные элементарные функции двух аргументов
играют важную роль при преобразованиях сложных логических выражений, а также при преобразовании функциональных цифровых узлов.
Функции n переменных, значения которых заданы во всех точках области определения, считаются полностью определенными ФАЛ. Если какая-либо функция имеет запрещенные наборы переменных и ее значения на указанных наборах не определены, то такая ФАЛ называется не полностью определенной. Такие наборы будем отмечать в таблицах истинности (*) и при необходимости доопределять их значениями 0 и 1. Эти вопросы будут рассматриваться позже.
Логические функции, которые считаются полностью определенными, могут быть представлены различными формами.
ДНФ – дизъюнктивная нормальная форма записи ФАЛ представляется в виде суммы (дизъюнкции) ряда элементарных членов (минтермов), каждый из которых является произведением (конъюнкцией) аргументов или их инверсий. Термин “нормальная форма” предполагает, что в логическом выражении, задающем функцию, последовательно выполняются не более двух базовых операций (кроме инверсии).
Запишем ФАЛ в ДНФ:
; (1)
Функцию (3.19) можно записать в виде дизъюнкции минтермов:
, где
- конъюнкции аргументов ФАЛ, называемые минтермами.
СДНФ – совершенная дизъюнктивная нормальная форма записи ФАЛ представляется в ДНФ, где в каждом элементарном члене (минтерме), имеющем одинаковую размерность, представлены все аргументы функции или их инверсии.
Запишем ФАЛ в СДНФ:
. (2)
Если записать ФАЛ в виде:
, (3)
то форма представления данной функции не является СДНФ, так как второй минтерм не содержит аргумента
, а также не является ДНФ, так как третий минтерм
не является элементарным.
Функцию
можно упростить (минимизировать) и представить минимальной ДНФ (МДНФ).
(4)
Полученные элементарные члены МДНФ называются импликантами.
КНФ – конъюнктивная нормальная форма записи ФАЛ, представляется в виде произведения (конъюнкции) ряда элементарных членов (макстермов), которые являются суммой (дизъюнкцией) аргументов ФАЛ.
Запишем функцию
в КНФ:
. (5)
СКНФ – совершенная конъюнктивная нормальная форма записи ФАЛ представляется в КНФ, где в каждом элементарном члене (макстерме) представлены все аргументы функции либо их инверсии.
Запишем функцию
в СКНФ:
. (6)
По функциям, представленным в СДНФ и СКНФ, можно построить таблицу истинности и наоборот – по таблице истинности можно записать ФАЛ в СДНФ и СКНФ.
На основании общей табл. 1 составим таблицу истинности функции неравнозначности
и запишем ее в СДНФ и СКНФ.
На наборах N(2,3), где функция принимает значения 1, записываем ФАЛ в СДНФ, а на наборах N(1,4) – в СКНФ. При записи ФАЛ в СДНФ аргументы x=0 записываются с инверсией
, а в СКНФ – без инверсии.
При записи функции в СДНФ по таблице истинности необходимо записать столько дизъюнктивных членов (минтермов), представляющих собой конъюнкции всех аргументов, сколько единиц содержит функция в таблице. Минтермы соединяются знаком логического суммирования.
Если в наборе значение аргумента равно нулю, то в конъюнкцию входит инверсия данного аргумента.
При записи ФАЛ в СКНФ необходимо записать столько конъюнктивных членов (макстермов), сколько нулей содержит функция. Макстермы (конъюнкции аргументов) соединяются знаком логического умножения. Если в наборе значение аргумента равно нулю, то в дизъюнкцию входит аргумент без инверсии.
| Синякина Г.Е. МММММММММММММММммухамедшиной. |
| Монтаж, наладка и эксплуатация САУ |
13. Представления чисел ЭВМ.
Кодирование информации в ЦВМ.
Для хранения чисел в памяти компьютера используется два формата: целочисленный (естественная форма) и с плавающей точкой (нормализованная форма) (точка — разделительный знак для целой и дробной части числа). Целочисленный формат (формат с фиксированной точкой) используется для представления в компьютере целых (англ. integer) положительных и отрицательных чисел. Для этого, как правило, используются форматы, кратные байту: 1, 2, 4 байта.
В форме с фиксированной запятой числа изображаются в виде последовательности цифр с постоянным для всех чисел положением запятой (или точки), отделяющей целую часть от дробной.
Эта форма проста и привычна для большинства пользователей, но имеет небольшой диапазон представления чисел и поэтому не всегда пригодна при вычислениях. Если же в результате какой-либо арифметической операции получается число, выходящее за допустимый диапазон, то происходит переполнение разрядной сетки, и все дальнейшие вычисления теряют смысл.
Однобайтовое представление применяется только для положительных целых чисел. В этом формате отсутствует знаковый разряд. Наибольшее двоичное число, которое может быть записано при помощи 1 байта, равно 11111111, что в десятичной системе счисления соответствует числу 25510.
Для положительных и отрицательных целых чисел обычно используется 2 и 4 байта, при этом старший бит выделяется под знак числа: 0 — плюс, 1 — минус. Самое большое (по модулю) целое число со знаком, которое может поместиться в
2-байтовом формате, это число 0111111111111111, то есть при помощи подобного кодирования можно представить числа от −32 76810 до 32 76710.
Обрати внимание!
Если число вышло за указанные границы, произойдет переполнение! Поэтому при работе с большими целыми числами под них выделяется больше места, например 4 байта.
Формат с плавающей точкой (нормализованная форма) используется для представления в компьютере действительных чисел (англ. real). Числа с плавающей точкой размещаются, как правило, в 4 или 8 байтах.
Нормализованная форма представления чисел обеспечивает огромный диапазон их записи и является основной в современных ЭВМ.
Представление целого положительного числа в компьютере
Для представления целого положительного числа в компьютере используется следующее правило: · число переводится в двоичную систему;
· результат дополняется нулями слева в пределах выбранного формата;
· последний разряд слева является знаковым, в положительном числе он равен 0.
Например, положительное число +13510 в зависимости от формата представления в компьютере будет иметь следующий вид:
· для формата в виде 1 байта — 10000111 (отсутствует знаковый разряд);
· для формата в виде 2 байтов — 0000000010000111;
· для формата в виде 4 байтов — 00000000000000000000000010000111.
Представление целого отрицательного числа в компьютере
Для представления целого отрицательного числа в компьютере используется дополнительный код. Такое представление позволяет заменить операцию вычитания числа операцией сложения с дополнительным кодом этого числа. Знаковый разряд целых отрицательных чисел всегда равен 1.
Для представления целого отрицательного числа в компьютере используется следующее правило:
· число без знака переводится в двоичную систему;
· результат дополняется нулями слева в пределах выбранного формата;
· полученное число переводится в обратный код (нули заменяются единицами, а единицы — нулями);
· к полученному коду прибавляется 1.
Обратный код для положительного двоичного числа совпадает с его прямым кодом, а для отрицательного числа нужно во всех разрядах, кроме знакового, нули заменить единицами и наоборот.
Дополнительный код для положительного числа совпадает с его прямым кодом, а для отрицательного числа образуется путем прибавления 1 к обратному коду.
Отрицательное число может быть представлено в виде 2 или 4 байт. Например, представим число −13510 в 2-байтовом формате:
· -13510 10000111 (перевод десятичного числа без знака в двоичный код);
· 0000000010000111(дополнение двоичного числа нулями слева в пределах формата);
· 0000000010000111 1111111101111000(перевод в обратный код);
· 1111111101111000 1111111101111001 (перевод в дополнительный код).
Представление вещественного (действительного) числа в компьютере
Вещественное число может быть представлено в экспоненциальном виде, например:
1600000010=0,16•108
−0,000015610=−0,156•10−4
В этом формате вещественное число (R) представляется в виде произведения мантиссы (m) и основания системы счисления (P) в целой степени (n), называемой порядком.
Представим это в общем виде, как: R=m•Pn.
Порядок n указывает, на какое количество позиций и в каком направлении должна сместиться в мантиссе точка (запятая), отделяющая дробную часть от целой. Мантисса, как правило, нормализуется, то есть представляется в виде правильной дроби 0 < m < 1.
Мантисса должна быть правильной дробью, у которой первая цифра после точки (запятой в обычной записи) отлична от нуля. Если это требование выполнено, то число называется нормализованным.
При представлении в компьютере действительного числа с плавающей точкой тоже используется нормализованная мантисса и целый порядок. И мантисса и порядок представляются в двоичном виде, как это было описано выше.
Для размещения вещественного числа обычно используется 2 или 4 байта. В 2-байтовом формате представления вещественного числа первый байт и три разряда второго байта выделяются для размещения мантиссы, в остальных разрядах второго байта размещаются порядок числа, знаки числа и порядка.
В 4-байтовом формате представления вещественного числа первые три байта выделяются для размещения мантиссы, в четвертом байте размещаются порядок числа, знаки числа и порядка.
Чем больше разрядов отводится под запись мантиссы, тем выше точность представления числа.
Пример записи числа 6,2510=110,012=0,11001•211, представленного в нормализованном виде, в четырёхбайтовом формате с семью разрядами для записи порядка.
| Синякина Г.Е. МММММММММММММММммухамедшиной. |
| Монтаж, наладка и эксплуатация САУ |
14. Логическое устройство.
Схема, график, таблица инстинности
