Алгебра логики
<<  Арифметические операции Приоритет арифметических операций Математические функции Массивы Логические операции Приоритет операций Готовые для 3 класса легко без регистраций смс  >>
4. Минимизация логических функций
4. Минимизация логических функций
Логическая функция может иметь несколько различных минимальных
Логическая функция может иметь несколько различных минимальных
Пример: для данной логической функции
Пример: для данной логической функции
Найдем МДНФ:
Найдем МДНФ:
4.2 Минимизация логических функций с помощью карты Карно
4.2 Минимизация логических функций с помощью карты Карно
Пример 4.2.1 пусть логическая функция задана своей областью единиц f
Пример 4.2.1 пусть логическая функция задана своей областью единиц f
Карта Карно логической функции 3-х переменных – это таблица размера 2
Карта Карно логической функции 3-х переменных – это таблица размера 2
Пример 4.2.2 пусть задана логическая функция f (X1 , X2 , X3 ) =
Пример 4.2.2 пусть задана логическая функция f (X1 , X2 , X3 ) =
Карта Карно логической функции 4-х переменных – это таблица размера 4
Карта Карно логической функции 4-х переменных – это таблица размера 4
Пример 4.2.3 пусть задана логическая функция f (X1 , X2 , X3 , Х4 ) =
Пример 4.2.3 пусть задана логическая функция f (X1 , X2 , X3 , Х4 ) =
Карта Карно логической функции 5-ти переменных – это 2 таблицы размера
Карта Карно логической функции 5-ти переменных – это 2 таблицы размера
Пример 4.2.4 пусть задана логическая функция f (X1 , X2 , X3 , Х4 ,
Пример 4.2.4 пусть задана логическая функция f (X1 , X2 , X3 , Х4 ,
Карты Карно логических функций 2-х, 3-х и 4-х переменных – 2-мерные, т
Карты Карно логических функций 2-х, 3-х и 4-х переменных – 2-мерные, т
Свойства карт Карно:
Свойства карт Карно:
Соседние клетки карты Карно = клетки, имеющие общую сторону, учитывая
Соседние клетки карты Карно = клетки, имеющие общую сторону, учитывая
Соседними клетками к клетке 5 (0101) являются клетки 1 (0001), 4
Соседними клетками к клетке 5 (0101) являются клетки 1 (0001), 4
Вспомогательные понятия:
Вспомогательные понятия:
Интервал единиц логической функции: интервал, для всех векторов
Интервал единиц логической функции: интервал, для всех векторов
Koнтуры карты Карно:
Koнтуры карты Карно:
Контуры:
Контуры:
Связь контуров с интервалами:
Связь контуров с интервалами:
Алгоритм минимизации методом карты Карно :
Алгоритм минимизации методом карты Карно :
Пример 4.2.6 пусть задана логическая функция f (X1 , X2 , X3 ) =
Пример 4.2.6 пусть задана логическая функция f (X1 , X2 , X3 ) =
Недостатки метода Карно:
Недостатки метода Карно:
Определения:
Определения:
Пример 4.2.7 пусть задана логическая функция f (X1 , X2 , X3 ) =
Пример 4.2.7 пусть задана логическая функция f (X1 , X2 , X3 ) =
Все максимальные интервалы нулей:
Все максимальные интервалы нулей:

Презентация на тему: «Минимизация логических функций». Автор: Моника. Файл: «Минимизация логических функций.pps». Размер zip-архива: 249 КБ.

Минимизация логических функций

содержание презентации «Минимизация логических функций.pps»
СлайдТекст
1 4. Минимизация логических функций

4. Минимизация логических функций

Карты Карно.

Задача минимизации логической функции заключается в том, чтобы найти наиболее компактное её представление в виде нормальной формы минимальной сложности – минимальной дизъюнктивной нормальной формы (МДНФ) или минимальной конъюнктивной нормальной формы (МКНФ).

Минимальной сложности ДНФ = МДНФ. Минимальной сложности КНФ = МКНФ.

Минимальная нормальная форма логической функции – это из всех возможных нормальных форм такая нормальная форма, которая содержит наименьшее число компонентов вида Xi или ? Xi .

2 Логическая функция может иметь несколько различных минимальных

Логическая функция может иметь несколько различных минимальных

нормальных форм МДНФ или МКНФ равной сложности.

4.1 Минимизация логических функций путем преобразований

Алгоритм:

1. шаг: найти ДНФ или КНФ

2. Шаг: выполнить все возможные поглощения и склеивания по формулам 10 и 11:

10. Законы склеивания: (A & B) ? (A & ? B) ? A (A ? B) & (A ? ? B) ? A

11. Законы поглощения: A & (A ? B) ? A A ? (A & B) ? A

3 Пример: для данной логической функции

Пример: для данной логической функции

f(X1, X2, X3) = (X1 ? (? X2 ? X3 )) ? (? X1 ? X2)

найти а) ДНФ и МДНФ; b) КНФ и МКНФ.

