Diskreetne matemaatika kodutöö (0)

Дискретная математика
Tal inn  University  of  Technology
Домашняя работа
Xxxx Xxxxxxx
000000
IAXX00
Исходная функция
       
00
01
11
10
x4
x3x4
x1x2
00
0
1
x1
10
1
0
11
1
1
1
0
x2
01
0
0
1
0
x3
100
000
0
000
0
110
1
010
M¹=                                              M¯=                                                 
0        M°= 
0
         
001
110
1
100
1
101
1
Tallinn University of Technology 2012
1111
1
010
2
0111
101
1
001
0
1110
0
011
0
Отмеченная карта Карно
x4
x4
0000
0001
0011
0010
0000
0001
0011
0010
0
1
0
1
0
1
3
2
1000
1001
1011
1010
1
0
1000
1001
1011
1010
x1
1
0
8
9
11
10
1100
1101
1111
1110
x1
1
1
1
0
x2
1100
1101
1111
1110
1
1
1
0
0100
0101
0111
0110
12
13
15
14
0
0
1
0
x2
0100
0101
0111
0110
0
0
1
0
x3
4
5
7
6
x3
Tallinn University of Technology 2012
3
Метод карт Карно - МДНФ
x4
0000
0001
0011
0010
0
1
0
1
3
2
1000
1001
1011
1010
1
0
X1X3X4vX1X2X4vX3X4vX2X3
x1
8
9
11
10
1100
1101
1111
1110
1
1
1
0
12
13
15
14 x2
0100
0101
0111
0110
0
0
1
0
4
5
7
6
x3
Tallinn University of Technology 2012
4
Метод карт Карно - МКНФ
x4
0000
0001
0011
0010
0
1
(X
0
1
3
2
3vX1)(X2vX4)(X1vX3vX4)
1000
1001
1011
1010
1
0
x1
8
9
11
10
1100
1101
1111
1110
1
1
1
0
12
13
15
14 x2
0100
0101
0111
0110
0
0
1
0
4
5
7
6
x3
Tallinn University of Technology 2012
5
Метод Мак-Класки – МДНФ этап I
100
0
(8)
1000
110
1 (2)
0010
0
M¹= 
(1)
0001
110
1
(12 1100
1111
0111
2 (3)
0011
001
(10 1010
0
000
(13 1101
1
M¯= 
001
1
3 (7)
0111
101
(11) 1011
1
4 (15 1111
101
Tallinn University of Technology 2012
6
0
Метод Мак-Класки – МДНФ этап I
(8/12)
1-00
(8)
1000
(8/12)
10-1
1 (2)
0010
1 (2/3)
001-
(1)
0001
(2/10)
-010
1 (2/3/10/11) -01-
(12 1100
(2/10/3/11) -01-
(1/3)
00-1
2 (3)
0011
(12/13) 110-
2 (3/11/7/15) --11
(10 1010
(3/7/11/15) --11
2 (3/11)
-011
(13 1101
(3/7)
0-11
(10/11) 101-
3 (7)
0111
(13/15) 11-1
(11) 1011
3 (7/15)
-111
4 (15 1111
(1
T
1/15)allinn Un
1-11 iversity of Technology 2012
7
Метод Мак-Класки – МДНФ этап II
Построение импликантной матрицы и решение задачи покрытия.
1000 1100 1101 1111 0111 0010
--11
1-00     -01-     11-1     или  110-
-01-
0
0
0
0
0
1
X3X4      X1X3X4         X2X3       X1X2X4   или   
--11
0
0
0
1
1
0
X1X2X3
1-00
1
1
0
0
0
0
10-0
1
0
0
0
0
0
X
00-1
0
0
0
0
0
0
3X4vX1X3X4vX2X3vX1X2X4
110-
0
1
1
0
0
0
11-1
0
0
1
1
0
0
Tallinn University of Technology 2012
8
Метод Мак-Класки – МКНФ этап I
000
0
0
(0)
0000
010
M°= 
0
1
(4)
0100
(1)
0001
100
1
(9)
1001
010
1
(5)
0101
1110
2
(6)
0110
000
011
(3)
0011
1
0
M¯= 
001
(10 1010
1
101
3
(14 1110
1
101
Tallinn Un
(11 iversit
101y
1 of Technology 2012
9
0
Метод Мак-Класки – МКНФ этап I
0
(0/4)
0-00
0
(0)
0000
(0/1)
000-
(0/1/1/3)
00--
1
(4)
0100
(0/1/1/3)
00--
(1/9)
-001
(1)
0001
1
(0/1/1/9)
-00-
1
(0/1/1/9)
-00-
1
(1/3)
00-1
(9)
1001
(0/1/4/5)
0-0-
(0/1/4/5)
0-0-
(4/5)
010-
(5)
0101
(0/4/4/6)
0--0
(0/4/4/6)
0--0
(4/6)
01-0
2
(6)
0110
(1/9/9/11)
-0-1
(1/9/9/11)
-0-1
(9/11)
10-1
(3)
0011
(1/9/3/11)
-0-1
2
(1/3/9/11)
-0-1
(6/14)
-110
(10 1010
2
(1/3/9/11)
-0-1
(1/3/3/11)
-0-1
2
(3/11)
-011
(1/3/3/11)
-0-1
(4/6/6/14)
-11-
3
(14 1110
(10/14 1-10
(4/6/6/14)
-11-
(11 1011
(10/11 101-
) Tallinn University of Technology 2012
10
Метод Мак-Класки – МКНФ этап II
0000
0100
1001
0101 1110 0110
0-0-
 -0-1 1-10
00--
1
0
0
0
0
0
(X1vX3)(X2vX4)(X1vX3vX4)
-00-
1
0
1
0
0
0
0-0-
1
1
0
1
0
0
0--0
10
1
0
0
0
1
-0-1
0
0
1
0
0
0
-0-1
0
0
1
0
0
1
-0-1
0
0
1
0
0
1
-11-
0
0
0
0
1
1
1-10
0
0
0
0
1
0
101-
0
0
0
0
0
0
Tallinn University of Technology 2012
11
Преобразование к базису {&, ¬}
Преобразование МДНФ
X3X4vX1X3X4vX2X3vX1X2X4 = (X4vX2)X3v(X3X4vX2X4)X1 = (X4vX2)X3(X3X
= 4 v
XX
4 2
XX
2 4
X)X
3X 1
3     
X4X2X4X1 
                                                                           
             
Преобразование МКНФ
(X3vX1)(X2vX4)(X1vX3vX4) = (X3vX1)(X2vX4)(X1vX3vX4) = (X3X1)(X2X4)(X1X3X4) 
Tallinn University of Technology 2012
12
Преобразование к базису {↑}
X
4X2X3X3X4X2X4X1  (X4X2X3) 
) =
↑(X3X4X2X4X1  
= (((X4 ↑X4) ↑X2) ↑X3) ↑(((((X3 ↑X3) ↑(X4 ↑X4)) ↑(X2 ↑X4)) 
↑X1)
Tallinn University of Technology 2012
13
Представление (реализация) 
схемой
Tallinn University of Technology 2012
14

Document Outline

• Slide 1
• Исходная функция
• Отмеченная карта Карно
• Метод карт Карно - МДНФ
• Метод карт Карно - МКНФ
• Метод Мак-Класки – МДНФ этап I
• Метод Мак-Класки – МДНФ этап I
• Метод Мак-Класки – МДНФ этап II
• Метод Мак-Класки – МКНФ этап I
• Метод Мак-Класки – МКНФ этап I
• Метод Мак-Класки – МКНФ этап II
• Преобразование к базису
• Преобразование к базису
• Представление (реализация) схемой