Государственный комитет по образованию Российской Федерации Московский институт радиотехники, электроники и автоматики факультет кибернетики кафедра интеллектуальных технологий и систем группа ИР-1-95 Тема: "Логические системы в различных функциональных наборах и их реализация" Курс: "Теоретические основы информатики" Задание № 29.419, 7.942, 26.345 Студент: Лепихов И.М. Руководитель: Семёнов А.И. @? ?ЛИМ? @? Иван Лепихов Москва 1997 Задание на курсовое проектирование по курсу: "Теоретические основы информатики" Студента: Лепихова И.М. гр. ИР-1-95. Тема: "Логические схемы в различных функциональных наборах и их реализация" 1. Исходные данные 1.1. Строка из шестнадцати символов А = { a0,a1, ..., a15 } 1.2. Матричный индикатор 5 ? 7 = 35 ячеек. Множество признаков H = { h0,h1, ..., h35 } 1.3. Условие формирования строки символов и отображения T:H ? A --> F. 1.4. Правило выделения ФАЛ из данных пункта 1.3. 1.5. Интегральный набор К155 (по справочнику) 1.6. Условие формирования подпространства Ф F3, h5-->F5.
     Отображение T:H ? A --> F Табл. 1 2.3. Нахождение номеров ФАЛ по карте Карно
    Следующим этапом является нахождение 10-значных номеров ФАЛ по карте Карно, общий вид которой для 4-ех переменных представлен на рисунке 2.2. Цифры в квадратах являются степенью числа 2 при определении номера ФАЛ, выбранных в данной работе на рисунке 2.2а,б,в Рис. 2.2 Карта Карно со степенями двойки 2.4. Таблица истинности. Табл. истинности для ФАЛ. Табл. 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.5. Представление ФАЛ в совершенной нормальной форме.
    Представим выбранные признаки в совершенной дизъюнктивной нормальной форме (СДНФ) и совершенной конъюнктивной нормальной форме (СКНФ). Для этого из таблицы истинности ФАЛ (см. табл. 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) 2.6. Минимизация ФАЛ
    Проведем минимизацию полученных ФАЛ при помощи карты Карно и представим их в ДНФ. Для этого попытаемся оптимальным образом объединить 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 2.7. Представление ФАЛ в виде куба 3. Исследование ФАЛ. 3.1. Матрица отношений.
    Построить матрицу отношений T:H ? A. Матрица отношений представляет собой таблицу, строками которой являются записи (кортежи признаков), а строками отношения, которые имеют все уникальные имена. ............