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


 

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

28538. КРАТКИЕ СВЕДЕНИЯ О КРИПТОАНАЛИЗЕ 39.5 KB
  Нарушителю доступны все зашифрованные тексты. Нарушитель может иметь доступ к некоторым исходным текстам для которых известны соответствующие им зашифрованные тексты. Его применение осложнено тем что в реальных криптосистемах информация перед шифрованием подвергается сжатию превращая исходный текст в случайную последовательность символов или в случае гаммирования используются псевдослучайные последовательности большой длины. Дифференциальный или разностный криптоанализ – основан на анализе зависимости изменения шифрованного текста...
28539. Получение случайных чисел 45 KB
  Последовательности случайных чисел найденные алгоритмически на самом деле не являются случайными т. Однако при решении практических задач программно получаемую последовательность часто все же можно рассматривать как случайную при условии что объем выборки случайных чисел не слишком велик. В связи с этим для случайных чисел найденных программным путем часто применяют название псевдослучайные числа.
28540. Теоретико-информационный подход к оценке криптостойкости шифров 50.63 KB
  Начнем с описания модели вскрытия секретного ключа.Из этой модели в частности следует что сегодня надежными могут считаться симметричные алгоритмы с длиной ключа не менее 80 битов. необходимого для взлома симметричного алгоритма с различной длиной ключа. Тот факт что вычислительная мощность которая может быть привлечена к криптографической атаке за 10 лет выросла в 1000 раз означает необходимость увеличения за тот же промежуток времени минимального размера симметричного ключа и асимметричного ключа соответственно примерно на 10 и 20...
28541. Классификация основных методов криптографического закрытия информации 79.5 KB
  Символы шифруемого текста заменяются другими символами взятыми из одного алфавита одноалфавитная замена или нескольких алфавитов многоалфавитная подстановка. Таблицу замены получают следующим образом: строку Символы шифруемого текста формируют из первой строки матрицы Вижинера а строки из раздела Заменяющие символы образуются из строк матрицы Вижинера первые символы которых совпадают с символами ключевого слова. Очевидно akjk1 если j =k a1j= aknkj1 если j...
28542. Шифрование в каналах связи компьютерной сети 59.5 KB
  Самый большой недостаток канального шифрования заключается в том что данные приходится шифровать при передаче по каждому физическому каналу компьютерной сети. В результате стоимость реализации канального шифрования в больших сетях может оказаться чрезмерно высокой. Кроме того при использовании канального шифрования дополнительно потребуется защищать каждый узел компьютерной сети по которому передаются данные. Если абоненты сети полностью доверяют друг другу и каждый ее узел размещен там где он защищен от злоумышленников на этот недостаток...
28543. Использование нелинейных операций для построения блочных шифров 35.87 KB
  В большинстве блочных алгоритмов симметричного шифрования используются следующие типы операций: Табличная подстановка при которой группа битов отображается в другую группу битов. Эти операции циклически повторяются в алгоритме образуя так называемые раунды. Входом каждого раунда является выход предыдущего раунда и ключ который получен по определенному алгоритму из ключа шифрования K.
28544. МЕТОДЫ ЗАМЕНЫ 152.5 KB
  К достоинствам блочных шифров относят похожесть процедур шифрования и расшифрования, которые, как правило, отличаются лишь порядком действий. Это упрощает создание устройств шифрования, так как позволяет использовать одни и те же блоки в цепях шифрования и дешифрования.
28546. О возможности реализации абсолютной секретности в постановке Шеннона 58.5 KB
  А это в свою очередь может повлиять на выбор противником своих действий и таким образом совершенной секретности не получится. Следовательно приведенное определение неизбежным образом следует из нашего интуитивного представления о совершенной секретности. Для совершенной секретности системы величины PEM и PM должны быть равны для всех E и M.