Использование метода для получения минимальной КНФ

Для получения Минимальной Конъюнктивной Нормальной Формы (МКНФ), используя метод Куайна, вводятся слудующие критерии:

· для минимизации берётся не СДНФ, а СКНФ функции;

· склеиваемые пары членов меняются на: или ;

· правило операции поглощения выглядит следующим образом:

Изм.

Лист

№ докум.

Подпись

Дата

Лист

КР 15.02.07 09 00 00 ПЗ

Разраб.

Синякина Г.Е. МММММММММММММММммухамедшиной.

Провер.

Тулинцева Л.Н.

Реценз.

Н. Контр.

Утверд.

Монтаж, наладка и эксплуатация САУ

Лит.

Листов

СПбГЭУПТ 332-з

12. Функции алгебры логики

Радиоэлектроника в настоящее время во многом определяет научно- технический прогресс и объединяет ряд отдельных областей науки и техники, развившихся из радиотехники и электроники.
Радиотехника - область науки и техники, связанная с разработкой устройств и систем, обеспечивающих генерирование, усиление, преобразование, хранение, а также излучение и прием электромагнитных колебаний радиочастотного диапазона, используемых для передачи информации.
В современных радиотехнических системах и комплексах до 90% разрабатываемых устройств реализуется на элементах цифровой и вычислительной техники и используются цифровые методы обработки сигналов.
В настоящее время бурно развивается по экспоненциальному закону вычислительная техника и ее элементная база. А не так давно первые интегральные микросхемы (1958 год) содержали до десяти транзисторов. Сегодня современные микропроцессоры содержат до 10 миллионов транзисторов на один кристалл, и менее чем через десять лет это число достигнет 100 миллионов транзисторов.
Уже отошла в историю дискретная схемотехника, когда различные узлы строились на печатных платах с использованием отдельных навесных радиоэлектронных компонентов: транзисторов, резисторов, конденсаторов и других элементов. Ранее соединения выполнялись с помощью внешнего печатного монтажа, теперь соединения и монтаж осуществляется внутри кристалла. Поэтому современный инженер электронной техники должен владеть передовыми методами и технологиями, чтобы уметь приспособить их завтра к вычислительной технике будущих поколений, овладеть практическими приемами проектирования устройств на программируемых логических интегральных схемах.
Логические выражения n двоичных переменных с помощью конечного числа логических операций можно рассматривать как некоторую функцию, отражающую взаимную связь между входными и выходными переменными. Логические операции конъюнкции и дизъюнкции можно представить простейшими функциями вида: и . Эти функции называются аналогично логическим операциям – функциями И и ИЛИ.
Такие ФАЛ подобно логическим выражениям могут быть заданы аналитическим и табличным способами.
При аналитическом способе ФАЛ задается в виде логических выражений, получаемых путем логических преобразований с помощью законов и правил Булевой алгебры.
При табличном способе ФАЛ задается таблицей истинности, где число всех возможных наборов (комбинаций) аргументов конечно. Если число аргументов ФАЛ равно n, то число их возможных наборов , а число различных функций , тогда при n=2, F=16. Составим таблицу истинности для функций двух аргументов.

Изм.

Лист

№ докум.

Подпись

Дата

Лист

КР 15.02.07 09 00 00 ПЗ

Таблица 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

Изм.

Лист

№ докум.

Подпись

Дата

Лист

КР 15.02.07 09 00 00 ПЗ

В таблице 2 часто применяемыми являются функции:

-повторители 1-го и 2-го аргументов;

– инверсии 1-го и 2-го аргументов;

– функция И (конъюнкция), логическое умножение;

– функция И-НЕ (базис Шеффера);

– функция ИЛИ (дизъюнкция), логическое сложение;

– функция ИЛИ-НЕ (базис Пирса);

– функция неравнозначности, реализуется ЛЭ “Исключающее ИЛИ” (сумматор по модулю два);

– функция равнозначности реализуется ЛЭ “Исключающее ИЛИ-НЕ”.
Рассмотренные элементарные функции двух аргументов

