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

Размещено на http://www.allbest.ru/

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

Выбор системы счисления

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

Х_р = к_nрⁿ + к_n-1р^n-1 к_n-2р^n-2…+ к₀р⁰ (1)

здесь к_i = 0, …, р-1.

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

При выборе основания счисления требуется удовлетворить противоречивым условиям. С одной стороны число р следует взять большим, т.к. в этом случае количество слагаемых в (1) будет меньше. Однако в этом случае возрастает количество формирователей сигналов, а различие между соседними уровнями уменьшается, что затрудняет идентификацию сигналов и увеличивает вероятность ошибок. Оптимизация данной задачи при минимальных затратах и максимальной помехозащищенности дает ответ р=2,71. На практике в цифровой технике принята система счисления с основанием 2. Соответственно в (1) к принимает значения либо 0, либо1.

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

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

Над булевыми переменными возможны различные логические операции и функциональные преобразования.

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

Логическое отрицание или инверсия некоторой логической переменной, например переменной х, это также логическая переменная, принимающая значение обратное значению переменной х, и обозначаемая как х (далее в тексте х). Постулаты операции отрицания: если х=0, то х=1 и наоборот если х=1, то х=0.

Дизъюнкция (логическое сложение) или функция ИЛИ (OR) - это функция f(x1, x2), которая истинна тогда, когда истинна хотя бы одна из ее переменных. Постулаты операции сложения:

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

Конъюнкция (логическое умножение) или функция И (AND) - это функция f1(x1, x2), которая истинна тогда, когда все ее переменные одновременно истинны. Постулаты операции умножения:

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

булев алгебра логический цифровой

Таб.1

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

Способы записи ФАЛ

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

Зависимость выходных переменны у, выраженная через совокупность входных переменных х1,х2,…хn с помощью операций алгебры логики, носит название функции алгебры логики (ФАЛ). Понятие ФАЛ является базовым в алгебре логики. Для описания ФАЛ используются различные формы: словесная, табличная, алгебраическая, последовательность десятичных чисел и кубических комплексов.

Пример словесного описания для функции 3ИЛИ: логическая функция трех переменных равна единице, если одна из переменных равна единице.

Описание ФАЛ из предыдущего примера в виде таблицы истинности:

Таблица для описания функции n переменных содержит 2ⁿ строк. Соответственно функция n аргументов имеет 2ⁿ наборов переменных. Количество столбцов равно сумме чисел n+m. В данном случае (всего одна выходная переменная): 3+1=4 столбца.

Описание ФАЛ в виде последовательности десятичных чисел легко понять на примере. Возьмем за основу таблицу истинности предыдущего примера. Первое значение у=1 функция имеет на наборе 001. Переводят этот двоичный код в десятичный -1. Следующая единица: 010 2, и т.д. Полученная ФАЛ записывается в следующем виде:

у(х1,х2,х3) = (1,2,3,4,5,6,7).

На некоторых этапах разработки логических устройств удобно ФАЛ представлять координатным (графическим) способом. При небольшом количестве аргументов (n<6), наиболее распространенным из них является метод карт Карно. Карта Карно представляет собой двухкоординатную таблицу - несколько видоизмененную таблицу истинности. 2ⁿ наборов, представленных соседними клетками, отличаются значением только одной переменной.

Правила построения Карно сhttp://de.ifmo.ru/library/electron/ - импликанталедующие:

1)Количество клеток равно количеству строк таблицы истинности.

2)Слева и сверху располагаются значения аргументов. Порядок размещения аргументов таков, что в двух соседних по горизонтали и вертикали клетках отличается значение только одного аргумента (поэтому соседними считаются и клетки, находящиеся на противоположных краях таблицы).

3)В клетки заносятся соответствующие значения ЛФ.

На рис.3 приведена карта Карно для функции 3ИЛИ.

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

Различают две формы написания ФАЛ алгебраическим выражением ДНФ и КНФ.

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

у(х1,х2,х3) = х1х2+х1х3+х1х2х3

При проектировании устройств чаще имеют дело с совершенной дизъюнктивной нормальной формой (СДНФ). Получают СДНФ из таблиц истинности следующим образом:

