4601

Основы булевой алгебры. Построение комбинационных схем по структурной формуле на однотипных базовых элементах

Контрольная

Математика и математический анализ

Основы булевой алгебры Для описания работы схем вычислительной техники и автоматики используют булеву алгебру. Булевой функцией называют функцию f(x1, x2, х3,…, xn), аргументы которой x1, x1, x2, xn и сама функция принимают значение 0 или 1. Табл...

Русский

2012-11-23

163 KB

27 чел.

Основы булевой алгебры

Для описания работы схем вычислительной техники и автоматики используют булеву алгебру.

Булевой функцией называют функцию f(x1, x2, х3,…, xn), аргументы которой x1, x1, x2, …, xn и сама функция принимают значение 0 или 1.

Таблицу, показывающую, какие значения принимает булева функция при всех сочетаниях значений её аргументов, называют таблицей истинности. Таблица истинности булевой функции n аргументов содержит 2n строк, n столбцов значений аргументов и 1 столбец значений функций. Например, таблицей 1 задана булева функция Y=f(x1, х2, х3) от трех переменных х1, x2, х3. Она содержит 23 = 8 строк и четыре столбца.

Таблица №1

X1

X2

X3

Y

0

0

1

1

1

1

0

0

1

0

0

0

0

0

1

1

0

1

1

1

1

1

1

1

1

0

0

0

0

0

1

1

Булеву функцию y=f(x1, x2), определенную таблицей истинности 2, называют логическим сложением или дизъюнкцией и обозначают символом, т. е. используют такую запись: у=x1x2. На основании таблицы 2 можно записать таблицу 3 логического сложения. Она отличается от обычного сложения только тем, что 1+1 принимают равным 1.

Булеву функцию y=f(x12), определенную таблицей истинности 4, называют логическим умножением или конъюнкцией и обозначают символом, т. е. используют запись у=х1х2. На основании таблицы истинности 4 можно записать таблицу 5 логического умножения. Она полностью совпадает с таблицей умножения для чисел 0, 1.

Логическое сложение обозначают также знаком «+», а логическое умножениезнаком «∙».

Булеву функцию у=f(x), определенную таблицей 6, называют отрицанием и обозначают её чертой, т. е. записывают у=.


Таблица №2       Таблица №3   Таблица №4       Таблица №5        Таблица №6

x1

x2

y

00=0

01=1

10=1

11=1

x1

x2

y

00=0

01=0

10=0

11=1

x

0

0

0

0

0

0

0

1

0

1

1

0

1

0

1

0

1

0

1

1

0

0

1

1

1

1

1

1

На основании таблиц логического сложения, умножения и отрицания можно записать:

а) 1+ x = 1,  в) x + =1,   д) ,  ж) ,

б) 0 + x = x,  г) x + = x,   е) ,  З) .

Для конъюнкции, дизъюнкции и отрицания справедливы следующие законы:

1) переместительный:

x1+ x2 = x2 + x1

2) сочетательный:

,

( x1+ x2) + x3 = x1+ (x2 + x3).

3) первый распределительный закон:

;

второй распределительный:

;

4) инверсный:

,

.

Любой из законов легко проверить путём составления таблиц истинности для обеих частей равенства. Например, проверим правильность закона . Составим таблицы №7 и №8.

Таблица №7      Таблица №8

x1

x2

x1

x2

0

0

0

1

0

0

1

1

1

0

1

0

1

0

1

1

0

1

1

0

0

1

1

0

0

1

1

1

1

1

0

1

1

0

0

0

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

Структурная формула

Булево выражение y=f(x1, х2, ...,xn) можно рассмотреть как структурную формулу, определяющую структуру логического устройства, цепь которого состоит из элементов И, ИЛИ, НЕ.

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

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

1. Число конъюнкций равно числу строк таблицы истинности, в которых функция равна 1 ( y=1).

2. Знак инверсии ставится над переменными, которые в соответствующих строках равны 0.

Например, для таблицы 1 СДНФ булевой функции будет содержать четыре конъюнкции, соединенные между собой логическим сложением:

Таблица №1

x3

x2

x1

y

0

0

0

0

0

0

1

0

0

1

0

0

0

1

1

1

1

0

