|  Логические системы в различных функциональных наборах и их реализация |
При
этом достаточно четырехразрядного двоичного числа, определяющего значение XYZP,
которым в дальнейшем будет кодироваться номер каждого символа. Например, второй
символ «В» должен иметь код 0001, первый «И» - 0000 и т.д.
Таблица
истинности для выбранных признаков представлена в таблице 2, где ФАЛ - функция
алгебры логики, в которых значение 1 принимается для кодов, имеющих значение
признака h, равного 1. В общем случае h Ì {0,1}. Следует учесть, что h1àF1,
h3àF3, h5àF5.
Отображение
T:H ´ A à F
Табл. 1
Следующим
этапом является нахождение 10-значных номеров ФАЛ по карте Карно, общий вид
которой для 4-ех переменных представлен на рисунке 2.2. Цифры в квадратах
являются степенью числа 2 при определении номера ФАЛ, выбранных в данной работе
на рисунке 2.2а,б,в
Рис.
2.2 Карта Карно со степенями двойки
Табл.
истинности для ФАЛ. Табл. 2
Нахождение номера ФАЛ: F1
|
|
|
N(F1)
= 20 + 21 + 23 + 25+ 27 +
26 + 29 + 212 + + 213 + 214
= 29419
|
Нахождение номера ФАЛ: F3
|
|
|
N(F3)
= 21 + 22 + 212 + 28+ 29 +
210 + 211 = 7942
|
Нахождение номера ФАЛ: F5
|
|
N(F5)
= 20 + 23 + 25 + 26 + 27 +
29+ 210 + 213 + + 214 = 26345
|
Представим
выбранные признаки в совершенной дизъюнктивной нормальной форме (СДНФ) и совершенной
конъюнктивной нормальной форме (СКНФ). Для этого из таблицы истинности ФАЛ (см.
табл. 2) выпишем конституэнты 0 и 1.
ФАЛ в СДНФ примет вид:
F1(X,Y,Z,P)
= (X,Y,Z,P) Ú (X,Y,Z,P) Ú (X,Y,Z,P) Ú (X,Y,Z,P) Ú
(X,Y,Z,P) Ú (X,Y,Z,P) Ú (X,Y,Z,P) Ú (X,Y,Z,P) Ú (X,Y,Z,P) Ú (X,Y,Z,P)
F3(X,Y,Z,P)
= (X,Y,Z,P) Ú (X,Y,Z,P) Ú (X,Y,Z,P) Ú (X,Y,Z,P) Ú
(X,Y,Z,P) Ú (X,Y,Z,P) Ú (X,Y,Z,P)
F5(X,Y,Z,P)
= (X,Y,Z,P) Ú (X,Y,Z,P) Ú (X,Y,Z,P) Ú (X,Y,Z,P) Ú
(X,Y,Z,P) Ú (X,Y,Z,P) Ú (X,Y,Z,P) Ú (X,Y,Z,P) Ú (X,Y,Z,P)
ФАЛ в СКНФ примет вид:
F1(X,Y,Z,P)
= (X Ú Y Ú Z Ú P) & (X Ú Y Ú Z Ú P) & (X Ú Y Ú Z Ú P) & (X Ú Y Ú Z Ú P) & (X Ú Y Ú Z Ú P) & (X Ú Y Ú Z Ú P)
F3(X,Y,Z,P)
= (X Ú Y Ú Z Ú P) & (X Ú Y Ú Z Ú P) & (X Ú Y Ú Z Ú P) & (X Ú Y Ú Z Ú P) & (X Ú Y Ú Z Ú P) & (X Ú Y Ú Z Ú P) & (X Ú Y Ú Z Ú P) & (X Ú Y Ú Z Ú P) & (X Ú Y Ú Z Ú P)
F5(X,Y,Z,P)
= (X Ú Y Ú Z Ú P) & (X Ú Y Ú Z Ú P) & (X Ú Y Ú Z Ú P) & (X Ú Y Ú Z Ú P) & (X Ú Y Ú Z Ú P) & (X Ú Y Ú Z Ú P) & (X Ú Y Ú Z Ú P)
Проведем
минимизацию полученных ФАЛ при помощи карты Карно и представим их в ДНФ. Для
этого попытаемся оптимальным образом объединить 0-кубы в кубы большей
размерности. Клетки, образующие k-куб, дают минитерм n-k ранга, где n - число
переменных, которые сохраняют одинаковое значение на этом k-кубе. Таким
образом, получим ДНФ выбранных ФАЛ.
Рис
2.2а Рис 2.2б Рис 2.2в
Проведем минимизацию алгебраическим путем,
воспользовавшись тождеством а È а = а.
1. XYZP Ú XYZP Ú XYZP Ú XYZP Ú XYZP Ú XYZP Ú XYZP Ú XYZP Ú XYZP Ú XYZP Ú XYZP Ú XYZP = XYZ Ú XZP Ú XZP Ú YZP Ú XYZ Ú XZP = ZP Ú XYZ Ú XZP Ú YZP Ú XYZ
2. XYZP Ú XYZP Ú XYZP Ú XYZP Ú XYZP Ú XYZPÚ XYZP Ú XYZP Ú XYZP Ú XYZP = YZP Ú YZP Ú XZP Ú XYZ Ú XYZ = XY Ú YZP Ú YZP Ú XZP
3. Ú XYZP Ú XYZP Ú XYZP Ú XYZP Ú XYZP Ú XYZPÚ XYZP Ú XYZP Ú XYZP Ú XYZP Ú XYZP = XZP Ú XYP Ú XYZ Ú XZP Ú XZP Ú XYZP
Построить
матрицу отношений T:H ´ A. Матрица отношений представляет собой таблицу, строками которой
являются записи (кортежи признаков), а строками отношения, которые имеют все
уникальные имена. Матрица отношения представлена в таблице 3.
Матрица
отношений. Табл. 3
Определим
классы толерантности. Рассмотрим классы толерантности k1, k2,
k3, имеющие общие элементы, следовательно, являющиеся
пересекающимися множествами.
h1 = h(a1) = h(A) = { X0, X1, X3, X5,
X6, X7, X9, X12, X13, X14
}
h2 = h(a2) = h(B) = { X1, X2, X8, X9,
X10, X11, X12 }
h3 = h(a3) = h(C) = { X0, X3, X5, X6,
X7, X9, X10, X13, X14 }
Проанализировав классы h1, h2,
h3, можно получить: k1 Ç k2 = 0;
k1 Ç k3 = 0; k2
Ç k3 = 0, т.е. {k1, k2, k3 }
- образуют класс толерантности
Результаты исследования занесем в таблицу 3.
Определим классы
эквивалентности для этого множества А = {Х0, Х1, ...., Х15
} разобьем на классы эквивалентности, получим 6 классов
М1 = {AC} = {X0,X3,X5,X6
X7,X13,X14}
М2 = {AB} = {X1,X12}
М3 = {B} = {X2,X8,X11}
М4 = { } = {X4,X15}
М5 = {ABC} = {X9}
М6 = {BC} = {X10}
При
этом каждый класс полностью определяется любым его представителем. Сопоставив
результаты исследования с результатами пункта 3.2 получим следующие зависимости
|
М1 Ì K1
|
М2 Ì K1
|
М3 Ì K2
|
М5 Ì K1
|
М6 Ì K2
|
|
М1 Ì K3
|
М2 Ì K2
|
|
М5 Ì K2
|
М6 Ì K3
|
|
|
|
М5 Ì K3
|
|
или
K1 = M1 È M2 È M5
K2 = M2 È M3 È M5 È M6
K3 = M1 È M5 È M6
Результаты
исследования занесены в таблицу 3. Результаты исследования на эквивалентность и
толерантность необходимы для оптимизации построения логической схемы.
Матрицу
эквивалентности и толерантности можно представить в виде квадрата, по диагонали
которого строятся классы эквивалентности, а затем устраиваются отношения
толерантности. Матрица эквивалентности и толерантности представлена в таблице
4.
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Матрица
эквивалентности и толерантности. Таблица 4.
Диаграмма
Эйлера дает наглядное представление о том, как распределяются признаки по
классам толерантности и эквивалентности. Диаграмма Эйлера для выбранных ФАЛ
представлена на рисунке 3.5.
Диаграмма
Эйлера. Рис. 3.5
Комбинационная
схема автомата распознавания набора признаков H = {h1, h3,
h5 } построена на основе результатов исследований в пункте 3.1 и пункте
3.4.
Таблица
5
Используя таблицу 5, можно записать следующие
отношения:
G1 =
(XYZP) Ú (XYZP) Ú (XYZP) Ú (XYZP) Ú (XYZP) Ú (XYZP) Ú (XYZP) = (XYZP) Ú (XYZP) Ú (XYZP) Ú (XYZ) Ú (YZP)
G2 =
(XYZP) Ú (XYZP)
G3 =
(XYZP) Ú (XYZP) Ú (XYZP)
G4 =
(XYZP) Ú (XYZP)
G5 =
(XYZP)
G6 =
(XYZP)
Тогда ФАЛ можно представить в виде:
F1 = G1
Ú G2
Ú G5
F3 = G2
Ú G3
Ú G5
Ú G6
F5 = G1
Ú G5
Ú G6
Эти отношения эквивалентны ФАЛ в СДНФ,
полученным в пункте 2.5.
Комбинационная схема строилась в два этапа:
1 этап: - построение комбинационной схемы на
элементах и, или,
(нестандартных).
2 этап: - замена нестандартных элементов на
стандартные и-не
Окончательный вариант комбинационной схемы
приведен в приложении 1.
1. В.П. Сигорский. «Математический аппарат
инженера» - издательство Киев: Техника - 1975 г.
Проведя анализ на
толерантность и эквивалентность, мы построили автомат, распознающий кортеж признаков
H = {h1, h3, h5 }, который состоит из 16 - ти
логических элементов.
Страницы: 1, 2
|
© 2009 Все права защищены.
Наверх