Минимальные КНФ

1.

Минимальные КНФ

2. Минимальные КНФ

3. Минимальные КНФ

4. Алгоритм минимизации частично определенных функций классе ДНФ

1. СДНФ функции f0 .
2. сокращенная ДНФ функции f1 .
3. С помощью матрицы покрытий коституент
единицы функции f0 простыми импликантами
функции f1 строим все тупиковые ДНФ (для
некоторых доопределений функции f ) .
4. Среди полученных ТДНФ выбираем простейшие,
они являются минимальными ДНФ ( для некоторых
доопределений функции f ) .

5. Алгоритм минимизации частично определенных функций классе ДНФ

6. Алгоритм минимизации частично определенных функций классе ДНФ

7. Алгоритм минимизации частично определенных функций классе ДНФ

f ( x, y, z, t ) = (1---010010-01--1)
x y z t
f f0 f1
0 0 0 0
0 0 0 1
0 0 1 0
0 0 1 1
0 1 0 0
0 1 0 1
0 1 1 0
0 1 1 1
1 0 0 0
1 0 0 1
1 0 1 0
1 0 1 1
1 1 0 0
1 1 0 1
1 1 1 0
1 1 1 1
1
0
1
0
0
1
0
0
1
1
1
0
0
0
0
1
0
0
1
0
0
0
1
0
0
1
1
1
1
1
0
1
0
0
1
0
1
0
1
1
1
1
0000
------0001
0010
1000
-----0011
0101
1010
1100
-----1101
1110
------1111

8.

Алгоритм минимизации частично определенных
функций классе ДНФ
0000 +
------0001 +
0010 +
1000 +
-----0011 +
0101 +
1010 +
1100 +
-----1101 +
1110 +
------1111 +
00000-0
-000
----00-1
0-01
001-010
10-0
1-00
-----
-101
1-10
11011-0
-------11-1
111-

9.

Минимальные формы
0000 +
------0001 +
0010 +
1000 +
-----0011 +
0101 +
1010 +
1100 +
-----1101 +
1110 +
------1111 +
000- +
00-0 +
-000 +
----00-1 +
0-01
001- +
-010 +
10-0 + -101
1-00 + 1-10 +
110- +
----11-0 +
-------11-1 +
111- +
00- -0-0
-----1- -0
------11- -

10.

Минимальные формы

11.

Алгоритм минимизации частично определенных
функций классе ДНФ

12.

Алгоритм минимизации частично определенных
функций классе ДНФ

13.

Алгоритм минимизации частично определенных
функций классе ДНФ

14. Алгоритм минимизации частично определенных функций классе ДНФ

выделяются максимальные прямоугольники,
содержащие хотя бы одну единицу и не содержащие
нулей.
D cf x 1 x 3 x 1 x2 x2 x3 x1 x3 .

15. Алгоритм минимизации частично определенных функций классе ДНФ

16.

Алгоритм минимизации частично определенных
функций классе КНФ
x y z t
f f0 f1 f
h0 h1
0 0 0 0
0 0 0 1
0 0 1 0
0 0 1 1
0 1 0 0
0 1 0 1
0 1 1 0
0 1 1 1
1 0 0 0
1 0 0 1
1 0 1 0
1 0 1 1
1 1 0 0
1 1 0 1
1 1 1 0
1 1 1 1
1
0
1
0
0
1
0
0
1
1
0
0
0
0
1
0
1
1
0
1
0
1
0
0
0
0
1
0
0
0
0
1
0
0
1
0
0
0
1
0
0
1
1 0
1 1 1 0 1
1 0
0 1
0 1
1 0
0 1
1 0 1
1 0
1 1 1 0
0
1
1
1
1
0
1
1
0
1
1
1
0
1
1
0
0001
0010
0100
------0011
0110
1001
1010
------0111
1011
1101
1110

17. Алгоритм минимизации частично определенных функций классе КНФ

0001 +
0010 +
0100 +
------0011 +
0110 +
1001 +
1010 +
------0111 +
1011 +
1101 +
1110 +
00-1
-011
0010-10
-010
01-0
------0-11
-011
011-110
10-1
1011-10
1-01