Решение:

9.a)

8.a)

( X1 ? (?X2 ? X3)) ? (? X1 ? X2) = ( X1 ? (?X2 ? X3)) & (? X1 ? X2) ? ? ?( X1 ? (?X2 ? X3)) & ?(? X1 ? X2) = (? X1 ? ?X2 ? X3) & (? X1 ? X2) ? ? ?(?X1 ? (?X2 ? X3)) & X1 & ?X2 = (? X1 ? ?X2 ? X3) & (? X1 ? X2) ? ? X1 & X2 & ?X3 & X1 & ?X2 = (? X1 ? ?X2 ? X3) & (? X1 ? X2) = = ?X1& ?X1 ? ?X1&X2 ? ?X2&?X1 ? ?X2&X2 ? X3& ?X1 ? X3&X2 = =?X1 ? ?X1&X2 ? ? X1& ?X2 ? ? X1&X3 ? X2&X3

8.a)

7.b)

7.B) дважды

4.a)

0

5.А)

6.f)

0

Кнф

Днф

4 Найдем МДНФ:

Найдем МДНФ:

Найдем МКНФ:

11.b )

?X1 ? ?X1&X2 ? ? X1& ?X2 ? ? X1&X3 ? X2&X3 = ?X1 ? X2&X3

11.а ) добавим Х3

(?X1 ? ?X2 ? X3) & (?X1 ? X2) = = (?X1 ? ?X2 ? X3) & (?X1 ? X2) & (?X1 ? X2 ? X3) = = (?X1 ? X3) & (?X1 ? X2)

10.b)

Мднф

Кнф

Мкнф

5 4.2 Минимизация логических функций с помощью карты Карно

4.2 Минимизация логических функций с помощью карты Карно

Карта Карно – топологическое представление таблицы истинности логической функции на плоскости или в пространстве.

Каждой строке таблицы истинности логической функции соответствует одна клетка карты Карно.

Карта Карно логической функции 2-х переменных – это таблица размера 2 x 2:

X2 X1

0

1

0

0

1

1

2

3

6 Пример 4.2.1 пусть логическая функция задана своей областью единиц f

Пример 4.2.1 пусть логическая функция задана своей областью единиц f

(X1 , X2 ) = ?(0,1,3)1

Таблица истинности:

Карта Карно:

X2 X1

0

1

X1 , X2

f (X1 , X2 )

0 0 0

1

0

1 0

1 1

0 1 1

1

1 0 2

0

1

0 2

1 3

1 1 3

1

7 Карта Карно логической функции 3-х переменных – это таблица размера 2

Карта Карно логической функции 3-х переменных – это таблица размера 2

x 4:

X2 X3 X1

00

01

11

10

0

0

1

3

2

1

4

5

7

6

8 Пример 4.2.2 пусть задана логическая функция f (X1 , X2 , X3 ) =

Пример 4.2.2 пусть задана логическая функция f (X1 , X2 , X3 ) =

(1,3,6,7)1

Таблица истинности:

Карта Карно:

X1, X2, X3

f (X1, X2, X3)

X2 X3 X1

00

01

11

10

0

0 0

1 1

1 3

0 2

1

0 4

0 5

1 7

1 6

0 0 0 0

0

0 0 1 1

1

0 1 0 2

0

0 1 1 3

1

1 0 0 4

0

1 0 1 5

0

1 1 0 6

1

1 1 1 7

1

9 Карта Карно логической функции 4-х переменных – это таблица размера 4

Карта Карно логической функции 4-х переменных – это таблица размера 4

x 4:

X3 X4 X1 X2

00

01

11

10

00

0

1

3

2

01

4

5

7

6

11

12

13

15

14

10

8

9

11

10

10 Пример 4.2.3 пусть задана логическая функция f (X1 , X2 , X3 , Х4 ) =

Пример 4.2.3 пусть задана логическая функция f (X1 , X2 , X3 , Х4 ) =

(0,1,6,8,9,12,14)1

Карта Карно:

X3 X4 X1 X2

