- •Содержание
- •6. Элементарные двоичные переключательные функции
- •7. Основные законы булевой алгебры и преобразование
- •Приложение 2. Варианты контрольных заданий по дисциплине
- •Предисловие
- •Дискретная математика
- •1. Множества и алгебраические системы. Булевы алгебры
- •1.1. Основные понятия теории множеств
- •1.2. Основные операции над множествами
- •1.3. Декартово произведение множеств
- •1.4. Соответствия и функции
- •1.5. Отношения
- •1.6. Использование множеств в языке Паскаль
- •2. Элементы общей алгебры
- •2.1. Операции на множествах
- •2.2. Группа подстановок Галуа
- •2.3. Алгебра множеств (алгебра Кантора)
- •2.4. Алгебраические системы. Решетки
- •2.5. Задание множеств конституентами
- •2.6. Решение уравнений в алгебре множеств.
- •3. Элементы комбинаторики
- •3.1. Комбинаторные вычисления
- •3.2. Основные понятия комбинаторики
- •3.3. Размещения
- •3.4. Перестановки
- •3.5. Сочетания
- •3.6. Треугольник Паскаля.
- •3.7. Бином Ньютона
- •3.8. Решение комбинаторных уравнений
- •4. Основные понятия теории графов
- •4.1. Способы задания графов
- •4.2. Характеристики графов
- •4.3. Понятие о задачах на графах
- •4.4. Задача о Ханойской башне
- •5. Переключательные функции и способы их задания
- •5.1. Понятие о переключательных функциях
- •5.2. Двоичные переключательные функции и способы их задания
- •5.3. Основные бинарные логические операции
- •5.4. Понятие о переключательных схемах и технической реализации переключательных функций
- •5.5. Использование логических операций в теории графов
- •6. Элементарные двоичные переключательные функции и функциональная полнота систем переключательных функций
- •6.1. Элементарные переключательные функции одной переменной
- •6.2. Элементарные переключательные (логические) функции двух переменных
- •6.3. Функциональная полнота систем переключательных функций
- •6.4. Базисы представления переключательных функций
- •6.5. Пример анализа и определения свойств пф, заданной десятичным номером
- •7. Основные законы булевой алгебры и преобразование переключательных функций
- •7.1. Основные законы булевой алгебры переключательных функций
- •7.2. Равносильные преобразования. Упрощение формул алгебры переключательных функций
- •7.3. Преобразование форм представления переключательных функций
- •8. Минимизация переключательных функций
- •8.1. Цель минимизации переключательных функций
- •8.2. Основные понятия и определения, используемые при минимизации
- •8.3. Аналитические методы минимизации переключательных функций
- •8.4. Минимизация переключательных функций по картам Карно
- •8.5. Метод поразрядного сравнения рабочих и запрещенных наборов
- •Минимизация переключательных функций на основе поразрядного сравнения рабочих и запрещенных восьмеричных наборов.
- •8.6. Минимизация переключательных функций, заданных в базисе {, и, не}
- •8.7. Минимизация систем переключательных функций
- •8.8. Минимизация переключательных функций методом неопределенных коэффициентов
- •9. Понятие об автомате и его математическом описании
- •9.1. Основные определения теории конечных автоматов
- •9.2. Описание конечных детерминированных автоматов
- •9.3. Понятие о технической интерпретации конечных автоматов
- •9.4. Синтез комбинационных автоматов в заданном базисе
- •9.5. Булева производная
- •9.6. Элементарные автоматы памяти на основе комбинационного автомата и задержки
- •9.7. Синтез автомата – распознавателя последовательности
- •10. Элементы теории кодирования
- •10.1. Понятие о кодировании
- •10.2. Системы счисления, как основа различных кодов
- •10.3. Понятие о помехоустойчивом кодировании
- •10.4. Кодирование по Хэммингу
- •10.5. Кодирование с использованием циклических кодов и математического аппарата умножения и деления полиномов. Сигнатурный анализ
- •10.6. Понятие о криптографической защите информации
- •10.7. Понятие о сжатии информации
6.4. Базисы представления переключательных функций
Функционально полные системы переключательных функций представляют собой базис. Всего можно получить 17 различных минимальных базисов из логических функций двух переменных.
Имеются функции, обладающие всеми пятью отмеченными свойствами. Таковы функции и(см. табл. 25). Часто их называют соответственно ИЛИ-НЕ, И-НЕ. Таким образом, это базисы, состоящие из одной функции (базис Вебба и базис Шеффера). Этот факт очень важен при технической реализации дискретных устройств: достаточно иметь элементы, реализующие только одну из этих функций, чтобы построить любую, сколь угодно сложную схему.
Имеются базисы, состоящие из двух функций:
Иногда используется не минимальный базис – из трех функций:
Имеется и довольно экзотический базис Жегалкина:
В дальнейшем нам пригодится так называемый импликативный базис
Функционально полные толерантные базисы представления переключательных функций.
Если рассматривать переключательные функции большего числа аргументов, то можно поставить задачу отыскания базисов, не зависящих от некоторых модификаций соответствующих функций. Такие модификации могут быть, например, вызваны подстановкой констант 0, 1 и инверсией переменных, что происходит при некоторых отказах (дефектах) соответствующих логических элементов [34]. Такие базисы называют толерантными. Например, переключательная функция четырех переменных – толерантный базис – функционально полная толерантная функция, которая при подстановке констант вместо переменных или при инверсии переменных модифицируется также в базисную функцию:
6.5. Пример анализа и определения свойств пф, заданной десятичным номером
Дано: двоичная переключательная функция (ПФ) №17410.
Получим соответствующий двоичный код: 101011102 (27+25+23+22+21). Таблица истинности ПФ №17410 показана в табл. 28.
Таблица 28
Таблица истинности
переменные |
ВС |
f(abc) |
| ||
а |
b |
с |
| ||
0 |
0 |
0 |
0 |
0 |
20 |
0 |
0 |
1 |
1 |
1 |
21 |
0 |
1 |
0 |
2 |
1 |
22 |
0 |
1 |
1 |
3 |
1 |
23 |
1 |
0 |
0 |
4 |
0 |
24 |
1 |
0 |
1 |
5 |
1 |
25 |
1 |
1 |
0 |
6 |
0 |
26 |
1 |
1 |
1 |
7 |
1 |
27 |
Получим восьмеричный код ПФ: 2568.
Получим шестнадцатеричный код ПФ: АЕ16.
Получим символическую форму: f(abc)10=1,2,3,5,7 [0,4,6].
В двоичном виде: f(abc)2=001201121012 1112.
Определим свойства ПФ №17410.
1. Поскольку на наборе 000 ПФ равна 0, то ПФ обладает свойством сохранения константы «0».
2. Поскольку на наборе 111 ПФ равна 1, то ПФ обладает свойством сохранения константы «1».
3. Рассмотрим все возможные линейные ПФ от трех аргументов в зависимости от значений коэффициентов полинома :
Таблица 29
Переключательные функции от трех аргументов
Значение коэффициентов |
Линейная функция | |||
k0 |
k1 |
k2 |
k3 | |
0 |
0 |
0 |
0 |
≡0 |
0 |
0 |
0 |
1 |
a |
0 |
0 |
1 |
0 |
b |
0 |
0 |
1 |
1 |
ab |
0 |
1 |
0 |
0 |
c |
0 |
1 |
0 |
1 |
ca |
0 |
1 |
1 |
0 |
cb |
0 |
1 |
1 |
1 |
cba |
1 |
0 |
0 |
0 |
≡1 |
1 |
0 |
0 |
1 |
=a1 |
1 |
0 |
1 |
0 |
b1= |
1 |
0 |
1 |
1 |
ab1= |
1 |
1 |
0 |
0 |
1c= |
1 |
1 |
0 |
1 |
ca1= |
1 |
1 |
1 |
0 |
1bc= |
1 |
1 |
1 |
1 |
Проверим, не равна ли наша функция функциям:
, , ,
и их инверсиям:
, ,, .
Для этого получим соответствующие векторы этих линейных ПФ (табл. 30).
Таблица 30
Векторы переключательных функций
Переменные | ||||||||||
a |
b |
c | ||||||||
0 |
0 |
0 |
0 |
0 |
0 |
0 |
1 |
1 |
1 |
1 |
0 |
0 |
1 |
0 |
1 |
1 |
1 |
1 |
0 |
0 |
0 |
0 |
1 |
0 |
1 |
0 |
1 |
1 |
0 |
1 |
0 |
0 |
0 |
1 |
1 |
1 |
1 |
0 |
0 |
0 |
0 |
1 |
1 |
1 |
0 |
0 |
1 |
1 |
0 |
1 |
0 |
0 |
1 |
0 |
1 |
0 |
1 |
1 |
0 |
1 |
0 |
0 |
1 |
0 |
1 |
1 |
1 |
0 |
0 |
1 |
1 |
0 |
1 |
0 |
0 |
1 |
1 |
1 |
1 |
0 |
0 |
0 |
1 |
1 |
1 |
1 |
0 |
Видим, что ни один из полученных векторов этих восьми линейных ПФ не совпадает с вектором нашей функции.
Следовательно, функция №17410 – не линейная.
4. Определим, обладает ли наша ПФ свойствами самодвойственности.
Для этого проанализируем её вектор в двоичном коде (рис. 38).
Рис. 38. Вектор в двоичном коде
Видим, что симметричные разряды 5 и 2 неортогональны. Следовательно, ПФ – несамодвойственна. У самодвойственной ПФ симметричные разряды ортогональны (противоположны).
5. Определим, монотонна ли наша ПФ.
Посмотрим на куб соседних чисел. Монотонная функция по всем возможным путям из вершины (000) в вершину (111) монотонна. Однако наша функция на наборе (010) принимает значение «1», а на большем сравнимом наборе (110) – «0». Следовательно, она не монотонна.
Представим вектор свойств ПФ (табл. 31):
Таблица 31
Вектор свойств ПФ
1 |
2 |
3 |
4 |
5 |
№ свойства |
1 |
1 |
0 |
0 |
0 |
наличие свойства |
В восьмеричном коде вектор свойств равен 308, а в шестнадцатеричном – 1816.