Для получения Минимальной Конъюнктивной Нормальной Формы (МКНФ), используя метод Куайна, вводятся слудующие критерии:
· для минимизации берётся не СДНФ, а СКНФ функции;
· склеиваемые пары членов меняются на:
или
;
· правило операции поглощения выглядит следующим образом:
![Использование метода для получения минимальной КНФ Использование метода для получения минимальной КНФ - student2.ru](/images/logika/ispolzovanie-metoda-dlya-polucheniya-minimalnoy-knf-358804-3.png)
Синякина Г.Е. МММММММММММММММммухамедшиной. |
Монтаж, наладка и эксплуатация САУ |
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 часто применяемыми являются функции:
![Использование метода для получения минимальной КНФ Использование метода для получения минимальной КНФ - student2.ru](/images/logika/ispolzovanie-metoda-dlya-polucheniya-minimalnoy-knf-358804-110.png)
-повторители 1-го и 2-го аргументов;
![Использование метода для получения минимальной КНФ Использование метода для получения минимальной КНФ - student2.ru](/images/logika/ispolzovanie-metoda-dlya-polucheniya-minimalnoy-knf-358804-111.png)
– инверсии 1-го и 2-го аргументов;
![Использование метода для получения минимальной КНФ Использование метода для получения минимальной КНФ - student2.ru](/images/logika/ispolzovanie-metoda-dlya-polucheniya-minimalnoy-knf-358804-112.png)
– функция И (конъюнкция), логическое умножение;
![Использование метода для получения минимальной КНФ Использование метода для получения минимальной КНФ - student2.ru](/images/logika/ispolzovanie-metoda-dlya-polucheniya-minimalnoy-knf-358804-113.png)
– функция И-НЕ (базис Шеффера);
![Использование метода для получения минимальной КНФ Использование метода для получения минимальной КНФ - student2.ru](/images/logika/ispolzovanie-metoda-dlya-polucheniya-minimalnoy-knf-358804-114.png)
– функция ИЛИ (дизъюнкция), логическое сложение;
![Использование метода для получения минимальной КНФ Использование метода для получения минимальной КНФ - student2.ru](/images/logika/ispolzovanie-metoda-dlya-polucheniya-minimalnoy-knf-358804-115.png)
– функция ИЛИ-НЕ (базис Пирса);
![Использование метода для получения минимальной КНФ Использование метода для получения минимальной КНФ - student2.ru](/images/logika/ispolzovanie-metoda-dlya-polucheniya-minimalnoy-knf-358804-116.png)
– функция неравнозначности, реализуется ЛЭ “Исключающее ИЛИ” (сумматор по модулю два);
![Использование метода для получения минимальной КНФ Использование метода для получения минимальной КНФ - student2.ru](/images/logika/ispolzovanie-metoda-dlya-polucheniya-minimalnoy-knf-358804-117.png)
– функция равнозначности реализуется ЛЭ “Исключающее ИЛИ-НЕ”.
Рассмотренные элементарные функции двух аргументов
![Использование метода для получения минимальной КНФ Использование метода для получения минимальной КНФ - student2.ru](/images/logika/ispolzovanie-metoda-dlya-polucheniya-minimalnoy-knf-358804-28.png)
играют важную роль при преобразованиях сложных логических выражений, а также при преобразовании функциональных цифровых узлов.
Функции n переменных, значения которых заданы во всех точках области определения, считаются полностью определенными ФАЛ. Если какая-либо функция имеет запрещенные наборы переменных и ее значения на указанных наборах не определены, то такая ФАЛ называется не полностью определенной. Такие наборы будем отмечать в таблицах истинности (*) и при необходимости доопределять их значениями 0 и 1. Эти вопросы будут рассматриваться позже.
Логические функции, которые считаются полностью определенными, могут быть представлены различными формами.
ДНФ – дизъюнктивная нормальная форма записи ФАЛ представляется в виде суммы (дизъюнкции) ряда элементарных членов (минтермов), каждый из которых является произведением (конъюнкцией) аргументов или их инверсий. Термин “нормальная форма” предполагает, что в логическом выражении, задающем функцию, последовательно выполняются не более двух базовых операций (кроме инверсии).
Запишем ФАЛ в ДНФ:
![Использование метода для получения минимальной КНФ Использование метода для получения минимальной КНФ - student2.ru](/images/logika/ispolzovanie-metoda-dlya-polucheniya-minimalnoy-knf-358804-119.png)
; (1)
Функцию (3.19) можно записать в виде дизъюнкции минтермов:
![Использование метода для получения минимальной КНФ Использование метода для получения минимальной КНФ - student2.ru](/images/logika/ispolzovanie-metoda-dlya-polucheniya-minimalnoy-knf-358804-120.png)
, где
![Использование метода для получения минимальной КНФ Использование метода для получения минимальной КНФ - student2.ru](/images/logika/ispolzovanie-metoda-dlya-polucheniya-minimalnoy-knf-358804-121.png)
- конъюнкции аргументов ФАЛ, называемые минтермами.
СДНФ – совершенная дизъюнктивная нормальная форма записи ФАЛ представляется в ДНФ, где в каждом элементарном члене (минтерме), имеющем одинаковую размерность, представлены все аргументы функции или их инверсии.
Запишем ФАЛ в СДНФ:
![Использование метода для получения минимальной КНФ Использование метода для получения минимальной КНФ - student2.ru](/images/logika/ispolzovanie-metoda-dlya-polucheniya-minimalnoy-knf-358804-122.png)
. (2)
Если записать ФАЛ в виде:
![Использование метода для получения минимальной КНФ Использование метода для получения минимальной КНФ - student2.ru](/images/logika/ispolzovanie-metoda-dlya-polucheniya-minimalnoy-knf-358804-123.png)
, (3)
то форма представления данной функции не является СДНФ, так как второй минтерм не содержит аргумента
![Использование метода для получения минимальной КНФ Использование метода для получения минимальной КНФ - student2.ru](/images/logika/ispolzovanie-metoda-dlya-polucheniya-minimalnoy-knf-358804-10.png)
, а также не является ДНФ, так как третий минтерм
![Использование метода для получения минимальной КНФ Использование метода для получения минимальной КНФ - student2.ru](/images/logika/ispolzovanie-metoda-dlya-polucheniya-minimalnoy-knf-358804-125.png)
не является элементарным.
Функцию
![Использование метода для получения минимальной КНФ Использование метода для получения минимальной КНФ - student2.ru](/images/logika/ispolzovanie-metoda-dlya-polucheniya-minimalnoy-knf-358804-126.png)
можно упростить (минимизировать) и представить минимальной ДНФ (МДНФ).
![Использование метода для получения минимальной КНФ Использование метода для получения минимальной КНФ - student2.ru](/images/logika/ispolzovanie-metoda-dlya-polucheniya-minimalnoy-knf-358804-127.png)
(4)
Полученные элементарные члены МДНФ называются импликантами.
КНФ – конъюнктивная нормальная форма записи ФАЛ, представляется в виде произведения (конъюнкции) ряда элементарных членов (макстермов), которые являются суммой (дизъюнкцией) аргументов ФАЛ.
Запишем функцию
![Использование метода для получения минимальной КНФ Использование метода для получения минимальной КНФ - student2.ru](/images/logika/ispolzovanie-metoda-dlya-polucheniya-minimalnoy-knf-358804-128.png)
в КНФ:
![Использование метода для получения минимальной КНФ Использование метода для получения минимальной КНФ - student2.ru](/images/logika/ispolzovanie-metoda-dlya-polucheniya-minimalnoy-knf-358804-129.png)
. (5)
СКНФ – совершенная конъюнктивная нормальная форма записи ФАЛ представляется в КНФ, где в каждом элементарном члене (макстерме) представлены все аргументы функции либо их инверсии.
Запишем функцию
![Использование метода для получения минимальной КНФ Использование метода для получения минимальной КНФ - student2.ru](/images/logika/ispolzovanie-metoda-dlya-polucheniya-minimalnoy-knf-358804-130.png)
в СКНФ:
![Использование метода для получения минимальной КНФ Использование метода для получения минимальной КНФ - student2.ru](/images/logika/ispolzovanie-metoda-dlya-polucheniya-minimalnoy-knf-358804-131.png)
. (6)
По функциям, представленным в СДНФ и СКНФ, можно построить таблицу истинности и наоборот – по таблице истинности можно записать ФАЛ в СДНФ и СКНФ.
На основании общей табл. 1 составим таблицу истинности функции неравнозначности
![Использование метода для получения минимальной КНФ Использование метода для получения минимальной КНФ - student2.ru](/images/logika/ispolzovanie-metoda-dlya-polucheniya-minimalnoy-knf-358804-132.png)
и запишем ее в СДНФ и СКНФ.
На наборах N(2,3), где функция принимает значения 1, записываем ФАЛ в СДНФ, а на наборах N(1,4) – в СКНФ. При записи ФАЛ в СДНФ аргументы x=0 записываются с инверсией
![Использование метода для получения минимальной КНФ Использование метода для получения минимальной КНФ - student2.ru](/images/logika/ispolzovanie-metoda-dlya-polucheniya-minimalnoy-knf-358804-134.png)
, а в СКНФ – без инверсии.
При записи функции в СДНФ по таблице истинности необходимо записать столько дизъюнктивных членов (минтермов), представляющих собой конъюнкции всех аргументов, сколько единиц содержит функция в таблице. Минтермы соединяются знаком логического суммирования.
Если в наборе значение аргумента равно нулю, то в конъюнкцию входит инверсия данного аргумента.
При записи ФАЛ в СКНФ необходимо записать столько конъюнктивных членов (макстермов), сколько нулей содержит функция. Макстермы (конъюнкции аргументов) соединяются знаком логического умножения. Если в наборе значение аргумента равно нулю, то в дизъюнкцию входит аргумент без инверсии.
Синякина Г.Е. МММММММММММММММммухамедшиной. |
Монтаж, наладка и эксплуатация САУ |
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. Логическое устройство.
Схема, график, таблица инстинности