0

1

1

0

1

0

1

1

0

1

1

1

1

1

СКНФ представляет собой конъюнкцию нескольких дизъюнкций, каждая из которых содержит все переменные или их отрицания. СКНФ булевой функции на основании таблицы истинности записывается следующим образом:

1. Число дизъюнкций равно числу строк таблицы истинности, в которых функция равна 0 == 0).

2. Над теми переменными, которые в соответствующих строках равны 1, ставят знак инверсии.

Например, для таблицы 1 СКНФ булевой функции будет содержать четыре дизъюнкции соединенные между собой логическим умножением:

y =()()()()

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

y=

=

=

==.

Построение комбинационных схем по структурной формуле на однотипных базовых элементах

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

Рис. 1

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

Рисунок 2


 

А также другие работы, которые могут Вас заинтересовать

44889. «Гнездо» Аксаковых. Творческий путь С.Т. Аксакова, место и значение его творчества в истории русской литературы 29 KB
  Гнездо Аксаковых. Аксакова место и значение его творчества в истории русской литературы. Аксаков Сергей Тимофеевич 17911859 его сыновья: Константин 18171860 Иван 18231886. Аксаков родился в Уфе в старинной дворянской семье отец чиновник мать дочь наместника.
44890. Новое время. Европа в начале нового времени 14.19 KB
  Новое время неразрывно связывается с утверждением €œбуржуазным индустриальным прогрессомâ€. В последнее время многие историки склоняются к мнению что нельзя искусственно отрывать от буржуазной цивилизации такие явления как великие географические открытия реформация и гуманизм научная революция которые дали толчок к зарождению буржуазии.: ранее новое время когда капитализм только зарождался и существовал в виде одного из укладов жизни.
44891. Методика формирования и развития системы понятий о химическом элементе 23.19 KB
  Цель изучения химических производств показать учащимся как достижения науки используются для практических нужд отразить роль науки как движущей силы производства и прогресса. Изучение химических производств позволяет существенно усилить экологическую сторону обучения химии раскрыть возможность реализации и требований экологической безопасности при грамотной организации производства что является важной воспитательной задачей курса химии средней школы. Структура системы понятий об основах химического производства. На этом основании можно...
44893. Понятие ОМ. Общественное мнение и паблицитный капитал как результаты PR-деятельности 20.26 KB
  Общественное мнение и паблицитный капитал как результаты PRдеятельности Общественное мнение - это специфическое проявление общественного сознания выражающееся в оценках как в устной так и в письменной форме и характеризующее явное отношение групп общественности к актуальным проблемам действительности представляющим общественный интерес. Для PRдеятельности Общественное мнение его преобразование изменение в нужном для субъекта PR направлении это объект и продукт PRдеятельности. Программы деятельности субъектов PR...
44894. Travelling. Путешествие 15.03 KB
  It is аlwys interesting to discover new things different wys of life to meet different people to try different food to listen to different musicl rhythms. Most trvellers nd holidymkers tke cmer with them nd tke pictures of everything tht interests them the sights of city old churches nd cstles views of mountins lkes vlleys plins wterflls forests different kinds of trees flowers nd plnts nimls nd birds.
44895. Трудная жизненная ситуация как категория социальной работы 23 KB
  Устоявшиеся нормативные стандарт трудныепротиворесчивые Признаки ТЖС:1 Неадекватность алгоритм. ЧеловекаТЖС ситуация соц.Факторы ТЖС: поведенческий экзистенциональный вероятностнопрогностическийСтруктура ТЖС:участники связан. Классификация ТЖС: по харкам субъектаиндивидуал.
44896. Синтаксические нормы 15.33 KB
  Благодаря преступной халатности водителя произошла эта авария Выбор падежной формы при гл. Выбор предлога. Выбор падежа при глаголе с отрицанием.
44897. Поняття культури мови. Комунікативні якості культури мови 25.5 KB
  Поняття культури мови. Комунікативні якості культури мови. Культура мови ознака літературної мови параметр за яким встановлюються авторитетні загальновизнані стандарти реалізовані в нормах писемного й усного спілкування. З культурою мови насамперед пов'язують уміння правильно говорити й писати дотримуватися всіх норм літературної мови.