Преобразование функций алгебры логики

Тождества алгебры логики

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

Тождества имеют вид:

Преобразование функций алгебры логики - student2.ru Преобразование функций алгебры логики - student2.ru

Преобразование функций алгебры логики - student2.ru Преобразование функций алгебры логики - student2.ru ,

Преобразование функций алгебры логики - student2.ru Преобразование функций алгебры логики - student2.ru ,

Преобразование функций алгебры логики - student2.ru Преобразование функций алгебры логики - student2.ru .

Из этих тождеств следует:

- если аргумент равен нулю, то его отрицание равно единице и наоборот;

- если хотя бы один сомножитель равен нулю, то произведение всегда будет равно нулю;

- если хотя бы одно слагаемое равно единице, то сумма всегда будет равна единице.

Законы алгебры логики

Переместительный закон:

Преобразование функций алгебры логики - student2.ru (2.1)

Преобразование функций алгебры логики - student2.ru (2.2)

Из этого закона следует, что в выражениях алгебры логики допустима перестановка мест слагаемых и сомножителей.

Сочетательный закон:

Преобразование функций алгебры логики - student2.ru (2.3)

Преобразование функций алгебры логики - student2.ru (2.4)

Выражения (2.3) и (2.4) свидетельствуют о том, что при такой записи функций дизъюнкции и конъюнкции скобки можно опустить.

Распределительный закон:

Преобразование функций алгебры логики - student2.ru (2.5)

Преобразование функций алгебры логики - student2.ru (2.6)

Выражение (2.5) позволяет раскрывать скобки и выносить за скобки отдельные аргументы. Справедливость выражения (2.6) можно доказать с помощью таблицы истинности.

Таблица 2.1.

Наборы аргументов   Левая часть выражения (2.6)   Правая часть выражения (2.6)
Преобразование функций алгебры логики - student2.ru Преобразование функций алгебры логики - student2.ru Преобразование функций алгебры логики - student2.ru Преобразование функций алгебры логики - student2.ru Преобразование функций алгебры логики - student2.ru Преобразование функций алгебры логики - student2.ru
0 0 0
0 0 1
0 1 0
0 1 1
1 0 0
1 0 1
1 1 0
1 1 1

Из таблицы 2.1. следует, что левая часть выражения (2.6) на всех наборах аргументов равна правой части. Таким образом доказана справедливость данной записи распределительного закона.

Закон инверсии (правило Де-Моргана):

Преобразование функций алгебры логики - student2.ru (2.7)

Преобразование функций алгебры логики - student2.ru (2.8)

Для доказательства справедливости выражений (2.7) и (2.8) построим таблицы истинности, соответственно таблица 2.2. и таблица 2.3.

Таблица 2.2.

Наборы аргументов   Левая часть   Правая часть
Преобразование функций алгебры логики - student2.ru Преобразование функций алгебры логики - student2.ru Преобразование функций алгебры логики - student2.ru Преобразование функций алгебры логики - student2.ru Преобразование функций алгебры логики - student2.ru Преобразование функций алгебры логики - student2.ru
0 0
0 1
1 0
1 1

Левая и правая части выражения (2.7) равны на всех наборах аргументов.

Таблица 2.3.

Наборы аргументов   Левая часть   Правая часть
Преобразование функций алгебры логики - student2.ru Преобразование функций алгебры логики - student2.ru Преобразование функций алгебры логики - student2.ru Преобразование функций алгебры логики - student2.ru Преобразование функций алгебры логики - student2.ru Преобразование функций алгебры логики - student2.ru
0 0
0 1
1 0
1 1

Из таблицы 2.3. следует, что выражение (2.8) справедливо.

Закон двойного отрицания:

Преобразование функций алгебры логики - student2.ru .

Закон повторения:

Преобразование функций алгебры логики - student2.ru (2.9)

Преобразование функций алгебры логики - student2.ru (2.10)

Выражения (2.9) и (2.10) в доказательстве не нуждаются.

Закон поглощения:

Преобразование функций алгебры логики - student2.ru (2.11)

Преобразование функций алгебры логики - student2.ru (2.12)

Закон поглощения (2.11) и (2.12) докажем аналитическим путем.

