bulevy-funktsii-i-postr.-log.-skhem (1016573), страница 6

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 6)

Для любой булевой функции f  x1, x2 ,..., xn  , отличной от тождественной единицы, справедливо представление&x11  x2 2  ...  xn n ,1,..., n  | f 1,..., n 0которое является единственным.Этот вид называется совершенной конъюнктивной нормальной формой функции f  x1, x2 ,..., xn  и записывается СКНФ.Доказательство.

Пусть функция f  x1, x2 ,..., xn  отлична отf  x1,..., xn  тождественной единицы, тогда функция f  x1, x2 ,..., xn  отличнаот тождественного нуля. Напишем разложение этой функции поk  n переменнымf  x1,..., xn  Vx11  x2 2  ...  xn n  f 1, 2 ,..., n  ,1, 2 ,..., n Bnчто можно переписать в эквивалентном видеf  x1,..., xn  Vx11  ...  xn n  f 1, ..., n  1,..., n  | f 1,..., n 1Vx11  ...  xn n  f 1,..., n  .1,..., n  | f 1,..., n 0Учитывая, что в первой дизъюнкции все значения функции равныединице, а вторая обнуляется из-за того, что все значения функции в ней равны нулю, получаемf  x1,..., xn  Vx11  ...

 xn n  f 1,..., n  .1,..., n  | f 1,..., n 1Так как f  x1,..., xn   f  x1,..., xn  , то, применяя правила де Моргана, имеемf  x1,..., xn  Vx11  ...  xn n  f 1, ..., n  1,..., n  | f 1,..., n 1&x11  x2 2  ...  xn n  f 1,..., n  1,..., n  | f 1,..., n 1 0&x11  x2 2  ...  xn n  f 1,..., n  1,..., n  | f 1,..., n 046&x11  x2 2  ...  xn n ,1,..., n  | f 1,..., n 0где x  x так как x1  x  x0  x1 и x0  x  x  x1  x0 .Из единственности СДНФ для функции f  x1,..., xn  вытекаетединственность СКНФ для функции f  x1,..., xn   f  x1,..., xn  .Утверждение теоремы доказано.□Определение 8.2.3.

Формула вида xi1  xi 2  ...  xi m , где12mm  1 , ik 1,2,..., n ,  k 0,1 и все переменные различны,называется элементарной дизъюнкцией ранга m на множествебулевых переменных x1, x2 ,..., xn . Если ранг элементарной дизъ-юнкции равен n , то дизъюнкция x11  ...  xn n называется полной.Определение 8.2.4. Представление функции f  x1, x2 ,..., xn  ввиде конъюнкций элементарных дизъюнкций, где существует хотя бы одна неполная дизъюнкция, называется конъюнктивнойнормальной формой (КНФ).Пример 8.2.1.

Для функции f  x, y, z    0001 0101 найтиСДНФ и СКНФ. По СДНФ функции f  x, y, z  построить логическую схему при помощи вентилей «И», «ИЛИ», «НЕ», найти еёзадержку и цену по Квайну.Решение. Составим таблицу функции f  x, y, z  :xyzf00000010010001111000101111001111Найдём СДНФ:f  x, y , z  xa yb z c  V xa yb z c V a,b,c | f  a,b,c 1 0,1,11,0,11,1,1 x0 y1z1  x1 y 0 z1  x1 y1z1  xyz  x yz  xyz .47Найдём СКНФ:f  x, y , z  & a,b,c | f  a ,b,c 0xa yb  z c & xa yb  z c 0,0,0 0,0,1 0,1,0 1,0,0 1,1,0  x0  y 0  z 0  x0  y 0  z 1  x0  y1  z 0  x1  y 0  z 0   x 1  y 1  z 0  x1  y1  z1  x1  y1  z 0  x1  y 0  z1  x0  y1  z1  x0  y 0  z1   x  y  z    x  y  z   x  y  z    x  y  z    x  y  z  .zу x11&&1&2 ярус1 ярус3 ярусРис. 8.2.1.

Логическая схема, реализующая СДНФ функции.48Логическая схема, реализующая СДНФ функции f  x, y, z при помощи вентилей «И», «ИЛИ», «НЕ», показана на рис.8.2.1.Для схемы на рис.8.2.1. задержка - T  3 , цена по Квайну SQ=14.Пример 8.2.2. Для функций f1  x, y, z   x y  yz  xz ,f 2  x, y, z   x  xyz  yz , f3  x, y, z   xy  xz  z y :1) выяснить вопрос о равносильности ДНФ функций f1 , f 2 ,f3 сведением их к СДНФ;2) при помощи основных эквивалентностей преобразоватьДНФ функции f 2 в КНФ.Решение.1.

Применяя эквивалентности x  x  1 , x  x  x иx  y  z   xy  xz , сведём данные функции к СДНФ.Преобразуя формулу функции f1f1  x, y, z   x y  yz  xz  x y 1  1 yz  x 1 z  x y  z  z  x  x  yz  x  y  y  z  x yz  x yz  xyz  xyz  xyz  x yz ,получим СДНФ функции f1 :f1  x, y, z   x yz  x yz  xyz  xyz  xyz  x yz .Преобразуя формулу функции f 2f 2  x, y, z   x  xyz  yz  x 11  xyz  1 yz  x  y  y  z  z  xyz  x  x  yz  xyz  xyz  x yz  x yz  xyz  x yz  x yz  xyz  xyz  x yz  x yz  xyz  x yz ,получим СДНФ функции f 2 :f 2  x, y, z   xyz  xyz  x yz  x yz  xyz  x yz .Преобразуя формулу функции f3f3  x, y, z   xy  xz  z y  xy 1  x 1 z  1 z y  xy  z  z  x  y  y  z  x  x  z y  xyz  xyz  xyz  x yz  xz y  xz y ,получим СДНФ функции f3 :49f3  x, y, z   xyz  xyz  xyz  x yz  xz y  xz y .Сравнивая СДНФ этих функций, делаем вывод, что f1  f3  f 2 .2.

