вход Вход Регистрация



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

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

 

1.1 Булева алгебра

При проектировании логических схем и цифровых устройств в качестве математического аппарата применяется алгебра логики или булева алгебра, разработанная в середине ХІХ века ирландским математиком Джорджем Булем, далее развитие и применение получили в 1910 году П.С. Эренфеста и в 1938 году К. Шенноном.

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

Логической функцией называется функция вида F( x1, x2, ..., xп ), которая, как и ее аргументы x1, x2, ..., xn, может принимать только два значения – 0 или 1. Для любой логической функции от n переменных существует число N=2n различных наборов, и если на этих наборах функция определена, то такая функция называется полностью определенной. При этом число логических функций от n переменных (x1, x2, ..., xn) равно 2N= 22n.

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

Над переменными в алгебре логики можно производить три основных действия: логическое сложение (+, V) или операция ИЛИ (дизъюнкция), логическое умножение (&–энд, ·, ?) или операция И (конъюнкция) и логическое отрицание или операция НЕ (инверсия):

 

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

 

Основные законы алгебры логики:

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

1. Переместительный закон (закон коммутативности) для логического умножения и логического сложения: a·b = b·a; a+b = b+a.

2. Сочетательный закон (закон ассоциативности) для логического умножения и логического сложения: (a·b)·c = a·(b·c); (a+b)+c = a+(b+c).

3. Распределительный закон (дистрибутивный закон): a+b·c=(a+b)(a+c);

(b+c)·a=a·b+a·c;

a+b·c=(a·1+b·c)=a·(1+b+c)+b·c=a·a+a·b+a·c+b·c=a·(a+b)+c·(a+b)=

=(a+b)·(a+c).

4. Закон поглощения: a+a·b=a·(1+b)=a; a·(a+b)=a·a+a·b=a.

5. Закон склеивания: ; ; ; .

6. Закон отрицания (закон двойственности, закон де Моргана): ; ; - «стрелка Пирса» (функция «Вебба») ,

- «штрих Шеффера», .

7. Закон двойного отрицания: .

8. Закон умножения на 1 и 0 : a·1=a; a·0=0; a·a=a.

9. Закон сложения с 1 и 0: a+1=1; a+0=a; a+a=a.

10. Закон исключения и противоречия: ; .

11. Константы: ; .

12. Операция «Исключающее ИЛИ» (неравнозначность, сумма по

модулю 2): .

13. Операция сравнения (равнозначность, эквивалентность):

.

Законы 1 – 10 свидетельствуют о том, что алгебра логики обладает свойством двойственности (дуальности) относительно операций логического сложения и умножения. Двойственность определяется как изменение всех знаков операций И на знаки операций ИЛИ или всех знаков операций ИЛИ на знаки операций И.

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

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

Конституенты единицы и нуля - это комбинации переменных, при которых функция соответственно обращается в единицу или нуль.

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

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

Количество минтермов и макстермов заданного числа аргументов совпадает с числом различных наборов аргументов N = 2n.

 

Свойства минтермов и макстермов:

1. Между индексами і одноименных минтермов и макстермов булевых n переменных существуют следующие соотношения: , , где индекс i – десятичное число и соответствует двоичному коду, отвечающему комбинации значений аргументов функции.

2. Логическая сумма всех минтермов любого числа переменных равна единице, т.е..

3. Логическое произведение всех макстермов любого числа переменных равно нулю, т.е..

4. Логическое произведение минтермов, имеющих разные индексы, равно нулю, т.e. Qi·Qj=0, при i ? j.

5. Логическая сумма неодинаковых макстермов равна единице, т.е. Di+Dj=1, при i ? j.

Для построения СДНФ логической функции FCDHФ от n переменных, заданной таблицей истинности, необходимо по каждому набору переменных, на котором функция принимает значение 1, записать конъюнкцию – минтерм вида и все такие конъюнкции соединить знаками дизъюнкции. При этом переменные, имеющие значение нуля, инвертируются , , ,где i – десятичные числа, соответствующие тем наборам аргументов, на которых F=Fi=1.