00

01

11

10

00

1 0

1 1

0 3

0 2

01

0 4

0 5

0 7

1 6

11

1 12

0 13

0 15

1 14

10

1 8

1 9

0 11

0 10

11 Карта Карно логической функции 5-ти переменных – это 2 таблицы размера

Карта Карно логической функции 5-ти переменных – это 2 таблицы размера

4 x 4:

Х5 = 0

Х5 = 1

X3 X4 X1 X2

00

01

11

10

X3 X4 X1 X2

00

01

11

10

00

0

1

3

2

00

16

17

19

18

01

4

5

7

6

01

20

21

23

22

11

12

13

15

14

11

28

29

31

30

10

8

9

11

10

10

24

25

27

26

12 Пример 4.2.4 пусть задана логическая функция f (X1 , X2 , X3 , Х4 ,

Пример 4.2.4 пусть задана логическая функция f (X1 , X2 , X3 , Х4 ,

Х5) = ?(2,3,5,6,7,11,15,16,17,18,19,21,22,23,26,27,30,31)1

Х5 = 0

Х5 = 1

X3 X4 X1 X2

00

01

11

10

X3 X4 X1 X2

00

01

11

10

00

0 0

0 1

1 3

1 2

00

1 16

1 17

1 19

1 18

01

0 4

1 5

1 7

1 6

01

0 20

1 21

1 23

1 22

11

0 12

0 13

1 15

0 14

11

0 28

0 29

1 31

1 30

10

0 8

0 9

1 11

0 10

10

0 24

0 25

1 27

1 26

13 Карты Карно логических функций 2-х, 3-х и 4-х переменных – 2-мерные, т

Карты Карно логических функций 2-х, 3-х и 4-х переменных – 2-мерные, т

е. представимы на плоскости. Карты Карно логических функций 5-ти и 6-ти переменных - 3-х мерные или пространственные.

14 Свойства карт Карно:

Свойства карт Карно:

Каждой клетке карты Карно соответствует один аргумент-вектор логической функции. Число соседних клеток к каждой клетке карты Карно равно числу переменных карты. Аргумент-векторы любых двух соседних клеток карты Карно являются ближайшими друг к другу аргумент-векторами (отличаются друг от друга только в одной координате).

15 Соседние клетки карты Карно = клетки, имеющие общую сторону, учитывая

Соседние клетки карты Карно = клетки, имеющие общую сторону, учитывая

также возможность свернуть карту Карно в пространстве.

Соседними клетками к клетке 3 (011) являются клетки 1 (001), 2 (010) и 7 (111).

Соседними клетками к клетке 4 (100) являются клетки 0 (000), 5 (101) и 6 (110).

X2 X3 X1

00

01

11

10

0

0

1

3

2

1

4

5

7

6

16 Соседними клетками к клетке 5 (0101) являются клетки 1 (0001), 4

Соседними клетками к клетке 5 (0101) являются клетки 1 (0001), 4

(0100), 7 (0111) и 13 (1101).

Соседними клетками к клетке 8 (1000) являются клетки 0 (0000), 9 (1001), 12 (1100) и 10 (1001).

Соседними клетками к клетке 12 (1100) являются клетки 4 (0100), 8 (1000), 13 (1101) и 14 (1110).

X3 X4 X1 X2

00

01

11

10

00

0

1

3

2

01

4

5

7

6

11

12

13

15

14

10

8

9

11

10

17 Вспомогательные понятия:

Вспомогательные понятия:

n-мерное Булево пространство {0,1}n: множество всех возможных двоичных векторов (X1 , X2 ,...,Xn ) длины n .

Ближайшие векторы: двоичные векторы равной длины, которые отличаются друг от друга только в одной координате.

Интервал длины 2m: множество таких двоичных векторов (X1, X2 ,...,Xn ), среди которых для каждого вектора найдется точно m ближайших к нему векторов. Например, {000, 001, 010, 011} или {0100, 0110}.

Компактное представление интервала: представление через постоянные координаты, изменяющиеся координаты заменяют символом ” - ” . {000, 001, 010, 011} = {0 - -} {0100, 0110} = {0 1 - 0}

18 Интервал единиц логической функции: интервал, для всех векторов

Интервал единиц логической функции: интервал, для всех векторов

которого значение функции f(X1 ,X2 ,...,Xn )=1. Максимальный интервал единиц логической функции: такой интервал единиц, который не содержится ни в одном другом интервале единиц.

19 Koнтуры карты Карно:

Koнтуры карты Карно:

Группы клеток карты Карно определенных размеров называют контурами.

Для карт Карно, определенных на плоскости, контурами являются прямоугольники, с допустимыми размерами сторон 2m x 2n, m, n = 0, 1, 2 … 1 x 1 1 x 2 1 x 4 2 x 1 2 x 2 2 x 4 4 x 1 4 x 2 4 x 4

20 Контуры:

Контуры:

X3 X4 X1 X2

00

01

11

10

00

0

1

3

2

01

4

5

7

6

11

12

13

15

14

10

8

9

11

10

21 Связь контуров с интервалами:

Связь контуров с интервалами:

Каждый контур карты Карно соответствует определенному интервалу.

Пример 4.2.5 пусть задана логическая функция f (X1 , X2 ) = ?(0,1,2,3,7)1

{0 - -}={000, 001, 010, 011}

{-11}={011, 111}

{1-0}={100, 110}

{10-}={100, 101}

Карта Карно:

Интервалы:

X2 X3 X1

00

01

11

10

0

1 0

1 1

1 3

1 2

1

0 4

0 5

1 7

0 6

22 Алгоритм минимизации методом карты Карно :

Алгоритм минимизации методом карты Карно :

Представить логическую функцию картой Карно. Покрыть на карте все 1-цы (для получения МДНФ) или все 0-ли (для получения МКНФ) возможно меньшим числом возможно более крупных размеров контурами. Найти для каждого контура соответствующий ему интервал. По постоянным переменным интервалов записать элементарные конъюнкции МДНФ или элементарные дизъюнкций МКНФ по правилу составления СДНФ или СКНФ по заданной области истинности или ложности.

Каждый контур карты Карно дает одну элементарную конъюнкцию в МДНФ или одну элементарную дизъюнкцию в МКНФ .

23 Пример 4.2.6 пусть задана логическая функция f (X1 , X2 , X3 ) =

Пример 4.2.6 пусть задана логическая функция f (X1 , X2 , X3 ) =

(1,3,6,7)1 Найти МДНФ и МКНФ методом Карно.

{0-1}={001, 011}

{11-}={111, 110}

{0-0}={000, 010} и

{10-}={100, 101}

(X1 ? X3) & (?X1 ? X2)

Решение:

X2 X3 X1

00

01

11

10

Карта Карно:

0

0 0

1 1

1 3

0 2

Интервалы области единиц:

1

0 4

0 5

1 7

1 6

Мднф:

?X1&X3 ? X1& X2.

Интервалы области нулей:

Мкнф:

24 Недостатки метода Карно:

Недостатки метода Карно:

Метод применим только для логических функций до 7-ми переменных. Выбор контуров происходит визуально и не существует алгоритма, обеспечивающего наилучшее, оптимальное решение.

25 Определения:

Определения:

Каждый интервал области единиц логической функции называют импликантой логической функции. Максимальную импликанту (максимальный интервал единиц) называют простой импликантой логической функции. Дизъюнкция всех простых импликант логической функции образуют сокращенную ДНФ логической функции. Аналогичным образом определяются максимальный интервал области нулей логической функции и сокращенная КНФ

26 Пример 4.2.7 пусть задана логическая функция f (X1 , X2 , X3 ) =

Пример 4.2.7 пусть задана логическая функция f (X1 , X2 , X3 ) =

(1,3,6,7)1 Найти сокращенные ДНФ и МКНФ методом Карно.

{0-1}={001, 011}

{-11}={011, 111}

{11-}={111, 110}

?X1&X3 ? X2& X3 ? X1& X2.

Сокращенная ДНФ:

Решение:

Карта Карно:

X2 X3 X1

00

01

11

10

Все простые импликанты:

0

0 0

1 1

1 3

0 2

1

0 4

0 5

1 7

1 6

27 Все максимальные интервалы нулей:

Все максимальные интервалы нулей:

{0-0}={000, 010}

{-00}={000, 100}

{10-}={100, 101}

Сокращенная КНФ:

(X1 ? X3) & (X2 ? X3) & (?X1 ? X2)

X2 X3 X1

00

01

11

10

0

0 0

1 1

1 3

0 2

1

0 4

0 5

1 7

1 6

«Минимизация логических функций»
http://900igr.net/prezentacija/algebra/minimizatsija-logicheskikh-funktsij-173918.html
cсылка на страницу
Урок

Алгебра

35 тем
Слайды
900igr.net > Презентации по алгебре > Алгебра логики > Минимизация логических функций