4601

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

Контрольная

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

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

Русский

2012-11-23

163 KB

31 чел.

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

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

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


 

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

29604. СМК делятся на СМИ, слухи и наружную рекламу 18.05 KB
  СМК делятся на СМИ слухи и наружную рекламу 1. Слухи оказывают большое влияние на формирование общественного мнения благодаря обсуждению в малых приватных группах без освещения в СМИ. СМИ являются основным видом массовых коммуникаций т. СМИ безличные средства доставки информации потребителю.
29605. Функции СМК в массовом обществе. Характеристики СМК как основного рекламоносителя 16.67 KB
  Функции СМК в массовом обществе. Характеристики СМК как основного рекламоносителя Деятельность СМК организуется и управляется специальными учреждениями редакциями теле и радиокомпаниями и др. СМК выступает в двуединой роли: как институт участвующий в процессе формирования целей развития общества обеспечивая его стабильность и как механизм их актуализации. Массмедиа служат неотъемлемой составной частью механизма осуществления роли СМК в жизни социума.
29606. Механизмы осуществления роли СМК в жизни социума. Деятельность СМК как реализация интересов разных социальных субъектов 13.38 KB
  Деятельность СМК как реализация интересов разных социальных субъектов. Деятельность СМК организуется и управляется специальными учреждениями редакциями теле и радиокомпаниями и др. СМК выступает в двуединой роли: как институт участвующий в процессе формирования целей развития общества обеспечивая его стабильность и как механизм их актуализации.
29607. Специфика функций СМК как следствие различных выразительных средств 14.88 KB
  Систематизация выразительных средств Выразительные средства СМК являются носителями информационного сообщения содержания. Количество выразительных средств применяемых на практике непрерывно возрастает. Выбор выразительных средств осуществляется с учетом цели сообщения то есть основное внимание уделяется содержанию послания однако его форма то есть средство выражения играет важную роль.
29608. Мифология в коммуникации. СМИ как субъект смыслопостроения 14.72 KB
  Карлова: Мы внутри мифа. 2 природы: иллюзорность для наблюдателя извне это мир абсурда и реальность для носителя мифа. У мифа есть жизненные этапы от рождения до смерти. открытие мифа 2.
29609. Внушение и манипуляция: технологии и методики применения в деятельности средств массовой информации 21.31 KB
  Внушение это метод психологического воздействия на сознание личности или группы людей основанный на некритическом и часто неосознанном восприятии информации. При внушении сначала происходит восприятие информации содержащей готовые выводы а затем на ее основе формируются мотивы и установки определенного поведения. В процессе внушения интеллектуальная аналитикосинтезирующая активность сознания либо отсутствует либо она значительно ослаблена а восприятие информации настроений чувств шаблонов поведения базируется на механизмах...
29610. Место архетипов, стереотипов, установок в механизме осуществления функций СМК 18.84 KB
  Стереотип относиться к докоммуникативной стадии. Стереотипустоявшееся отношение к происходящим событиям выработанное на основе сравнения их с внутренними идеалами Стереотип от греч. Стереотип нечто повторяемое в неизменном виде; шаблон действия поведения и пр.
29611. Политическая коммуникация 17.42 KB
  ; коммуникация с помощью организаций в частности политических партий которые служат связующим звеном между управляющими и управляемыми и групп давления; коммуникация с помощью неформальных контактов. Политическая реклама находится на стыке самых разнообразных дисциплин она вбирает в себя знания из сферы политических наук политологии политической философии социологии психологии и др. Пушкарева определяет четыре основных канала политической коммуникации: официальный который регулирует движение информационных потоков от...
29612. Средства массовой информации как основной вид массовой коммуникации. Понятие, сущность, структура СМИ. Тенденции развития 15.13 KB
  Понятие сущность структура СМИ. СМИ система творческих и технических структур взаимодействующих между собой и с другими социальными системами в целях формирования и передачи потока информации действующая в сфере массовой коммуникации актуализирующая и формирующая представления об окружающем мире в современном общественном сознании. Функции СМИ: информир воспитательная развлекательная интеграция общества и его саморегуляция Просветительская распростронение культуры обрзовывающая презентационная формирование общ мнения соц....