Что такое findslide.org?

FindSlide.org - это сайт презентаций, докладов, шаблонов в формате PowerPoint.

Для правообладателей

Обратная связь

Email: Нажмите что бы посмотреть 

Яндекс.Метрика

Презентация на тему Минимизация логических функций. Вычислительная техника

Содержание

Минимизация упрощение формы записисхема реализуется с наименьшим числом элементов
Минимизация логических функцийВычислительная техника Минимизация упрощение формы записисхема реализуется с наименьшим числом элементов Минимальная нормальная формаНормальная форма логической функции, содержащая наименьшее число элементовМинимальная ДНФ = Методы минимизацииНепосредственных преобразованийКвайна и Мак-КласкиКарно-Вейча МЕТОД НЕПОСРЕДСТВЕННЫХ ПРЕОБРАЗОВАНИЙ Минимизация логических функций Метод непосредственных преобразований Применение законов алгебры логики Результат − тупиковая форма логической функции Тупиковая формаЛогическое выражение, к слагаемым которого больше не могут быть применены операции Функции a и b называются равносильными, если при одинаковых входных данных они ЗАКОНЫ ЛОГИКИ 1. Идемпотентностьa & a ≡ a a ∨ a ≡ a 2. Коммутативностьa & b ≡ b & aa ∨ b ≡ b ∨ a 3. Ассоциативностьa & (b & с) ≡ (a & b) & сa 4. Дистрибутивностьa & (b∨с) ≡ (a & b) ∨ (a & с)a 5. Закон двойного отрицания¬(¬a) ≡ a 6. Законы поглощенияa & (a ∨ b) ≡ aa ∨ (a & b) ≡ a 7. Законы де Моргана¬(a ∨ b) ≡ ¬a & ¬ b¬(a & 8. Закон исключённого третьего¬a ∨ a ≡ 1 9. Закон противоречия¬a & a ≡ 0 10. Свойства тавтологии и противоречия1 & a ≡ a 1 11. Законы склеивания(a & b) ∨ (a & ¬b) ≡ a(a ∨ 12. Законы поглощенияa & (a ∨ b) ≡ aa ∨ (a & b) ≡ a ПримерМинимизировать СДНФ(¬А ⋅ ¬В ⋅ С) ∨∨(А ⋅ ¬В ⋅ С) ∨∨(А ⋅ В ⋅ С) Пример(¬А ⋅ ¬В ⋅ С) ∨(А ⋅ ¬В ⋅ С) ∨∨(А ⋅ В ⋅ С) ≡ Пример(¬А ⋅ ¬В ⋅ С) ∨(А ⋅ ¬В ⋅ С) ∨∨(А ⋅ В ⋅ С) ≡ Пример(¬А ⋅ ¬В ⋅ С) ∨(А ⋅ ¬В ⋅ С) ∨∨(А ⋅ В ⋅ С) ≡ Пример(¬А ⋅ ¬В ⋅ С) ∨(А ⋅ ¬В ⋅ С) ∨∨(А ⋅ Пример(¬А ⋅ ¬В ⋅ С) ∨(А ⋅ ¬В ⋅ С) ∨∨(А ⋅ ПроблемаОпределить, какие элементарные конъюнкции / дизъюнкции надо склеивать КАРТЫ ВЕЙЧА-КАРНОМинимизация логических функций Эдвард Вестбрук ВейчАмериканский физик1952 «Метод диаграмм для минимизации логических функций»1924 — 2013 Морис Карнород. 1924Американский физик1953Усовершенствовал метод Вейча Карта КарноГрафическое представление таблицы истинности логических функций Таблица, содержащая по 2n прямоугольных Код Грея система счисления, в которой два соседних значения различаются только в одном разряде Пример Пример Пример Пример Пример Пример Пример Правила ДНФ КНФ1. Объединяем смежные клетки с единицами (нулями) Правила5. Крайние строки и столбцы являются соседними между собой Правила6.Несмежные области, расположенные симметрично оси(ей), могут объединяться в одну Правила 7. Для каждой области записываем конъюнкцию (дизъюнкцию) переменных, не изменяющих своё ПримерF = ¬ X2 ∨ X1 Пример ‒ МДНФF = X1 ⋅¬ X2 ∨ ¬X1⋅ X2 Пример ‒ МКНФF = (X1 ∨ X2) ⋅ (¬X1∨ ¬ X2) Пример Формула(¬А ⋅ ¬В ⋅ С) ∨∨(А ⋅ ¬В ⋅ С) ∨∨(А ⋅ (А ∨ В ∨ С) ⋅⋅ (А ∨ ¬В ∨ С) ⋅⋅ Пример ПримерF = ¬В ⋅ С ∨ A ⋅ CМДНФ ПримерF = С ⋅ (A ∨ ¬В)МКНФ НедостаткиПрименим для функций до 7 переменныхВыбор областей ‒ визуальноНет алгоритма, обеспечивающего оптимальное решение МЕТОД КВАЙНА И МАК-КЛАСКИ Минимизация логических функций Виллард ван Орман КуайнАмериканский философ, логик и математик1993премия Рольфа Шока в области Эдвард Дж. Мак-КласкиПочётный профессор Стэнфордского университета.Пионер в области электротехникиПервый алгоритм проектирования комбинационных схем1908 — 2000 Метод Квайна и Мак-Класкицелесообразно, когда число входных переменных превышает 6 – 7
Слайды презентации

Слайд 2 Минимизация
упрощение формы записи
схема реализуется с наименьшим числом

Минимизация упрощение формы записисхема реализуется с наименьшим числом элементов

элементов

Слайд 3 Минимальная нормальная форма
Нормальная форма логической функции, содержащая наименьшее

Минимальная нормальная формаНормальная форма логической функции, содержащая наименьшее число элементовМинимальная ДНФ

число элементов
Минимальная ДНФ = МДНФ
Минимальная КНФ = МКНФ
Логическая функция

может иметь несколько МДНФ или МКНФ одинаковой сложности

Слайд 4 Методы минимизации
Непосредственных преобразований
Квайна и
Мак-Класки


Карно-Вейча

Методы минимизацииНепосредственных преобразованийКвайна и Мак-КласкиКарно-Вейча

Слайд 5 МЕТОД НЕПОСРЕДСТВЕННЫХ ПРЕОБРАЗОВАНИЙ
Минимизация логических функций

МЕТОД НЕПОСРЕДСТВЕННЫХ ПРЕОБРАЗОВАНИЙ Минимизация логических функций

Слайд 6 Метод непосредственных преобразований

Применение законов алгебры логики
Результат

Метод непосредственных преобразований Применение законов алгебры логики Результат − тупиковая форма логической функции

− тупиковая форма логической функции

Слайд 7 Тупиковая форма
Логическое выражение, к слагаемым которого больше не

Тупиковая формаЛогическое выражение, к слагаемым которого больше не могут быть применены

могут быть применены операции склеивания
Для одной функции может существовать

несколько тупиковых форм
Минимальная форма − тупиковая форма логической функции минимальной длины

Слайд 8 Функции a и b называются равносильными, если при

Функции a и b называются равносильными, если при одинаковых входных данных

одинаковых входных данных они принимают одинаковые значения
a ≡ b

Слайд 9 ЗАКОНЫ ЛОГИКИ

ЗАКОНЫ ЛОГИКИ

Слайд 10 1. Идемпотентность
a & a ≡ a
a ∨

1. Идемпотентностьa & a ≡ a a ∨ a ≡ a

a ≡ a

Слайд 11 2. Коммутативность
a & b ≡ b & a
a

2. Коммутативностьa & b ≡ b & aa ∨ b ≡ b ∨ a

∨ b ≡ b ∨ a

Слайд 12 3. Ассоциативность
a & (b & с) ≡ (a

3. Ассоциативностьa & (b & с) ≡ (a & b) &

& b) & с
a ∨ (b ∨ с) ≡

(a ∨ b) ∨ с

Слайд 13 4. Дистрибутивность
a & (b∨с) ≡ (a & b)

4. Дистрибутивностьa & (b∨с) ≡ (a & b) ∨ (a &

∨ (a & с)
a ∨ (b & с) ≡

(a ∨ b) & (a ∨ с)


Слайд 14 5. Закон двойного отрицания
¬(¬a) ≡ a


5. Закон двойного отрицания¬(¬a) ≡ a

Слайд 15 6. Законы поглощения
a & (a ∨ b) ≡

6. Законы поглощенияa & (a ∨ b) ≡ aa ∨ (a & b) ≡ a

a
a ∨ (a & b) ≡ a


Слайд 16 7. Законы де Моргана
¬(a ∨ b) ≡ ¬a

7. Законы де Моргана¬(a ∨ b) ≡ ¬a & ¬ b¬(a

& ¬ b
¬(a & b) ≡ ¬a ∨ ¬

b


Слайд 17 8. Закон исключённого третьего
¬a ∨ a ≡ 1


8. Закон исключённого третьего¬a ∨ a ≡ 1

Слайд 18 9. Закон противоречия
¬a & a ≡ 0

9. Закон противоречия¬a & a ≡ 0

Слайд 19 10. Свойства тавтологии и противоречия
1 & a ≡

10. Свойства тавтологии и противоречия1 & a ≡ a 1

a 1 ∨ a ≡ 1
0 &

a ≡ 0 0 ∨ a ≡ a
¬ 0 ≡ 1 ¬ 1 ≡ 0



Слайд 20 11. Законы склеивания
(a & b) ∨ (a &

11. Законы склеивания(a & b) ∨ (a & ¬b) ≡ a(a

¬b) ≡ a
(a ∨ b) & (a ∨ ¬

b) ≡ a

Слайд 21 12. Законы поглощения
a & (a ∨ b) ≡

12. Законы поглощенияa & (a ∨ b) ≡ aa ∨ (a & b) ≡ a

a
a ∨ (a & b) ≡ a


Слайд 22 Пример
Минимизировать СДНФ
(¬А ⋅ ¬В ⋅ С) ∨
∨(А ⋅

ПримерМинимизировать СДНФ(¬А ⋅ ¬В ⋅ С) ∨∨(А ⋅ ¬В ⋅ С) ∨∨(А ⋅ В ⋅ С)

¬В ⋅ С) ∨
∨(А ⋅ В ⋅ С)



Слайд 23 Пример
(¬А ⋅ ¬В ⋅ С) ∨(А ⋅ ¬В

Пример(¬А ⋅ ¬В ⋅ С) ∨(А ⋅ ¬В ⋅ С) ∨∨(А ⋅ В ⋅ С) ≡

⋅ С) ∨
∨(А ⋅ В ⋅ С) ≡



Слайд 24 Пример
(¬А ⋅ ¬В ⋅ С) ∨(А ⋅ ¬В

Пример(¬А ⋅ ¬В ⋅ С) ∨(А ⋅ ¬В ⋅ С) ∨∨(А ⋅ В ⋅ С) ≡

⋅ С) ∨
∨(А ⋅ В ⋅ С) ≡



Слайд 25 Пример
(¬А ⋅ ¬В ⋅ С) ∨(А ⋅ ¬В

Пример(¬А ⋅ ¬В ⋅ С) ∨(А ⋅ ¬В ⋅ С) ∨∨(А ⋅ В ⋅ С) ≡

⋅ С) ∨
∨(А ⋅ В ⋅ С) ≡



Слайд 26 Пример
(¬А ⋅ ¬В ⋅ С) ∨(А ⋅ ¬В

Пример(¬А ⋅ ¬В ⋅ С) ∨(А ⋅ ¬В ⋅ С) ∨∨(А

⋅ С) ∨
∨(А ⋅ В ⋅ С) ≡
(¬А ⋅

¬В ⋅ С) ∨ (А ⋅ ¬В ⋅ С) ∨
∨ (А ⋅ ¬В ⋅ С) ∨ (А ⋅ В ⋅ С)



Слайд 27 Пример
(¬А ⋅ ¬В ⋅ С) ∨(А ⋅ ¬В

Пример(¬А ⋅ ¬В ⋅ С) ∨(А ⋅ ¬В ⋅ С) ∨∨(А

⋅ С) ∨
∨(А ⋅ В ⋅ С) ≡
(¬А ⋅

¬В ⋅ С) ∨ (А ⋅ ¬В ⋅ С) ∨
∨(А ⋅ ¬В ⋅ С) ∨ (А ⋅ В ⋅ С)
≡ (¬В ⋅ С) ∨ (А ⋅ С) ≡
≡ С ⋅ (А ∨ ¬В)



Слайд 28

Слайд 29

Слайд 30 Проблема
Определить, какие элементарные конъюнкции / дизъюнкции надо склеивать

ПроблемаОпределить, какие элементарные конъюнкции / дизъюнкции надо склеивать

Слайд 31 КАРТЫ ВЕЙЧА-КАРНО
Минимизация логических функций

КАРТЫ ВЕЙЧА-КАРНОМинимизация логических функций

Слайд 32 Эдвард Вестбрук Вейч
Американский физик


1952
«Метод диаграмм для минимизации

Эдвард Вестбрук ВейчАмериканский физик1952 «Метод диаграмм для минимизации логических функций»1924 — 2013

логических функций»


1924 — 2013

Слайд 33 Морис Карно
род. 1924
Американский физик

1953
Усовершенствовал метод Вейча

Морис Карнород. 1924Американский физик1953Усовершенствовал метод Вейча

Слайд 34 Карта Карно
Графическое представление таблицы истинности логических функций
Таблица,

Карта КарноГрафическое представление таблицы истинности логических функций Таблица, содержащая по 2n

содержащая по 2n прямоугольных ячеек,
где n — число

логических переменных

Слайд 35 Код Грея
система счисления, в которой два соседних

Код Грея система счисления, в которой два соседних значения различаются только в одном разряде

значения различаются только в одном разряде

Слайд 36 Пример

Пример

Слайд 37 Пример

Пример

Слайд 38 Пример

Пример

Слайд 39 Пример

Пример

Слайд 40

Слайд 41 Пример

Пример

Слайд 42 Пример

Пример

Слайд 43 Пример

Пример

Слайд 44 Правила
ДНФ КНФ
1. Объединяем смежные

Правила ДНФ КНФ1. Объединяем смежные клетки с единицами (нулями) в

клетки с единицами (нулями) в максимально возможные области, содержащие

2n клеток
2. В области НЕ должно находиться клеток, содержащих нули (единицы)
3. Области могут пересекаться
4. Возможно несколько вариантов покрытия

Слайд 45 Правила
5. Крайние строки и столбцы являются соседними между

Правила5. Крайние строки и столбцы являются соседними между собой

собой

Слайд 46 Правила
6.Несмежные области, расположенные симметрично оси(ей), могут объединяться в

Правила6.Несмежные области, расположенные симметрично оси(ей), могут объединяться в одну

одну



Слайд 47 Правила
7. Для каждой области записываем конъюнкцию (дизъюнкцию)

Правила 7. Для каждой области записываем конъюнкцию (дизъюнкцию) переменных, не изменяющих

переменных, не изменяющих своё значение
Если неизменная переменная равна

нулю (единице) − инвертируем
8.Конъюнкции (дизъюнкции) областей объединяем дизъюнкцией (конъюнкцией).

Слайд 48 Пример


F = ¬ X2 ∨ X1

ПримерF = ¬ X2 ∨ X1

Слайд 49 Пример ‒ МДНФ


F = X1 ⋅¬ X2 ∨

Пример ‒ МДНФF = X1 ⋅¬ X2 ∨ ¬X1⋅ X2

¬X1⋅ X2

Слайд 50 Пример ‒ МКНФ


F = (X1 ∨ X2) ⋅

Пример ‒ МКНФF = (X1 ∨ X2) ⋅ (¬X1∨ ¬ X2)

(¬X1∨ ¬ X2)

Слайд 51 Пример

Пример

Слайд 52 Формула
(¬А ⋅ ¬В ⋅ С) ∨
∨(А ⋅ ¬В

Формула(¬А ⋅ ¬В ⋅ С) ∨∨(А ⋅ ¬В ⋅ С) ∨∨(А

⋅ С) ∨
∨(А ⋅ В ⋅ С)

Совершенная дизъюнктивная нормальная

форма (СДНФ)

Слайд 53 (А ∨ В ∨ С) ⋅
⋅ (А ∨

(А ∨ В ∨ С) ⋅⋅ (А ∨ ¬В ∨ С)

¬В ∨ С) ⋅
⋅ (А ∨¬ В ∨ ¬С)

⋅
⋅ (¬А ∨ В ∨ С) ⋅
⋅ (¬А ∨ ¬В ∨ С)

Совершенная конъюнктивная нормальная форма (СКНФ)



Слайд 54 Пример



Пример

Слайд 55 Пример







F = ¬В ⋅ С ∨ A ⋅

ПримерF = ¬В ⋅ С ∨ A ⋅ CМДНФ

C

МДНФ


Слайд 56 Пример







F = С ⋅ (A ∨ ¬В)

МКНФ



ПримерF = С ⋅ (A ∨ ¬В)МКНФ

Слайд 57

Слайд 58 Недостатки
Применим для функций до 7 переменных
Выбор областей ‒

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

визуально
Нет алгоритма, обеспечивающего оптимальное решение

Слайд 59 МЕТОД КВАЙНА И МАК-КЛАСКИ
Минимизация логических функций

МЕТОД КВАЙНА И МАК-КЛАСКИ Минимизация логических функций

Слайд 60 Виллард ван Орман Куайн
Американский философ, логик и математик


1993
премия

Виллард ван Орман КуайнАмериканский философ, логик и математик1993премия Рольфа Шока в

Рольфа Шока в области логики и философии

1908 — 2000

Слайд 61 Эдвард Дж. Мак-Класки
Почётный профессор Стэнфордского университета.

Пионер в области

Эдвард Дж. Мак-КласкиПочётный профессор Стэнфордского университета.Пионер в области электротехникиПервый алгоритм проектирования комбинационных схем1908 — 2000

электротехники

Первый алгоритм проектирования комбинационных схем
1908 — 2000

  • Имя файла: minimizatsiya-logicheskih-funktsiy-vychislitelnaya-tehnika.pptx
  • Количество просмотров: 108
  • Количество скачиваний: 1
- Предыдущая Товарный знак. Фирменное наименование
Следующая - Аттестационная работа. Я плюс компьютер равно здоровье?

Похожие презентации

Прямоугольная система координат Прямоугольная система координат 68
Умножение и деление на 3 план-конспект урока по математике (2 класс) по теме Умножение и деление на 3 план-конспект урока по математике (2 класс) по теме 93
Виды углов треугольника методическая разработка по математике (3 класс) Виды углов треугольника методическая разработка по математике (3 класс) 33
Число и цифра 5 план-конспект урока по математике (1 класс) по теме Число и цифра 5 план-конспект урока по математике (1 класс) по теме 96
Геометричні фігури Геометричні фігури 84
Правила дорожного движения + математика = безопасность на дорогах Правила дорожного движения + математика = безопасность на дорогах 98
Презентация Переместительное свойство сложения Презентация Переместительное свойство сложения 88
Cоотношение предметов двух заданных форм при выборе из четырёх. презентация урока для интерактивной доски по математике (младшая группа) Cоотношение предметов двух заданных форм при выборе из четырёх. презентация урока для интерактивной доски по математике (младшая группа) 36
Презентация по математике Деление десятичных дробей Презентация по математике Деление десятичных дробей 90
Математика в нашей жизни Математика в нашей жизни 88
Устный счёт по теме Сложение и вычитание чисел в пределах 100 Устный счёт по теме Сложение и вычитание чисел в пределах 100 78
Презентация Современный урок математики Презентация Современный урок математики 88
Тема урока: Число и цифра 7. учебно-методический материал по математике (1 класс) по теме Тема урока: Число и цифра 7. учебно-методический материал по математике (1 класс) по теме 38
my protiv narkotikov my protiv narkotikov 38
Математика 1 класс Решение уравнений план-конспект урока по математике (1 класс) по теме Математика 1 класс Решение уравнений план-конспект урока по математике (1 класс) по теме 115
Тема: Виды треугольников план-конспект урока по математике (4 класс) Тема: Виды треугольников план-конспект урока по математике (4 класс) 105
Презентация к уроку математики Повторение изученного в 3 четв презентация к уроку математики (2 класс) по теме Презентация к уроку математики Повторение изученного в 3 четв презентация к уроку математики (2 класс) по теме 97
Решение задач на комбинации многогранников и тел вращения Решение задач на комбинации многогранников и тел вращения 115
Учебно- методический комплект :Когда делимое меньше делителя 4 класс. учебно-методический материал по математике (4 класс) по теме Учебно- методический комплект :Когда делимое меньше делителя 4 класс. учебно-методический материал по математике (4 класс) по теме 154
Как возникла геометрия Как возникла геометрия 73
Презентация по теме Проценты в нашей жизни (6 класс) Презентация по теме Проценты в нашей жизни (6 класс) 106
Презентация по математике на тему Касательная к окружности Презентация по математике на тему Касательная к окружности 110
Сложение и вычитание вида : а +_4,5,6,7,8,9 Сложение и вычитание вида : а +_4,5,6,7,8,9 103
План-конспект занятия Спешим на помощь любимым героям! методическая разработка по математике (старшая группа) по теме План-конспект занятия Спешим на помощь любимым героям! методическая разработка по математике (старшая группа) по теме 101
Условие перпендикулярности прямой и плоскости Условие перпендикулярности прямой и плоскости 83
Презентация И прекрасна и сильна математика страна презентация к уроку по математике (старшая группа) Презентация И прекрасна и сильна математика страна презентация к уроку по математике (старшая группа) 133
Презентация к уроку по теме График квадратичной функции Презентация к уроку по теме График квадратичной функции 76
Сюжетные задачи Сюжетные задачи 108
Морской пейзаж Морской пейзаж 100
Таблица умножения на 7 Таблица умножения на 7 84