26.10.2000

лекция 1

ПРИЛОЖЕНИЕ БУЛЕВЙ АЛГЕБРЫ К СИНТЕЗУ КОМБИНАЦИОННЫХ СХЕМ.

Схемы

Комбинационные

Последовательностные

Комбинационные схемы – это схемы, в которых значение выхода зависит только от значений входных сигналов.

Последовательностные схемы – это схемы с памятью…

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

Элементы булевой алгебры:

А) числа

Б) переменные

В) операции

Г) выражения

Д) функции

Е) законы

Числа: два числа, логический ноль и логическая единица в булевой алгебре отождествляются с понятиями истина или ложь.(1- истина 0-ложь).

Переменные булевы (логические, двоичные) – это переменные, которые принимают значения из множества {0,1} ( X{0,1})

Операции: в булевой алгебре 3 операции:

1. отрицание (инверсия)

2. конъюнкция (логическое умножение)

3. дизъюнкция (логическое сложение)

Старшинство операций: , AND, OR

Отрицание является унарной операцией.

Обозначение: X, X – отрицание

a&b, a*b, ab, ab – конъюнкция

ab - дизъюнкция

Выражение – это переменные, соединенные знаками операций. Порядок операции задается старшинством, для изменения порядка операций используются скобки.

Функцией булевой или логической называется такая функция,

аргументами которой являются булевы переменные, а сама функция принимает значения из множества: Y(х)  {0,1} Область определения булевой функции является совокупность 2ⁿ двоичных наборов ее аргументов, где n - число переменных (аргументов). Набор аргументов можно рассматривать как компонентный двоичный вектор.

Формы задания булевой функции.

1. Аналитическая форма - в виде логического умножения.

2. Табличная – в виде таблицы истинности.

3. Графическая.

4. Таблично - графическая – в виде карты Карно.

5. Числовая.

6. Символическая.

№1 Аналитическая форма:

Y³(X)=(X₁ X₂)X₃

Y³(X)=X₁X₂X₃  X₁X₂X₃  X₁X₂X₃

№2 Табличная форма:

X1	X2	X3	X1X2	Y(X)
0	0	0	1	1
0	0	1	1	0
0	1	0	1	1
0	1	1	1	0
1	0	0	0	0
1	0	1	0	0
1	1	0	1	1
1	1	1	1	0

Переход от аналитической формы к табличной всегда однозначный, а обратный переход - нет.

Скажем, эта же таблица для: Y³(X)=X₁X₂X₃  X₁X₂X₃  X₁X₂X₃

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

номер	Закон	Название
1	ab=ba ab=ba	переместительный
2	(ab)c=a(bc) (ab)c=a(bc)	Сочетательный (ассоциативный)
3	a(bc)=abac abc=(ab)(ac)	Дистрибутивный
4	a=a (a)=a	Двойного отрицания
5	aa=a aa=a	Тавтология
6	a0=0 a0=a	Нулевой переменной
7	a1=a a1=1	Единичной переменной
8	aa=0 aa=1	Дополнительного элемента
9	ab=ab ab=ab ab=ab ab=ab	Правило Де Моргана (двойственность)
10	aab=a a(ab)=a	Поглощения
11	aab=ab a(ab)=ab	Сокращения
12	abab=b (ab)(ab)=b	Склеивания

Комментарии к законам:

Для доказательства законов можно использовать метод совершенной индукции или другие законы.

1. Метод совершенной индукции состоит в доказательстве эквивалентности левой и правой частей на всех наборах аргументов. Для этого составляется таблица истинности.

2. Использование законов для доказательства других (кроме законов

Де Моргана)

Пример:

aab=a(1b)=a

abab=b(aa)=b

Де Моргана:

a	b	ab	ab	ab
0	0	0	1	1
0	1	1	0	0
1	0	1	0	0
1	1	1	0	0

1. Большинство законов являются парой соотношений, при этом одно соотношений можно получить из другого заменой дизъюнкции на конъюнкцию и конъюнкции на дизъюнкцию. (метод неприменим для законов с константой). В случае с константой ее надо менять на противоположную. Это свойство называется – дуальностью законов булевой алгебры.

2. Некоторые законы можно распространять на произвольное число аргументов.

Пример: dcab=abcd

3. В любом законе любую переменную можно заменять на произвольное логическое выражение

Пример: abab=b

b=cd

a(cd) a(cd)=cd

4. Законы булевой алгебры используются для упрощения выражений булевых функций.

Разнообразие булевых функций.

1. Булева функция от одной переменной.

Обозначение аргумента и функции	Значение аргумента и функции		Наименование функции
X	0	1
F01	0	0	Логический «0»
F11	0	1	Повторение «Х»
F21	1	0	Инверсия «Х»
F31	1	1	Логическая «1»

Логический ноль или единица - это вырожденные функции (не зависят от аргумента )

2. булева функция от двух переменных.

Обозначение аргумента и функции	Значение аргумента и функции				Обозначение функции	Наименование функции	Представление функции в булевом базисе
X1	0	0	1	1
X2	0	1	0	1
F02	0	0	0	0	0	Логический «0»	-------
F12	0	0	0	1	X1 & X2	Конъюнкция	X1 X2
F22	0	0	1	0	X1 X2	Запрет x1 по x2	X1 X2
F32	0	0	1	1	X1	Повторение x1	-------
F42	0	1	0	0	X2 X1	Запрет x2 по x1	X1 X2
F52	0	1	0	1	X2	Повторение x2	-------
F62	0	1	1	0	X1  X2	Сложение по mod2	X1 X2 X1 X2
F72	0	1	1	1	X1 X2	Дизъюнкция	X1 X2
F82	1	0	0	0	X1  X2 X1 X2	Функция Вебба Пирса	X1  X2
F92	1	0	0	1	X1 X2	Равнозначность эквивалентность	X1 X2 X1 X2
F102	1	0	1	0	X2	Инверсия x2	-------
F112	1	0	1	1	X2 X1	Импликация от x2 к x1	X1 X2
F122	1	1	0	0	X1	Инверсия x1	-------
F132	1	1	0	1	X1 X2	Импликация от x1 к x2	X1 X2
F142	1	1	1	0	X1 X2	Штрих Шеффера	X1 X2
F152	1	1	1	1	1	Логическая «1»	-------

27.10.2000

Определение: Булева функция от переменных называется вырожденной по аргументу, если ее значение не зависит от этого аргумента, т.е. для всех наборов аргументов выполняется следующее правило:

Соответственно вырожденными являются следующие функции:

Функция запрета: (запрет по) принимает значение, равное нулю, при равенстве запрещающей переменной единице и повторяет значение аргумента при равенстве запрещающей переменной нулю.

Функция импликации. Понятие импликации в булевой алгебре отождествляется с выражением следования (если…, то…)

Пример:

А – на небе дождь

В – на небе тучи

В А (если идет дождь, то на небе тучи)