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

UptoLike

ВУЗ: 

МУМ | Москва

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

Рубрика: 

Имен но сис те ма Же гал ки на S
6
= {&, Å} функ цио наль но пол на, так как
конъ юнк ция не ли ней на, а сло же ние по мо ду лю 2 — не мо но тон но.
1.5.9 Ал геб ра Же гал ки на
Ал геб ра на зы ва ет ся мно же ст вом ло ги че ских функ ций с дву мя би -
нар ны ми опе ра ция ми & и Å на зы ва ет ся ал геб рой Же гал ки на.
Функ цию
X Y&
мож но пи сать XY.
Таб ли ца ис тин но сти для X Å Y и XY.
X Y
X Å Y
XY
1
1
0
0
1
0
1
0
0
1
1
0
1
0
0
0
Ос нов ные рав но силь но сти ал геб ры Же гал ки на:
1)
X Y Y XÅ º Å
; 1¢)
X Y Y X× º ×
;
2)
X Y Z XY XZ( )Å º Å
; 2¢)
3)
( ) ( )X Y Z X Y ZÅ Å º Å Å
; 3¢)
( ) ( )X Y Z X Y Z× º ×
;
4)
X XÅ = 0
; 4¢)
X X X× =
;
5)
X XÅ =0
; 5¢)
X × =0 0
;
X X× =1
.
Все то ж де ст ва, кро ме 4) и 4¢) ана ло гич ны ариф ме ти че ско му сло -
же нию и ум но же нию, по это му эта ал геб ра ино гда на зы ва ет ся ариф ме -
ти кой по mod2.
От ри ца ние:
X Xº Å1
, т.к.
1 1 1 0 0 0 1 1= Å = = Å =;
.
Дизъ юнк ция:
1)
X Y X Y X Y XY X Y XY X YÚ º × º Å Å Å º Å Å Å Å º Å Å( ) ( )( )1 1 1 1 1
2)
X Y Z XYZ XY XZ X Y Z XZÚ Ú º Å Å Å Å Å Å
.
Не труд но ви деть, что ес ли в про из воль ной фор му ле ал геб ры Же -
гал ки на рас крыть скоб ки и про из ве сти все воз мож ные уп ро ще ния, то
по лу чит ся фор му ла, имею щая вид сум мы про из ве де ний, на зы вае мая
по ли но мом по mod2. От бу ле вой фор му лы все гда мож но пе рей ти к фор -
му ле ал геб ры Же гал ки на, и, сле до ва тель но, мно го чле ну Же гал ки на.
47
Именно система Жегалкина S6 = {&, Å} функционально полна, так как
конъюнкция нелинейна, а сложение по модулю 2 — немонотонно.

     1.5.9 Алгебра Жегалкина

     Алгебра называется множеством логических функций с двумя би-
нарными операциями & и Å называется алгеброй Жегалкина.
     Функцию X &Y можно писать XY.

                  Таблица истинности для X Å Y и XY.
                    X           Y        XÅY           XY
                    1           1         0             1
                    1           0          1            0
                    0           1          1            0
                    0           0          0            0

     Основные равносильности алгебры Жегалкина:
     1) X Å Y º Y Å X ;               1¢) X ×Y º Y × X ;
     2) X (Y Å Z ) º XY Å XZ ;        2¢)
     3) ( X Å Y ) Å Z º X Å (Y Å Z ) ;          3¢) ( X ×Y )Z º X (Y × Z );
     4) X Å X = 0;                            4¢) X × X = X ;
     5) X Å 0 = X ;                           5¢) X × 0 = 0; X ×1 = X .
     Все тождества, кроме 4) и 4¢) аналогичны арифметическому сло-
жению и умножению, поэтому эта алгебра иногда называется арифме-
тикой по mod2.
     Отрицание: X º X Å1, т.к. 1 = 1 Å 1 = 0; 0 = 0 Å 1 = 1.
     Дизъюнкция:
 1) X Ú Y º ( X ×Y ) º ( X Å 1)(Y Å 1) Å 1 º XY Å X Å Y Å 1 Å 1 º XY Å X Å Y

           2) X Ú Y Ú Z º XYZ Å XY Å XZ Å X Å Y Å Z Å XZ .
      Нетрудно видеть, что если в произвольной формуле алгебры Же-
галкина раскрыть скобки и произвести все возможные упрощения, то
получится формула, имеющая вид суммы произведений, называемая
полиномом по mod2. От булевой формулы всегда можно перейти к фор-
муле алгебры Жегалкина, и, следовательно, многочлену Жегалкина.
                                                                              47

Страницы