Для визначення лінійності функції подамо її у вигляді полінома Жегалкіна 
";


Мы поможем в написании ваших работ!



ЗНАЕТЕ ЛИ ВЫ?

Для визначення лінійності функції подамо її у вигляді полінома Жегалкіна



 

f = /а/bc # abc=(a#1)(b#1)c # abc =abc#ac#bc#c#abc =ac#bc#c

 

 

Оскільки поліном містить добутки змінних, то функція не є лінійною.

 

Отже, із п'яти необхідних для створення ФПС властивостей відсутні дві – не зберігання константи «0» та «1», тому дана функція не утворює ФПС.

 

 

Мінімізувати за допомогою методу Квасна-Мак-Класкі-Петрика 5 функцій (f0, f1,

F2, f3, f4) 5-ти змінних (a, b, c, d, e). Функції задано за допомогою таблиці ТZ.3. Побудувати

Таблицю, яка ілюструє процес знаходження простих імплікант,і таблицю покриття

(імплікантну таблицю). За допомогою методу Петрика визначити всі мінімальні розв'язки.

Кожний третій набір для кожної з функцій має невизначене значення. Відлік починається

Від першого згори одиничного значення функції з врахуванням зміщення, величина якого

позначена у табл. ТZ.3:

 

S - відлік починається безпосередньо від першого згори одиничного значення;

-S - відлік починається від попереднього набору відносно першого згори одиничного

значення;

+S - відлік починається від наступного набору відносно першого згори одиничного

значення.

 

К О С Т І В Я Р
                               
                               

 

 

Зміщення невизначеного значення -S S +S -S S
№ набору a b c d e f0 f1 f2 f3 f4
                     
            x0     Х1  
              X0     Х1
                x1    
            x0     х0  
              x1     Х1
                X1    
            x1     х1  
              x0     х0
                x1    
            Х0     Х1  
              x1     Х0
                Х0    
            Х1     х0  
              Х1     Х1
                Х1    
            х0     х0  
              х0     Х0
                х1    
            Х0     х1  
              х0     х0
                Х1    
            х1     Х0  
              х1     х1
                х0    
            Х1     х0  
              х0     Х0
                Х0    
            х0     Х0  
              х1     Х1
                х1    
            Х0     х0  

Будуємо таблицю, яка ілюструє знаходження простих імплікант:

Мінімізація функції f0

1 2 3

К П У C К П У С К П У    
  а0 + a0b0 000_1 f0 + f0g3 0_0_1 k0 -    
  а1 + a0b1 0_001 f1 + f1g1 0_0_1 k1 -    
  а2 + a1b0 0001_ f2 + f2g6 0_01_ k2 -    
  а3 + a1b2 0_010 f3 + f2g8 _001_ k3 -    
  b0 + a1b4 _0010 f4 + f3g1 0_01_ k4 -    
  b1 + a2b3 0_100 f5 - f4g2 _001_ k5 -    
  b2 + a3b4 100_0 f6 - g0h3 _0_11 l0 -    
  b3 + b0c0 00_11 g0 + g1h4 _ _011 l1 -    
  b4 + b0c1 0_011 g1 + g2h0 _0_11 l2 -    
  c0 + b0c3 _0011 g2 + g2h1 _ _011 l3 -    
  c1 + b1c1 010_1 g3 + g3h7 _10_1 l4 -    
  c2 + b1c2 01_01 g4 + g4h8 _1_01 l5 -    
  c3 + b1c5 _1001 g5 + g5h1 _10_1 l6 -    
  c4 + b2c1 0101_ g6 - g5h2 _1_01 l7 -    
  c5 + b3c2 0110_ g7 + g7h9 _110_ l8 -    
  c6 + b4c3 1001_ g8 + g8h5 10_1_ l9 -    
  d0 + c0d0 _0111 h0 - h3i1 1_ _11 m0 -    
  d1 + c1d1 _1011 h1 - h4i0 1_ _11 m1 -    
  d2 + c2d2 _1101 h2 - h5i3 1_11_ m2 -    
  d3 + c3d0 10_11 h3 + h6i0 1_11_ m3 -    
  e0 + c3d1 c4d0 c4d3 c5d1 c5d2 c6d2 c6d3 1_011 h4 + h7i2 11_ _1 m4 -    
      1011_ 1_110 110_1 11_01 1110_ 111_0 h5 h6 h7 h8 h9 h10 + + + + + + h8i1 h9i3 h10i2 11_ _1 111_ _ 111_ _ m5 m6 m7 - - -    
         
d0e0 d1e0 d2e0 d3e0 1_111 11_11 111_1 1111_ i0 i1 i2 i3 + + + +  
                           

 

 

Отже простими імплікантами є кон’юнкції:

