Конкурсы по математике
<<  Элементы компьютерной математики Птичий КВН  >>
Курс: Элементы компьютерной математики
Курс: Элементы компьютерной математики
Лекция №6
Лекция №6
Пять замечательных классов логических функций
Пять замечательных классов логических функций
Пять замечательных классов логических функций
Пять замечательных классов логических функций
Пять замечательных классов логических функций
Пять замечательных классов логических функций
Пять замечательных классов логических функций
Пять замечательных классов логических функций
Пять замечательных классов логических функций
Пять замечательных классов логических функций
Пять замечательных классов логических функций
Пять замечательных классов логических функций
Пять замечательных классов логических функций
Пять замечательных классов логических функций
Пять замечательных классов логических функций
Пять замечательных классов логических функций
Пять замечательных классов логических функций
Пять замечательных классов логических функций
Пять замечательных классов логических функций
Пять замечательных классов логических функций
Пять замечательных классов логических функций
Пять замечательных классов логических функций
Пять замечательных классов логических функций
Пять замечательных классов логических функций
Пять замечательных классов логических функций
Пять замечательных классов логических функций
Пять замечательных классов логических функций
Пять замечательных классов логических функций
Пять замечательных классов логических функций
Пять замечательных классов логических функций
Пять замечательных классов логических функций
Пять замечательных классов логических функций
Пять замечательных классов логических функций
Пять замечательных классов логических функций
Пять замечательных классов логических функций
Пять замечательных классов логических функций
Пять замечательных классов логических функций
Пять замечательных классов логических функций
ФПС логических функций 2 аргументов могут быть составлены из ЛФ,
ФПС логических функций 2 аргументов могут быть составлены из ЛФ,
Функционально полные системы логических функций
Функционально полные системы логических функций
Функции НЕ, И, ИЛИ (например, f12, f1, f7) также образуют ФПС
Функции НЕ, И, ИЛИ (например, f12, f1, f7) также образуют ФПС
Функционально полные системы логических функций
Функционально полные системы логических функций
Функционально полные системы логических функций
Функционально полные системы логических функций
Доказано, что только монотонные ЛФ могут быть представлены в форме, не
Доказано, что только монотонные ЛФ могут быть представлены в форме, не
В современных ЭВМ в качестве физической величины, соответствующей
В современных ЭВМ в качестве физической величины, соответствующей
Функции f3 и f5 не влияют на полноту системы (табл
Функции f3 и f5 не влияют на полноту системы (табл
Ослабленная теорема о функциональной полноте
Ослабленная теорема о функциональной полноте
Кроме тривиальных ЛФ (f0, f15, f3 и f5) в ФПС целесообразно включить
Кроме тривиальных ЛФ (f0, f15, f3 и f5) в ФПС целесообразно включить
В качестве немонотонной ЛФ, требующей для реализации инвертор, удобно
В качестве немонотонной ЛФ, требующей для реализации инвертор, удобно
То же наблюдается в системах Вебба, Шеффера (три логических элемента
То же наблюдается в системах Вебба, Шеффера (три логических элемента
Формы представления логических функций
Формы представления логических функций
Формы представления логических функций
Формы представления логических функций
Дизъюнктивная нормальная форма (ДНФ) - дизъюнкция конъюнктивных термов
Дизъюнктивная нормальная форма (ДНФ) - дизъюнкция конъюнктивных термов
Теорема
Теорема
Формы представления логических функций
Формы представления логических функций
Отсутствующий в терме аргумент вводится, таким образом, в конъюнкцию и
Отсутствующий в терме аргумент вводится, таким образом, в конъюнкцию и
В дальнейшем, при минимизации, оценка затрат оборудования на
В дальнейшем, при минимизации, оценка затрат оборудования на
Вторую оценку лучше находить, построив сначала логическую
Вторую оценку лучше находить, построив сначала логическую
Процесс минимизации ЛФ в дизъюктивном (Д-) базисе можно представить
Процесс минимизации ЛФ в дизъюктивном (Д-) базисе можно представить
Минимизация логических функций
Минимизация логических функций
Если на каком-то наборе ЛФ f1 принимает значение у1, а ЛФ f2 -
Если на каком-то наборе ЛФ f1 принимает значение у1, а ЛФ f2 -
Таблица 2.8 Импликанта функции f2 Пример
Таблица 2.8 Импликанта функции f2 Пример
Собственная часть конъюнкции - это ее любая сокращенная часть
Собственная часть конъюнкции - это ее любая сокращенная часть
Минимизация логических функций
Минимизация логических функций
Минимизация логических функций
Минимизация логических функций
Минимизация логических функций
Минимизация логических функций
Неполное склеивание отличается от полного только тем, что склеиваемые
Неполное склеивание отличается от полного только тем, что склеиваемые
Минимизация логических функций
Минимизация логических функций
Поглощение:
Поглощение:
В методе испытания термов (простых импликант) ТДНФ находится по СкДНФ
В методе испытания термов (простых импликант) ТДНФ находится по СкДНФ
Затем то же самое проделывают с оставшимся выражением (проход «в
Затем то же самое проделывают с оставшимся выражением (проход «в
Пример 1. Испытание терма (1): терм нелишний
Пример 1. Испытание терма (1): терм нелишний
Испытание терма х1х3 (2): терм нелишний
Испытание терма х1х3 (2): терм нелишний
Таким образом, f(ТДНФ)= «Углубление» далее не производится, поскольку
Таким образом, f(ТДНФ)= «Углубление» далее не производится, поскольку
Метод минимизирующих карт представляет собой просто более удобную
Метод минимизирующих карт представляет собой просто более удобную
Минимизация логических функций
Минимизация логических функций
Геометрический метод минимизации ЛФ имеет ограниченную применимость:
Геометрический метод минимизации ЛФ имеет ограниченную применимость:
Отдельные вершины квадрата соответствуют 2-буквенным термам ( и т.д.),
Отдельные вершины квадрата соответствуют 2-буквенным термам ( и т.д.),
Конечно, есть еще один вариант склеивания вершин - всех четырех, но
Конечно, есть еще один вариант склеивания вершин - всех четырех, но
Кстати, видна прямая связь с методом неопределенных коэффициентов
Кстати, видна прямая связь с методом неопределенных коэффициентов
В примере ЛФ из метода неопределенных коэффициентов (рис
В примере ЛФ из метода неопределенных коэффициентов (рис
Лекция окончена
Лекция окончена

Презентация на тему: «Элементы компьютерной математики». Автор: Lena. Файл: «Элементы компьютерной математики.ppt». Размер zip-архива: 1028 КБ.

Элементы компьютерной математики

содержание презентации «Элементы компьютерной математики.ppt»
СлайдТекст
1 Курс: Элементы компьютерной математики

Курс: Элементы компьютерной математики

Лектор – Склярова Елена Александровна

2 Лекция №6

Лекция №6

Тема: Элементы компьютерной математики (ЭКМ)

II. Элементы математической логики Пять замечательных классов логических функций Функционально полные системы логических функций Формы представления логических функций Минимизация логических функций

3 Пять замечательных классов логических функций

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

Все пять рассматриваемых ниже классов обладают свойством замкнутости: любая ЛФ, полученная из ЛФ каждого класса с помощью операций суперпозиции и подстановки аргументов, принадлежит этому же классу. Функции в этих классах: - линейные; - сохраняющие нуль; - сохраняющие единицу; - монотонные; - самодвойственные.

4 Пять замечательных классов логических функций

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

Линейная ЛФ может быть представлена многочленом Жегалкина не выше первой степени: Таким образом, каждой линейной ЛФ можно поставить в соответствие (n+1)-разрядное число. Тогда количество различных линейных ЛФ n аргументов составит 2n+1. Так, при n = 1 все 21+1 = 4 функции линейны:

5 Пять замечательных классов логических функций

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

Среди ЛФ двух аргументов (табл. 4.) линейных – 22+1 = 8. Можно найти многочлены Жегалкина для всех 16 ЛФ двух аргументов, а затем выбрать из них линейные. Второй способ - выписать все возможные линейные многочлены:

6 Пять замечательных классов логических функций

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

Теорема 1. В результате операций суперпозиции и подстановки аргументов из линейных ЛФ получаются также линейные ЛФ, и только они. Иначе говоря, класс линейных функций замкнут. Аналогичные теоремы будут сформулированы и доказаны для остальных четырех замечательных классов.

7 Пять замечательных классов логических функций

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

Доказательство. А: Суперпозиция. После подстановки выражений Y вместо х в f, раскрытия скобок и приведения подобных получается новая линейная функция Здесь надо заметить, что все произведения вила аibjk тоже имеют значения 0 или 1.

8 Пять замечательных классов логических функций

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

Пример. В: Подстановка аргументов. Здесь доказательство очевидно: линейность формы Жегалкина не зависит от порядка задания аргументов. Пример.

9 Пять замечательных классов логических функций

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

Логическая функция, сохраняющая нуль, на нулевом наборе имеет значение 0. Очевидно, среди ЛФ n аргументов ровно половина функций, сохраняющих нуль, т.е. Q0=2n-1. Так, для n = 2 (табл. 2.4) получаем Q0=24-1=8. Это f0 … f7 (x1, x2).

10 Пять замечательных классов логических функций

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

Теорема 2. В результате операций суперпозиции и подстановки аргументов из ЛФ, сохраняющих нуль, получаются также ЛФ, сохраняющие нуль, и только они. Доказательство. А: Суперпозиция. Тогда f1 (у1, …, уm)0…0 = 0, поскольку Y1, …, Yn на этом же наборе имеют значение 0. Значит, и набор (х1, …, xn) - также нулевой, а здесь f (0, …, 0) = 0.

11 Пять замечательных классов логических функций

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

В: Подстановка аргументов. Доказательство очевидно: перестановка аргументов, имеющих одинаковые значения (нуль), никакой роли не играет, нулевой набор остается нулевым и нулевое значение ЛФ сохраняется. Логическая функция, сохраняющая единицу, на единичном наборе имеет значение 1. Далее все аналогично предшествующему случаю. Так, Q0=2n-1. Восемь ЛФ, сохраняющих единицу, при n=2 (табл. 4) – это f1, f3, f5, f7, f9, f11, f13, f15, т.е. все функции с нечетными номерами.

12 Пять замечательных классов логических функций

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

Теорема 3 и ее доказательство вполне аналогичны случаю теоремы 2. Определение монотонной логической функции требует введения еще одного понятия - сравнимых и несравнимых наборов аргументов. Дело в том, что свойство монотонности обязательно только для пар сравнимых наборов. Итак, два набора аргументов сравнимы, если значению каждого аргумента в каком-то из них соответствует неменьшее значение того же аргумента в другом наборе, т.е. 0 соответствует 0 или 1, а 1 - только 1. Тогда первый из этих наборов считается меньшим, чем другой. Например, наборы (0, 0, 0, 1, 0) и (0, 1, 0, 1, 0) сравнимы, причем первый меньше второго. И, наоборот, наборы (0, 0, 0, 1, 0) и (0, 1, 0, 0, 1) несравнимы, здесь для четырех аргументов выполняется условие «меньше - равно» (0 < 1 или 0 = 0), а для одного - «больше» (1 > 0).

13 Пять замечательных классов логических функций

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

Монотонная логическая функция при любом возрастании набора аргументов имеет неубывающее значение. Несравнимые наборы не рассматриваются. При n = 2 имеем 3 + 2 + 1 = 6 пар наборов. Из них только одна пара (00 и 10) - несравнимые наборы. Таким образом, для анализа ЛФ на монотонность нужно сделать 5 проверок. Оказывается, среди ЛФ двух аргументов (табл. 4) - 6 монотонных: f0, f1, f3, f5 (наборы 01 и 10 несравнимы), f7, f15.

14 Пять замечательных классов логических функций

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

Теорема 4. В результате операций суперпозиции и подстановки аргументов из монотонных ЛФ получаются также монотонные ЛФ, и только они. Доказательство. А: Суперпозиция. Рассмотрим некоторый набор . Ему соответствует набор . Имеем равенство: . Теперь увеличим набор ky, тогда любой набор не уменьшится. А значит, поскольку все функции Y также монотонные, не уменьшится набор kx. В силу монотонности функции f не уменьшится и ее значение, равное, кстати, значению функции f1. Таким образом, монотонность f1 доказана.

15 Пять замечательных классов логических функций

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

В: Подстановка аргументов. При увеличении набора (х1, х2, ..., хn) набор (х2, х1, ..., хn) также увеличивается, поскольку позиции аргументов при этом никакой роли не играют. Поскольку f - монотонная функция, ее значения не убывают, а значит, не убывают значения f1. Отсюда следует, что f1 - монотонная функция. Для определения самодвойственной ЛФ необходимо ввести понятие противоположных наборов. В паре противоположных наборов значения аргументов взаимно инверсны. Например, наборы (0, 0, 0, 1, 0) и (1, 1, 1, 0, 1) - противоположные, а наборы (0, 0, 0, 1, 0) и (1, 1, 1, 0, 0) - нет.

16 Пять замечательных классов логических функций

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

Самодвойственная логическая функция на противоположных наборах имеет противоположные (взаимноинверсные) значения. Т.е. нулю соответствуют единицы, а единице - нуль. Среди ЛФ 2 аргументов - четыре самодвойственных функции: f3, f5, f10, f12 (табл. 4).

17 Пять замечательных классов логических функций

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

Теорема 5. В результате операций суперпозиции и подстановки аргументов из самодвойственных ЛФ получаются также самодвойственные ЛФ, и только они. Доказательство. A: Суперпозиция. Набору соответствует набор , так, что . Теперь инвертируем набор ky. Поскольку все функции Y самодвойственные, набор kx также инвертируется, т.е. становится противоположным по отношению к себе. Самодвойственность функции f влечет при этом ее инверсию, а значит – инверсию f1. Таким образом, самодвойственность f1 доказана.

18 Пять замечательных классов логических функций

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

В: Подстановка аргументов. Инверсия набора (х1, х2, …, хn) влечет инверсию и набора (х2, х1, ..., хn), поскольку позиции аргументов при этом никакой роли не играют. В силу самодвойственности f ее значение f(х2, ..., хn) инвертируется, а вместе с этим инвертируется и значение f1. Таким образом, f1 - самодвойственная функция.

19 Пять замечательных классов логических функций

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

Техническая задача определения набора логических элементов (ЛЭ), позволяющего построить любую логическую схему, сводится к математической задаче отыскания функционально полной системы логических функции (ФПС ЛФ). Система ЛФ называется функционально полной, если с помощью ЛФ, входящих в эту систему, можно получить любую, сколь угодно сложную ЛФ — с помощью операции суперпозиции и подстановки аргументов. Свойство-требование полноты приводит к аналогии с системой аксиом. Там, кроме этого, рассматриваются еще непротиворечивость и независимость. Последнее свойство в преломлении для ФПС не является необходимым. Как раз некоторая зависимость базовых ЛФ, т.е. входящих в ФПС, может способствовать снижению общих затрат оборудования, т.е. повышению экономичности (п. 6).

20 Пять замечательных классов логических функций

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

Теорема о функциональной полноте системы логических функций. Для функциональной полноты системы ЛФ необходимо и достаточно, чтобы эта система включала хотя бы одну нелинейную ЛФ, хотя бы одну ЛФ, несохраняющую единицу, хотя бы одну немонотонную ЛФ и хотя бы одну несамодвойственную ЛФ. Необходимость следует из теорем 1 ... 5. Действительно, пусть, напротив, ФПС включает только линейные функции. В силу замкнутости класса линейных функций (теорема 1) окажется невозможным получать нелинейные ЛФ (они, конечно, есть), т.е. на самом деле ФПС - вовсе не функционально полная. И т.д. Доказательство достаточности не рассматривается.

21 Пять замечательных классов логических функций

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

Следует отметить, ФПС не обязательно содержит пять ЛФ. Дело в том, что многие ЛФ одновременно являются и нелинейными, и немонотонными, и т.п. Система ЛФ независимая, если ни одна из входящих в нее ЛФ не может быть получена из других с помощью операций суперпозиции и подстановки аргументов. Доказано, что максимальное количество ЛФ независимой ФПС равно 4.

22 ФПС логических функций 2 аргументов могут быть составлены из ЛФ,

ФПС логических функций 2 аргументов могут быть составлены из ЛФ,

совместно перекрывающих пустые клетки в строках 1 … 5 табл. 6. Таблица 6 Логические функции и замечательные классы

Функционально полные системы логических функций

Класс ЛФ

f0

f1

f2

f3

f4

f5

f6

f7

f8

f9

f10

f11

f12

f13

f14

f15

1

Линейные

+

+

+

+

+

+

+

+

2

Сохраняющие 0

+

+

+

+

+

+

+

+

3

Сохраняющие 1

+

+

+

+

+

+

+

+

4

Монотонные

+

+

+

+

+

+

5

Самодвойствен-ные

+

+

+

+

23 Функционально полные системы логических функций

Функционально полные системы логических функций

Анализ табл. 6 позволяет, например, подтвердить функциональную полноту системы Жегалкина (f1, f6, f15), т.е. системы «конъюнкция - сложение по модулю 2 - константа единица». Примеры ФПС, содержащих 2 ЛФ: - f0, f11 (константа нуль и обратная импликация); - f0, f13 (константа нуль и прямая импликация) Наконец, такая ФПС может быть представлена одной (!) функцией: - f8 (функция Вебба, х1 о х2); - f14 (штрих Шеффера, х1 / х2). Важно отметить, ФПС Вебба и Шеффера сохраняют функциональную полноту и при количестве аргументов n > 2.

24 Функции НЕ, И, ИЛИ (например, f12, f1, f7) также образуют ФПС

Функции НЕ, И, ИЛИ (например, f12, f1, f7) также образуют ФПС

Это булева ФПС (Джордж Буль - английский математик XIX в). Она избыточна - можно исключить f1 или f7. Логические функции технически реализуются в логических элементах. Например, инверсию (отрицание) реализует элемент НЕ, инвертор (рис. 2.2а), конъюнкцию - элемент И, элемент совпадения, конъюнктор (рис. 2.2б), дизъюнкцию - элемент ИЛИ, элемент разделения, дизъюнктор (рис. 2.2в). Элементы И, ИЛИ могут иметь любое количество входов (n ? 2).

Функционально полные системы логических функций

25 Функционально полные системы логических функций

Функционально полные системы логических функций

При реализации на реле (рис. 2.2а) инвертору соответствует пара «нормально замкнутых» контактов. Катушка реле не показана. Подача в нее тока (х = 1) приводит к срабатыванию реле, т.е. размыканию контактов ( ). В исходном же состоянии х = 0 и (цепь замкнута; можно вообразить себе еще последовательно включенную лампу и полюса источника питания). Конъюнктор и дизъюнктор представляют оба возможных типа соединений - последовательное и параллельное.

26 Функционально полные системы логических функций

Функционально полные системы логических функций

Требования к набору логических элементов: - функциональная полнота; - простота, экономичность (минимум «деталей»); - унифицированность (минимум различных элементов); - функциональная гибкость (минимум затрат оборудования в реализуемой сложной схеме). Последние два требования противоречивы: узкий (унифицированный) набор может оказаться менее гибким, чем неузкий.

27 Доказано, что только монотонные ЛФ могут быть представлены в форме, не

Доказано, что только монотонные ЛФ могут быть представлены в форме, не

содержащей инверсий. Таким образом, в ФПС обязательно наличие функции, требующей при своей реализации инвертор. Этому условию, в частности, отвечают система Шеффера и система Вебба

Функционально полные системы логических функций

28 В современных ЭВМ в качестве физической величины, соответствующей

В современных ЭВМ в качестве физической величины, соответствующей

логической, используется электрическое напряжение. Например, логическому нулю соответствует нулевой уровень электрического напряжения (0 В), а логической единице - уровень, надежно отличающийся от нулевого (+5В; +3.3В и т.п.). При этом фактически без каких-либо видимых затрат оборудования реализуются четыре тривиальные ЛФ: f0, f15, f3, f5.

Функционально полные системы логических функций

29 Функции f3 и f5 не влияют на полноту системы (табл

Функции f3 и f5 не влияют на полноту системы (табл

6), а f0 и f15 совместно перекрывают 3 замечательных класса ЛФ: - несохраняющие 0 (f15); - несохраняющие 1 (f0); - несамодвойственные (f0 и f15).

Функционально полные системы логических функций

30 Ослабленная теорема о функциональной полноте

Ослабленная теорема о функциональной полноте

Для функциональной полноты системы ЛФ, содержащей константу нуль и константу единица, необходимо и достаточно, чтобы эта система содержала хотя бы одну нелинейную функцию и хотя бы одну немонотонную. Доказательство этой теоремы следует из неослабленной теоремы. Обычно дело обстоит наоборот: сначала доказывают ослабленную теорему, а потом уже на ее основе - теорему неослабленную.

Функционально полные системы логических функций

31 Кроме тривиальных ЛФ (f0, f15, f3 и f5) в ФПС целесообразно включить

Кроме тривиальных ЛФ (f0, f15, f3 и f5) в ФПС целесообразно включить

одну из монотонных нетривиальных и нелинейных функций. Таких оказывается всего две: f1 (конъюнкция) и f7 (дизъюнкция). Они равноценны с точки зрения принадлежности к замечательным классам (табл. 6), им соответствуют почти одинаковые по сложности элементы.

Функционально полные системы логических функций

32 В качестве немонотонной ЛФ, требующей для реализации инвертор, удобно

В качестве немонотонной ЛФ, требующей для реализации инвертор, удобно

включить в систему f12= или f10= . В итоге получаются две такие ФПС: (0, 1, х, & , ) и (0, 1, х, , ). Правда, при этом реализация дизъюнкции в первой системе и конъюнкции - во второй связаны с использованием 4 логических элементов вместо одного

Функционально полные системы логических функций

33 То же наблюдается в системах Вебба, Шеффера (три логических элемента

То же наблюдается в системах Вебба, Шеффера (три логических элемента

против одного): Таким образом, наиболее подходящей оказывается как раз булева ФПС (И, ИЛИ, НЕ). Именно она и реализуется в современном элементном базисе интегральных микросхем (ИМС). Тривиальные функции здесь, конечно, также присутствуют (0, 1, х), хотя в принципе можно обойтись и без них:

Функционально полные системы логических функций

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

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

В общем случае процесс преобразования (упрощения) логического выражения (функции) к трем таким этапам: - табличное представление ЛФ; - запись выражения для ЛФ в канонической форме; - минимизация ЛФ. Требования к канонической форме: - представимость любой ЛФ (универсальность формы); - простота алгоритма представления; - удобство дальнейшего упрощения - минимизации.

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

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

Таблица 7 Канонические формы ЛФ

ДНФ - дизъюнктивная нормальная форма; КНФ - конъюнктивная нормальная форма; СДНФ - совершенная ДНФ; СКНФ - совершенная КНФ; СкДНФ - сокращенная ДНФ; СкКНФ - сокращенная КНФ; ТДНФ - тупиковая ДНФ; ТКНФ - тупиковая КНФ; МДНФ - минимальная ДНФ; МКНФ - минимальная КНФ.

Форма

Форма

Количество

Количество

Д-базис

К-базис

Днф

Кнф

?1

Сднф

Скнф

1

СкДНФ

СкКНФ

1

Тднф

Ткнф

?1

Мднф

Мкнф

?1

36 Дизъюнктивная нормальная форма (ДНФ) - дизъюнкция конъюнктивных термов

Дизъюнктивная нормальная форма (ДНФ) - дизъюнкция конъюнктивных термов

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

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

37 Теорема

Теорема

Любая логическая функция, кроме константы нуль, может быть представлена в СДНФ: k - номер набора, где функция имеет значение 1. Доказательство. Достаточно рассмотреть две группы наборов аргументов. Там, где ЛФ имеет значение 0, получаем дизъюнкцию нулей, поскольку ни одна из конституент единицы на таких наборах не равна 1. И, наоборот, там, где ЛФ имеет значение 1, справа - дизъюнкция нулей и одной единицы. Очевидно, любая ЛФ имеет единственную СДНФ.

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

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

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

Правило получения СДНФ следует из формулы в теореме: надо составить дизъюнкцию всех конституент единицы ЛФ. Формирование конъюнктивного терма, представляющего конституенту единицы, показано ранее (п. 4). Запись выражения логической функции в СДНФ не обязательно начинать с таблицы значений функции. Возможен довольно простой переход к СДНФ от ДНФ. При этом используется операция развертывания (закон исключенного третьего):

39 Отсутствующий в терме аргумент вводится, таким образом, в конъюнкцию и

Отсутствующий в терме аргумент вводится, таким образом, в конъюнкцию и

прямо, и инверсно. Пример.

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

40 В дальнейшем, при минимизации, оценка затрат оборудования на

В дальнейшем, при минимизации, оценка затрат оборудования на

реализацию ЛФ будет производиться по Квайну. Здесь действуют даже две оценки: общее количество букв (Сбкв) и общее количество входов всех логических элементов (Свх), используемых в схеме, реализующей функцию. Операция развертывания, как видно и из примера, приводит к увеличению обоих значений:

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

41 Вторую оценку лучше находить, построив сначала логическую

Вторую оценку лучше находить, построив сначала логическую

(функциональную) схему (рис.). Иногда рассматривают и третью оценку - количество логических элементов (Сэл). В случае f получаем: Сэл ДНФ=3+2+1=6, Сэл СДНФ=3+5+1=9. В конъюнктивном (К-) базисе все аналогично.

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

42 Процесс минимизации ЛФ в дизъюктивном (Д-) базисе можно представить

Процесс минимизации ЛФ в дизъюктивном (Д-) базисе можно представить

как последовательность преобразований

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

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

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

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

44 Если на каком-то наборе ЛФ f1 принимает значение у1, а ЛФ f2 -

Если на каком-то наборе ЛФ f1 принимает значение у1, а ЛФ f2 -

значение у2, то говорят, что на этом наборе f1 своим значением у1 накрывает значение у2 функции f2. Если функция f1 принимает значение 0 на тех же наборах, что и f2, то говорят, что f1 входит в функцию f2, или является импликантой: f1 ? f2. Или Таким образом, f1 имеет неменьшее количество нулей, чем f2. Причем все нули f2 накрыты нулями f1 (табл. 8).

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

45 Таблица 2.8 Импликанта функции f2 Пример

Таблица 2.8 Импликанта функции f2 Пример

Конституента единицы входит в свою функцию. Действительно, конституента единицы функции f равна 1 только при f=1. Термин «импликанта» связан с понятием ЛФ импликация: Действительно, указанная импликация имеет нулевое значение только при f1=1 и f2=0, а этот случай невозможен.

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

f2

f1

0

0

1

X

46 Собственная часть конъюнкции - это ее любая сокращенная часть

Собственная часть конъюнкции - это ее любая сокращенная часть

Элементарная конъюнкция входит в свою собственную часть, например: Входящая в ЛФ элементарная конъюнкция, никакая собственная часть которой в эту ЛФ уже не входит, называется простой импликантой ЛФ. Иначе говоря, простые импликанты - это самые короткие конъюнктивные термы, являющиеся импликантами.

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

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

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

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

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

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

Теперь берется набор, где ЛФ равна 1. Простые импликанты выбираются среди всех элементарных конъюнкций, входящих в ЛФ, в том числе и среди конституент единицы. Если какая-то конституента не является простой импликантой, значит, она заменена своей собственной частью. Но эта собственная часть на наборах, где входящие в нее конституенты единицы равны 1, также равна 1 (х1х3 и х1 х2 х3, например). Таким образом, среди всех простых импликант на каждом наборе, где f=1, найдется обязательно хотя бы одна, равная 1. И, значит, получается единичная дизъюнкция. Очевидно, если набор всех простых импликант содержит только конституенты единицы, СкДНФ совпадает с СДНФ.

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

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

Методы получения СкДНФ базируются на простом множестве операций: - полное склеивание; - неполное склеивание; - обобщенное склеивание; - поглощение. Операция полного склеивания - фактически обратная по отношению к операции развертывания: В общем случае произвольного терма Т склеивание «по х»:

50 Неполное склеивание отличается от полного только тем, что склеиваемые

Неполное склеивание отличается от полного только тем, что склеиваемые

термы временно не удаляются (хотя и не нарушают равенства - в связи с идемпотентностью дизъюнкции). Дело в том, что эти же термы могут быть востребованы для других склеиваний. Общий случай неполного склеивания (по х):

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

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

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

Обобщенное склеивание, в отличие от уже рассмотренных склеиваний, не требует одинаковой длины склеиваемых термов: На первый взгляд, выражение даже усложнилось. Однако это не всегда так. Может быть, новообразование Т1Т2 окажется полезным (это связано с операцией поглощения). Доказательство формулы обобщенного склеивания в случае очевидно ( ). Пусть . Тогда требуется Т1Т2=0. Но, с другой стороны, имеем хТ1=0 и . Это при х=0 означает Т2=0, а при х=1-Т1= 0. Т.е. в любом случае Т1Т2=0.

52 Поглощение:

Поглощение:

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

53 В методе испытания термов (простых импликант) ТДНФ находится по СкДНФ

В методе испытания термов (простых импликант) ТДНФ находится по СкДНФ

Один из термов (по очереди) исключают. Оставшееся выражение дает 0 при f(СкДНФ)=0. Однако при f(СкДНФ)=1 оставшееся выражение может давать 0, т.е. единица в СкДНФ обеспечивалась удаленным термом. Значит, испытываемый терм нелишний, исключать его нельзя. Проверку оставшегося выражения на 1 необходимо произвести, таким образом, на всех наборах аргументов, где испытываемый терм имеет значение 1. Если оставшееся выражение всюду единично, то испытываемый терм лишний.

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

54 Затем то же самое проделывают с оставшимся выражением (проход «в

Затем то же самое проделывают с оставшимся выражением (проход «в

глубину»). При этом уже испытанные и оказавшиеся нелишними термы повторно не исключаются. После нахождения первой ТДНФ все начинается сначала, но испытывается следующий по порядку терм и т.д. Метод испытания термов явно неудобен при большом количестве термов (простых импликант) в СкДНФ.

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

55 Пример 1. Испытание терма (1): терм нелишний

Пример 1. Испытание терма (1): терм нелишний

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

56 Испытание терма х1х3 (2): терм нелишний

Испытание терма х1х3 (2): терм нелишний

Испытание терма (3): терм лишний!

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

57 Таким образом, f(ТДНФ)= «Углубление» далее не производится, поскольку

Таким образом, f(ТДНФ)= «Углубление» далее не производится, поскольку

все термы в оставшемся выражении уже испытаны. Да и, кроме того, удаление любого из двух оставшихся термов не имеет смысла - тождественной единицы после такого удаления не получится.

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

58 Метод минимизирующих карт представляет собой просто более удобную

Метод минимизирующих карт представляет собой просто более удобную

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

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

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

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

Пример. Оставшиеся двухбуквенные термы составляют вторую МДНФ:

Х1

Х2

Х3

Х1х2

Х1х3

Х2х3

Х1х2х3

F(х1, х2, х3)

0

0

0

00

00

00

000

1

0

0

1

00

01

01

001

1

0

1

0

01

00

10

010

0

0

1

1

01

01

11

011

1

1

0

0

10

10

00

100

1

1

0

1

10

11

01

101

0

1

1

0

11

10

10

110

1

1

1

1

11

11

11

111

1

60 Геометрический метод минимизации ЛФ имеет ограниченную применимость:

Геометрический метод минимизации ЛФ имеет ограниченную применимость:

количество аргументов - не более трех. С четырьмя аргументами работать становится неудобно. ЛФ двух аргументов графически (геометрически) представляется на плоскости в виде двоичного квадрата

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

61 Отдельные вершины квадрата соответствуют 2-буквенным термам ( и т.д.),

Отдельные вершины квадрата соответствуют 2-буквенным термам ( и т.д.),

стороны 1-буквенным термам. Таким образом, операция склеивания двухбуквенных термов отображается в двоичном квадрате как объединение вершин, принадлежащих одной и той же стороне. Например, если f(х1, х2) имеет единичное значение на наборах (1, 0) и (1, 1), что отмечено на рис. кружками, то в результате «склеивания» соответствующих вершин находим, очевидно:

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

62 Конечно, есть еще один вариант склеивания вершин - всех четырех, но

Конечно, есть еще один вариант склеивания вершин - всех четырех, но

это уже - константа единица (0-буквенный терм). Для случая 3 аргументов строится двоичный куб (рис. 2.7). Склеивание вершин в двоичном кубе может быть четырех видов: - изолированная вершина (вырожденное склеивание; 3 буквенный терм); - две вершины ребра (2-буквенный терм); - четыре вершины грани (1-буквенный терм); - все восемь вершин куба (константа единица - 0-буквенный терм).

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

63 Кстати, видна прямая связь с методом неопределенных коэффициентов

Кстати, видна прямая связь с методом неопределенных коэффициентов

Там их было (при n = 3) 26 = 6 + 12 + 8. Здесь эти слагаемые означают соответственно: количество граней (6), ребер (12) и вершин (8). Проба на склеивание вершин делается «по максимуму» - сначала в гранях, затем на ребрах и, наконец, остаются изолированные вершины.

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

64 В примере ЛФ из метода неопределенных коэффициентов (рис

В примере ЛФ из метода неопределенных коэффициентов (рис

) результативные грани не получаются, есть только ребра. Их надо выбрать («скомбинировать») оптимальным, те. неизбыточным, способом. Так получаются обе МДНФ. Склеивание отмечено сплошными контурами (МДНФ 1) и двойными линиями (МДНФ 2).

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

65 Лекция окончена

Лекция окончена

Нажмите клавишу <ESC> для выхода

«Элементы компьютерной математики»
http://900igr.net/prezentacija/matematika/elementy-kompjuternoj-matematiki-104248.html
cсылка на страницу

Конкурсы по математике

19 презентаций о конкурсах по математике
Урок

Математика

71 тема
Слайды
900igr.net > Презентации по математике > Конкурсы по математике > Элементы компьютерной математики