Конкурсы по математике
<<  Элементы компьютерной математики Птичий КВН  >>
Лекция №6
Лекция №6		 Функции НЕ, И, ИЛИ (например, f12, f1, f7) также образуют ФПС
Функции НЕ, И, ИЛИ (например, f12, f1, f7) также образуют ФПС		 В современных ЭВМ в качестве физической величины, соответствующей
В современных ЭВМ в качестве физической величины, соответствующей		 Вторую оценку лучше находить, построив сначала логическую
Вторую оценку лучше находить, построив сначала логическую		 Процесс минимизации ЛФ в дизъюктивном (Д-) базисе можно представить
Процесс минимизации ЛФ в дизъюктивном (Д-) базисе можно представить
Геометрический метод минимизации ЛФ имеет ограниченную применимость:
Геометрический метод минимизации ЛФ имеет ограниченную применимость:		 Кстати, видна прямая связь с методом неопределенных коэффициентов
Кстати, видна прямая связь с методом неопределенных коэффициентов
Лекция окончена
Лекция окончена		 Лекция окончена
Лекция окончена
Картинки из презентации «Элементы компьютерной математики» к уроку математики на тему «Конкурсы по математике»

Автор: Lena. Чтобы познакомиться с картинкой полного размера, нажмите на её эскиз. Чтобы можно было использовать все картинки для урока математики, скачайте бесплатно презентацию «Элементы компьютерной математики.ppt» со всеми картинками в zip-архиве размером 1028 КБ.

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

