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


 

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

41821. Браузер. Примеры работы с Интернет-магазином, Интернет СМИ, Интернет-библиотекой 500.57 KB
  Изучение функциональной структуры web-браузеров и уметь выполнять навигацию по гиперссылкам, открытие, просмотр и загрузку различных информационных ресурсов. Научиться оформлять заказы в Интернет-магазине. Изучить принцип работы Интернет-библиотеки и Интернет-СМИ.
41822. Инструмент Roughen Brush (Огрубление) 91.22 KB
  Инструмент Roughen Brush Огрубление позволяет превратить объект с гладким контуром в рваный с острыми зубцеобразными краями. Инструмент Roughen Brush Огрубление можно применять к фигурам представляющим собой кривую Безье. Если фигура не является кривой Безье то при попытке применить к ней инструмент Roughen Brush Огрубление программа предложит автоматически преобразовать объект в кривую Безье.
41823. Исследование особенностей и способов поиска правовой информации в СПС КОДЕКС 46.72 KB
  38 Кто руководит Конституционным судом Российской Федерации Найдите и вставьте в данный документ фотографию этого чиновника. Зорькин Валерий Дмитриевич Найдите координаты Центральной избирательной комиссии Российской Федерации.9 Сколько документов на сегодняшний день содержится в системе Сколько новых документов появилось в разделе международное право Всего 959376 В Международном праве 238 Сколько новостей в январе 2013 года...
41824. Программирование алгоритмов формирования и обработки двумерных массивов 79.24 KB
  Выполнения данной лабораторной работы состоит в изучении средств, приемов и получении практических навыков разработки, написания и отладки программ формирования и обработки двумерных массивов...
41825. Работа с данными в программе Microsoft Excel 277 KB
  Цель данной лабораторной работы - научиться создавать с помощью пакета Excel тип рабочей таблицы, соответствующий базе данных. А также научиться работать с данными таблицы Excel как с базой данных.
41826. Решение задачи аппроксимации исходных данных 47 KB
  В окне Algebra1 решаем исходное уравнение ( команда Solve→Expression), выбираем численные значение корней (Numerically) и, указывая ОИК, находим равенство: Проверить найденные значения корней.
41827. Система питания двигателя Зил-138 от газаоболонной установки 218.85 KB
  В цилиндрическом корпусе 24 редуктора размещены камера А первой ступени камера Б второй ступени и кольцеобразная камера В вакуумного разгружателя.Одна из стенок камеры первой ступени образована резиновой диафрагмой 5 края которой зажаты между корпусом редуктора и крышкой 4.В камере второй ступени находится зажатая по окружности между верхней частью корпуса и крышкой 36 диафрагма 37. Ее центральная часть соединена рычагом 29 с клапаном 9 второй ступени.
41828. Проведение исследования на основе готовой компьютерной модели 163.07 KB
  LINE х1 у1х2 у2 cоператор изображающий отрезок прямой х1 у1 начало отрезка х2 y2 конец отрезка c номер цвета. LINE х1 у1х2 у2 c B оператор изображающий прямоугольник со сторонами параллельными осями координат. LINE х1 у1х2 у2 c BF оператор изображающий закрашенный прямоугольник c номер цвета.146 6 Перемещение начала координат в центр экрана LINE 3.
41829. Работа с запросами в MS Access 117.5 KB
  Порядок выполнения задания Создание запросавыборки Создать запрос содержащий поля: Идент.Для этого необходимо выполнить следующую последовательность действий: При выбранной вкладке Запросы выполнить щелчок по кнопке . Открывается окно Новый запрос в котором выбрать режим создания запроса Конструктор затем ; Открывается окно Запрос1: запрос на выборку а затем активизируется окно Добавление таблицы в котором выбрать из списка таблиц таблицу Сотрудник щелчком мыши по имени таблицы а затем выполнить щелчок по кнопке после чего...