Математика. Раздел 1. Дискретная математика. Тетрадь 1.2. Казанцев Э.Ф. - 42 стр.

UptoLike

ВУЗ: 

МУМ | Москва

Составители: 

Рубрика: 

а) пусть фор му ла В есть сла гае мое ДНФ не со дер жа щее пе ре мен -
ной Х, то гда на до за ме нить сла гае мое В на сла гае мое
B x x& ( )Ú
º
º Ú( & ) ( & )B x B x
по фор му ле рас ще п ле ния;
б) ес ли в ДНФ фор му лы А встре тят ся два оди на ко вых сла гае мых
B Ú B то лиш нее на до от бро сить, так как B Ú B º B;
в) ес ли в не ко то рое сла гае мое В пе ре мен ная Х вхо дит два ж ды,
лиш нюю пе ре мен ную на до от бро сить, так как X & X º X;
г) ес ли сла гае мое В со дер жит конъ юнк ции
X X&
, то это сла гае -
мое мож но от бро сить, так как
X X& º 0
, сле до ва тель но
B º 0
, а лож ное
вы ска зы ва ние из дизъ юнк ции мож но вы бро сить, так как
C C CÚ º
.
При мер: при вес ти к СДНФ сле дую щую фор му лу:
(X
1
& ØX
1
& X
3
) Ú (X
1
& ØX
3
& X
1
) Ú X
2
º .
Пер вую эле мен тар ную конъ юнк цию (X
1
& ØX
1
& X
3
) от бра сы ва ем
по свой ст ву г), во вто рой эле мен тар ной конъ юнк ции (X
1
& ØX
3
& X
1
)
мож но ос та вить толь ко од но вхо ж де ние Х
1
по свой ст ву в). За тем про во -
дим пре об ра зо ва ния по фор му ле рас ще п ле ния:
º (X
1
& ØX
3
) Ú X
2
º (X
1
& ØX
3
& X
2
) Ú (X
1
& ØX
3
& X
2
) Ú
Ú (X
2
& X
1
) Ú (X
2
& ØX
1
) º (X
1
& ØX
3
& X
2
) Ú (X
1
& ØX
3
& ØX
2
) Ú
Ú (X
2
& X
1
& X
3
) Ú (X
2
& X
1
& ØX
3
) Ú (X
2
& ØX
1
& X
3
) Ú
Ú (X
2
& ØX
1
& ØX
3
) º (X
1
& X
2
& ØX
3
) Ú (X
1
& ØX
2
& ØX
3
) Ú
Ú (X
1
& X
2
& X
3
) Ú (ØX
1
& X
2
& X
3
) Ú (ØX
1
& X
2
& ØX3).
Здесь (X
2
& X
1
& ØX
3
) встре ча ет ся два раза, по это му од но от бра сы -
ва ем, а ос таль ные рас по ла га ем в по ряд ке воз рас та ния ин дек сов, что по -
зво ля ет лег ко об на ру жить оди на ко вые и от бро сить лиш ние.
Раз лич ные СДНФ фор му лы А мо гут от ли чать ся толь ко по ряд ком
сле до ва ния сво их дизъ юнк тив ных чле нов, то есть СДНФ — един ст вен -
на. Ана ло гич но оп ре де ля ет ся со вер шен ная конъ юнк тив ная нормальная
форма (СКНФ).
1.5.8 Ло ги че ские функ ции
Функ ци ей ал геб ры ло ги ки (или ло ги че ской функ ци ей) от n пе ре -
мен ных f(x
1
…x
n
) на зы ва ет ся n-ар ная опе ра ция на мно же ст ве {0,1}, то
есть функ ция, при ни маю щая зна че ния 0 и 1. Вся кая ло ги че ская функ -
ция n пе ре мен ных мо жет быть за да на таб ли цей ис тин но сти (таб ли -
42
      а) пусть формула В есть слагаемое ДНФ не содержащее перемен-
ной Х, тогда надо заменить слагаемое В на слагаемое B & ( x Ú x ) º
º (B & x ) Ú (B & x ) по формуле расщепления;
      б) если в ДНФ формулы А встретятся два одинаковых слагаемых
B Ú B то лишнее надо отбросить, так как B Ú B º B;
      в) если в некоторое слагаемое В переменная Х входит дважды,
лишнюю переменную надо отбросить, так как X & X º X;
      г) если слагаемое В содержит конъюнкции X & X , то это слагае-
мое можно отбросить, так как X & X º 0, следовательно B º 0, а ложное
высказывание из дизъюнкции можно выбросить, так как C Ú C º C .

     Пример: привести к СДНФ следующую формулу:
               (X1 & ØX1 & X3) Ú (X1 & ØX3 & X1) Ú X2 º .
     Первую элементарную конъюнкцию (X1 & ØX1 & X3) отбрасываем
по свойству г), во второй элементарной конъюнкции (X1 & ØX3 & X1)
можно оставить только одно вхождение Х1 по свойству в). Затем прово-
дим преобразования по формуле расщепления:
         º (X1 & ØX3) Ú X2 º (X1 & ØX3 & X2) Ú (X1 & ØX3 & X2) Ú
     Ú (X2 & X1) Ú (X2 & ØX1) º (X1 & ØX3 & X2) Ú (X1 & ØX3 & ØX2) Ú
          Ú (X2 & X1 & X3) Ú (X2 & X1 & ØX3) Ú (X2 & ØX1 & X3) Ú
       Ú (X2 & ØX1 & ØX3) º (X1 & X2 & ØX3) Ú (X1 & ØX2 & ØX3) Ú
         Ú (X1 & X2 & X3) Ú (ØX1 & X2 & X3) Ú (ØX1 & X2 & ØX3).
      Здесь (X2 & X1 & ØX3) встречается два раза, поэтому одно отбрасы-
ваем, а остальные располагаем в порядке возрастания индексов, что по-
зволяет легко обнаружить одинаковые и отбросить лишние.
      Различные СДНФ формулы А могут отличаться только порядком
следования своих дизъюнктивных членов, то есть СДНФ — единствен-
на. Аналогично определяется совершенная конъюнктивная нормальная
форма (СКНФ).

     1.5.8 Логические функции

      Функцией алгебры логики (или логической функцией) от n пере-
менных f(x1…xn) называется n-арная операция на множестве {0,1}, то
есть функция, принимающая значения 0 и 1. Всякая логическая функ-
ция n переменных может быть задана таблицей истинности (табли-
42

Страницы