- для каждого набора входных переменных на котором ФАЛ равна единице записывают конституенты единицы - элементарные конъюнкции, причем переменные, равные нулю, записывают с инверсией.

- логически суммируют полученные конституенты единицы.

Запись СДНФ для функции 3ИЛИ сделаем, воспользовавшись ее табличным представлением.

у(х1,х2,х3) = х1х2х3+х1х2х3+х1х2х3+х1х2х3+х1х2х3+х1х2х3+ х1х2х3

Вторая форма записи ФАЛ - это конъюнктивная нормальная форма (КНФ).

Конъюнктивной нормальной формой называется логическое произведение элементарных логических сумм, в каждую из которых аргумент или его инверсия входит один раз.

Аналогично, существует совершенная конъюнктивная нормальная форма (СКНФ).

Получают СКНФ из таблиц истинности следующим образом:

- для каждого набора входных переменных на котором ФАЛ равна нулю записывают конституенты нуля - элементарные логические суммы входных переменных, причем переменные, равные единице, записывают с инверсией. логически перемножают полученные конституенты нуля.

Запись СКНФ для функции 3ИЛИ сделаем, воспользовавшись ее табличным представлением.

у(х1,х2,х3) = х1+х2+х3.

Простейшие функции алгебры логики

Кроме приведенных выше трех элементарных логических функций практический интерес представляют еще 13. В таблице №2 приведены 16 простейших функций двух переменных х1 и х2.

Таб.2

Принцип двойственности

Рассмотрим таблицы истинности для функций И и ИЛИ. Нетрудно заметить, что таблицы легко взаимно трансформируются. Действительно, если параметры и функцию И инвертировать, а конъюнкцию заменить дизъюнкцией, получим определение функции ИЛИ.

Свойство взаимного преобразования постулатов конъюнкции и дизъюнкции называется принципом двойственности. Именно поэтому законы алгебра логики представлены в двух формах записи: конъюнктивной и дизъюнктивной. Принцип двойственности имеет большое практическое значение, сокращая до двух (И+НЕ или ИЛИ+НЕ) количество элементарных функций, необходимых для построения сложных логических выражений.

Логические функции и логические элементы

Вводя понятие логической функции в начале лекции (см.рис.1), мы представляли логическое устройство, реализующее эту функцию, в виде «черного ящика». В действительности устройство состоит из набора электронных схем, причем вид логической функции и состав набора схем связаны определенным образом. Аналогично тому, как сложное логическое выражение можно составить из элементарных функций, сложное логическое устройство можно представит в виде комбинации элементарных логических элементов (схем). Соответственно каждой элементарной ФАЛ можно сопоставить электронную схему (логический элемент - ЛЭ). В таблице №3 приведены некоторые простейшие ФАЛ и эквивалентные логические элементы.

Таб.№3.

Полная система логических функций. Понятие о базисе

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

В соответствии с принципом двойственности любое сложное устройство можно реализовать в двух базисах:

1) "И-НЕ" (базис Шеффера)

2) "ИЛИ-НЕ" (базис Пирса или функция Вебба).

Примеры реализации логических операций в базисах “И-НЕ” и “ИЛИ-НЕ”.

Рис.3.Реализация операции “НЕ”:

Для реализации функции И сделаем следующие преобразования:

у=х1х2 у=х1+х2 = х1х2. Откуда видно, как И можно реализовать в обоих базисах:

Рис.5.Реализация операции ИЛИ в базисе И-НЕ и ИЛИ-НЕ.

Пример реализации комбинационного устройства в базисе "И-НЕ". Пусть задана функция, реализуемая комбинационным устройством, в аналитической форме

F=x1x2+x3x4+x1x4

Используя закон де Моргана и с учетом закона двойного инвертирования, запишем эту функцию в виде

F= x1x2+x3x4+x1x4 = (x1x2)(x3x4)(x1x4)

Как следует из полученного аналитического выражения, логическое устройство должно содержать три двухвходовых и один трехвходовой элемент И-НЕ. Функциональная схема комбинационного устройства, построенная в базисе И-НЕ, показана на рис. 6.

Рис.6.

Размещено на Allbest.ru