содержание презентации «Элементы компьютерной математики.ppt»
Сл Текст Сл Текст
1Курс: Элементы компьютерной 30уже на ее основе - теорему неослабленную.
математики. Лектор – Склярова Елена Функционально полные системы логических
Александровна. функций.
2Лекция №6. Тема: Элементы компьютерной 31Кроме тривиальных ЛФ (f0, f15, f3 и
математики (ЭКМ). II. Элементы f5) в ФПС целесообразно включить одну из
математической логики Пять замечательных монотонных нетривиальных и нелинейных
классов логических функций Функционально функций. Таких оказывается всего две: f1
полные системы логических функций Формы (конъюнкция) и f7 (дизъюнкция). Они
представления логических функций равноценны с точки зрения принадлежности к
Минимизация логических функций. замечательным классам (табл. 6), им
3Пять замечательных классов логических соответствуют почти одинаковые по
функций. Все пять рассматриваемых ниже сложности элементы. Функционально полные
классов обладают свойством замкнутости: системы логических функций.
любая ЛФ, полученная из ЛФ каждого класса 32В качестве немонотонной ЛФ, требующей
с помощью операций суперпозиции и для реализации инвертор, удобно включить в
подстановки аргументов, принадлежит этому систему f12= или f10= . В итоге получаются
же классу. Функции в этих классах: - две такие ФПС: (0, 1, х, & , ) и (0,
линейные; - сохраняющие нуль; - 1, х, , ). Правда, при этом реализация
сохраняющие единицу; - монотонные; - дизъюнкции в первой системе и конъюнкции -
самодвойственные. во второй связаны с использованием 4
4Пять замечательных классов логических логических элементов вместо одного.
функций. Линейная ЛФ может быть Функционально полные системы логических
представлена многочленом Жегалкина не выше функций.
первой степени: Таким образом, каждой 33То же наблюдается в системах Вебба,
линейной ЛФ можно поставить в соответствие Шеффера (три логических элемента против
(n+1)-разрядное число. Тогда количество одного): Таким образом, наиболее
различных линейных ЛФ n аргументов подходящей оказывается как раз булева ФПС
составит 2n+1. Так, при n = 1 все 21+1 = 4 (И, ИЛИ, НЕ). Именно она и реализуется в
функции линейны: современном элементном базисе интегральных
5Пять замечательных классов логических микросхем (ИМС). Тривиальные функции
функций. Среди ЛФ двух аргументов (табл. здесь, конечно, также присутствуют (0, 1,
4.) линейных – 22+1 = 8. Можно найти х), хотя в принципе можно обойтись и без
многочлены Жегалкина для всех 16 ЛФ двух них: Функционально полные системы
аргументов, а затем выбрать из них логических функций.
линейные. Второй способ - выписать все 34Формы представления логических
возможные линейные многочлены: функций. В общем случае процесс
6Пять замечательных классов логических преобразования (упрощения) логического
функций. Теорема 1. В результате операций выражения (функции) к трем таким этапам: -
суперпозиции и подстановки аргументов из табличное представление ЛФ; - запись
линейных ЛФ получаются также линейные ЛФ, выражения для ЛФ в канонической форме; -
и только они. Иначе говоря, класс линейных минимизация ЛФ. Требования к канонической
функций замкнут. Аналогичные теоремы будут форме: - представимость любой ЛФ
сформулированы и доказаны для остальных (универсальность формы); - простота
четырех замечательных классов. алгоритма представления; - удобство
7Пять замечательных классов логических дальнейшего упрощения - минимизации.
функций. Доказательство. А: Суперпозиция. 35Формы представления логических
После подстановки выражений Y вместо х в функций. Таблица 7 Канонические формы ЛФ.
f, раскрытия скобок и приведения подобных ДНФ - дизъюнктивная нормальная форма; КНФ
получается новая линейная функция Здесь - конъюнктивная нормальная форма; СДНФ -
надо заметить, что все произведения вила совершенная ДНФ; СКНФ - совершенная КНФ;
аibjk тоже имеют значения 0 или 1. СкДНФ - сокращенная ДНФ; СкКНФ -
8Пять замечательных классов логических сокращенная КНФ; ТДНФ - тупиковая ДНФ;
функций. Пример. В: Подстановка ТКНФ - тупиковая КНФ; МДНФ - минимальная
аргументов. Здесь доказательство очевидно: ДНФ; МКНФ - минимальная КНФ. Форма. Форма.
линейность формы Жегалкина не зависит от Количество. Количество. Д-базис. К-базис.
порядка задания аргументов. Пример. Днф. Кнф. ?1. Сднф. Скнф. 1. СкДНФ. СкКНФ.
9Пять замечательных классов логических 1. Тднф. Ткнф. ?1. Мднф. Мкнф. ?1.
функций. Логическая функция, сохраняющая 36Дизъюнктивная нормальная форма (ДНФ) -
нуль, на нулевом наборе имеет значение 0. дизъюнкция конъюнктивных термов.
Очевидно, среди ЛФ n аргументов ровно Конъюнктивный терм - конъюнкция
половина функций, сохраняющих нуль, т.е. аргументов, взятых прямо или инверсно.
Q0=2n-1. Так, для n = 2 (табл. 2.4) Пример. Аналогично с использованием
получаем Q0=24-1=8. Это f0 … f7 (x1, x2). понятия дизъюнктивного терма определяется
10Пять замечательных классов логических конъюнктивная нормальная форма (КНФ).
функций. Теорема 2. В результате операций Например, Формы представления логических
суперпозиции и подстановки аргументов из функций.
ЛФ, сохраняющих нуль, получаются также ЛФ, 37Теорема. Любая логическая функция,
сохраняющие нуль, и только они. кроме константы нуль, может быть
Доказательство. А: Суперпозиция. Тогда f1 представлена в СДНФ: k - номер набора, где
(у1, …, уm)0…0 = 0, поскольку Y1, …, Yn на функция имеет значение 1. Доказательство.
этом же наборе имеют значение 0. Значит, и Достаточно рассмотреть две группы наборов
набор (х1, …, xn) - также нулевой, а здесь аргументов. Там, где ЛФ имеет значение 0,
f (0, …, 0) = 0. получаем дизъюнкцию нулей, поскольку ни
11Пять замечательных классов логических одна из конституент единицы на таких
функций. В: Подстановка аргументов. наборах не равна 1. И, наоборот, там, где
Доказательство очевидно: перестановка ЛФ имеет значение 1, справа - дизъюнкция
аргументов, имеющих одинаковые значения нулей и одной единицы. Очевидно, любая ЛФ
(нуль), никакой роли не играет, нулевой имеет единственную СДНФ. Формы
набор остается нулевым и нулевое значение представления логических функций.
ЛФ сохраняется. Логическая функция, 38Формы представления логических
сохраняющая единицу, на единичном наборе функций. Правило получения СДНФ следует из
имеет значение 1. Далее все аналогично формулы в теореме: надо составить
предшествующему случаю. Так, Q0=2n-1. дизъюнкцию всех конституент единицы ЛФ.
Восемь ЛФ, сохраняющих единицу, при n=2 Формирование конъюнктивного терма,
(табл. 4) – это f1, f3, f5, f7, f9, f11, представляющего конституенту единицы,
f13, f15, т.е. все функции с нечетными показано ранее (п. 4). Запись выражения
номерами. логической функции в СДНФ не обязательно
12Пять замечательных классов логических начинать с таблицы значений функции.
функций. Теорема 3 и ее доказательство Возможен довольно простой переход к СДНФ
вполне аналогичны случаю теоремы 2. от ДНФ. При этом используется операция
Определение монотонной логической функции развертывания (закон исключенного
требует введения еще одного понятия - третьего):
сравнимых и несравнимых наборов 39Отсутствующий в терме аргумент
аргументов. Дело в том, что свойство вводится, таким образом, в конъюнкцию и
монотонности обязательно только для пар прямо, и инверсно. Пример. Формы
сравнимых наборов. Итак, два набора представления логических функций.
аргументов сравнимы, если значению каждого 40В дальнейшем, при минимизации, оценка
аргумента в каком-то из них соответствует затрат оборудования на реализацию ЛФ будет
неменьшее значение того же аргумента в производиться по Квайну. Здесь действуют
другом наборе, т.е. 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) несравнимы, здесь для Формы представления логических функций.
четырех аргументов выполняется условие 41Вторую оценку лучше находить, построив
«меньше - равно» (0 < 1 или 0 = 0), а сначала логическую (функциональную) схему
для одного - «больше» (1 > 0). (рис.). Иногда рассматривают и третью
13Пять замечательных классов логических оценку - количество логических элементов
функций. Монотонная логическая функция при (Сэл). В случае f получаем: Сэл
любом возрастании набора аргументов имеет ДНФ=3+2+1=6, Сэл СДНФ=3+5+1=9. В
неубывающее значение. Несравнимые наборы конъюнктивном (К-) базисе все аналогично.
не рассматриваются. При n = 2 имеем 3 + 2 Формы представления логических функций.
+ 1 = 6 пар наборов. Из них только одна 42Процесс минимизации ЛФ в дизъюктивном
пара (00 и 10) - несравнимые наборы. Таким (Д-) базисе можно представить как
образом, для анализа ЛФ на монотонность последовательность преобразований.
нужно сделать 5 проверок. Оказывается, Минимизация логических функций.
среди ЛФ двух аргументов (табл. 4) - 6 43Минимизация логических функций. При
монотонных: f0, f1, f3, f5 (наборы 01 и 10 этом ДНФ называется минимальной ДНФ
несравнимы), f7, f15. (МДНФ), если она содержит не большее
14Пять замечательных классов логических количество букв, чем любая другая ДНФ этой
функций. Теорема 4. В результате операций же функции. Таким образом, здесь действует
суперпозиции и подстановки аргументов из единственный критерий минимальности –
монотонных ЛФ получаются также монотонные Сбкв. Минимальных ДНФ, как и тупиковых,
ЛФ, и только они. Доказательство. А: может быть несколько. Ясно, что МДНФ
Суперпозиция. Рассмотрим некоторый набор . выбираются из множества ТДНФ. Базовыми
Ему соответствует набор . Имеем равенство: компонентами для ДНФ и КНФ любого вида
. Теперь увеличим набор ky, тогда любой являются соответственно элементарные
набор не уменьшится. А значит, поскольку конъюнкции (конъюнктивные термы) и
все функции Y также монотонные, не элементарные дизъюнкции (дизъюнктивные
уменьшится набор kx. В силу монотонности термы). Например, и.
функции f не уменьшится и ее значение, 44Если на каком-то наборе ЛФ f1
равное, кстати, значению функции f1. Таким принимает значение у1, а ЛФ f2 - значение
образом, монотонность f1 доказана. у2, то говорят, что на этом наборе f1
15Пять замечательных классов логических своим значением у1 накрывает значение у2
функций. В: Подстановка аргументов. При функции f2. Если функция f1 принимает
увеличении набора (х1, х2, ..., хn) набор значение 0 на тех же наборах, что и f2, то
(х2, х1, ..., хn) также увеличивается, говорят, что f1 входит в функцию f2, или
поскольку позиции аргументов при этом является импликантой: f1 ? f2. Или Таким
никакой роли не играют. Поскольку f - образом, f1 имеет неменьшее количество
монотонная функция, ее значения не нулей, чем f2. Причем все нули f2 накрыты
убывают, а значит, не убывают значения f1. нулями f1 (табл. 8). Минимизация
Отсюда следует, что f1 - монотонная логических функций.
функция. Для определения самодвойственной 45Таблица 2.8 Импликанта функции f2
ЛФ необходимо ввести понятие Пример. Конституента единицы входит в свою
противоположных наборов. В паре функцию. Действительно, конституента
противоположных наборов значения единицы функции f равна 1 только при f=1.
аргументов взаимно инверсны. Например, Термин «импликанта» связан с понятием ЛФ
наборы (0, 0, 0, 1, 0) и (1, 1, 1, 0, 1) - импликация: Действительно, указанная
противоположные, а наборы (0, 0, 0, 1, 0) импликация имеет нулевое значение только
и (1, 1, 1, 0, 0) - нет. при f1=1 и f2=0, а этот случай невозможен.
16Пять замечательных классов логических Минимизация логических функций. f2. f1. 0.
функций. Самодвойственная логическая 0. 1. X.
функция на противоположных наборах имеет 46Собственная часть конъюнкции - это ее
противоположные (взаимноинверсные) любая сокращенная часть. Элементарная
значения. Т.е. нулю соответствуют единицы, конъюнкция входит в свою собственную
а единице - нуль. Среди ЛФ 2 аргументов - часть, например: Входящая в ЛФ
четыре самодвойственных функции: f3, f5, элементарная конъюнкция, никакая
f10, f12 (табл. 4). собственная часть которой в эту ЛФ уже не
17Пять замечательных классов логических входит, называется простой импликантой ЛФ.
функций. Теорема 5. В результате операций Иначе говоря, простые импликанты - это
суперпозиции и подстановки аргументов из самые короткие конъюнктивные термы,
самодвойственных ЛФ получаются также являющиеся импликантами. Минимизация
самодвойственные ЛФ, и только они. логических функций.
Доказательство. A: Суперпозиция. Набору 47Минимизация логических функций.
соответствует набор , так, что . Теперь Теорема. Любая ЛФ может быть представлена
инвертируем набор ky. Поскольку все в СкДНФ, т.е. как дизъюнкция всех своих
функции Y самодвойственные, набор kx также простых импликант (здесь имеется в виду и
инвертируется, т.е. становится вырожденный случай константы нуль, когда
противоположным по отношению к себе. дизъюнкция эта - пустая). Доказательство.
Самодвойственность функции f влечет при Рассматриваются две группы наборов
этом ее инверсию, а значит – инверсию f1. аргументов. Там, где ЛФ равна 0, все
Таким образом, самодвойственность f1 простые импликанты как входящие в эту ЛФ
доказана. также равны 0. Получается дизъюнкция
18Пять замечательных классов логических нулей.
функций. В: Подстановка аргументов. 48Минимизация логических функций. Теперь
Инверсия набора (х1, х2, …, хn) влечет берется набор, где ЛФ равна 1. Простые
инверсию и набора (х2, х1, ..., хn), импликанты выбираются среди всех
поскольку позиции аргументов при этом элементарных конъюнкций, входящих в ЛФ, в
никакой роли не играют. В силу том числе и среди конституент единицы.
самодвойственности f ее значение f(х2, Если какая-то конституента не является
..., хn) инвертируется, а вместе с этим простой импликантой, значит, она заменена
инвертируется и значение f1. Таким своей собственной частью. Но эта
образом, f1 - самодвойственная функция. собственная часть на наборах, где входящие
19Пять замечательных классов логических в нее конституенты единицы равны 1, также
функций. Техническая задача определения равна 1 (х1х3 и х1 х2 х3, например). Таким
набора логических элементов (ЛЭ), образом, среди всех простых импликант на
позволяющего построить любую логическую каждом наборе, где f=1, найдется
схему, сводится к математической задаче обязательно хотя бы одна, равная 1. И,
отыскания функционально полной системы значит, получается единичная дизъюнкция.
логических функции (ФПС ЛФ). Система ЛФ Очевидно, если набор всех простых
называется функционально полной, если с импликант содержит только конституенты
помощью ЛФ, входящих в эту систему, можно единицы, СкДНФ совпадает с СДНФ.
получить любую, сколь угодно сложную ЛФ — 49Минимизация логических функций. Методы
с помощью операции суперпозиции и получения СкДНФ базируются на простом
подстановки аргументов. множестве операций: - полное склеивание; -
Свойство-требование полноты приводит к неполное склеивание; - обобщенное
аналогии с системой аксиом. Там, кроме склеивание; - поглощение. Операция полного
этого, рассматриваются еще склеивания - фактически обратная по
непротиворечивость и независимость. отношению к операции развертывания: В
Последнее свойство в преломлении для ФПС общем случае произвольного терма Т
не является необходимым. Как раз некоторая склеивание «по х»:
зависимость базовых ЛФ, т.е. входящих в 50Неполное склеивание отличается от
ФПС, может способствовать снижению общих полного только тем, что склеиваемые термы
затрат оборудования, т.е. повышению временно не удаляются (хотя и не нарушают
экономичности (п. 6). равенства - в связи с идемпотентностью
20Пять замечательных классов логических дизъюнкции). Дело в том, что эти же термы
функций. Теорема о функциональной полноте могут быть востребованы для других
системы логических функций. Для склеиваний. Общий случай неполного
функциональной полноты системы ЛФ склеивания (по х): Минимизация логических
необходимо и достаточно, чтобы эта система функций.
включала хотя бы одну нелинейную ЛФ, хотя 51Минимизация логических функций.
бы одну ЛФ, несохраняющую единицу, хотя бы Обобщенное склеивание, в отличие от уже
одну немонотонную ЛФ и хотя бы одну рассмотренных склеиваний, не требует
несамодвойственную ЛФ. Необходимость одинаковой длины склеиваемых термов: На
следует из теорем 1 ... 5. Действительно, первый взгляд, выражение даже усложнилось.
пусть, напротив, ФПС включает только Однако это не всегда так. Может быть,
линейные функции. В силу замкнутости новообразование Т1Т2 окажется полезным
класса линейных функций (теорема 1) (это связано с операцией поглощения).
окажется невозможным получать нелинейные Доказательство формулы обобщенного
ЛФ (они, конечно, есть), т.е. на самом склеивания в случае очевидно ( ). Пусть .
деле ФПС - вовсе не функционально полная. Тогда требуется Т1Т2=0. Но, с другой
И т.д. Доказательство достаточности не стороны, имеем хТ1=0 и . Это при х=0
рассматривается. означает Т2=0, а при х=1-Т1= 0. Т.е. в
21Пять замечательных классов логических любом случае Т1Т2=0.
функций. Следует отметить, ФПС не 52Поглощение: Минимизация логических
обязательно содержит пять ЛФ. Дело в том, функций.
что многие ЛФ одновременно являются и 53В методе испытания термов (простых
нелинейными, и немонотонными, и т.п. импликант) ТДНФ находится по СкДНФ. Один
Система ЛФ независимая, если ни одна из из термов (по очереди) исключают.
входящих в нее ЛФ не может быть получена Оставшееся выражение дает 0 при
из других с помощью операций суперпозиции f(СкДНФ)=0. Однако при f(СкДНФ)=1
и подстановки аргументов. Доказано, что оставшееся выражение может давать 0, т.е.
максимальное количество ЛФ независимой ФПС единица в СкДНФ обеспечивалась удаленным
равно 4. термом. Значит, испытываемый терм
22ФПС логических функций 2 аргументов нелишний, исключать его нельзя. Проверку
могут быть составлены из ЛФ, совместно оставшегося выражения на 1 необходимо
перекрывающих пустые клетки в строках 1 … произвести, таким образом, на всех наборах
5 табл. 6. Таблица 6 Логические функции и аргументов, где испытываемый терм имеет
замечательные классы. Функционально полные значение 1. Если оставшееся выражение
системы логических функций. №. Класс ЛФ. всюду единично, то испытываемый терм
f0. f1. f2. f3. f4. f5. f6. f7. f8. f9. лишний. Минимизация логических функций.
f10. f11. f12. f13. f14. f15. 1. Линейные. 54Затем то же самое проделывают с
+. +. +. +. +. +. +. +. 2. Сохраняющие 0. оставшимся выражением (проход «в
+. +. +. +. +. +. +. +. 3. Сохраняющие 1. глубину»). При этом уже испытанные и
+. +. +. +. +. +. +. +. 4. Монотонные. +. оказавшиеся нелишними термы повторно не
+. +. +. +. +. 5. Самодвойствен-ные. +. +. исключаются. После нахождения первой ТДНФ
+. +. все начинается сначала, но испытывается
23Функционально полные системы следующий по порядку терм и т.д. Метод
логических функций. Анализ табл. 6 испытания термов явно неудобен при большом
позволяет, например, подтвердить количестве термов (простых импликант) в
функциональную полноту системы Жегалкина СкДНФ. Минимизация логических функций.
(f1, f6, f15), т.е. системы «конъюнкция - 55Пример 1. Испытание терма (1): терм
сложение по модулю 2 - константа единица». нелишний. Минимизация логических функций.
Примеры ФПС, содержащих 2 ЛФ: - f0, f11 56Испытание терма х1х3 (2): терм
(константа нуль и обратная импликация); - нелишний. Испытание терма (3): терм
f0, f13 (константа нуль и прямая лишний! Минимизация логических функций.
импликация) Наконец, такая ФПС может быть 57Таким образом, f(ТДНФ)= «Углубление»
представлена одной (!) функцией: - f8 далее не производится, поскольку все термы
(функция Вебба, х1 о х2); - f14 (штрих в оставшемся выражении уже испытаны. Да и,
Шеффера, х1 / х2). Важно отметить, ФПС кроме того, удаление любого из двух
Вебба и Шеффера сохраняют функциональную оставшихся термов не имеет смысла -
полноту и при количестве аргументов n > тождественной единицы после такого
2. удаления не получится. Минимизация
24Функции НЕ, И, ИЛИ (например, f12, f1, логических функций.
f7) также образуют ФПС. Это булева ФПС 58Метод минимизирующих карт представляет
(Джордж Буль - английский математик XIX собой просто более удобную модификацию
в). Она избыточна - можно исключить f1 или метода неопределенных коэффициентов. Здесь
f7. Логические функции технически используется табличная форма задания
реализуются в логических элементах. уравнений. Причем указываются не
Например, инверсию (отрицание) реализует коэффициенты, а сами термы, им
элемент НЕ, инвертор (рис. 2.2а), соответствующие (возможно, в условном
конъюнкцию - элемент И, элемент виде). Вычеркивание нулевых термов и
совпадения, конъюнктор (рис. 2.2б), дальнейший перебор вариантов - вполне
дизъюнкцию - элемент ИЛИ, элемент аналогичны соответствующим действиям в
разделения, дизъюнктор (рис. 2.2в). предыдущем методе. Минимизация логических
Элементы И, ИЛИ могут иметь любое функций.
количество входов (n ? 2). Функционально 59Минимизация логических функций.
полные системы логических функций. Пример. Оставшиеся двухбуквенные термы
25Функционально полные системы составляют вторую МДНФ: Х1. Х2. Х3. Х1х2.
логических функций. При реализации на реле Х1х3. Х2х3. Х1х2х3. F(х1, х2, х3). 0. 0.
(рис. 2.2а) инвертору соответствует пара 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.
1) приводит к срабатыванию реле, т.е. 10. 00. 100. 1. 1. 0. 1. 10. 11. 01. 101.
размыканию контактов ( ). В исходном же 0. 1. 1. 0. 11. 10. 10. 110. 1. 1. 1. 1.
состоянии х = 0 и (цепь замкнута; можно 11. 11. 11. 111. 1.
вообразить себе еще последовательно 60Геометрический метод минимизации ЛФ
включенную лампу и полюса источника имеет ограниченную применимость:
питания). Конъюнктор и дизъюнктор количество аргументов - не более трех. С
представляют оба возможных типа соединений четырьмя аргументами работать становится
- последовательное и параллельное. неудобно. ЛФ двух аргументов графически
26Функционально полные системы (геометрически) представляется на
логических функций. Требования к набору плоскости в виде двоичного квадрата.
логических элементов: - функциональная Минимизация логических функций.
полнота; - простота, экономичность 61Отдельные вершины квадрата
(минимум «деталей»); - унифицированность соответствуют 2-буквенным термам ( и
(минимум различных элементов); - т.д.), стороны 1-буквенным термам. Таким
функциональная гибкость (минимум затрат образом, операция склеивания двухбуквенных
оборудования в реализуемой сложной схеме). термов отображается в двоичном квадрате
Последние два требования противоречивы: как объединение вершин, принадлежащих
узкий (унифицированный) набор может одной и той же стороне. Например, если
оказаться менее гибким, чем неузкий. f(х1, х2) имеет единичное значение на
27Доказано, что только монотонные ЛФ наборах (1, 0) и (1, 1), что отмечено на
могут быть представлены в форме, не рис. кружками, то в результате
содержащей инверсий. Таким образом, в ФПС «склеивания» соответствующих вершин
обязательно наличие функции, требующей при находим, очевидно: Минимизация логических
своей реализации инвертор. Этому условию, функций.
в частности, отвечают система Шеффера и 62Конечно, есть еще один вариант
система Вебба. Функционально полные склеивания вершин - всех четырех, но это
системы логических функций. уже - константа единица (0-буквенный
28В современных ЭВМ в качестве терм). Для случая 3 аргументов строится
физической величины, соответствующей двоичный куб (рис. 2.7). Склеивание вершин
логической, используется электрическое в двоичном кубе может быть четырех видов:
напряжение. Например, логическому нулю - изолированная вершина (вырожденное
соответствует нулевой уровень склеивание; 3 буквенный терм); - две
электрического напряжения (0 В), а вершины ребра (2-буквенный терм); - четыре
логической единице - уровень, надежно вершины грани (1-буквенный терм); - все
отличающийся от нулевого (+5В; +3.3В и восемь вершин куба (константа единица -
т.п.). При этом фактически без каких-либо 0-буквенный терм). Минимизация логических
видимых затрат оборудования реализуются функций.
четыре тривиальные ЛФ: f0, f15, f3, f5. 63Кстати, видна прямая связь с методом
Функционально полные системы логических неопределенных коэффициентов. Там их было
функций. (при n = 3) 26 = 6 + 12 + 8. Здесь эти
29Функции f3 и f5 не влияют на полноту слагаемые означают соответственно:
системы (табл. 6), а f0 и f15 совместно количество граней (6), ребер (12) и вершин
перекрывают 3 замечательных класса ЛФ: - (8). Проба на склеивание вершин делается
несохраняющие 0 (f15); - несохраняющие 1 «по максимуму» - сначала в гранях, затем
(f0); - несамодвойственные (f0 и f15). на ребрах и, наконец, остаются
Функционально полные системы логических изолированные вершины. Минимизация
функций. логических функций.
30Ослабленная теорема о функциональной 64В примере ЛФ из метода неопределенных
полноте. Для функциональной полноты коэффициентов (рис.) результативные грани
системы ЛФ, содержащей константу нуль и не получаются, есть только ребра. Их надо
константу единица, необходимо и выбрать («скомбинировать») оптимальным,
достаточно, чтобы эта система содержала те. неизбыточным, способом. Так получаются
хотя бы одну нелинейную функцию и хотя бы обе МДНФ. Склеивание отмечено сплошными
одну немонотонную. Доказательство этой контурами (МДНФ 1) и двойными линиями
теоремы следует из неослабленной теоремы. (МДНФ 2). Минимизация логических функций.
Обычно дело обстоит наоборот: сначала 65Лекция окончена. Нажмите клавишу
доказывают ослабленную теорему, а потом <ESC> для выхода.
Элементы компьютерной математики.ppt
http://900igr.net/kartinka/matematika/elementy-kompjuternoj-matematiki-104248.html
cсылка на страницу

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

