4601

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

Контрольная

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

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

Русский

2012-11-23

163 KB

30 чел.

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

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

Булевой функцией называют функцию 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


 

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

44052. Условия формирования культуры взаимоотношений у детей старшего дошкольного возраста в условиях детского клуба «Эрудит» 178.54 KB
  Границы старшего дошкольного возраста определяются исследователями как возраст 5 – 7 лет. Однако в то же время многие дети идут в школу с 6 лет, поэтому возраст 6 – 7 лет одновременно относят и к периоду младшего школьного возраста. Поскольку развитие детей происходит в индивидуальном темпе, мы будем ориентироваться на средние показатели, согласно которым период от 5 до 7 лет является периодом старшего дошкольного возраста.
44053. Повышение эффективности деятельности планово-экономического отдела предприятия ЗАО «Атлант» 1.52 MB
  Эконометрическое моделирование временных рядов. Моделирование объемов производства с использованием анализа временных рядов Построение модели объема выпуска продукции на основе временных рядов Программная поддержка эконометрического моделирования объема выпуска продукции.
44054. Расчет потребного количества оборудования 502 KB
  Определение трудоёмкости по видам оборудования производится по данным базового предприятия по согласованию с преподавателем и пропорционально трудоёмкости изготовления детали-представителя
44055. Изучение взаимодействия морского и железнодорожного транспорта на примере ОАО «Архангельский морской торговый порт» 566 KB
  Все это уменьшает пропускные и перевозочные возможности железных дорог ведет к росту порожнего пробега вагонов к снижению производительности их использования и к другим отрицательным последствием. [29] Перевозки грузов осуществляемые в смешанном сообщении с двумя перевалками в основном менее эффективны чем с одной и в прямом железнодорожном сообщении как по общей величине приведенных затрат так и по потребному парку вагонов и по затратам трудовых ресурсов. Навалочные и насыпные грузы отправляемые маршрутами или группами вагонов...
44056. Проект мероприятий по разработке нового турпродукта в Сысертском районе Свердловской области на примере ООО «УРАЛ ТУР» 398 KB
  Туризм экскурсии это важная форма отдыха людей ориентации их свободного времени тем более что состояние физического и нравственного здоровья вызывает серьезные опасения и требует использования всех возможных средств по исправлению сложившийся в последние годы ситуации. в стоимость тура должна быть включена хотя бы одна из перечисленных ниже услуг: трансфер экскурсии или аренда автомобиля.; памятки о сроках подачи заявок на авиабилеты проживание питание скидки на группу; заявка бронирования тура дата № заказа...
44057. Повышение социальной компетентности подростков 15-16 лет, выпускников детских домов, средствами социально-культурной деятельности 1.04 MB
  Теоретические основы формирования социальной компетентности подростков выпускников детских домов с помощью средств социально-культурной деятельности Сущность и определение социальной компетентности. Особенности процесса формирования социальной компетентности у подростков.
44058. Проектування дорожнього СТО-А 370 KB
  Автомобілі на станції технічного обслуговування СТО приймаються відповідно до встановлених правил. Значний ріст парку легкових автомобілів що належать населенню в Україні вимагає збільшення проектування дорожніх СТОА. Виробничотехнічну базу системи технічного обслуговування автомобілів в основному складають підприємства структурні одиниці трьох видів: СТОА у тому числі майстерні і пункти ТО і ремонту; бази і склади матеріальнотехнічного постачання; гаражі і стоянки автомобілів. Сучасні СТОА здійснюють: продаж і...
44059. Разработка бизнес-плана по производству кондитерских изделий ООО «Бансес» 251.5 KB
  Важнейшей задачей разработки бизнеспланов является проблема привлечения и обоснования инвестиций и кредитов в том числе зарубежных необходимых для осуществления проектов технического перевооружения и реконструкции предприятий. 1337580 руб. 5788080 руб. Общая стоимость проекта по производству кондитерских изделий 936671 руб.
44060. Психологізм творчості Михайла Коцюбинського 475 KB
  Зображення процесів внутрішнього життя героїв у дитячих оповіданнях письменника За обєкт дослідження обрано дитячу та малу прозу Михайла Коцюбинського Цвіт яблуні Сон Що записано в книгу життя В дорозі Дорогою ціною Дебют Лялечка Ft morgn Харитя Ялинка Маленький грішник Intermezzo як найпоказовішу з погляду психологічного зображення зрілості авторської концепції. Із метою ширшого обґрунтування останньої комплексного розгляду художнього психологізму залучено інформацію про особисте життя...