Логические системы в различных функциональных наборах и их реализация (стр. 2 из 2)

Представим выбранные признаки в совершенной дизъюнктивной нормальной форме (СДНФ) и совершенной конъюнктивной нормальной форме (СКНФ). Для этого из таблицы истинности ФАЛ (см. табл. 2) выпишем конституэнты 0 и 1.

ФАЛ в СДНФ примет вид:

F₁(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)

F₃(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)

F₅(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)

ФАЛ в СКНФ примет вид:

F₁(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)

F₃(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)

F₅(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)

2.6. Минимизация ФАЛ

Проведем минимизацию полученных ФАЛ при помощи карты Карно и представим их в ДНФ. Для этого попытаемся оптимальным образом объединить 0-кубы в кубы большей размерности. Клетки, образующие k-куб, дают минитерм n-k ранга, где n - число переменных, которые сохраняют одинаковое значение на этом k-кубе. Таким образом, получим ДНФ выбранных ФАЛ.

Рис 2.2а Рис 2.2б Рис 2.2в

Проведем минимизацию алгебраическим путем, воспользовавшись тождеством а È а = а.

XYZP Ú XYZP Ú XYZP Ú XYZP Ú XYZP Ú XYZP Ú XYZP Ú XYZP Ú XYZP Ú XYZP Ú XYZP Ú XYZP = XYZ Ú XZP Ú XZP Ú YZP Ú XYZ Ú XZP = ZP Ú XYZ Ú XZP Ú YZP Ú XYZ

XYZP Ú XYZP Ú XYZP Ú XYZP Ú XYZP Ú XYZPÚ XYZP Ú XYZP Ú XYZP Ú XYZP = YZP Ú YZP Ú XZP Ú XYZ Ú XYZ = XY Ú YZP Ú YZP Ú XZP

Ú XYZP Ú XYZP Ú XYZP Ú XYZP Ú XYZP Ú XYZPÚ XYZP Ú XYZP Ú XYZP Ú XYZP Ú XYZP = XZP Ú XYP Ú XYZ Ú XZP Ú XZP Ú XYZP

2.7. Представление ФАЛ в виде куба

3. Исследование ФАЛ.

3.1. Матрица отношений.

Построить матрицу отношений T:H ´ A. Матрица отношений представляет собой таблицу, строками которой являются записи (кортежи признаков), а строками отношения, которые имеют все уникальные имена. Матрица отношения представлена в таблице 3.

Матрица отношений. Табл. 3

3.2. Исследование ФАЛ на толерантность.

Определим классы толерантности. Рассмотрим классы толерантности k₁, k₂, k₃,имеющие общие элементы, следовательно, являющиеся пересекающимися множествами.

h₁ = h(a₁) = h(A) = { X₀, X₁, X₃, X₅, X₆, X₇, X₉, X₁₂, X₁₃, X₁₄}

h₂ = h(a₂) = h(B) = { X₁, X₂, X₈, X₉, X₁₀, X₁₁, X₁₂}

h₃ = h(a₃) = h(C) = { X₀, X₃, X₅, X₆, X₇, X₉, X₁₀, X₁₃, X₁₄}

Проанализировав классы h₁, h₂, h₃, можно получить: k₁Ç k₂= 0;

k₁Ç k₃= 0; k₂Ç k₃= 0, т.е. {k₁, k₂, k₃} - образуют класс толерантности

Результаты исследования занесем в таблицу 3.

3.3. Исследование ФАЛ на эквивалентность.

Определим классы эквивалентности для этого множества А = {Х₀, Х₁, ...., Х₁₅} разобьем на классы эквивалентности, получим 6 классов

М₁ = {AC} = {X₀,X₃,X₅,X₆ X₇,X₁₃,X₁₄}

М₂ = {AB} = {X₁,X₁₂}

М₃ = {B} = {X₂,X₈,X₁₁}

М₄ = { } = {X₄,X₁₅}

М₅ = {ABC} = {X₉}

М₆ = {BC} = {X₁₀}

При этом каждый класс полностью определяется любым его представителем. Сопоставив результаты исследования с результатами пункта 3.2 получим следующие зависимости

М₁Ì K₁	М₂Ì K₁	М₃Ì K₂	М₅Ì K₁	М₆Ì K₂
М₁Ì K₃	М₂Ì K₂	М₅Ì K₂	М₆Ì K₃
М₅Ì K₃

или

K₁ = M₁È M₂È M₅

K₂ = M₂È M₃È M₅È M₆

K₃ = M₁È M₅È M₆

Результаты исследования занесены в таблицу 3. Результаты исследования на эквивалентность и толерантность необходимы для оптимизации построения логической схемы.

3.4. Матрица эквивалентности и толерантности.

Матрицу эквивалентности и толерантности можно представить в виде квадрата, по диагонали которого строятся классы эквивалентности, а затем устраиваются отношения толерантности. Матрица эквивалентности и толерантности представлена в таблице 4.

Матрица эквивалентности и толерантности. Таблица 4.

3.5. Диаграмма Эйлера.

Диаграмма Эйлера дает наглядное представление о том, как распределяются признаки по классам толерантности и эквивалентности. Диаграмма Эйлера для выбранных ФАЛ представлена на рисунке 3.5.

Диаграмма Эйлера. Рис. 3.5

3.6. Построение комбинационной схемы.

Комбинационная схема автомата распознавания набора признаков H = {h₁, h₃, h₅} построена на основе результатов исследований в пункте 3.1 и пункте 3.4.

Таблица 5

Используя таблицу 5, можно записать следующие отношения:

G₁ = (XYZP) Ú (XYZP) Ú (XYZP) Ú (XYZP) Ú (XYZP) Ú (XYZP) Ú (XYZP) = (XYZP) Ú (XYZP) Ú (XYZP) Ú (XYZ) Ú (YZP)

G₂ = (XYZP) Ú (XYZP)

G₃ = (XYZP) Ú (XYZP) Ú (XYZP)

G₄ = (XYZP) Ú (XYZP)

G₅ = (XYZP)

G₆ = (XYZP)

Тогда ФАЛ можно представить в виде:

F₁ = G₁Ú G₂Ú G₅

F₃ = G₂Ú G₃Ú G₅Ú G₆

F₅ = G₁Ú G₅Ú G₆

Эти отношения эквивалентны ФАЛ в СДНФ, полученным в пункте 2.5.

Комбинационная схема строилась в два этапа:

1 этап: - построение комбинационной схемы на элементах и, или,

(нестандартных).

2 этап: - замена нестандартных элементов на стандартные и-не

Заключение

Проведя анализ на толерантность и эквивалентность, мы построили автомат, распознающий кортеж признаков H = {h₁, h₃, h₅}, который состоит из 16 - ти логических элементов.

Список литературы

1. В.П. Сигорский. «Математический аппарат инженера» - издательство Киев: Техника - 1975 г.