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


 

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

82994. Незвичайний урок малювання 60.5 KB
  Мета: закріпити правила поведінки і безпеки життєдіяльності в комп’ютерному класі. Ознайомити учнів з інтерфейсом графічного редактора «Tux Paint», навчити користуватися інструментами і палітрою кольорів. Розвивати увагу, пам’ять, творчі здібності. Формувати інформаційну, самоосвітню...
82995. Як зимують птахи взимку? Подорож на ялинку до звірят. Створення аплікації зі рваних різнокольорових серветок 160 KB
  Мета. Продовжувати вчити встановлювати взаємозв’язки між змінами в неживій природі, житті рослин та тварин;розвивати уяву, мислення, пізнавальний інтерес; розширити, узагальнити знання про зимуючих птахів та звірів; розкрити особливість життя птахів та звірів узимку та залежність їх життя...
82996. «Колядники». Колядки. Щедрівки 72 KB
  Розширити знання дітей з української обрядовості, показати, як святкували Різдво, про народні традиції колядування, щедрування; навчати спостерігати, як у віршованих творах зображено святкування традиційних свят українського народу. Викликати в учнів інтерес до традицій українського народу у відзначенні свята Різдво.
82997. Світ звуків і фарб 1.71 MB
  Пачкуля та Чистюля; костюм Оле Лукойє 7 костюмів гномів різних кольорів; кошик із яблуками; малюнок Пачкулі; два набори шапочок усіх барв веселки; конверт для Білосніжки; книжки із зображенням гномів; баночки з водою альбомні аркуши фарби кисточки серветки палітри; відеозапис м-ф Білосніжка і сім гномів проектор.
82998. Гроші в житті людини 742 KB
  Мета: сформувати уявлення в учнів про такі поняття як гроші та багатство, вчити правильно визначати життєві цінності, обирати правильну життєву позицію, розвивати навички правильного користування здобутою інформацією. Задачі: дати визначення поняття грошей та багатства; дати порівняльну характеристику...
82999. Казка – дитяча опера «Коза Дереза» муз. М. Лисенко, Дніпрова Чайка. Омоніми – слова однакові за написанням, різні за значенням 492.5 KB
  Формування поняття про багатозначність слів в українській мові, виробляти вміння правильно вживати багатозначні слова в мовленні; розширювати уявлення про значення слів; збагачувати словниковий запас, розвивати монологічне та діалогічне мовлення, мислення, самостійність...
83000. ЇЖА, КОРИСНА ДЛЯ ЗДОРОВ’Я 661.5 KB
  Мета: Розширити уявлення дітей про їжу корисну для здоровя вчити їх правильно харчуватися виховувати естетичні смаки щодо зовнішнього вигляду страв. Обладнання: Малюнки ілюстрації таблиці слайди до теми предметні малюнки із зображенням продуктів для гри Смачного...
83001. Как животные готовятся к зиме? 107.5 KB
  Цель: Продолжать формировать представления о птицах и зверях, устанавливать взаимосвязь между изменениями в неживой природе, жизни растений и животных; развивать логическое мышление; воспитывать желание беречь родную природу. Оборудование: таблицы, рисунки с изображением птиц и зверей зимой, образцы.
83002. Резание бумаги и картона. Изготовление раздаточного материала для дидактической игры «Рыбалка» 254.5 KB
  Цель: формировать умение резать бумагу прямыми и закругленными линиями; совершенствовать умение вырезать фигуры по шаблону; развивать пространственные навыки воображение фантазию; воспитывать аккуратность. Обвести и вырезать по шаблону верхний нижний плавник.