Для построения СКНФ логической функции FCКHФ от n переменных, заданной таблицей истинности, необходимо по каждому набору переменных, на котором функция принимает значение 0, записать дизъюнкцию – макстерм вида и все такие дизъюнкции соединить знаками конъюнкции. При этом переменные, имеющие значение единицы, инвертируются: ,, где i – десятичные числа, соответствующие тем наборам аргументов, на которых F=Fi=0.

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

Логическая функция может быть упрощена непосредственно алгебраическим преобразованием с помощью законов алгебры логики (склеивания и поглощения). Но, как правило, такие преобразования требуют громоздких выкладок, а также знаний и навыков. Для функций, имеющих большое число переменных (больше трех) и большое число слагаемых, существуют специальные методы. Наиболее часто применяют методы с использованием карт Вейча и карт Карно, представляющим собой прямоугольную таблицу с числом клеток 2n. Каждой строке (столбцу) этой таблицы соответствует определенная комбинация аргументов (переменных), каждая клетка соответствует определенному набору значений аргументов так, что при всяком переходе из одной клетки в соседнюю вдоль строки или столбца изменяется значение лишь одного аргумента функции. Карты Карно отличаются от диаграмм Вейча порядком расположения аргументов, перечисляемых в циклическом коде (коде Грея) двоичных чисел.

 

Алгоритм минимизации логической функции состоит из следующих этапов:

1. Логическую функцию следует привести к СДНФ (СКНФ). Для этого необходимо воспользоваться законами алгебры логики 2, 3, 7-10, а в каждый из членов функции, в которых отсутствуют аргументы, ввести выражение вида и воспользоваться равенством для СДНФ (, для СКНФ), где i - отсутствующий в члене аргумент.

2. Заполнить минтермами (макстермами) прямоугольную таблицу, количество клеток которой равно числу возможных минтермов 2n. Минтермы логической функции отмечаются 1 в соответствующих клетках таблицы, а макстермы - 0. Два минтерма, находящиеся в соседних клетках, могут быть заменены одним логическим произведением, содержащим на одну переменную меньше, на основании законов дистрибутивности, склеивания и сложения (умножения) с 1 и 0. В общем случае наличие единиц (нулей) в 2К соседних клетках позволяет исключить К переменных.

3. В заполненной таблице обводят прямоугольными контурами все единицы (нули). При проведении контуров придерживаются следующих правил: контур должен быть прямоугольным; внутри контура должны быть только клетки, заполненные 1 (0); количество клеток находящихся внутри контура, должно быть целой степенью числа 2, т.е. 1, 2, 4, 8, 16; одни и те же клетки, заполненные 1 (0), могут входить в несколько контуров; самая нижняя и самая верхняя строки таблицы, а также самый левый и самый правый столбцы считаются соседними; контуров должно быть как можно меньше, а сами контуры - как можно большими.

4. Выражение минимальной ДНФ (МДНФ) функции записывается следующим образом. Каждый контур в МДНФ представляется членом, число переменных в котором на K меньше общего n – числа аргументов функции, т.е. равно n – К. Каждый член МДНФ составляет лишь из тех аргументов, которые для соответствующего контура являются общими, т.е. имеют значения без инверсии либо с инверсией. В общем случае функция может иметь несколько минимальных форм, которым соответствуют различные, но равноценные по числу членов МДНФ.

Например: Задана функция четырех переменных (аргументов)

В СДИФ

 

Наносим на карту Карно, произведем накрытие

Запишем результат накрытый в виде дезъюнкции конъюнкций (суммы произведений):

Функция до минимизации имела 16 наборов переменных, после четыре.

 

© 2018
  • Сайт "Литературка"
  • мы собираем различную техническую, образовательную, научную литратуру