Лекция. Совершенные нормальные формы булевых функций. Определение 1
 Скачать 0.53 Mb.
|
|
1 Совершенные нормальные формы булевых функций. Определение 1. Булевой функцией от n аргументов называется функция ) ,..., , ( 2 1 n x x x f f , заданная на множестве n 1 , 0 и принимающая значения в двухэлементном множестве 1 , 0 Определение 2. Две булевы функции от n аргументов ) ,..., , ( 2 1 n x x x f и ) ,..., , ( 2 1 n x x x g называются равными, если любым одинаковым наборам значений аргументов n x x x ,..., , 2 1 обе эти функции сопоставляют одинаковые элементы из множества 1 , 0 Теорема 1. Число различных булевых функций от n аргументов равно n 2 2 Теорема 2. Для булевых функций выполняются следующие равенства: 1) x x x x x x , ; 2) x y y x x y y x , ; 3) ) ( ) ( ), ( ) ( z y x z y x z y x z y x ; 4) x x x 1 , 1 1 ; 5) 0 0 , 0 x x x ; 6) ) ( ) ( ), ( ) ( z x y x z y x z x y x z y x ; 7) x x y x x x y x ) ( , ) ( ; 8) y x x y x y x x y x ) ( , ) ( ; 9) y x y x y x y x ) ( , ) ( ; 10) 0 , 1 x x x x ; 11) x x Теорема 3. Для булевых функций справедливы следующие равенства: 1) 0 , 1 x x x x ; 2) x y y x ; 3) z y x z y x ; 4) x x x x 0 , 1 ; 5) y x y x ; 6) x y y x ; 2 7) 1 x x ; 8) x x x ; 9) x x x ; 10) x x 1 ; 11) 1 0 x ; 12) 1 1 x ; 13) x x 0 Теорема 4. Справедливы следующие равенства, выражающие одни булевы функции через другие: 1) y x y x ; 2) y x y x ; 3) y y x y x ; 4) y x y x ; 5) y x y x ; 6) y x y x x y y x y x ; 7) x x x ; 8) y x y x ; 9) y y x x y x y x ; 10) x x x ; 11) ) ( y x y x ; 12) y y x x y x y x Совершенная дизъюнктивная нормальная форма (СДНФ) Определение 3. Элементарной конъюнкцией (ЭК) булевой функции ) ,..., , ( 2 1 n x x x f f называется выражение вида ik i i x x x 2 1 (отрицание на любых местах). Определение 4. Дизъюнктивной нормальной формой (ДНФ) называется дизъюнкция нескольких элементарных конъюнкций. Определение 5. Элементарная конъюнкция называется правильной, если ни одна переменная в ней не повторяется. Определение 6. Элементарная конъюнкция называется полной, если в ней присутствуют все n переменных. 3 Определение 7. Дизъюнктивная нормальная форма называется совершенной (СДНФ), если в ней все элементарные конъюнкции правильные и полные. Теорема 5. Всякую булеву функцию можно представить в виде СДНФ, причем это представление единственно. Совершенная конъюнктивная нормальная форма (СКНФ) Определение 8. Элементарной дизъюнкцией (ЭД) булевой функции ) ,..., , ( 2 1 n x x x f f называется выражение вида ik i i x x x 2 1 (отрицание на любых местах). Определение 9. Конъюнктивнойнормальной формой (КНФ) называется конъюнкция нескольких элементарных дизъюнкций. Определение 10. Элементарная дизъюнкция называется правильной, если ни одна переменная в ней не повторяется. Определение 11. Элементарная дизъюнкция называется полной, если в ней присутствуют все n переменных. Определение 12. Конъюнктивная нормальная форма называется совершенной (СКНФ), если в ней все элементарные дизъюнкции правильные и полные. Теорема 6. Всякую булеву функцию можно представить в виде СКНФ, причем это представление единственно. Пусть дана булева функция ) ,..., , ( 2 1 n x x x f f Определение 13. Двойственной булевой функцией называется булева функция * f , заданная формулой ) ,..., , ( ) ,..., , ( 2 1 2 1 * * n n x x x f x x x f f Заметим, что f f * * . Определение 14. Композиция булевых функций – это сложная функция, составленная из нескольких булевых функций. Т е о р е м а 7. (закон двойственности): Двойственная к композиции булевых функций есть соответствующая композиция двойственных булевых функций. С л е д с т в и е 1. Если в формуле присутствует только дизъюнкции, конъюнкции и отрицания, то для получения двойственной достаточно заменить дизъюнкцию конъюнкцией и наоборот. С л е д с т в и е 2. Двойственной к СДНФ является СКНФ. 4 Алгоритмы получения СДНФ и СКНФ: 1. Привести булеву функцию к совершенной дизъюнктивной нормальной форме. Для этого необходимо воспользоваться следующим алгоритмом: 1) Выразить все булевы функции через конъюнкцию, дизъюнкцию и отрицание. 2) Раскрыть скобки и получить ДНФ. 3) Сделать все элементарные конъюнкции правильными. Для этого необходимо воспользоваться следующими равенствами: 0 , , x x x x x x x x 4) Сделать все элементарные конъюнкции полными. Если элементарная конъюнкция не содержит переменную x, то ее необходимо умножить на x x 1 5) Вернуться к пункту 2. Через конечное число шагов будет получена СДНФ. Если в ней содержится несколько одинаковых ЭК, то согласно тождеству x x x x из них необходимо оставить только одну. 2. Привести булеву функцию к совершенной конъюнктивной нормальной форме. Для этого необходимо: 1) Найти двойственную булеву функцию * f 2) Преобразовать булеву функцию * f в СДНФ. 3) Найти двойственную булеву функцию для * f : СКНФ СДНФ f f * * * Минимизация булевых функций. Определение 1. Длиной элементарной конъюнкции называется количество переменных в ней. Определение 2. Длиной дизъюнктивной нормальной формы называется сумма длин, входящих в неё. Определение 3. Элементарные конъюнкции называются соседними, если они имеют одинаковую длину и отличаются на одну переменную (в одной элементарной конъюнкции присутствует переменная, а в другой её отрицание). Определение 4. Дизъюнктивная нормальная форма минимальной 5 длины, тождественно равной данной булевой функции, называется ее минимальной дизъюнктивной нормальной формой (МДНФ). Определение 5. Дизъюнктивная нормальная форма, не допускающая склеек, называется тупиковой. Очевидно, что у любой булевой функции существует минимальная дизъюнктивная нормальная форма, так как из всех длин l = 1, 2, 3..., равных ей дизъюнктивных нормальных форм, всегда можно выбрать минимальную. К сожалению, единственность отсутствует: многие булевы функции имеют несколько МДНФ одинаковой длины. Преобразования логической формулы к минимальной дизъюнктивной нормальной форме разбивается на 2 этапа: 1. Пусть удалось выделить в ДНФ множитель вида x x , тогда, заменив его единицей, можно уменьшить длину ДНФ. Эта процедура называется склейкой по переменной х. Чтобы обнаружить склейку в ДНФ, необходимо найти в ней соседние элементарные конъюнкции. С помощью соседних элементарных конъюнкций получается склейка. Иногда она бывает минимальной, но чаще минимизацию можно продолжить. 2. С помощью сокращающих логических тождеств возможно ещё уменьшить длину тупиковой дизъюнктивной нормальной формы. К ним относятся: а) x xy x - закон поглощения; б) y x y x x - закон сокращения. Система булевых функций. Теорема Поста. Определение 1. Система булевых функций называется полной, если всякая булева функция является суперпозицией функций из этой системы. Определение 2. Суперпозицией булевых функций , , , , 1 1 2 1 1 1 1 m y y y g …, n m n n n n y y y g , , , 2 1 в булеву функцию ) ..., , ( 1 n x x f называется новая булева функция, получающаяся из функции ) ..., , ( 1 n x x f подстановкой вместо (всех или некоторых) аргументов функций , 1 g …, n g соответственно , , , , 1 1 2 1 1 1 1 m y y y g f …, n m n n n n y y y g , , , 2 1 . Полученная функция от n m m 1 аргументов. 6 Теорема 1. Следующие системы булевых функций являются полными: 1) , , , 2) , , , 3) , , 4) , , 5) , , 6) , 7) Определение 3. Булевафункция ) ..., , ( 1 n x x f сохраняет 0, если 0 ) 0 ..., , 0 ( f 0 P – класс всех булевых функций, сохраняющих 0. Определение 4. Булевафункция ) ..., , ( 1 n x x f сохраняет 1, если 1 ) 1 ..., , 1 ( f 1 P – класс всех булевых функций, сохраняющих 1. Определение 5. Двойственной булевой функцией к функции ) ..., , ( 1 n x x f называется булева функция * f , заданная формулой ) ,..., , ( ) ,..., , ( 2 1 2 1 * * n n x x x f x x x f f Булева функция называется самодвойственной, если f f * . S – класс всех самодвойственных булевых функций. Определение 6. Введем на множестве 1 , 0 отношение порядка, полагая, что 0 0 , 1 0 , 1 1 . Булева функция ) ..., , ( 1 n x x f называется монотонной, если для любых 1 , 0 ..., , , ..., , 1 1 n n β β α α из n n β α β α ..., , 1 1 немедленно следует, что n n β β f α α f ..., , ..., , 1 1 Класс всех монотонных функций обозначается M. Определение 7. Булева функция ) ..., , ( 1 n x x f называется линейной, если её можно представить в виде многочлена Жегалкина степени не выше первой, а именно n n n x a x a a x x f ) ..., , ( 1 1 0 1 , где n a a ..., , 0 – постоянные, равные либо 0, либо 1. Класс всех линейных функций обозначается L. Определение 8. Класс булевых функций C называется замкнутым классом (классом Поста), если он вместе со всеми своими функциями содержит любую их суперпозицию. Лемма. Классы 0 P , 1 P , S, M и L замкнуты. Теорема 2. (Теорема Поста) Система булевых функций ,... ,..., , 1 0 s f f f является полной тогда и только тогда, когда в этой системе имеется функция, не принадлежащая классу 0 P , имеется функция, не принадлежащая классу 1 P , имеется функция, не принадлежащая классу S, имеется функция, не принадлежащая классу M, имеется функция, не принадлежащая классу L. 7 Алгоритм проверки системы булевых функций на полноту: 1. Проверить каждую из функций 3 2 1 , , f f f на принадлежность к замкнутому классу 0 P ‒ класс функций, сохраняющих 0. 2. Проверить каждую из функций 3 2 1 , , f f f на принадлежность к замкнутому классу 1 P ‒ класс функций, сохраняющих 1. 3. Проверить каждую из функций 3 2 1 , , f f f на принадлежность к замкнутому классу S ‒ класс самодвойственных функций. 4. Проверить каждую из функций 3 2 1 , , f f f на принадлежность к замкнутому классу M ‒ класс монотонных функций. 5. Проверить каждую из функций 3 2 1 , , f f f на принадлежность к замкнутому классу L ‒ класс линейных функций. 6. Составить таблицу Поста вида: 0 P 1 P S M L 1 f 2 f 3 f Заполнить таблицу знаками «+» и «–» в соответствии с тем, принадлежит ли функция i f , где 3 , 1 i , определённому замкнутому классу булевых функций. 7. По теореме Поста сделать вывод о полноте системы: 1) если в каждом столбце таблицы присутствует хотя бы один знак «–», то система 3 2 1 , , f f f является полной; 2) если существует хотя бы один столбец, в котором все знаки «+», то система полной не является. |