Логические выражения.
С помощью логических операций из простых высказываний можно построить логические выражения, которые так же называются булевскими функциями. Примером булевской функции может служить:
С = ((Ā ۷ В) → В)۷ А.
Как и в обычной математике существует порядок выполнения операций, так же и в булевской алгебре существует старшинство операций. Первыми выполняются операции в скобках, затем операции в следующем порядке: отрицание, конъюнкция и дизъюнкция, импликация, эквиваленция. Равносильные операции выполняются по порядку слева направо.
Приняты следующие эквивалентные преобразования (равносильности), которые могут быть доказаны при помощи таблиц истинности:
1. Ā = А закон двойного отрицания
2. А&В = В&А коммутативный закон для конъюнкции
3. А۷В = В۷А коммутативный закон для дизъюнкции
4. (А&В)&С = А&(В&С) ассоциативный закон для конъюнкции
5. (А۷В)۷С = А۷(В۷С) ассоциативный закон для дизъюнкции
6. А&(В۷С) = (А&В)۷(А&С)
7. А۷(В&С) = (А۷В)&(А۷С) дистрибутивные законы
8. А&В = А۷В
9. А۷В = А&В законы де Моргана
10. А&А = А закон идемпотенции для конъюнкции
11. А۷А = А закон идемпотенции для дизъюнкции
12. А&1 = А закон единицы для конъюнкции
13. А&0 = 0 закон нуля для конъюнкции
14. А۷1 = 1 закон единицы для дизъюнкции
15. А۷0 = А закон нуля для дизъюнкции
16. А۷Ā = 1 закон исключения третьего
17. А&Ā = 0 закон противоречия
18. А→В = Ā۷В
19. А↔В = (А→В)&(В→А) = (Ā۷В)&(А۷В) = (А&В)۷(Ā&В)
20. А۷(А&В) = А
21. А&(А۷В) А законы поглощения
22. А&(Ā۷В) = А&В
23. А۷(Ā&В) = А۷В
Существует несколько стандартных форм, к которым приводятся логические выражения с помощью эквивалентных преобразований:
Первая форма – дизъюнктивная нормальная форма (ДНФ), имеет стандартный вид А1۷А2۷…۷Аn, где каждое из составляющих высказываний есть конъюнкция простых высказываний и их отрицаний.
Вторая форма – конъюнктивная нормальная форма (КНФ), имеет вид А1&А2&…&Аn, где каждое из составляющих высказываний есть дизъюнкция простых высказываний и их отрицаний.
Способы задания булевских функций.
Наиболее распространенными способами задания булевских функций является табличное и алгебраическое.
Задать булевскую функцию можно, определяя ее значения для всех наборов значений аргументов. Каждый из аргументов может иметь два значения – 0 и 1; следовательно, nаргументов могут принимать 2nразличных наборов. Рассмотрим на примере функции, имеющей 3 аргумента (Х1, Х2и Х3), общее число наборов составляет 23 = 8. Для составления алгебраической записи булевской функции необходима таблица истинности данной функции. Предположим, что для функцииF имеется следующая таблица истинности:
|
№ |
Х1 |
Х2 |
Х3 |
F |
|
1 |
0 |
0 |
0 |
0 |
|
2 |
0 |
0 |
1 |
1 |
|
3 |
0 |
1 |
0 |
0 |
|
4 |
0 |
1 |
1 |
1 |
|
5 |
1 |
0 |
0 |
0 |
|
6 |
1 |
0 |
1 |
1 |
|
7 |
1 |
1 |
0 |
0 |
|
8 |
1 |
1 |
1 |
1 |
Для составления алгебраической формы по результатам таблицы истинности сделаем следующее:
В комбинациях, где функция принимает значение 1: аргумент заменим именем функции, если он равен 1, а ноль – заменим на имя с отрицанием. Все элементы соединим знаками дизъюнкции. Для нашего примера получится:
F(Х1,Х2,Х3) = (Х1&Х2&Х3)۷(Х1&Х2&Х3)۷(Х1&Х2&Х3)۷(Х1&Х2&Х3).
Функция представляет дизъюнктивную нормальную форму (в данном случае форма является совершенной, так как в каждой группе представлены одновременно все 3 аргумента). Каждая группа дизъюнкций называется коституентой единицы.
Аналогично, для комбинаций, где функция принимает значение нуля, можно построить алгебраическую форму:
F(Х1,Х2,Х3) = (Х1۷Х2۷Х3)& (Х1۷Х2۷Х3)& (Х1۷Х2۷Х3)& (Х1۷Х2۷Х3).
Функция при такой записи представляет собой конъюнктивную нормальную форму. Каждая конъюнкция называется конституентой нуля.
Основы булевой алгебры лежат в основе не только информационных процессов, но и используются при создании цифровых устройств.