18. Алгоритм минимизации частично определенных функций классе КНФ

0001 +
0010 +
0100 +
------0011 +
0110 +
1001 +
1010 +
------0111 +
1011 +
1101 +
1110 +
00-1 +
-011 +
001- +
0-10 +
-010 +
01-0
------0-11 +
-011 +
011- +
-110 +
10-1 +
101- +
1-10 +
1-01
-0-1
0-1-01--10
-0-1
0-1-01--10
01-0
1-01

19. Алгоритм минимизации частично определенных функций классе КНФ

-0-1
0-1-01--10
01-0
1-01

20. Алгоритм минимизации частично определенных функций классе КНФ

-0-1
0-1-01--10
01-0
1-01

21. Алгоритм минимизации частично определенных функций классе КНФ

22. Алгоритм минимизации частично определенных функций классе КНФ

-минимальное доопределение функции f в классе КНФ

23. Алгоритм минимизации частично определенных функций классе КНФ

24.

25.

26.

27.

28.

29.

30.

31.

32.

33.

34.

35.

Метод испытания импликант
f (~
x 3 ) x1x3 x4 x2 x3 x4 x1x2 x4 x1x2 x3 x2 x3 x4
x1 x3 x4
x1 0
x3 1
x4 1
0 1 1
0 1 1
1 0 1
1 0 0
0 0 0
3
~
f ( x ) x2 x3 x4 x1x2 x4 x1x2 x3 x2 x3 x4
f (~
x 3 ) x2 1 1 0 x2 1 0 x2 0 x2 0 0 нельзя
x2 0 0 0
x2
ядро

36.

Метод испытания импликант
f (~
x 3 ) x1x3 x4 x2 x3 x4 x1x2 x4 x1x2 x3 x2 x3 x4
x2 x3 x4
x2 0
x3 1
x4 1
f (~
x 3 ) x1x3 x4 x1x2 x4 x1x2 x3 x2 x3 x4
f (~
x 3 ) x1 1 1 x1 1 1 x1 1 0 1 0 0
x1 x1 0 0
1
можно
не ядро

37.

Метод испытания импликант
f (~
x 3 ) x1x3 x4 x2 x3 x4 x1x2 x4 x1x2 x3 x2 x3 x4
ядро
?
?
?
ядро
f (~
x 3 ) x1x3 x4 x1x2 x4 x1x2 x3 x2 x3 x4
ядро
ядро

38.

Метод испытания импликант
f (~
x 3 ) x1x3 x4 x1x2 x4 x1x2 x3 x2 x3 x4
x1x2 x4
x1 1
x2 0
x4 1
3
~
f ( x ) 0 x3 0
нельзя

39.

Метод испытания импликант
f (~
x 3 ) x1x3 x4 x1x2 x4 x1x2 x3 x2 x3 x4
x1x2 x3
x1 1
x2 0
x3 0
f (~
x 3 ) 0 0 x4 0 x4 1
можно

40.

Метод испытания импликант
f (~
x 3 ) x1x3 x4 x2 x3 x4 x1x2 x4 x1x2 x3 x2 x3 x4
f (~
x 3 ) x1x3 x4 x1x2 x4 x2 x3 x4

41.

Операция штрих Шеффера

42.

Операция штрих Шеффера
правила перехода от ДНФ функции к выражению с
использованием операции " Штрих Шеффера ".
- заменить все операции дизъюнкции на операции
Шеффера
- заменить все операции конъюнкции на операции
Шеффера
- группы букв, которые соответствуют дизъюнктивным
членам, заключить в скобки.

43.

Операция (стрелка) Пирса

44.

Операция штрих Шеффера
правила перехода от от КНФ перейти к базису Пирса
- заменить операции дизъюнкции операциями Пирса
- заменить операции конъюнкции операциями Пирса
- заключить в скобки все те группы букв, которые
соответствуют конъюнктивным членам.

45.

45

46.

46

47.

47

48.

48

49.

49

50.

50