играют важную роль при преобразованиях сложных логических выражений, а также при преобразовании функциональных цифровых узлов.
Функции n переменных, значения которых заданы во всех точках области определения, считаются полностью определенными ФАЛ. Если какая-либо функция имеет запрещенные наборы переменных и ее значения на указанных наборах не определены, то такая ФАЛ называется не полностью определенной. Такие наборы будем отмечать в таблицах истинности (*) и при необходимости доопределять их значениями 0 и 1. Эти вопросы будут рассматриваться позже.
Логические функции, которые считаются полностью определенными, могут быть представлены различными формами.
ДНФ – дизъюнктивная нормальная форма записи ФАЛ представляется в виде суммы (дизъюнкции) ряда элементарных членов (минтермов), каждый из которых является произведением (конъюнкцией) аргументов или их инверсий. Термин “нормальная форма” предполагает, что в логическом выражении, задающем функцию, последовательно выполняются не более двух базовых операций (кроме инверсии).
Запишем ФАЛ в ДНФ:

; (1)
Функцию (3.19) можно записать в виде дизъюнкции минтермов:

, где

- конъюнкции аргументов ФАЛ, называемые минтермами.
СДНФ – совершенная дизъюнктивная нормальная форма записи ФАЛ представляется в ДНФ, где в каждом элементарном члене (минтерме), имеющем одинаковую размерность, представлены все аргументы функции или их инверсии.
Запишем ФАЛ в СДНФ:

. (2)
Если записать ФАЛ в виде:

, (3)

Изм.

Лист

№ докум.

Подпись

Дата

Лист

КР 15.02.07 09 00 00 ПЗ

то форма представления данной функции не является СДНФ, так как второй минтерм не содержит аргумента

, а также не является ДНФ, так как третий минтерм

не является элементарным.
Функцию

можно упростить (минимизировать) и представить минимальной ДНФ (МДНФ).

(4)
Полученные элементарные члены МДНФ называются импликантами.
КНФ – конъюнктивная нормальная форма записи ФАЛ, представляется в виде произведения (конъюнкции) ряда элементарных членов (макстермов), которые являются суммой (дизъюнкцией) аргументов ФАЛ.
Запишем функцию

в КНФ:

. (5)
СКНФ – совершенная конъюнктивная нормальная форма записи ФАЛ представляется в КНФ, где в каждом элементарном члене (макстерме) представлены все аргументы функции либо их инверсии.
Запишем функцию

в СКНФ:

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

и запишем ее в СДНФ и СКНФ.

На наборах N(2,3), где функция принимает значения 1, записываем ФАЛ в СДНФ, а на наборах N(1,4) – в СКНФ. При записи ФАЛ в СДНФ аргументы x=0 записываются с инверсией

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

Изм.

Лист

№ докум.

Подпись

Дата

Лист

КР 15.02.07 09 00 00 ПЗ

Разраб.

Синякина Г.Е. МММММММММММММММммухамедшиной.

Провер.

Тулинцева Л.Н.

Реценз.

Н. Контр.

Утверд.

Монтаж, наладка и эксплуатация САУ

Лит.

Листов

СПбГЭУПТ 332-з

13. Представления чисел ЭВМ.
Кодирование информации в ЦВМ.

Для хранения чисел в памяти компьютера используется два формата: целочисленный (естественная форма) и с плавающей точкой (нормализованная форма) (точка — разделительный знак для целой и дробной части числа). Целочисленный формат (формат с фиксированной точкой) используется для представления в компьютере целых (англ. integer) положительных и отрицательных чисел. Для этого, как правило, используются форматы, кратные байту: 1, 2, 4 байта.

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

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

Однобайтовое представление применяется только для положительных целых чисел. В этом формате отсутствует знаковый разряд. Наибольшее двоичное число, которое может быть записано при помощи 1 байта, равно 11111111, что в десятичной системе счисления соответствует числу 255¹⁰.

Для положительных и отрицательных целых чисел обычно используется 2 и 4 байта, при этом старший бит выделяется под знак числа: 0 — плюс, 1 — минус. Самое большое (по модулю) целое число со знаком, которое может поместиться в
2-байтовом формате, это число 0111111111111111, то есть при помощи подобного кодирования можно представить числа от −32 768¹⁰ до 32 767¹⁰.

Обрати внимание!

Если число вышло за указанные границы, произойдет переполнение! Поэтому при работе с большими целыми числами под них выделяется больше места, например 4 байта.

