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


 

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

30314. Понятие о словосочетании. Разное понимание словосочетания в современной лингвистике. Типология словосочетаний 35 KB
  Непредикативное Интонационно не оформленное Коммуникационно не законченное ССЧ являясь синтаксической едцой может быть описано в 3х аспектах: Формальный Содержательный Коммуникативный Ссч строится по определенной структурной схеме. Ссч обладает смысловой устроенностью. ГЗ ссч это выраженные синтаксической связью синтаксические отношения между его компонентами рассматриваемые вне конкретного лексического наполнения. Ссч выполняет строительную функцию для предложения употребляется в качестве названия или заголовка составной...
30315. Предложение как синтаксическая единица. Его признаки и свойства. Понятие структурной схемы и парадигмы предложения 35.5 KB
  Понятие структурной схемы и парадигмы предложения. Универсальный признак предложения предикативность вслед за Шахматовым и Пешковским сформулировал Виноградов соотнесенность содержания предложения с действительностью. Существует широкое предикативность присуща всем предложениям и узкое понимание только те предложения в которых есть предикат предикативности. Универсальное свойство предложения позволяющее совокупности словоформ стать предложением интонационная оформленность.
30316. Понятие семантической структуры предложения, ее соотношение с формальной структурой 46 KB
  Эти отношения выражает предикат который организует положение дел и задаёт определённые места для предметов участников ситуации актантов определяя их количество и роли. Актанты это предметные распространители предиката актант субъектного типа актант объектного типа орудийный актант и т. В структуре пропозиции имеются также непредметные распространители предиката сирконстанты локатив темпоратив и др. Таким образом каждая пропозиция являясь моделью ситуации имеет свою структуру вершиной которой выступает предикат.
30317. Основы описания простого предложения. Типы предложений 29 KB
  Основы описания простого предложения. коммуникативную задачу выражающуюся интонацией и порядком слов Актуальное членение предложения. структура; порядок слов и интонация; члены предложения как компоненты предикативной основы П. По характеру выражаемого в них отношения к действительности различаются предложения реальной и ирреальной модальности с разнообразными оттенками модальных значений: реальности и ирреальности предположения сомнения уверенности возможности невозможности и т.
30318. Современный русский литературный язык как предмет научного изучения. Русский язык в современном мире 45.5 KB
  Русский язык в современном мире. Русский язык в современном мире. Языки имеют национальные границы каждый из языков своеобразен.
30319. Понятие о стилях ЛЯ. Принципы их классификации 198.5 KB
  ЛИТЕРАТУРНЫЙ ЯЗЫК наддиалектная подсистема форма существования национального языка которая характеризуется такими чертами как нормативность кодифицированность полифункциональность стилистическая дифференцированность высокий социальный престиж в среде носителей данного национального языка. Литературный язык является основным средством обслуживающим коммуникативные потребности общества; он противопоставлен некодифицированным подсистемам национального языка территориальным диалектам городским койне городскому просторечию...
30320. Проблема нормативности литературной речи. Классификация речевых ошибок 53 KB
  Нормы: 1. Ожегов дал такое определение языковой нормы: Норма это совокупность наиболее пригодных для обслуживания общества средств языка складывающихся как результат отбора языковых элементов из числа сосуществующих наличествующих образуемых вновь или извлекаемых из пассивного запаса прошлого в процессе социальной в широком смысле оценки этих элементов. Искусственные нормы устанавливаются в результате нормотворческой деятельности языковедов путем подготовки и издания авторитетных словарей и справочников и даже законодательных актов ...