1.2 Базис и, или, не. Свойства элементарных функций алгебры логики
Пусть x - некоторая логическая переменная. Тогда:
1. , что означает возможность исключения из логического выражения всех членов, имеющих двойное отрицание, заменив их исходной величиной;
2. - правила подобных преобразований, которые позволяют сокращать длину логических выражений;
3. x0=x;
4. x1=1;
5. x . 0=0;
6. x .1=x;
7. ;
8. .
Дизъюнкция и конъюнкция обладают рядом свойств, аналогичных свойствам обычных арифметических операций сложения и умножения:
1). свойство ассоциативности (сочетательный закон):
x1(x2x3)=(x1x2)x3, x1(x2 x3)=(x1 x2) x3;
2). свойство коммутативности (переместительный закон):
x1x2=x2x1, x1x2=x2 x1;
3). свойство дистрибутивности (распределительный закон):
для конъюнкции относительно дизъюнкции
x1&(x2x3)=(x1&x2)(x1&x3);
для дизъюнкции относительно конъюнкции
x1x2&x3=(x1x2)&(x1x3).
Свойство дистрибутивности фактически определяет правила раскрытия скобок или взятия в скобки логических выражений.
Справедливость указанных свойств легко доказывается с помощью вышеизложенных аксиом.
Докажем, например, что
x1x2&x3=(x1x2)&(x1x3).
В самом деле, (x1x2)(x1x3) = x1x1 x1x3 x1x2 x2x3 = x1 x1x2 x1x3 x2x3 = x1(1 x2 x3) x2x3.
Аналогично можно доказать и другие законы.
Таким же образом доказывается правильность соотношений, известных как законы де Моргана:
, (5)
. (6)
Из законов де Моргана следует, что:
. (7)
, (8)
помощью которых появляется возможность выражать конъюнкцию через дизъюнкцию и отрицание или дизъюнкцию через конъюнкцию и отрицание.
Законы де Моргана и следствия из них справедливы для любого количества переменных:
, (9)
. (10)
Для логических функций устанавливаются соотношения, известные как законы поглощения:
x1 x1x2 = x1, (11)
x1&(x1x2) = x1. (12)
Очень важными в теории ФАЛ являются действия полного склеивания и неполного склеивания. Примеры выполнения этих действий с двумя конституентами 1 приведены ниже:
- полное склеивание; (13)
- неполное склеивание. (14)
Более важным для практики является неполное склеивание, так как для сложных ФАЛ исходные конституенты 1 Fi и Fj после получения результата склеивания друг с другом Fk сохраняются для сопоставления с другими минтермами в записи заданной ФАЛ и нового склеивания по одной из переменных, входящих в сопоставимые минтермы с отрицанием и без отрицания (отличающихся по одной переменной).
Рассмотренные основные соотношения позволяют описать равносильные булевы функции различными способами, вследствие чего открываются возможности выбора самых простых форм описания ФАЛ. Самые простые по форме ФАЛ реализуются на элементной базе по принципиальным схемам, имеющим самую низкую стоимость.
- Глава 1 5
- Глава 2 40
- Глава 3 88
- Введение
- Глава 1 логические основы цифровых автоматов
- 1.1 Основные понятия алгебры логики
- 1.2 Базис и, или, не. Свойства элементарных функций алгебры логики
- 1.3 Способы описания булевых функций
- 1.3.1 Табличное описание булевых функций
- 1.3.2 Аналитическое описание булевых функций
- 1.3.3 Числовая форма представления булевых функций
- 1.3.4 Графическая форма представления булевых функций
- 1.3.5 Геометрическое представление булевых функций
- 1.4 Минимизация функций алгебры логики
- 1.4.1 Минимизация с помощью минимизирующих карт
- 1.4.2 Минимизация функций алгебры логики по методу Квайна
- 1.4.3 Минимизация функций алгебры логики
- 1.5 Элементная база для построения комбинационных схем
- 1.5.1 Логические элементы и, или, не
- 1.5.1.1 Логические элементы и и и-не (Позитивная логика)
- 1.5.1.2 Логические элементы или, или-не (Позитивная логика)
- 1.5.2 Примеры технической реализации булевых функций
- 1.5.2.1 Функция исключающее-или (Сложение по модулю 2)
- 1.5.2.2 Минимизированная функция алгебры логики ф.(27) (Дешифратор второго рода)
- 1.5.3 Программируемые логические матрицы (плм)
- 1.5.3.1 Примеры плм
- 1.5.3.2 Процедуры программирования плм
- Глава 2 синтез цифровых автоматов
- 2.1 Определение абстрактного цифрового автомата
- 2.2 Методы описания цифровых автоматов
- 2.3 Синхронные и асинхронные цифровые автоматы
- 2.4 Связь между математическими моделями цифровых автоматов Мили и Мура
- 2.5 Минимизация абстрактных цифровых автоматов
- 2.5.1 Минимизация абстрактного автомата Мили
- 2.5.2 Минимизация абстрактного автомата Мура
- 2.6 Структурный синтез автоматов
- 2.6.1 Элементарные автоматы памяти
- 2.6.2 Синхронизация в цифровых автоматах
- 2.7 Структурный синтез цифровых автоматов по таблицам
- 2.8 Структурный синтез цифрового автомата по графу
- Глава 3 микропрограммные автоматы
- 3.1 Декомпозиция устройств обработки цифровой информации
- 3.2 Управляющие автоматы
- 3.3 Принцип действия управляющего автомата с хранимой в памяти логикой и микропрограммное управление
- 3.3.1 Горизонтальное микропрограммирование
- 3.3.2 Вертикальное микропрограммирование
- 3.3.3 Смешанное микропрограммирование
- 3.3.3.1 Вертикально - горизонтальное микропрограммирование
- 3.3.3.2 Горизонтально - вертикальное микропрограммирование
- 3.4 Управляющие автоматы с «жёсткой логикой»
- 3.5 Граф - схемы микропрограммных автоматов
- 3.6 Синтез микропрограммных автоматов по граф - схеме алгоритма
- 3.6.1 Синтез микропрограммного автомата Мили
- 3.6.2 Синтез микропрограммного автомата Мура
- 3.6.3 Минимизация микропрограммных автоматов
- Заключение