/ac/d/e: 0_100; a/b/c/e: 100_0; /ab/cd: 0101_; /bcde: _0111; b/cde: _1011; bc/de: _1101; /a/ce: 0_0_1; /a/cd: 0_01_; /b/cd: _001_; /bde: _0_11; /cde: _ _011; b/ce: _10_1; b/de: _1_01; bc/d: _110_; a/bd: 10_1_; ade: 1_ _11; acd: 1_11_; abe: 11_ _1; abc: 111_ _.

 

Мінімізація функції f1

1 2 3 4

К П У C К П У С К П У C К    
  а0 + a0b0 0001_ f0 + f0g5 0_01_ k0 + k0l7 __01_    
  а1 + a0b3 0_010 f1 + f0g9 _001_ k1 + k1l4 __01_    
  b0 + a0b6 _0010 f2 + f1g1 0_01_ k2 + k2l7 __01_    
  b1 + a1b3 010_0 f3 + f2g2 _001_ k3 + k3l4 __01_    
  b2 + a1b4 01_00 f4 + f3g4 010_ _ k4 - l6m4 1__1_    
  b3 + b0c0 00_11 g0 + f3g7 01_ _0 k5 - l6m5 1__1_    
  b4 + b0c1 0_011 g1 + f4g6 01_ _0 k6 - l7m2 1__1_    
  b5 + b0c3 _0011 g2 + g0h3 _0_11 l0 - l7m3 1__1_    
  b6 + b1c0 001_1 g3 - g1h4 _ _011 l1 - l8m4 1__1_    
  b7 + b2c1 010_1 g4 - g2h0 _0_11 l2 - l8m5 1__1_    
  c0 + b3c1 0101_ g5 + g2h1 _ _011 l3 - l9m0 1__1_    
  c1 + b3c2 01_10 g6 + g5h7 _101_ l4 - l9m1 1__1_    
  c2 + b4c2 011_0 g7 - g6h8 _1_10 l5 -      
  c3 + b5c3 100_1 g8 - g9h5 10_1_ l6 +    
  c4 + b6c3 1001_ g9 + g9h7 1_01_ l7 +    
  c5 + b6c4 10_10 g10 + g10h3 10_1_ l8 +    
  d0 + b7c4 101_0 g11 - g10h8 1_ _10 l9 +    
  d1 + c0d0 _0111 h0 - h3i1 1_ _11 m0 +      
  d2 + c1d1 _1011 h1 - h4i1 1_ _11 m1 +    
  d3 + c2d3 _1110 h2 - h5i3 1_11_ m2 +    
  e0 + c3d0 c3d1 c4d0 c4d3 c5d1 c5d3 10_11 h3 + h6i0 1_11_ m3 +    
      1_011 1011_ 1_110 1101_ 11_10 h4 h5 h6 h7 h8 + + + + + h7i3 h8i1 11_1_ 11_1_ m4 m5 + +      
       
             
d0e0 d1e0 d2e0 d3e0 1_111 11_11 111_1 1111_ i0 i1 i2 i3 + + + +  
     
   
                                 

Отже простими імплікантами є кон’юнкції:

/a/bce: 001_1; /ab/ce: 010_1; /abc/e: 011_0; a/b/ce: 100_1; a/bc/e: 101_0;

/bcde: _0111; b/cde: _1011; bcd/e: _1110; /ab/c: 010_ _; /ab/e: 01_ _0; /bd/e: _0_11;

/cde: _ _011; b/dc: _101_; bd/e: _1_10; /cd: _ _01_; ad: 1_ _1_

 

 

Мінімізація функції f2

 

1 2 3 4