другие презентации на тему «Элементы компьютерной математики»

«Периодическая система химических элементов» - 9-8 верных ответов – «5» баллов. А. 17 Б. 35 В. 35,5 Г. 52 6. Сколько электронов вращается вокруг ядра в атоме фтора? 15-16 баллов – «5» -зеленый вагончик. Станция узнавай-ка «Расскажи мне обо мне». 12-14 балла – «4» -желтый вагончик. Вокруг тебя творится мир живой. Итоги путешествия: Проверь себя: Характеристика химических элементов по плану:

«Размещение элементов» - Для числа выборов двух элементов из n данных: Сочетание. Для любых натуральных чисел n и k где n>k,справедливы равенства: Размещение и сочитание. Размещение. Формулы: В комбинаторике сочетанием из n по k называется набор k элементов, выбранных из данных n элементов. Комбинаторика.

«ЕГЭ по математике» - Подготовка к ЕГЭ по математике в 2010 году. Задания открытого банка заданий по математике, часть В. ЕГЭ 2010. Тематические тесты. Самое полное издание типовых вариантов реальных заданий ЕГЭ: 2010. Математика. Типовые тестовые задания. Подготовка к ЕГЭ-2010. ЕГЭ-2009. Репетитор. Универсальные материалы для подготовки учащихся.

