- •Часть II
- •Алгебра двузначной логики
- •Функции алгебры логики
- •Способы задания функций алгебры логики
- •Эквивалентность функций
- •Реализация функций формулами
- •Эквивалентность формул и тождества
- •Упрощение формул
- •Двойственные функции и принцип двойственности
- •Применение принципа двойственности
- •Аналитическая запись функций алгебры логики
- •Аналитическое построение сднф и скнф
- •Теорема о тройке связок
- •Полные системы функций и полиномы Жегалкина
- •Замыкание систем функций алгебры логики
- •Важнейшие замкнутые классы
- •Теорема Поста о полноте
- •Минимизация булевых функций
- •Основные понятия
- •Метод неопределенных коэффициентов
- •Тупиковые днф и алгоритм наискорейшего спуска
- •Геометрическое представление функций алгебры логики
- •Аналитическое построение сокращенной днф
- •Локальные алгоритмы
- •Алгоритм Куайна
- •Диаграммы Вейча–Карно
- •Построение днф по карте Карно
- •Задачи и упражнения
- •Список литературы
- •Часть II
- •400131, Волгоград, просп. Им. В.И.Ленина, 28
- •400131, Волгоград, ул. Советская, 35
-
Эквивалентность формул и тождества
Рассмотрим формулы: и . Их таблицы истинности представлены ниже в таблице 12.
x |
y |
х |
у |
|
|
0 |
0 |
1 |
1 |
1 |
1 |
0 |
1 |
1 |
0 |
1 |
1 |
1 |
0 |
0 |
1 |
0 |
0 |
1 |
1 |
0 |
0 |
1 |
1 |
Таблица 12 |
|
Как видно из таблицы 12, на одинаковых наборах значений переменных обе формулы принимают одинаковые истинностные значения, т.е. реализуют одну и ту же истинностную функцию.
Две формулы А и В называются эквивалентными, если функции fA и fB, соответствующие им, эквивалентны или равны, т.е. fA=fB. Для обозначения эквивалентных формул традиционно используется запись А=В, которую называют тождеством.
Следующие тождества характеризуют важнейшие свойства элементарных функций: {0, 1, , &, }. (Обозначим «∘» любую из функций: {&, , }.)
((x∘y)∘z)=(x∘(y∘z)) – свойство ассоциативности;
(x∘y)=(y∘х) – коммутативность;
конъюнкция и дизъюнкция дистрибутивны друг относительно друга: ((x y) & z) = ((x & z) (y & z)) ((x & y) z) = ((x z) & (y z));
– закон двойного отрицания;
– законы Де Моргана для конъюнкции и дизъюнкции;
(х & х) = x; (x x) = x – законы идемпотентности;
– закон исключенного третьего;
– закон противоречия;
(х & 0) = 0, (x 0) = x – умножение на ноль и сложение с нулем;
(х & 1) = х, (x 1) = 1 – умножение на единицу и сложение с единицей;
((х & y) x) = x, ((х y) & x) = x – законы поглощения.
Все тождества легко проверяются с помощью таблиц истинности.
-
Упрощение формул
Введем некоторые соглашения о записи и вычислениях формул.
В формулах будем опускать внешнюю пару скобок, т.е. вместо формулы (ху) будем писать выражение ху. Аналогично в выражениях со знаком отрицания вместо будем записывать .
По закону ассоциативности для операции «∘» вместо формулы ((x ∘ y) ∘ z) или (x∘(y ∘ z)) можно использовать выражение без скобок: x∘ y ∘ z. Для восстановления формулы достаточно расставить скобки, порядок которых не является существенным для вычислений.
Введем также соглашения о старшинстве операций: если в выражении с помощью скобок специально не указан порядок выполнения операций, то одинаковые по старшинству операции выполняются последовательно слева направо. Если в выражении имеются различные операции, то сначала выполняется отрицание, затем конъюнкция, дизъюнкция, импликация и т.д., самой последней выполняется эквиваленция. Скобки восстанавливаются по тому же правилу, например, в выражении хуzt скобки восстанавливаются в следующем порядке:
х(у)zt
(х(у))zt
((х(у))z)t
(((х(у))z)t)
Ввиду введенного старшинства операций не всякая формула может быть записана без скобок. Например, в выражениях х(уz) или х&(yz) дальнейшее исключение скобок невозможно, т.к. это может повлиять на значение, вычисленное по формуле.
В дальнейшем для компактности будем использовать следующую запись вместо х1&x2&…&xs, а также вместо х1x2…xs.
Из свойств элементарных функций следует ряд простых правил преобразования формул:
а) если один из сомножителей логического произведения равен нулю, то значение произведения также равно нулю;
б) если логическое произведение содержит не менее двух сомножителей, один из которых равен единице, то этот сомножитель можно сократить;
в) если логическая сумма содержит не менее двух слагаемых, одно из которых принимает значение ноль, то его можно сократить;
г) если хотя бы одно из слагаемых логической суммы принимает значение единица, то и вся логическая сумма равна единице;
д) пусть U1 – подформула формулы U; если в формуле U заменить любые вхождения подформулы U1 эквивалентной ей формулой В1, то в результате будет получена формула В, эквивалентная исходной формуле U.
Перечисленные свойства и правила позволяют преобразовывать формулы, получая новые тождества.
Рассмотрим эквивалентные преобразования формулы: 1= 2= 3= 4= 5=
Тождество 1 записано по правилу сокращения единичного сомножителя, тождество 2 – по правилу замены подформулы эквивалентной формулой, а именно: здесь для замены использовался закон исключенного третьего. В тождестве 3 применяется закон дистрибутивности. Тождество 4 получено по закону коммутативности. И, наконец, тождество 5 записано по закону поглощения, причем для наглядности «поглощающие элементы» подчеркнуты одинарной и двойной чертой.
Помимо описанных правил эквивалентных преобразований формул имеются также другие способы получения новых тождеств, которые основаны на понятии двойственности.