К П У C К П У С К П У C K П У  
  а0 + a0b0 0001_ f0 + f0g5 00_1_ k0 + k0l10 _0_1_ n0 -  
  b0 + a0b2 00_10 f1 + f0g8 0_01_ k1 - k0l11 _0_1_ n1 -  
  b1 + a0b4 0_010 f2 + f0g9 _001_ k2 + k2l8 _0_1_ n2 -  
  b2 + a0b6 _0010 f3 + f1g0 00_1_ k3 + k2l9 _0_1_ n3 -  
  b3 + b0c0 00_10 g0 + f1g10 _0_10 k4 + k3l10 _0_1_ n4 -  
  b4 + b0c1 0_011 g1 + f2g1 0_01_ k5 - k3l11 _0_1_ n5 -  
  b5 - b0c2 _0011 g2 + f3g2 _001_ k6 + k4l1 _0_1_ n6 -  
  b6 + b1c0 001_1 g3 + f3g6 _0_10 k7 + k4l4 _0_1_ n7 -  
  c0 + b1c3 _0101 g4 + g0h2 0_ _11 l0 + k6l8 _0_1_ n8 -  
  c1 + b2c0 0011_ g5 + g0h4 _0_11 l1 + k6l9 _0_1_ n9 -  
  c2 + b2c4 _0110 g6 + g1h0 0_ _11 l2 + k7l1 _0_1_ n10 -  
  c3 + b3c1 010_1 g7 - g1h5 _ _011 l3 + k7l4 _0_1_ n11 -  
  c4 + b4c1 0101_ g8 - g2h1 _0_11 l4 + l0m4 ___11 o0 -  
  d0 + b6c2 1001_ g9 + g2h3 _ _011 l5 + l0m5 ___11 o1 -  
  d1 + b6c4 10_10 g10 + g3h6 _01_1 l6 - l1m2 ___11 o2 -  
  d2 + c0d0 0_111 h0   g4h1 _01_1 l7 - l1m3 ___11 o3 -  
  d3 + c0d1 _0111 h1 + g5h8 _011_ l8 - l2m4 ___11 o4 -  
  d4 + c1d0 01_11 h2 + g6h1 _011_ l9 - l2m5 ___11 o5 -  
  e0 + c1d2 _1011 h3 + g9h8 10_1_ l10 - l3m0 ___11 o6 -  
      c2d1 10_11 h4 + g10h4 10_1_ l11 - l3m1 ___11 o7 -  
      c2d2 c3d1 c3d3 c4d1 c4d4 d0e0 d1e0 d2e0 d3e0 d4e0 1_011 h5 + h0i1 _ _111 m0 + l4m2 ___11 o8 -  
      101_1 1_101 1011_ 1_110 _1111 1_111 11_11 111_1 1111_ h6 h7 h8 h9 i0 i1 i2 i3 i4 + + + + + + + + + h1i0 h2i2 h3i0 h4i2 h5i1 h6i3 h7i1 h8i4 h9i1 _ _111 _1_11 _1_11 m1 m2 m3 + + + l4m3 l5m0 l5m1 ___11 ___11 ___11 o9 o10 o11 - - -  
1_ _11 1_ _11 1_1_1 1_1_1 1_11_ 1_11_ m4 m5 m6 m7 m8 m9 + + - - - -              
           
                                 

Отже простими імплікантами є кон’юнкції:

/abc/d/e: 01100; /ab/ce: 010_1; /ab/cd: 0101_; /a/cd: 0_01_; /bce: _01_1; /bcd: _011_;

a/bd: 10_1_; ace: 1_1_1; acd: 1_11_; /bd: _0_1_; de: _ _ _11.

 

Мінімізація функції f3

 

1 2 3

К П У C К П У С К П У  
  а0 + a0b2 _0001 f0 - g0h5 _011_ k0 -  
  а1 + a1b0 00_10 f1 - g1h1 _011_ k1 -  
  а2 + a1b1 0_010 f2 - h0i1 _ _111 k2 -  
  а3 + a2b0 001_0 f3 - h1i0 _ _111 k3 -  
  b0 + a3b2 1000_ f4 -      
  b1 + b0c0 0011_ g0 +    
  b2 + b0c4 _0110 g1 +    
  c0 + b1c1 0101_ g2 -    
  c1 + b1c6 _1010 g3 -      
  c2 + b2c3 100_1 g4 -    
  c3 + b2c5 1_001 g5 -    
  c4 + c0d0 0_111 h0 +    
  c5 - c0d1 _1001 h1 +    
  c6 - c1d0 01_11 h2 -    
  c7 - c2d0 011_1 h3 -    
  d0 + c3d1 10_11 h4 -      
  d1 + c4d1 1011_ h5 -    
  e0 + d0e0 _1111 i0 +    
  d1e0 1_111 i1 +    
   

 

 

Отже простими імплікантами є кон’юнкції:

ab/c/de: 11001; ab/cd/e: 11010; abc/d/e: 11100; /b/c/de: _0001; /a/bd/e: 00_10;

/a/cd/e: 0_010; /a/bc/e: 001_0; a/b/c/d: 1000_; /ab/cd: 0101_; b/cd/e: _1010;

a/b/ce: 100_1; a/c/de: 1_001; /abde: 01_11; /abce: 011_1; a/bde: 10_11;

a/bcd: 1011_; /bcd: _011_; cde: _ _111.

 

Мінімізація функції f4

1 2 3

