- •3. Алгебра логики
- •3.1. Понятие о простом и сложном высказывании
- •Упражнения
- •3.2. Логические операции над высказываниями
- •& 0 0 0 0 1 0 1 0 0 1 1 1Таблица истинности для конъюнкции
- •Упражнения
- •Упражнения
- •3.4. Аксиомы и законы алгебры логики
- •3.4.1. Правила склеивания для элементарных конъюнкций и
- •3.4.2. Правила поглощения для элементарных конъюнкций и
- •3.4.3. Правило развёртывания
- •Все ке для двух высказываний
- •Развёртывание элементарной дизъюнкции
- •Упражнения
- •3.5. Функции алгебры логики. Нормальные формы логических функций
- •Общая запись любой логической функции в сндф имеет вид
- •Пример. По заданной таблице истинности составить сндф функций
- •Снкф для выше приведенной таблицы истинности будут иметь вид
- •Упражнения
- •3.6. Минимизация логических функций
- •3.6.1. Расчетный метод минимизации
- •3.6.2. Табличный метод минимизации
- •3.6.3. Расчетно-табличный метод минимизации (метод Квайна)
- •Упражнения
- •3.7. Некоторые применения алгебры логики
- •Упражнения
- •Контрольные вопросы
Все ке для двух высказываний
Высказывания |
КЕ | ||||
|
|
|
|
|
|
0 |
0 |
1 |
0 |
0 |
0 |
0 |
1 |
0 |
1 |
0 |
0 |
1 |
0 |
0 |
0 |
1 |
0 |
1 |
1 |
0 |
0 |
0 |
1 |
Таблица 8
Все КН для двух высказываний
Высказывания |
КН | ||||
|
|
|
|
|
|
0 |
0 |
0 |
1 |
1 |
1 |
0 |
1 |
1 |
0 |
1 |
1 |
0 |
0 |
1 |
1 |
0 |
1 |
1 |
1 |
1 |
1 |
1 |
0 |
Развёртывание элементарных конъюнкций
1. В развертываемую элементарную конъюнкцию ранга вводятся в качестве дополнительных сомножителейединиц, где– число высказываний и.
2. Каждая единица представляется в виде , где– высказывание, отсутствующее в исходной конъюнкции.
3. Производится раскрытие всех скобок на основе распределительного закона 1-го рода, что приводит к развертыванию исходной конъюнкции ранга в логическую суммуКЕ.
Пример. Развернуть конъюнкцию . Здесь предполагается, что число высказываний, но два из них отсутствуют, тогда:
1.
2. .
3.
.
Развёртывание элементарной дизъюнкции
1. В развертываемую дизъюнкцию ранга вводится n-r нулей.
2. Каждый нуль представляется произведением , где– высказывание, отсутствующее в исходной дизъюнкции.
3. Полученная сумма преобразуется с помощью распределительного закона 2-го рода в логическое произведение КН.
Пример. Развернуть дизъюнкцию . Здесь число высказываний, отсутствует высказывание:
Упражнения
1. Используя алгебраические преобразования, доказать тождественную истинность или тождественную ложность формул:
1); 2); 3);
4); 5);
6); 7); 8);
9).
2. Доказать равносильности формул, не используя таблицы истинности:
1); 2); 3); 4);
5); 6); 7);
8); 9); 10);
11).
3. Упростить формулы:
1) 2); 3); 4);
5).
4. Привести следующие ниже формулы к базисам
1); 2); 3).
5. Развернуть конъюнкцию:
1) ; 2) .
6. Развернуть дизъюнкцию:
1) ; 2) .
3.5. Функции алгебры логики. Нормальные формы логических функций
Логическая функция [функция алгебры логики (ФАЛ)] – это выражение, представляющее собой сложное высказывание, состоящее из нескольких простых высказываний, связанных соединительными словами. Это сложное высказывание принимает значения 0 или 1 на всех наборах логических значений всех простых высказываний.
Как нетрудно заметить, приведенное определение ФАЛ полностью совпадает с определением формулы, данным в подразд. 3.3. Таким образом, всякая формула алгебры логики есть функция алгебры логики, в которой простые высказывания воспринимаются уже как переменные. Это правомочно, так как каждое из них принимает два значения: 0 или 1. А в зависимости от этого логические значения выражения тоже будут принимать значения 0 или 1, т.е. выражение является функцией в общепринятом смысле.
Набор логических переменных, или, иначе входной набор, – это определенная комбинация значений переменных в логической функции. Максимальное число различных входных наборов есть величина, где– число переменных.
Полностью определенная функция – это логическая функция, принимающая значение 0 или 1 на всех входных наборах.
Частично определенная функция – это логическая функция, значения которой определены не на всех входных наборах. Такие наборы называют безразличными.
Частично определенную логическую функцию можно сделать полностью определенной, приписав безразличным наборам произвольные значения: 0 или 1.
Используя законы и аксиомы алгебры логики и их следствия, можно получать логические выражения в различных формах. Среди них имеются такие формы, к которым можно свести любую логическую функцию. Такие формы определяют канонический вид логической функции. В алгебре логики каноническими принято считать нормальную дизъюнктивную форму (НДФ) и нормальную конъюнктивную форму (НКФ) и соответственно совершенную НДФ (СНДФ) и совершенную НКФ (СНКФ).
НДФ – это дизъюнкция нескольких элементарных конъюнкций. Эта форма называется нормальной, так как все ее члены имеют вид элементарных конъюнкций. Вследствие того, что все члены соединены в одну функцию знаком дизъюнкции, форма носит название дизъюнктивной. И, наконец, форма называется совершенной, если её члены имеют высший ранг, являясь конституентами единицы или нуля.