- •1. СТАНОВЛЕНИЕ ТЕОРИИ АВТОМАТОВ
- •1.1. Взаимосвязь теории автоматов и других
- •1.2. Подходы к определению конечного автомата
- •1.3. Сущность метода "черного ящика"
- •1.4. Основные задачи теории автоматов
- •2. ФОРМАЛЬНАЯ КЛАССИФИКАЦИЯ АБСТРАКТНЫХ АВТОМАТОВ И ИХ МАТЕМАТИЧЕСКИЕ МОДЕЛИ
- •2.1. Словесные определения автоматов
- •2.2. Формальное определение абстрактного автомата
- •2.3. Формальная классификация автоматов
- •2.4. Математические модели автоматов
- •2.4.1. Модель Мили
- •2.4.2. Модель Мура
- •2.4.3. Модель совмещенного автомата (С-автомата)
- •2.4.4. Модель микропрограммного автомата
- •3. СТРУКТУРНЫЕ МОДЕЛИ ПЕРВОГО УРОВНЯ АБСТРАКТНЫХ АВТОМАТОВ
- •3.1. Структурная модель автомата Мили
- •3.2. Структурная модель автомата Мура
- •3.3. Структурная модель С-автомата
- •3.4. Структурная модель микропрограммного автомата
- •4. СПОСОБЫ ЗАДАНИЯ АБСТРАКТНЫХ И СТРУКТУРНЫХ АВТОМАТОВ
- •4.1. Начальные языки
- •4.1.1. Язык регулярных выражений алгебры событий
- •4.1.2. Язык логических схем
- •4.1.3. Язык граф – схем алгоритмов
- •4.2. Автоматные языки
- •4.2.1. Таблицы переходов и выходов
- •4.2.2. Матрицы переходов и выходов
- •4.2.3. Граф автомата
- •4.3.2. Язык временных диаграмм
- •5. Минимизация абстрактных автоматов
- •6. МАТЕМАТИЧЕСКИЕ ОСНОВЫ АЛГЕБРЫ ЛОГИКИ
- •6.1. Формальное определение алгебры логики
- •6.2. Аксиомы, теоремы и законы алгебры логики
- •6.2.1. Аксиомы алгебры логики
- •6.2.2. Теоремы алгебры логики
- •6.2.3. Законы алгебры логики
- •6.3. Основные понятия и определения
- •6.4. Формы представления логических функций
- •6.4.1. Словесная форма представления логических функций
- •6.4.2. Табличная форма представления логических функций
- •6.4.3. Аналитическая форма представления логических функций
- •7. Минимизация логических функций
- •7.1. Методы минимизации логических функций на основе прямых аналитических преобразований СДНФ
- •7.2. Метод испытания импликант
- •7.3. Визуальные методы минимизации логических функций
- •7.3.2. Метод минимизации частично определенных логических функций с помощью карт Карно
- •7.4. Машинно-ориентированные методы минимизации логических функций
- •7.5. Групповая минимизация системы логических функций
- •8. ФУНКЦИОНАЛЬНО ПОЛНЫЕ СИСТЕМЫ ЭЛЕМЕНТАРНЫХ ЛОГИЧЕСКИХ ФУНКЦИЙ
- •9. ПРОГРАММИРУЕМЫЕ ЛОГИЧЕСКИЕ ИНТЕГРАЛЬНЫЕ СХЕМЫ
- •9.1. Программируемые логические матрицы
- •10. КОНЕЧНЫЕ ФУНКЦИОНАЛЬНЫЕ ПРЕОБРАЗОВАТЕЛИ
- •11. СИНТЕЗ И АНАЛИЗ ТИПОВЫХ КОМБИНАЦИОННЫХ АВТОМАТОВ
- •11.1. Шифратор (coder) и его синтез
- •11.2. Дешифратор и его синтез
- •11.3. Мультиплексор и его синтез
- •11.4. Синтез демультиплексора (распределителя)
- •12. Элементарные автоматы с памятью и их синтез
- •12.1. Понятие функционально полной системы элементарных автоматов
- •12.2. Разновидности триггеров
- •12.3. Обобщённая характеристика триггеров
- •12.4. Синтез однотактного асинхронного RS-триггера
- •12.4.1. Синхронный однотактный RS-триггер
- •12.5. Синхронный однотактный D-триггер
- •12.6.1. Принцип построения двухтактного триггера
- •12.6.2. Однотактный Т-триггер
- •12.6.3. Двухтактные Т-триггеры
- •12.7. Двухтактный JK-триггер
- •12.8. Двухтактные RS-триггеры и D-триггеры
- •Рис. 12.28. Синхронный двухтактный RS-триггер
- •Рис. 12.30. УГО синхронного двухтактного RS-триггера
- •БИБЛИОГРАФИЧЕСКИЙ СПИСОК
- •Учебное издание
|
x |
y |
z |
1 |
1 |
|
1 |
|
|
|
b1 |
|
|
|
|
& |
|
|
b2 |
1 |
|
|
|
|
f1 |
||
|
|
|
|
|
|
|
|
|
|||||||
|
|
|
|
|
|
|
|
|
|
|
|
||||
|
|
|
|
|
|
|
|
||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
& |
|
|
b3 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||
|
|
|
|
|
|
|
|
|
1 |
|
|
f2 |
|||
|
|
|
|
|
|
|
|
|
|
|
|
||||
|
|
|
|
|
|
|
|
|
|||||||
|
|
|
|
& |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
b4 |
|
||||||||
|
|
|
|
|
|
|
|||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|||
|
|
|
|
|
|
|
|
|
|
|
|
|
|||
|
|
|
|
& |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
b5 |
|
|
|
|
1 |
f3 |
||
|
|
|
|
|
|
|
|
|
|
||||||
|
|
|
|
& |
|
|
|
||||||||
|
|
|
|
|
|
b6 |
|
|
|
|
|
|
|
||
|
|
|
|
|
|
|
|
|
|||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||
|
|
|
|
|
|
|
|
|
|
|
|
|
|||
|
|
|
|
& |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Рис. 7.7. Реализация минимизированной системы функций логической схемой
8. ФУНКЦИОНАЛЬНО ПОЛНЫЕ СИСТЕМЫ ЭЛЕМЕНТАРНЫХ ЛОГИЧЕСКИХ ФУНКЦИЙ
Любую логическую функцию в алгебре логики можно представить в виде СДНФ и СКНФ, используя триэлемента р- ные логические функции: инверсию, конъюнкцию и дизъюнкцию. Данный набор представляет собой полный функциональный набор.
Система функций алгебры логики f1, f2, …, fm называется функционально полной, если любая логическая функция от произвольного числа n – аргументов может быть представлена суперпозицией функций f1, f2, …, fm.
Система логических функций, обладающая функциональной полнотой, называется функциональным базисом, а набор элементов, реализующих эти функции, называется эле-
ментным базисом.
Минимальным базисом называется такой базис из f1, f2, …, fn, для которого удаление хотя бы одной из функций fi, вхо-
110
дящих в этот базис, превращает систему функций f1, f2, …, fm в неполную.
Если осуществить преобразования над логическими функциями, заданными СДНФ и СКНФ по правилам де Моргана, взяв от них двойное отрицание, то получим функционально полные базисы, состоящие из одной или двух элементарных функций.
Функциональной полнотой обладают следующие элементные базисы:
1.И, ИЛИ, НЕ (основной базис);
2.И, НЕ;
3.ИЛИ, НЕ;
4.И-НЕ;
5.ИЛИ-НЕ;
6.1, И, .
До определенного момента времени для доказательства функциональной полноты системы элементарных функций f1, f2, …, fn использовался следующий эвристический прием.
Требовалось доказать, что если с помощью элементарных функций f1, f2, …, fn могли быть реализованы логические функции основного базиса (И, ИЛИ, НЕ), то в этом случае система функций f1, f2, …, fn считалась полной. Суть этого доказательства рассмотрим на примере логического базиса, состоящего из элемента И-НЕ.
1. Докажем, что с помощью элемента И-НЕ может быть реализована операция НЕ.
Дано y = a b ; пусть a=b, следовательно y = a a = a - реализована операция НЕ.
a & a
111
2. Докажем, что с помощью элемента И-НЕ может быть реализована операция И.
Дано y = a b ; рассмотрим функцию z = y = a b = a b - реализована операция И.
a |
|
a b |
& |
& |
b
3. Докажем, что с помощью элемента И-НЕ может быть реализована операция ИЛИ.
Необходимо получить операцию ИЛИ - y = a + b .
Рассмотрим функцию z = y = a +b = a b - реализована операция ИЛИ.
a |
& |
a +b |
|
|
|
|
|
& |
b &
Следовательно, базис И-НЕ является полным.
Для определения функционально полных систем логических функций необходимо для них определить наличие следующих пяти свойств:
1. Свойство сохранения нуля: данным свойством обл а-
дают те логические функции, для которых справедливо соотношение: f (0,0,...,0) = 0 , т.е. на нулевом наборе аргументов,
логическая функция принимает нулевые значения.
112
2. Свойство сохранения единицы: данным свойством обладают те логические функции, для которых справедливо соотношение: f (1,1,...,1) =1, т.е. на единичном наборе аргумен-
тов, логическая функция принимает единичные значения.
3. Свойство самодвойственности: данным свойством обладают те логические функции, для которых справедливо
соотношение: f (x1 , x2 ,..., xn ) = f (x1 , x2 ,..., xn ), т.е. самодвойственной является функция, у которой инвертирование значений всех аргументов приводит к инвертированию значений функции.
4.Свойство монотонности: функция обладает этим свойством, если для любой последовательности наборов, в каждом из которых аргументы не убывают, значения функции также не убывают, при этом полагаем, что 0<1.
5.Свойство линейности: данным свойством обладают
те логические функции, которые могут быть представлены в следующем виде:
f (x1, x2 ,..., xn ) = a0 a1x1 a2 x2 .... an xn , где ai {0,1}.
|
|
|
|
|
|
|
|
|
|
|
Таблица 8.1 |
|
Сводная таблица логических функций двух аргументов |
||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
Аргументы |
Значения |
Наименование |
|
Запись функций |
|
|
||||||
и функции |
аргументов |
функций |
|
|
|
|
|
|
|
|||
Специальные обо- |
|
В ДНФ или КНФ |
||||||||||
|
|
|
|
|
|
|
||||||
|
|
|
|
|
|
значения |
|
|
|
|
|
|
x1 |
0 |
0 |
1 |
1 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
x2 |
0 |
1 |
0 |
1 |
|
|
|
|
|
|
|
|
F0 |
0 |
0 |
0 |
0 |
Константа 0 |
F = 0 |
|
F0 |
= 0 |
|
|
|
|
|
|
|
|
|
0 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
F1 |
0 |
0 |
0 |
1 |
Конъюнкция, |
*, &, И |
|
F1 |
= x1 * x2 |
|||
|
логическое |
|
|
|
|
|
|
|
||||
|
|
|
|
|
умножение И |
|
|
|
|
|
|
|
F2 |
|
|
|
|
Запрет по x2 |
|
|
F |
= x * |
|
|
|
0 |
0 |
1 |
0 |
|
|
x |
2 |
|
||||
|
|
|
|
|
|
|
|
2 |
1 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
113 |
|
|
|
|
|
|
Продолжение табл. 8.1
F3 |
0 |
0 |
1 |
1 |
Повторитель |
|
F3 |
= x1 |
|
|
|
|
|
F3 = x1 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||||||||
|
x |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||
|
|
|
|
|
1 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
F4 |
0 |
1 |
0 |
0 |
Запрет по x |
|
|
|
|
|
|
|
|
|
|
|
F |
= |
|
|
|
|
|
* x |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||||||
|
|
|
|
|
|
|
|
|
|
|
x |
2 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||||||||||||||||||||
|
|
|
|
|
|
1 |
|
|
|
|
|
|
|
|
|
|
|
4 |
|
1 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||
F5 |
0 |
1 |
0 |
1 |
Повторитель |
|
F5 |
= x2 |
|
|
|
|
|
F5 |
= x2 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||||||||||
|
|
|
|
|
x2 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
F6 |
|
|
|
|
Исключающее |
F |
|
= x x |
|
|
F |
= x |
|
|
|
|
|
+ |
|
|
|
x |
|
|
|
|
|
|
||||||||||||||||||||
0 |
1 |
1 |
0 |
|
2 |
|
x |
|
|
|
|
x |
|
|
|
|
|
|
||||||||||||||||||||||||||||||
|
ИЛИ; сумма по |
6 |
|
1 |
|
|
|
|
6 |
|
1 |
|
|
|
2 |
|
|
|
1 |
|
|
|
|
2 |
|
|
|
|
|
|||||||||||||||||||
|
|
|
|
|
модулю два |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
F7 |
0 |
1 |
1 |
1 |
Дизъюнкция, |
|
F7 |
|
= x1 + x2 |
|
F7 |
= x1 + x2 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||||||||||||||||||||
лог. |
сложение, |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||||||||||||||||||||||||||||
|
|
|
|
|
ИЛИ |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
F8 |
|
|
|
|
Стрелка Пирса, |
F |
|
= x |
↓ x |
|
F8 = |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
= |
|
|
* |
|
|
|||||||||||||||
1 |
0 |
0 |
0 |
|
2 |
x1 + x2 |
x1 |
x2 |
||||||||||||||||||||||||||||||||||||||||
|
|
|
|
|
ИЛИ - НЕ |
|
8 |
|
|
|
1 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||||||||||
F9 |
|
|
|
|
равнозначностьЭквиваленция, |
↔, |
|
|
|
|
|
F9 |
|
= x1 x2 + |
|
|
|
|
||||||||||||||||||||||||||||||
1 |
0 |
0 |
1 |
|
|
|
|
|
|
x1 |
x2 |
|||||||||||||||||||||||||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
F10 |
|
|
|
|
Инверсия x2 |
|
F |
|
= |
|
|
|
|
|
|
F |
|
= |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||||
1 |
0 |
1 |
0 |
|
|
x |
2 |
|
|
|
|
|
x |
2 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||||||||||||||
|
|
|
|
|
|
|
|
10 |
|
|
|
|
|
|
|
10 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
F11 |
|
|
|
|
Импликация |
от |
F11 = x2 → x1 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||||||
1 |
0 |
1 |
1 |
|
F11 = x2 + x1 |
|
|
|
|
|
|
|||||||||||||||||||||||||||||||||||||
x2 |
к x1 |
|
|
|
|
|
|
|
|
|||||||||||||||||||||||||||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||
F12 |
1 |
1 |
0 |
0 |
Инверсия x1 |
|
F |
|
= |
|
|
|
|
|
|
F |
|
= |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||||
|
|
x |
|
|
|
|
|
|
x |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||||||||||||||||
|
|
|
|
|
|
|
|
12 |
1 |
|
|
|
|
|
12 |
|
|
|
|
|
|
|
1 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||
F13 |
|
|
|
|
Импликация |
от |
F13 |
= x1 → x2 |
|
F |
|
= x |
|
|
|
+ |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||||||||||||||
1 |
1 |
0 |
1 |
|
|
2 |
|
x |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||||||||||||||||||||||||
|
|
|
|
|
x1 |
к x2 |
|
|
|
|
|
|
|
|
|
|
|
13 |
|
|
|
|
|
|
|
|
|
|
|
|
1 |
|
|
|
|
|
|
|
|
|
|
|
|
|
||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||
F14 |
|
|
|
|
Штрих Шеффе- |
F14 |
= x1 / x2 |
|
F |
|
= |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||||||||||||||||||||
1 |
1 |
1 |
0 |
|
|
x * x |
2 |
|
|
|
|
|
|
|
|
|
|
|
||||||||||||||||||||||||||||||
|
|
|
|
|
ра,И-Н Е |
|
|
|
|
|
|
|
|
|
|
|
14 |
|
|
|
|
|
|
|
1 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||||
F15 |
1 |
1 |
1 |
1 |
Константа 1 |
|
F15 = 1 |
|
|
|
|
|
F15 = 1 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
В табл. 8.1 приведены элементарные логические функции одного и двух аргументов: таблицы истинности, представление в виде ДНФ или КНФ, названия наиболее используемых логических функций.
Рассмотрим наличие и отсутствие перечисленных выше пяти свойств у элементарных логических функций из таблицы 8.1. Результаты исследований занесем в таблицу 8 .2. Если функция обладает исследуемым свойством, то в соответствующей ячейке поставим “x”.
114
Таблица 8.2
x1 |
x2 |
F0 |
F1 |
F2 |
F3 |
F4 |
F5 |
F6 |
F7 |
F8 |
F9 |
F10 |
F11 |
F12 |
F13 |
F14 |
F15 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
0 |
1 |
0 |
0 |
0 |
0 |
1 |
1 |
1 |
1 |
0 |
0 |
0 |
0 |
1 |
1 |
1 |
1 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
1 |
0 |
0 |
0 |
1 |
1 |
0 |
0 |
1 |
1 |
0 |
0 |
1 |
1 |
0 |
0 |
1 |
1 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
1 |
1 |
0 |
1 |
0 |
1 |
0 |
1 |
0 |
1 |
0 |
1 |
0 |
1 |
0 |
1 |
0 |
1 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Св-во со- |
x |
x |
x |
x |
x |
x |
x |
x |
|
|
|
|
|
|
|
|
|
хранения 0 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Св-во со- |
|
x |
|
x |
|
x |
|
x |
|
x |
|
x |
|
x |
|
x |
|
хранения 1 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Св-во са- |
|
|
|
x |
|
x |
|
|
|
|
x |
|
x |
|
|
|
|
модвойст- |
|
|
|
|
|
|
|
|
|
|
|
|
|||||
венности |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Св-во |
|
x |
x |
|
x |
|
x |
|
x |
|
|
|
|
|
|
|
x |
монотон- |
|
|
|
|
|
|
|
|
|
|
|||||||
ности |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Св-во ли- |
x |
|
|
x |
|
x |
x |
|
|
x |
x |
|
x |
|
|
x |
|
нейности |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Наличие или отсутствие трех первых свойств можно определить по формулировке характерных свойств элементарных логических функций, влияющих на формирование функционально полных логических базисов.
Более подробно рассмотрим, как определяется наличие или отсутствие у логических функций четвертого свойства – свойства монотонности.
Из неубывающих значений аргументов логических функций строятся неубывающие наборы, состоящие из значений аргументов. Рассмотрим значения x1, x2 в таблице 8.2. Как видно из таблицы аргумент x1 не убывает, а аргумент x2 убывает. Для того, чтобы аргумент x2 не убывал, необходимо составлять наборы значений аргументов либо из 1,3,4 строк, либо из 1,2,4 строк таблицы 8.2.
115
Выпишем эти наборы значений:
x1 |
x2 |
x1 |
x2 |
0 |
0 |
0 |
0 |
0 |
1 |
1 |
0 |
1 |
1 |
1 |
1 |
В приведенных наборах аргумент x2 не убывает. Для того, чтобы логическая функция обладала свойством монотонности необходимо чтобы, для любой последовательности наборов, в каждом из которых аргументы функции не убывают, значения функции также не убывали. Далее рассмотрим, какие значения принимает логическая функция на сформированных наборах.
Для наглядности рассмотрим значения функции F5 из табл. 8.2:
x1 x2 F5 |
F5 x1 x2 |
||||
0 |
0 |
0 |
0 |
0 |
0 |
0 |
1 |
1 |
0 |
1 |
0 |
1 |
1 |
1 |
1 |
1 |
1 |
Как видно из приведенного примера функция F5 на неубывающих наборах значений аргументов принимает неубывающие значения функции, следовательно, логическая функция F5 обладает свойством монотонности.
Далее рассмотрим, как определяется наличие или отсутствие у логических функций пятого свойства – свойства линейности.
Логические функции обладают свойством линейности, если они могут быть представлены в следующем виде:
f (x1, x2 ,..., xn ) = a0 a1x1 a2 x2 .... an xn , |
(8.1) |
где ai {0,1}, i =0, n
116
Поскольку исследуемые нами логические функции зависят максимум от двух аргументов, то выражение (8.1) примет вид полинома Жегалкина (8.2):
|
f (x1, x2 ) = a0 a1x1 a2 x2 |
(8.2) |
||||||||||||||||||||
Коэффициенты ai {0,1}, |
i = |
|
определяются по табл. 8.3. |
|||||||||||||||||||
0,2 |
||||||||||||||||||||||
|
|
|
|
|
|
|
Таблица 8.3 |
|||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||
а2- коффи- |
а1- коффи- |
а0- коффи- |
|
Виды полинома (2.2), при |
||||||||||||||||||
циент |
циент |
|
циент |
|
соответствующих значени- |
|
||||||||||||||||
при x2 |
при x1 |
|
|
|
|
ях коэффициентов |
|
|||||||||||||||
|
|
|
|
|
|
ai {0,1}, i = |
|
|
|
|
|
|
|
|
||||||||
|
|
|
|
|
|
0,2 |
||||||||||||||||
0 |
0 |
0 |
|
f (x1 , x2 ) = 0 |
|
|||||||||||||||||
0 |
0 |
1 |
|
f (x1, x2 ) =1 |
|
|||||||||||||||||
|
|
|
|
|
|
|
||||||||||||||||
0 |
1 |
0 |
|
f (x1 , x2 ) = x1 |
|
|||||||||||||||||
0 |
1 |
1 |
|
f (x1 , x2 ) =1 x1 |
|
|||||||||||||||||
|
|
|
|
|
|
f (x1 , x2 ) = |
|
|
|
|
|
|
|
|
|
|||||||
|
|
|
|
|
|
x2 |
||||||||||||||||
1 |
0 |
0 |
|
f (x1 , x2 ) = x2 |
|
|||||||||||||||||
1 |
0 |
1 |
|
f (x1 , x2 ) = 1 x2 |
|
|||||||||||||||||
|
|
|
|
|
|
f (x1 , x2 ) = |
|
|
|
|
|
|
|
|||||||||
|
|
|
|
|
|
|
x1 |
|||||||||||||||
1 |
1 |
0 |
|
f (x1 , x2 ) = x1 x2 |
|
|||||||||||||||||
|
|
|
|
|
|
f (x1 , x2 ) = x1 |
|
|
|
+ x2 |
|
|
|
|||||||||
|
|
|
|
|
|
x2 |
x1 |
|||||||||||||||
1 |
1 |
1 |
|
f (x1 , x2 ) = 1 x1 x2 |
|
|||||||||||||||||
|
|
|
|
|
|
f (x1 , x2 ) = |
|
|
|
+ x2 x1 |
|
|||||||||||
|
|
|
|
|
|
x1 |
x2 |
|||||||||||||||
|
|
|
|
|
|
f (x1 , x2 ) = |
|
|
|
|||||||||||||
|
|
|
|
|
|
x1 x2 |
||||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||
|
|
117 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|