Преобразование функций алгебры логики - student2.ru .

Преобразование функций алгебры логики - student2.ru .

Закон склеивания:

Преобразование функций алгебры логики - student2.ru (2.13)

Доказательство аналитическое

Преобразование функций алгебры логики - student2.ru . (2.14)

Теорема разложения в ряд функции алгебры

Логики

Любая функция алгебры логики может быть разложена в ряд на основании теоремы разложения. Теорема разложения может быть представлена двумя формами следующим образом:

Преобразование функций алгебры логики - student2.ru (2.15)

Преобразование функций алгебры логики - student2.ru (2.16)

В выражениях (2.15) и (2.16) функция разложена по переменной х1. Тождества теоремы разложения доказываются путем подстановки в левые и правые части тождеств в начале Преобразование функций алгебры логики - student2.ru , Преобразование функций алгебры логики - student2.ru , а затем Преобразование функций алгебры логики - student2.ru , Преобразование функций алгебры логики - student2.ru . В обоих случаях тождества будут одинаковые.

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

Пример 2.1. Разложить функцию Преобразование функций алгебры логики - student2.ru сначала по х1, а затем по х2.

Преобразование функций алгебры логики - student2.ru

В результате разложения заданной функции получили ее стандартную форму.

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

Преобразование функций алгебры логики - student2.ru (2.17)

Преобразование функций алгебры логики - student2.ru (2.18)

Преобразование функций алгебры логики - student2.ru (2.19)

Преобразование функций алгебры логики - student2.ru (2.20)

Докажем справедливость выражения (2.17). Для этого функцию Преобразование функций алгебры логики - student2.ru левой части данного выражения разложим по переменной хi и в результате получим

Преобразование функций алгебры логики - student2.ru Преобразование функций алгебры логики - student2.ru Преобразование функций алгебры логики - student2.ru (2.21)

Левую и правую части выражения (2.21) умножим на хi согласно (2.17) и с учетом тождества Преобразование функций алгебры логики - student2.ru и закона повторения получим:

Преобразование функций алгебры логики - student2.ru Преобразование функций алгебры логики - student2.ru

Преобразование функций алгебры логики - student2.ru .

Аналогично можно доказать соотношения (2.18) ¸ (2.20).

Соотношения (2.17) ¸ (2.20) позволяют сделать следующие выводы:

1. Если в логическом выражении какой-то из аргументов находится в конъюнктивной связи с одноименными аргументами или их отрицаниями, то при упрощении логического выражения вместо одноименных аргументов записывается 1, а вместо их отрицания 0.

2. Если в логическом выражении отрицание какого-либо аргумента находится в конъюнктивной связи с одноименными аргументами или их отрицаниями, то при упрощении логического выражения вместо одноименных аргументов ставится 0, а вместо их отрицаний 1.

3. Если в логическом выражении какой-то из аргументов находится в дизъюнктивной связи с одноименными аргументами или их отрицаниями, то при упрощении логических выражений вместо одноименных аргументов записывается 0, а вместо их отрицаний 1.

4. Если в логическом выражении отрицание какого-либо аргумента находится в дизъюнктивной связи с одноименными аргументами или их отрицаниями, то при упрощении логического выражения вместо одноименных аргументов записывается 1, а вместо их отрицаний 0.

Пример 2.2. Упростить логическое выражение (логическую функцию) Преобразование функций алгебры логики - student2.ru .

Используя соотношение (2.17) получим Преобразование функций алгебры логики - student2.ru

Преобразование функций алгебры логики - student2.ru .

Пример 2.3. Упростить логическую функцию Преобразование функций алгебры логики - student2.ru

Преобразование функций алгебры логики - student2.ru .

Применяя соотношение (2.18) получим Преобразование функций алгебры логики - student2.ru Преобразование функций алгебры логики - student2.ru =

Преобразование функций алгебры логики - student2.ru .

Пример 2.4. Упростить логическую функцию Преобразование функций алгебры логики - student2.ru

Преобразование функций алгебры логики - student2.ru .

Применяя соотношение (2.19) получим Преобразование функций алгебры логики - student2.ru Преобразование функций алгебры логики - student2.ru =

Преобразование функций алгебры логики - student2.ru .

Наши рекомендации