Что такое 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
  • Количество просмотров: 126
  • Количество скачиваний: 1
- Предыдущая Товарный знак. Фирменное наименование
Следующая - Аттестационная работа. Я плюс компьютер равно здоровье?

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

Презентация к уроку-путешествию по математике Презентация к уроку-путешествию по математике 101
Как доказать истину в геометрии? Как доказать истину в геометрии? 123
Конспект занятия по ФЭМП в средней группе с применением ЦОР Путешествие к Лунтику презентация к занятию по математике (средняя группа) по теме Конспект занятия по ФЭМП в средней группе с применением ЦОР Путешествие к Лунтику презентация к занятию по математике (средняя группа) по теме 56
Линейная функция Линейная функция 98
prezentaciya po matematike znakomstvo s chislom 5 prezentaciya po matematike znakomstvo s chislom 5 126
Презентация к уроку Доли. Обыкновенные дроби Презентация к уроку Доли. Обыкновенные дроби 105
Презентация к уроку математике во 2 классе Закрепление пройденного. Таблица умножения и деления на 2 учебно-методическое пособие по математике (2 класс) Презентация к уроку математике во 2 классе Закрепление пройденного. Таблица умножения и деления на 2 учебно-методическое пособие по математике (2 класс) 120
Числа от 1 до 20. презентация к уроку по математике (1 класс) Числа от 1 до 20. презентация к уроку по математике (1 класс) 130
Занимательная матемтика презентация к уроку по математике (подготовительная группа) по теме Занимательная матемтика презентация к уроку по математике (подготовительная группа) по теме 142
Нечеткие числа Нечеткие числа 130
Алгоритм построения точек, симметричных данной относительно прямой Алгоритм построения точек, симметричных данной относительно прямой 195
Урок математики Мерка длины. Сантиметр план-конспект урока по математике (1 класс) Урок математики Мерка длины. Сантиметр план-конспект урока по математике (1 класс) 114
Круги Эйлера Круги Эйлера 116
Площадь прямоугольника план-конспект урока по математике (3 класс) Площадь прямоугольника план-конспект урока по математике (3 класс) 128
Свойства функций 8 класс Свойства функций 8 класс 110
Конспект урока по математике. Тема Деление нуля на число презентация к уроку по математике (3 класс) Конспект урока по математике. Тема Деление нуля на число презентация к уроку по математике (3 класс) 175
Презентация по математике на тему Уравнение плоскости Презентация по математике на тему Уравнение плоскости 128
Сложение вычитание положительных отрицательных чисел Сложение вычитание положительных отрицательных чисел 143
Проект Узоры и орнаменты на посуде проект по математике (2 класс) Проект Узоры и орнаменты на посуде проект по математике (2 класс) 239
Презентация научно-исследовательского проекта Математические функции в нашей жизни Презентация научно-исследовательского проекта Математические функции в нашей жизни 147
Шаг за шагом к ОГЭ Шаг за шагом к ОГЭ 120
Геометрические фигуры презентация к уроку по математике (старшая группа) Геометрические фигуры презентация к уроку по математике (старшая группа) 153
Открытый урок по математике в 1 классе : Число и цифра 6. план-конспект урока по математике (1 класс) по теме Открытый урок по математике в 1 классе : Число и цифра 6. план-конспект урока по математике (1 класс) по теме 112
Число 5 - Письмо цифры 5 Число 5 - Письмо цифры 5 111
Древние и новые счеты Древние и новые счеты 121
Решение задач на готовых чертежах. Подобные треугольники Решение задач на готовых чертежах. Подобные треугольники 104
Презентация по математике Деление с остатком Презентация по математике Деление с остатком 144
Презентация к занятию Математическое путешествие методическая разработка по математике (старшая группа) по теме Презентация к занятию Математическое путешествие методическая разработка по математике (старшая группа) по теме 127
Измерение Измерение 114