Файл: С. Д. Данилова С. С. Михайлова УланУдэ 2022дискретнаяматематика.pdf
ВУЗ: Не указан
Категория: Не указан
Дисциплина: Не указана
Добавлен: 04.12.2023
Просмотров: 280
Скачиваний: 10
ВНИМАНИЕ! Если данный файл нарушает Ваши авторские права, то обязательно сообщите нам.
43
Конъюнкции ????
1
????
2
????
2
̅̅̅????
4,
????
1
????
1
не являются элементарными, так как в первой конъюнк- ции вхождение переменной ????
2
, а во второй конъюнкции вхождение переменной ????
1
не един- ственны.
Определение 2.10. Число переменных, образующих элементарную конъюнкцию, называется рангом конъюнкции.
Пример
Ранги приведенных конъюнкций равны 3, 2, 1 и 0 соответственно:
Определение 2.11. Дизъюнктивной нормальной формой (ДНФ) логической функции
????(????
1
, … , ????
????
) называется формула, имеющая вид дизъюнкции элементарных конъюнкций.
При этом число элементарных конъюнкций называется длиной ДНФ.
Пример
ДНФ длины 3:
Определение 2.12. Минтермом, или полной конъюнкцией логической функции
????(????
1
, … , ????
????
), называется элементарная конъюнкция ранга n.
Пример
При n = 4 минтермами являются следующие конъюнкции:
Таким образом, СДНФ функции – это ДНФ, в которой каждая элементарная конъюнк- ция является минтермом.
В п. 2.1.5.4 покажем, что ДНФ функции не единственна в отличие от СДНФ.
Определение 2.12. Элементарной дизъюнкцией называется дизъюнкция переменных или их отрицаний, в которой каждая переменная встречается не более одного раза.
Пример
Определение 2.13. Число переменных, образующих элементарную дизъюнкцию, назы- вается рангом дизъюнкции.
44
Пример
Ранги дизъюнкций равны трем и одному соответственно:
Определение 2.15. Конъюнктивной нормальной формой (КНФ) логической функции
????(????
1
, … , ????
????
) называется формула, имеющая вид конъюнкции элементарных дизъюнкций.
При этом число элементарных дизъюнкций называется длиной КНФ.
Пример
КНФ длины 4:
Определение 2.16. Макстермом, или полной дизъюнкцией логической функции
????(????
1
, … , ????
????
), называется элементарная дизъюнкция ранга n.
Пример
При
n = 4
макстермами являются следующие дизъюнкции:
45
Определение 2.17. Формулы, содержащие кроме переменных только знаки конъюнк- ции, дизъюнкции и отрицания, называются булевыми формулами, а сами операции – конъ- юнкция, дизъюнкция и отрицание – булевыми операциями.
2.1.5.3. Булева алгебра функций
Определение 2.18. Алгебра, основным множеством которой является все множество логических функций, а операциями – дизъюнкция, конъюнкция и отрицание, называется
булевой алгеброй логических функций:
46
Равенства (1)–(10) справедливы при подстановке вместо переменных любых логиче- ских функций и, следовательно, любых формул, представляющих эти функции.
47
Необходимо соблюдать следующее правило подстановки: при подстановке формулы
F
вместо переменной x все вхождения x в исходное соотношение должны быть одновре- менно заменены формулой
F
Правило подстановки позволяет получить из соотношений (1)–(10) новые эквивалент- ные соотношения.
Получить формулы, эквивалентные данной формуле, используя эквивалентные соот- ношения, позволяет правило замены подформул:
Если какая-либо формула
F
содержит подформулу F
1
, то замена F
1
на эквивалентную ей формулу F
2
не изменит значения формулы
F
. Поэтому формула
F¢
, полученная из
F
та- кой заменой, эквивалентна формуле
F
. В этом случае замена всех вхождений исходной под- формулы необязательна.
2.1.5.4. Основные эквивалентные преобразования в булевой алгебре
Рассмотрим некоторые основные эквивалентные преобразования в булевой алгебре и новые соотношения, полученные с их помощью из соотношений (1)–(10), продолжая сквоз- ную нумерацию свойств булевых формул. Приведем доказательство некоторых эквива- лентных соотношений. При выполнении эквивалентных преобразований над знаками ра- венства запишем номера используемых эквивалентных соотношений.
48
49
II. Приведение к ДНФ (СДНФ).
Чтобы привести формулу к ДНФ, необходимо с помощью:
− закона двойного отрицания (6) и правил де Моргана (8) все отрицания довести до переменных, затем раскрыть скобки;
− правил идемпотентности (5), законов противоречия (9) и «исключенного третьего»
(10) удалить лишние конъюнкции и повторения переменных в конъюнкциях;
− свойств констант удалить константы.
50
Контрольные
вопросы
1. Какое множество является несущим множеством алгебры логики?
2. Что такое логическая функция?
3. Как обозначается множество всех логических функций?
4. Сколько существует логических функций n переменных?
5. Какие существуют способы задания логических функций?
6. Какие переменные логической функции называются фиктивными, какие – суще- ственными?
7. Какие наборы переменных логической функции называются соседними?
8. Как по таблице истинности можно определить фиктивные и существенные перемен- ные?
9. Что называется суперпозицией функций?
51 10. Что является логической формулой?
11. Какие формулы называются эквивалентными?
12. Какие методы позволяют получить новые эквивалентные соотношения?
13. Какие существуют способы доказательства эквивалентности формул?
14. Что называется разложением логической функции?
15. Что такое булева алгебра функций?
16. Что является типом булевой алгебры?
17. Какие операции определены в булевой алгебре?
18. Что такое элементарная конъюнкция и элементарная дизъюнкция, минтерм и макс- терм?
19. Что такое ранг конъюнкции и ранг дизъюнкции?
20. Как по таблице истинности можно построить СДНФ и СКНФ функции?
21. Какие эквивалентные преобразования позволяют упростить формулу?
22. Каким образом булеву формулу можно привести к ДНФ (СДНФ), КНФ (СКНФ)?
52
1 2 3 4 5 6 7 8 9 ... 12
Тема 2.2. Классы функций алгебры логики. Функциональная полнота
2.2.1. Двойственные функции. Класс самодвойственных функций
Определение 2.19. Логическая функция ????(????
1
, … , ????
????
) называется двойственной к функ- ции ????
∗
(????
1
, … , ????
????
) , если:
Пример
1. Построим таблицу функции, двойственной стрелке Пирса:
В результате выполненных замен видим, что стрелка Пирса двойственна штриху
Шеффера.
2. Парами двойственных функций являются:
− константы 0 и 1;
− дизъюнкция и конъюнкция;
− сложение по модулю 2 и эквиваленция;
− стрелка Пирса и штрих Шеффера.
Определение 2.20. Если функция двойственная самой себе, то такая функция называ- ется самодвойственной:
53
Множество всех самодвойственных функций образует класс самодвойственных функ-
ций – класс S.
Принцип двойственности
Если в формуле
F
заменить знаки всех логических функций на знаки двойственных им функций, то получится формула F
*
, реализующая функцию, двойственную той, которая реализуется формулой
F
Принцип двойственности в булевой алгебре: если в формуле
F
все конъюнкции заме- нить на дизъюнкции, дизъюнкции – на конъюнкции, 1 – на 0, 0 – на 1, то получится формула
F
*
, реализующая функцию, двойственную той, которая реализуется формулой
F
Следствие из принципа двойственности
Если функции равны, то и двойственные им функции равны.
54
2.2.2. Алгебра Жегалкина. Класс линейных функций
Определение 2.21. Алгебра, основным множеством которой является все множество логических функций, а операциями – конъюнкция и сложение по mod 2, называется алгеб-
рой Жегалкина:
Если в произвольной формуле алгебры Жегалкина раскрыть скобки и произвести все возможные упрощения по вышеприведенным соотношениям, то получится формула, име- ющая вид суммы произведений, т. е. полинома по mod 2, называемого полиномом Жегал- кина.
Определение 2.22. Элементарная конъюнкция называется монотонной, если она не со- держит отрицаний.
Определение 2.23. Полиномом Жегалкина функции ????(????
1
, … , ????
????
) называется формула вида:
55
Теорема:
Для всякой логический функции существует полином Жегалкина, и притом един- ственный.
Рассмотрим методы построения полинома Жегалкина.
Метод, базирующийся на преобразовании ДНФ.
Метод неопределенных коэффициентов
56
Пример
В общем виде полином Жегалкина функции трех переменных имеет вид:
Перепишем систему без нулевых слагаемых и единичных множителей:
57
Решая эту систему, получаем значения коэффициентов:
Коэффициенты подставим в исходный полином и получаем такой же полином Жегал- кина, как и в предыдущем примере:
Определение 2.23. Функция ????(????
1
, … , ????
????
) называется линейной, если ее полином Жегал- кина имеет вид:
Множество всех линейных функций образует класс линейных функций – класс L.
Пример
1. Все функции от одной переменной линейны.
2. Линейными функциями от двух переменных являются сложение по модулю 2 и эк- виваленция.
2.2.3. Монотонные функции. Класс монотонных функций
Определение 2.25. Функция ????(????
1
, … , ????
????
) называется монотонной, если для любых
Множество всех монотонных функций образует класс монотонных функций – класс M.
Пример
1. Константы 0, 1 и функция x монотонны. Функция x немонотонна. Дизъюнкция и конъюнкция любого числа переменных являются монотонными функциями.
2. Рассмотрим две функции от трех переменных:
58
Проверка монотонности функции непосредственно по определению требует анализа таблицы истинности функции и может оказаться довольно громоздким делом. Поэтому по- лезной для определения монотонности является следующая теорема.
Теорема:
Всякая булева формула, не содержащая отрицаний, представляет монотонную функ- цию, отличной от 0 и 1; и, наоборот, для любой монотонной функции, отличной от 0 и 1, найдется представляющая ее булева формула без отрицаний.
2.2.4.
Классы
функций, сохраняющих 0 и сохраняющих 1
Определение 2.26. Функция ????(????
1
, … , ????
????
) называется сохраняющей 0, если ????(0, … ,0) =
0 , и сохраняющей 1, если ????(1, … ,1) = 1. .
Множество всех функций, сохраняющих 0, образует класс функций,
сохраняющих
0
– класс T
0
Множество всех функций, сохраняющих 1, образует класс функций,
сохраняющих
1
– класс T
1
2.2.5.
Классы
Поста
Обобщим выше введенные понятия классов следующим определением.
59
Определение 2.27. Классами Поста называются следующие классы:
2.2.6. Полнота и замкнутость системы логических функций
Определение 2.28. Система функций называется функционально полной системой, если любая логическая функция может быть представлена формулой над , т. е. являться суперпозицией функций из системы .
Функционально полной будет любая система , через функции которой можно выра- зить конъюнкцию, дизъюнкцию и отрицание.