Применяя закон дистрибутивностиx  y  z   x  y  x  z ,преобразуем ДНФ функции f 2 в КНФ:   1  x  yz   yz  x  yz  yz  x   yz  y  yz  z   x   y  y  z  y   y  z   z  z   x  1  z  y    y  z   1  x   z  y   y  z    x  z  y  x  y  z  ,f 2  x, y, z    x  z  y  x  y  z  .f2  x, y, z   x  xyz  yz  x  x yz  yz  x  x x  yz  yz 9. Полные системы. Примеры полных системПусть A   f1, f 2 ,...  P2 - система булевых функций.Определение 9.1. Система A называется полной (в P2 ), еслилюбую булеву функцию можно выразить формулой над A .Теорема 9.1.

Система A  , ,  является полной.Доказательство. Если булева функция f отлична от тождественного нуля, то она выражается в виде совершенной дизъюнктивной нормальной формы, в которую входят лишь дизъюнкция,конъюнкция и отрицание. Если же f  0 , то f  x  x . Теоремадоказана.□Лемма 9.2. Если система A — полная, и любая функция системы A может быть выражена формулой над некоторой другойсистемой B , то B - также полная система.Доказательство. Рассмотрим произвольную булеву функцию f  x1, x2 ,..., xn  и две системы функций: A  g1, g2 ,... иB  h1, h2 ,... . В силу того, что система A полна, функция f можетбытьвыраженаввидеформулынадней:f  x1, x2 ,..., xn   I g1, g2 ,... , где gi  i  h1, h2 ,... , то есть функ50ция f представляется в виде f  x1, x2 ,..., xn   I1, 2 ,... , иначеговоря, может быть представлена формулой над B .

Перебираятаким образом все булевы функции, получим, что система Bтакже полна. Лемма доказана.□Теорема 9.3. Следующие системы являются полными в P2 :1)  x  y, x  ; 2)  x  y, x  ; 3)  x | y ; 4) x  y, x  y, 1 .Доказательство.1. Известно (теорема 9.1), что система A  x  y, x  y, x полна.

Покажем, что полна система B   x  y, x  . Действительно, из правил де Моргана x  y  x  y получаем, что x  y  x  y ,то есть конъюнкция выражается через дизъюнкцию и отрицание,и все функции системы A выражаются формулами над системойB . Согласно лемме 2 система B полна.2. Аналогично пункту 1, применяя правила де Моргана, выразим дизъюнкцию через конъюнкцию и отрицание: x  y  x  y⇔ x  y  x  y . Так как в п.1 показано, что система  x  y, x полна, то из леммы 9.2 следует истинность утверждения пункта2.3.

Так как x  x | x , x  y  x | y   x | y    x | y  и из п.2 извест-но, что система  x  y, x  полна, то согласно лемме 9.2 системаx | y полна.4. По лемме 9.2 система x  y, x  y, 1 полна, т.к. x  x  1и система  x  y, x  полна по п.2.Теорема доказана.□10. Теорема Жегалкина о представимости булевойфункции полиномомВ 1927 году российский математик И. И. Жегалкин(1869 - 1947) предложил полином в качестве одного из способовпредставления булевой функции.51Определение 10.1. Элементарная конъюнкция на множествебулевых переменных x1, x2 ,..., xn называется монотонной, еслиона не содержит отрицаний переменных.

Монотонная конъюнкция либо имеет вид xi1  xi2  ...  xim , где m  1 и ik 1,2,..., n , либоявляется константой 1.Определение 10.2. Полиномом Жегалкина от переменныхx1, x2 ,..., xn называется либо выражение видаK1  K 2  K3  ...  Kl ,где l  1 и все K j - различные монотонные конъюнкции на множестве переменных x1, x2 ,..., xn , либо константа 0.Запишем общий вид полинома Жегалкина от переменныхx1, x2 ,..., xn :a0  a1x1  ...  an xn  a12 x1x2  a13 x1x3  ...

 a12...n x1x2 ...xn ,где константы и переменные принимают значения либо 0, либо 1.Теорема 10.1 (теорема Жегалкина). Любую булеву функцию f  x1, x2 ,..., xn  можно единственным образом выразить полиномом Жегалкина над множеством переменных x1, x2 ,..., xn .Доказательство.1. Докажем существование полинома.Константа 0 – это полином Жегалкина по определению. Известно, что любая булева функция f  x1, x2 ,..., xn  , отличная оттождественного нуля, представима СДНФ, поэтому построим полином Жегалкина, применяя к СДНФ формулы x  x  1 иx  y  x  y   x  1 y  1  1  xy  x  y .СДНФ функции f  x1,..., xn  имеет вид:Vx11  x2 2  ...  xn n .1,..., n  | f 1,..., n 1Так как конъюнкции, входящие в СДНФ различные и полные, то произведение любой пары конъюнкций Ki и K j будетсодержать произведение противоположных переменных, поэтомуKi  K j  0 .

Характеристики

Список файлов учебной работы