Студопедия
Случайная страница | ТОМ-1 | ТОМ-2 | ТОМ-3
АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатика
ИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханика
ОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторика
СоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансы
ХимияЧерчениеЭкологияЭкономикаЭлектроника

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

Читайте также:
  1. I. КРАТКИЕ СВЕДЕНИЯ ИЗ ТЕОРИИ
  2. I. ОБЩИЕ СВЕДЕНИЯ
  3. I. Общие сведения
  4. I. Общие сведения о пациенте с травмой, ранением или хирургическим заболеванием
  5. I. Основные сведения
  6. I. Основные сведения
  7. I.1.Общие сведения

Теоретической основой построения ЭВМ являются специальные мате­матические дисциплины. Одной из них является алгебра логика или булева алгебра (Дж. Буль - английский математик прошлого столетия, основопо­ложник этой дисциплины). Ее аппарат широко используют для описания схем ЭВМ, их оптимизации и проектирования. Вся информация в ЭВМ представляется в двоичной системе счисления. Поставим в соответствие входным сигналам отдельных устройств ЭВМ соответствующие значения хi (i=1¸n), а выходным сигналам - значения функций yj (j=1¸m) (рис.8.1).

В этом случае зависимостями

yj=f(x1,x2,...xi,...xin) , (8.1)

где хi i-й вход; п - число входов; уj - j-й выход; т - число выходов в устройстве, можно описывать алгоритм работы любого устройства ЭВМ. Каждая такая зависимость уj называется «булевой» или логической функцией, у которой число возможных состояний и каждой ее независимой переменной равно двум, т.е. функцией алгебры логики, а ее аргументы определены на мно­жестве {0,1}. Алгебра логика устанавливает основные законы формирова­ния и преобразования логических функций. Она позволяет представить лю­бую сложную функцию в виде композиции простейших функций. Рассмотрим некоторые из них.

Известно, что количество всевозможных функций N от п аргументов вы­ражается зависимостью

(8.2)

При п=о можно определить две основные функции (N=2), не зависящие от каких-либо переменных: у0, тождественно равную нулю (у0º0), и у1, тож­дественно равную единице (у1º0). При п=1 зависимость (8.2) дает N=4. Представим зависимость значений этих функций от значения аргументах в виде таблицы.

В этой таблице, как и ранее, у0º0 и у1º0. Функция у2, а функция у3 (инверсия х).

Этим функциям соответствуют определенные технические аналоги. Схема, реализующая зависимость у2, называется повторителем, а схема у3=х - инвертором.

При п=2, N=16, т.е. от двух переменных можно построить шестнадцать различных функций. В табл. 8.1 представлена часть из них, имеющая фунда­ментальное значение при построении основных схем ЭВМ.

Таблица 8.1. Таблица функций от двух переменных

X1X2 Y0 Y1 Y2 Y3 Y4 Y5 Y6 Y7 Y8 Y9   Y15
0 0    
0 1 .... ....
1 0    
1 1    

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



Функция у4 представляет собой функцию логического сложения, дизъ­юнкцию. Она принимает значение единицы, если значение единицы имеет хотя бы одна переменная х1 или х2 :

у4=x1x2Úx1x2Úx1x2=x1Úx2 .

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

Функция у5 является инверсной функцией по отношению к у4:

у5=у4=x1Úx2= x1×x2

Она имеет название «отрицание дизъюнкции». Иногда в литературе встре­чается ее специальное название «стрелка Пирса», по фамилии математика, исследовавшего ее свойства.

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

у6=x1×x2 .

Функция y7 является инверсной функцией по отношению к у6 :

Загрузка...

y7=у6=x1×x2=x1Úx2

Она называется «отрицание конъюнкции» или « штрих Шеффера».

Функция у8 называется логической равнозначностью, она принимает зна­чение единицы, если все ее переменные имеют одинаковое значение (или 0 или 1):

у8= x1×x2Úx1×x2

Функция у9 является инверсной по отношению к у8 :

у9= у8= x1×x2Úx1×x2=x1×x2Úx1×x2

Она принимает значение единицы, если ее переменные имеют противо­положные значения.

Из перечисленных функций двух переменных можно строить сколь угод­но сложные зависимости, отражающие алгоритмы преобразования информа­ции, представленной в двоичной системе счисления. Алгебра логики устанавливает правила формирования логически полного базиса простейших функций, из которых могут строиться любые более сложные. Наиболее привычным базисом является набор трех функций {инверсия - é, дизъюнкция -Ú, конъюнкция - Ù или &}. Работа с функциями, представленными в этом базисе, очень похожа на использование операций обычной алгебры.

Алгебра логики устанавливает, что существуют и другие комбинации простейших логических функций, обладающих свойством логической полно­ты. Например, наборы логических функций {инверсия, дизъюнкция} и {ин­версия, конъюнкция} также являются логически полными. Наиболее инте­ресны минимальные базисы, включающие по одной операции {«отрицание дизъюнкции (Ú )»} и {«отрицание конъюнкции (Ù )»}. Однако работа с функ­циями, представленными в указанных базисах, требует от специалистов по проектированию ЭВМ определенных навыков.

8.2. Законы алгебры логики

Из определения вышеприведенных функций можно установить целый ряд простейших свойств:

xv1=1 xÙ0=0
xvx=l xÙ1= x xvxv ...vx=x
xv0=x хÙx=0 xÙxÙ...Ùx=x
xvx=x xÙx= x

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

коммутативный (переместительный)

x1×x2=x2×x1 x1Úx2=x2Úx1 ;

ассоциативный (сочетательный)

(x1×x2x3=(x1×x3x2 (x1Úx2) Úx3 = x1Ú (x2Úx3);

дистрибутивный (распределительный)

x1×(x2Úx3)=x1×x2Ú x1×x3 x1Úx2×x3=(x1Úx2)×(x1Úx3) .

Эти законы полностью идентичны законам обычной алгебры.

Закон поглощения. В дизъюнктивной форме ЛФ конъюнкция меньшего ранга, т.е. с меньшим числом переменных, поглощает все конъюнкции боль­шего ранга, если ее изображение содержится в них. Это же справедливо и для конъюнктивных форм:

x1Úx1×x2= x1 x1×(x1Úx2)=x1

Законы склеивания.

x1×x2Úx1×x2= x1 (x1Úx2) (x1Úx2)= x1,

FxÚFx=F (xÚF) (xÚF)= F,

где F - логическая функция общего вида, не зависящая от переменной x.


Дата добавления: 2015-07-08; просмотров: 124 | Нарушение авторских прав


Читайте в этой же книге: Способы представления и передачи двоичных чисел в ЭВМ | Анализ и синтез комбинационных схем | Неправильные тетрады |
<== предыдущая страница | следующая страница ==>
Конкурс эскизов| Понятие о минимизации логических функций

mybiblioteka.su - 2015-2021 год. (0.012 сек.)