К П У C К П У С К П У  
  а0 + a0b1 00_10 e0 - f1g3 0_11_ k0 -  
  а1 - b0c0 001_1 f0 - f1g5 _011_ k1 -  
  b0 + b1c0 0011_ f1 + f2g0 0_ 11_ k2 -  
  b1 + b1c2 0_110 f2 + f3g1 _011_ k3 -  
  b2 + b1c4 _0110 f3 +      
  b3 + b2c3 100_1 f4 -    
  c0 + b3c4 101_0 f5 -    
  c1 + b3c6 1_100 f6 -    
  c2 + c0d0 0_111 g0 +      
  c3 + c0d1 _0111 g1 +    
  c4 + c1d0 01_11 g2 -    
  c5 - c2d0 0111_ g3 +    
  c6 + c3d1 10_11 g4 -    
  d0 + c4d1 1011_ g5 +    
  d1 + c6d2 1110_ g6 -    
  d2 +        
     
       
       

 

 

Отже простими імплікантами є кон’юнкції:

/ab/c/d/e: 01000; ab/cd/e: 11010; /a/bd/e: 00_10; /a/bce: 001_1; a/b/ce: 100_1;

a/bc/e: 101_0; ac/d/e:1_100; / abde: 01_11; a/bde:10_11; abc/d: 1110_; /acd: 0_11_;

/bcd: _011_.

 

 

2.3 Мінімізувати за "1" за

Допомогою карт Карно функції, задані

табл. ТZ.3. Після мінімізації доповнити

Функції сполучними термами,

Підкреслити вирази для цих термів в

Аналітичному записі функції і позначити їх на картах Карно. Результат мінімізації повинен

Співпадати з одним із розв'язків, знайдених за допомогою методу Петрика.

К 17

О 57

С 26

Т 46

І 75

В 23

Я 31

Р 16

Мінімізація функції f0

 

00 1x 31 20
4x 51 7x 61
C0 Dx F1 E1
80 91 B1 Ax
10x 110 13x 121
140 151 171 16x
1C0 1Dх 1F1 1E0
180 19x 1B0 1A0

Склеювання клітинок 1,3,5,7,d,f,9,b результат – /аe

Склеювання клітинок 12,16, результат – a/bd/e

2) Склеювання клітинок результат 15, 1d, 17,1F – ace

Склеювання клітинок 19, 1B результат – ab/ce

Склеювання клітинок 6, E результат – /acd/e

 

Мінімізація функції f1

 

00 1x 31 2x
40 5x 71 61
Cx D1 Fx E1
80 9x B1 A0

 

 

100 11x 131 120
14x 151 17x 161
1C0 1D1 1F0 1Ex
18x 191 1Bx 1A0

 

1) Склеювання клітинок 1,3,5,7,D,F,9,B результат – /ae

 

2) Склеювання клітинок 6, E результат - /acd/e

Мінімізація функції f2

 

 

00 10 3x 20
40 51 71 6x
Cx D0 Fx E0
8x 91 Bx A1

 

 

 

 

 

 

 

 

 

 

100 110 130 12x
140 15x 171 161
1C0 1D1 1F0 1Ex
18x 191 1Bx 1A0
       

 

 

 

1) Склеювання клітинок 5,7 результат - /a/bce

2) Склеювання клітинок B,A результат - /ab/cd

3) Склеювання клітинок 9 результат – /ab/d/ce

4) Склеювання клітинок 15,17 результат – a/bce

5) Склеювання клітинок 16,E результат – acd/e

6) Склеювання клітинок 19, B результат – ab/ce

 

Мінімізація функції f3

00 1x 31 21
4x 51 7x 60
C0 Dx F1 E1
80 90 B0 Ax

 

 

 

10x 110 13x 121
140 150 171 16x
1Cx 1D1 1Fx 1E1
180 19x 1B0 1A0

 

 

1) Склеювання клітинок 1,3,5,7, результат -/a/be

2) Склеювання клітинок F,E результат - /abcd

3) Cклеювання клітинок 2 результат – /a/b/cd/e

4) Склеювання клітинок 13,12,16,17 результат –a/bd

5) Склеювання клітинок 1C, 1D,1F,1E результат – abc

Мінімізація функції f4

00 11 31 2x
40 5x 71 60
C0 D0 F1 Ex
8x 90 Bx A1

 

 

100 11x 131 121
14x 150 17x 160
1C0 1Dx 1F0 1E1
180 190 1B0 1Ax

1) Склеювання клітинок 1,3,5,7 результат - /a/be

2) Склеювання клітинокF,E,B,A результат - /abd

3) Склеювання клітинок13,12 результат – a/b/cd

4) Склеювання клітинок1E результат – abcd/e

 

 

2.4 Мінімізувати за "0" за допомогою карт Карно функції, задані табл. ТZ.3. Після

Мінімізації доповнити функції сполучними термами, підкреслити вирази для цих термів в



Поделиться:


Последнее изменение этой страницы: 2016-04-26; просмотров: 393; Нарушение авторского права страницы; Мы поможем в написании вашей работы!

infopedia.su Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав. Обратная связь - 3.224.147.211 (0.005 с.)