Лекции по дискретке (1021001), страница 17
Текст из файла (страница 17)
Переход от схемы в нормальном базисе к базисам Шеффера и Вебба и обратно, например, можно отобразить в следующей таблице (таблица 5.1).
Таблица 5.1.
| Нормальный базис | Базис Шеффера | Базис Вебба |
| не
| |
|
| и |
| |
| или | |
|
2. Логические функции, кроме их реализации функциональными схемами, реализуются также контактными, релейно-контактными и интегральными схемами.
3. Одна и та же схема (функциональная, контактная, релейно-контактная, интегральная) может быть реализована большим или меньшим числом функциональных базисных элементов (функций), для уменьшения которых, реализующих одну и ту же булеву функцию, разработана теория минимизации нормальных форм.
50.Основные понятия булевых функций.
Теорема.
Число всех различных булевых функций от n аргументов равно 
.
Доказательство:
Число различных наборов переменных x1, x2, … , xn, где xi {0,1} равно k=2n. Так как каждая булева функция принимает только 2 значения: 0 или 1, то число всех булевых функций от n переменных равно 
, что и требовалось доказать.
Определение.
Операцией сложения по модулю два, которая обозначается знаком , на множестве из двух элементов 0 и 1 называется операция со следующим законом композиции:
для a имеет место
a a ≐ 0 ; a 0 
0 a a .
Определение.
Элементарными булевыми функциями называются следующие функции:
e1(x) 0 – нуль-функция;
e2(x) 1 – единица-функция;
e3(x) x – функция x;
e4(x) = ù x – отрицание x;
e5(x, y) ≐ 
– конъюнкция x и y;
e6(x, y) ≐ 
– дизъюнкция x и y;
e7(x, y) ≐ x y – импликация x и y;
e8(x, y) ≐ x y – эквиваленция x и y;
e9(x, y) x y – сложение по модулю два x и y.
Замечания.
1. Таблица истинности для элементарных булевых функций имеет вид, представленный в табл. ниже.
Таблица
2. Заметим, что
1) x y = ù ( x y), то есть e9(x, y) = e4(e8(x, y)), то есть функция xy является суперпозицией функций xy и ù x.
2) 
– суперпозиция функций 
и , каждая из которых от двух переменных.
3) 0 = ù (
ù x); 1= ù x.
Приоритеты логических операций.
Операция ù имеет больший приоритет, чем 
;
Операция имеет больший приоритет, чем ;
Операция имеет больший приоритет, чем 
;
Операция имеет больший приоритет, чем ;
Операция имеет больший приоритет, чем .
Примеры функций, являющихся суперпозициями элементарных функций.
g1(x1, x2, x3, x4) ≐ 
ù x4
g2(x1, x2, x3) ≐ 
ù x2)
g3(x1, x2) ≐ ù 
Определение.
Пусть
1) u – переменная, при этом пусть u0= ù u, а u1=u;
2) ai {0,1} , 
;
3) u1, u2, … , un – переменные, причём не обязательно различные.
Тогда формула 
называется элементарной конъюнкцией, а 
– элементарной дизъюнкцией.
Примеры.
1. Элементарными конъюнкциями будут следующие формулы:
x, y, ù x, x y, x1 x1, 
, 
, 
, 
.
2. Элементарными дизъюнкциями будут следующие формулы:
x, y, ù y, x y, x x x, 
, 
, 
,
.
Ясно, что каждая элементарная конъюнкция и каждая элементарная дизъюнкция являются суперпозициями функций ù x, x y и x y.
Замечание.
Принимая для переменной u , что 
и 
, замечаем, что ua = 1 u = a, a
{0,1}.
В этом случае :
1) функция
Kn(x1, x2,…, xn) = 
(1)
такая, что Kn(a1, a2,…, an) = 1 и Kn(b1, b2,…, bn) = 0, если
(b1, b2,…, bn) (a1, a2,…, an);
2) функция
dn(x1, x2,…, xn)= 
(2)
такая, что dn(
) = 0 и dn(b1, b2,…, bn) = 1, если
(b1, b2,…, bn) ( ).
При этом в формулах (1) и (2) все переменные попарно различны.
Теорема.
Каждая булева функция является суперпозицией следующих функций: отрицания, конъюнкции и дизъюнкции.
Доказательство:
Первое доказательство.
Обозначим множество всех булевых функций через P2. Если данная функция f P2 является константой, равной нулю, то, согласно соотношению 0 = ù (x ù x) или 0 = x ù x, утверждение справедливо. В противном случае, существуют такие наборы (a1, a2,…, an), что f(a1, a2,…, an)=1. Для каждого такого набора (a1, a2,…, an) образуем элементарную конъюнкцию 
, которая имеет значение 1 только на наборе (a1, a2,…, an). Тогда
f(x1, x2,…, xn) =
, (3)
где дизъюнкции берётся по всем таким наборам (a1, a2,…, an), что f(a1, a2,…, an) = 1. Так как правая часть равенства (3) является суперпозицией требуемых функций, то теорема доказана.
Второе доказательство.
Если функция f P2 является константой равной 1, то, согласно 1= x ù x или 1=ù (x ù x), утверждение справедливо. В противном случае, существуют такие наборы (a1, a2,…, an), что f(a1, a2,…, an) 1, или, что то же самое, f(a1, a2,…, an) = 0. Таким образом, функция f(x1, x2,…, xn) может быть представлена в виде
f(x1, x2,…, xn) = 
, (4)
где конъюнкция берётся по всем таким наборам (a1, a2,…, an), что
f(a1, a2,…, an)=0. Правая часть равенства (4) опять, как и в первом доказательстве, является суперпозицией требуемых функций. Теорема доказана.
Определение.
Правая часть равенства (3) называется совершенной дизъюнктивной нормальной формой (кратко СДНФ) функции f(x1, x2,…, xn).
Замечание.
СДНФ существует только для тех булевых функций, которые не являются константами, равными нулю.
Определение.
Правая часть равенства (4) называется совершенной конъюнктивной нормальной формой (СКНФ) функции f(x1, x2,…, xn).
Замечание.
СКНФ существует только для тех булевых функций, которые не являются константами, равными единице.
Определение.
Конъюнкция всех аргументов функции (с отрицанием и без отрицания) называется полной и обозначается буквой K с соответствующим индексом. Индексом в обозначении служит номер набора или двоичное число, а также соответствующее ему десятичное, полученное при замене каждой переменной xi символом 1, а переменной ù xi – символом 0.
Определение.
Дизъюнкция всех аргументов функции (с отрицанием и без отрицания) называется полной и обозначается (в литературе) буквой D с соответствующим индексом. Индексом служит инверсионный номер набора или двоичное число, а также соответствующее ему десятичное, полученное при замене каждой переменной xi символом 0, а переменной ù xi – символом 1.
Примеры.
1. x1x2 – номер набора –112 = 310, полная конъюнкция обозначается K3.
2. 
– номер набора – 0102 = 210, полная конъюнкция обозначается K2.
3. x1 x2 – номер инверсионного набора – 002 – 010, полная дизъюнкция обозначается D0.
4. 
– номер инверсионного набора – 1012 – 510, полная дизъюнкция обозначается D5.
Определение.
Полная конъюнкция, принимающая значение 1 только на одном наборе аргументов, соответствующем её индексу, и значение 0 на всех остальных наборах, называется также конституэнтой (образующей) или характеристической функцией единицы.
Определение.
Полная дизъюнкция, принимающая значение 0 только на одном наборе аргументов, соответствующем её индексу, и значение 1 на всех остальных наборах, называется также конституэнтой (образующей) или характеристической функцией нуля.
Замечание.
Значение булевой функции для конкретных значений аргументов удобно обозначить символом с индексом в виде десятичного числа, соответствующего двоичному набору аргумента, например, f(1,1) = 3, f(1,0,1) = 5.
Примеры.
С учётом введённых определений булеву функцию f(x1, x2) можно записать {с учетом разложения в СДНФ или СКНФ} в следующем виде:
.
Замечание.
Приведенный пример показывает, каким образом можно перейти от табличного представления булевой функции к её аналитическому представлению. При табличном представлении функции задаются её значения i для каждого набора аргументов, определяемого индексом i. Так как в силу определения операции конъюнкции имеем 0Ki = 0 и 1Ki = Ki, то для представления функции в виде СДНФ нужно выписать дизъюнкцию всех тех конституэнт единицы Ki, для которых i = 1. Учитывая также, что 0Di=Di и 1Di=1, СКНФ получается как конъюнкция всех тех конституэнт нуля Di, для которых значение функции i равно 0.
51.Законы двойственности.
Определение.
Учитывая определённую симметрию операций и в аксиоматике алгебры Буля логических высказываний и операций, операции и называются двойственными.
Определение.
Формулы 
и * называются двойственными, если одна получается из другой заменой каждой операции на двойственную.
Примеры.
1. 
двойственна 
.
2. 
двойственна 
.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