«Названия химических элементов» - P. Об авторе. Определенный вид атомов называют химическим элементом. Дорогие ребята! О. Cu. Заполните пустые клетки русскими названиями следующих химических элементов: Ag, Br, Fe, H, I, O, Sn. Успехов в изучении химии! То в покое пребывали: Алюминий, натрий, калий, Фтор, бериллий, водород... Элементарный – начальный, относящийся к основам чего-нибудь (из толкового словаря С.И.Ожегова).

«Решение задач по математике» - Подбирается литература. Подготовка учащихся к участию в олимпиадах, соревнованиях и конкурсах по математике. «Горизонты науки и образования». Дальнейшие действия. Конкурсные работы. Определяются: цели и задачи исследования. Решение нестандартных задач. Постоянное совершенствование собственных умений в сфере современных информационных технологий.

«Химические элементы в клетке» - Строение молекулы воды. Все биоэлементы делятся на макроэлементы, микроэлементы и ультрамикроэлементы. Макроэлементы 99% всей массы клетки O, C, H, N, S, P, K, Mg, Na, Ca, Fe, Cl. Каков характер ковалентной связи между атомом кислорода и атомами водорода? Микроэлементы ионы тяжелых металлов, входящих в состав ферментов, гормонов 0,0001% Cu, Zn, I, F.

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

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

Математика

71 тема

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

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