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

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

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

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

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

y j=f(x 1, x 2,... x i,... x in), (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= x 1 x 2Ú x 1 x 2Ú x 1 x 2= x 1Ú x 2.

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

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

у 5= у 4= x 1Ú x 2= x 1× x 2

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

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

у 6 =x 1× x 2.

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

y7 = у 6= x 1× x 2= x 1Ú x 2

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

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

у 8= x 1× x 2Ú x 1× x 2

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

у 9= у 8 = x 1× x 2Ú x 1× x 2 =x 1× x 2Ú x 1× x 2

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

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

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

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

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

x v1=1 x Ù0=0  
x v x =l x Ù1 = x x vxv...v x=x
x v0= x х Ù x =0 x Ù x Ù...Ù x=x
x v x=x x Ù x= x  

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

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

x 1× x 2= x 2× x 1 x 1Ú x 2= x 2Ú x 1 ;

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

(x 1× x 2)× x 3=(x 1× x 3)× x 2 (x 1Ú x 2) Ú x 3 = x 1Ú (x 2Ú x 3);

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

x 1×(x 2Ú x 3)= x 1× x 2Ú x 1× x 3 x 1Ú x 2× x 3=(x 1Ú x 2)×(x 1Ú x 3).

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

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

x 1Ú x 1× x 2= x 1 x 1×(x 1Ú x 2)= x 1

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

x 1× x 2Ú x 1× x 2= x 1 (x 1Ú x 2) (x 1Ú x 2)= x 1,

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

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

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

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