Формат с плавающей точкой (нормализованная форма) используется для представления в компьютере действительных чисел (англ. real). Числа с плавающей точкой размещаются, как правило, в 4 или 8 байтах.

Нормализованная форма представления чисел обеспечивает огромный диапазон их записи и является основной в современных ЭВМ.

Представление целого положительного числа в компьютере

Изм.

Лист

№ докум.

Подпись

Дата

Лист

КР 15.02.07 09 00 00 ПЗ

Для представления целого положительного числа в компьютере используется следующее правило:

· число переводится в двоичную систему;

· результат дополняется нулями слева в пределах выбранного формата;

· последний разряд слева является знаковым, в положительном числе он равен 0.

Например, положительное число +135¹⁰ в зависимости от формата представления в компьютере будет иметь следующий вид:

· для формата в виде 1 байта — 10000111 (отсутствует знаковый разряд);

· для формата в виде 2 байтов — 0000000010000111;

· для формата в виде 4 байтов — 00000000000000000000000010000111.

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

Для представления целого отрицательного числа в компьютере используется дополнительный код. Такое представление позволяет заменить операцию вычитания числа операцией сложения с дополнительным кодом этого числа. Знаковый разряд целых отрицательных чисел всегда равен 1.

Для представления целого отрицательного числа в компьютере используется следующее правило:

· число без знака переводится в двоичную систему;

· результат дополняется нулями слева в пределах выбранного формата;

· полученное число переводится в обратный код (нули заменяются единицами, а единицы — нулями);

· к полученному коду прибавляется 1.

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

Дополнительный код для положительного числа совпадает с его прямым кодом, а для отрицательного числа образуется путем прибавления 1 к обратному коду.

Изм.

Лист

№ докум.

Подпись

Дата

Лист

КР 15.02.07 09 00 00 ПЗ

Отрицательное число может быть представлено в виде 2 или 4 байт.

Например, представим число −135¹⁰ в 2-байтовом формате:

· -13510 10000111 (перевод десятичного числа без знака в двоичный код);

· 0000000010000111(дополнение двоичного числа нулями слева в пределах формата);

· 0000000010000111 1111111101111000(перевод в обратный код);

· 1111111101111000 1111111101111001 (перевод в дополнительный код).

Представление вещественного (действительного) числа в компьютере

Вещественное число может быть представлено в экспоненциальном виде, например:

16000000¹⁰=0,16•10⁸

−0,0000156¹⁰=−0,156•10⁻⁴

В этом формате вещественное число (R) представляется в виде произведения мантиссы (m) и основания системы счисления (P) в целой степени (n), называемой порядком.

Представим это в общем виде, как: R=m•Pn.

Порядок n указывает, на какое количество позиций и в каком направлении должна сместиться в мантиссе точка (запятая), отделяющая дробную часть от целой. Мантисса, как правило, нормализуется, то есть представляется в виде правильной дроби 0 < m < 1.

Мантисса должна быть правильной дробью, у которой первая цифра после точки (запятой в обычной записи) отлична от нуля. Если это требование выполнено, то число называется нормализованным.

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

Изм.

Лист

№ докум.

Подпись

Дата

Лист

КР 15.02.07 09 00 00 ПЗ

Для размещения вещественного числа обычно используется 2 или 4 байта.

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

В 4-байтовом формате представления вещественного числа первые три байта выделяются для размещения мантиссы, в четвертом байте размещаются порядок числа, знаки числа и порядка.

Чем больше разрядов отводится под запись мантиссы, тем выше точность представления числа.

Пример записи числа 6,25¹⁰=110,01²=0,11001•2¹¹, представленного в нормализованном виде, в четырёхбайтовом формате с семью разрядами для записи порядка.

Изм.

Лист

№ докум.

Подпись

Дата

Лист

КР 15.02.07 09 00 00 ПЗ

Разраб.

Синякина Г.Е. МММММММММММММММммухамедшиной.

Провер.

Тулинцева Л.Н.

Реценз.

Н. Контр.

Утверд.

Монтаж, наладка и эксплуатация САУ

Лит.

Листов

СПбГЭУПТ 332-з

14. Логическое устройство.
Схема, график, таблица инстинности