Логические выражения

С помощью логических операций из простых высказываний можно построить логические выражения, которые так же называются булевскими функциями. Примером булевской функции может служить:

С = ((Ā ۷ В) → В) ۷ А.

Как и в обычной математике существует порядок выполнения операций, так же и в булевской алгебре существует старшинство операций. Первыми выполняются операции в скобках, затем операции в следующем порядке: отрицание, конъюнкция и дизъюнкция, импликация, эквиваленция. Равносильные операции выполняются по порядку слева направо.

Приняты следующие эквивалентные преобразования (равносильности), которые могут быть доказаны при помощи таблиц истинности:

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 аргументов могут принимать 2ⁿ различных наборов. Рассмотрим на примере функции, имеющей 3 аргумента (Х₁, Х₂ и Х₃), общее число наборов составляет 2³ = 8. Для составления алгебраической записи булевской функции необходима таблица истинности данной функции. Предположим, что для функции F имеется следующая таблица истинности:

№	Х1	Х2	Х3	F

Для составления алгебраической формы по результатам таблицы истинности сделаем следующее:

В комбинациях, где функция принимает значение 1: аргумент заменим именем функции, если он равен 1, а ноль – заменим на имя с отрицанием. Все элементы соединим знаками дизъюнкции. Для нашего примера получится:

F (Х₁,Х₂,Х₃) = (Х₁&Х₂&Х₃)۷(Х₁&Х₂&Х₃)۷(Х₁&Х₂&Х₃)۷(Х₁&Х₂&Х₃).

Функция представляет дизъюнктивную нормальную форму (в данном случае форма является совершенной, так как в каждой группе представлены одновременно все 3 аргумента). Каждая группа дизъюнкций называется коституентой единицы.

Аналогично, для комбинаций, где функция принимает значение нуля, можно построить алгебраическую форму:

F (Х₁,Х₂,Х₃) = (Х₁۷Х₂۷Х₃)& (Х₁۷Х₂۷Х₃)& (Х₁۷Х₂۷Х₃)& (Х₁۷Х₂۷Х₃).

Функция при такой записи представляет собой конъюнктивную нормальную форму. Каждая конъюнкция называется конституентой нуля.

Основы булевой алгебры лежат в основе не только информационных процессов, но и используются при создании цифровых устройств.

Дата добавления: 2014-01-06