.
Замечание: Если
, то .
Разделы презентаций
- Разное
- Английский язык
- Астрономия
- Алгебра
- Биология
- География
- Геометрия
- Детские презентации
- Информатика
- История
- Литература
- Математика
- Медицина
- Менеджмент
- Музыка
- МХК
- Немецкий язык
- ОБЖ
- Обществознание
- Окружающий мир
- Педагогика
- Русский язык
- Технология
- Физика
- Философия
- Химия
- Шаблоны, картинки для презентаций
- Экология
- Экономика
- Юриспруденция
Дискретная математика
Содержание
- 1. Дискретная математика
- 2. ДНФ и импликантыФункция f имплицирует функцию g,
- 3. Импликант Если f имплицирует g, и f
- 4. Если функция
- 5. Пусть
- 6. ПримерПусть
- 7. Утверждение 1Представление функции в виде ДНФ соответствует представлению
- 8. ПримерПусть функция представлена своей ДНФ.
- 9. Утверждение 2Любая конъюнкция ДНФ функции является импликантом данной функции.
- 10. Утверждение 3Если конъюнкция ДНФ функции не является простым
- 11. ОпределениеДНФ, состоящая только из простых импликантов, называется
- 12. ПримерПусть функция представлена своей ДНФ.Тогда ее единичное множество имеет вид:
- 13. ПримерОчевидно, что
- 14. ПримерПроверим, будет ли простым импликант
- 15. Примерто есть по-прежнему является
- 16. Скачать презентанцию
ДНФ и импликантыФункция f имплицирует функцию g, если .Замечание: Если ,
Слайды и текст этой презентации
Слайд 3Импликант
Если f имплицирует g, и f представлена единственной элементарной
конъюнкцией, то f называется импликантом g.
Если из импликанта нельзя удалить
ни одной переменной, то оно называется простым импликантом.
Слайд 4 Если функция
представима единственной элементарной конъюнкцией
– всех n переменных, то
;– m < n переменных, то
.
Теорема
Слайд 5Пусть
.
Она принимает значение
1 тогда и только тогда, когда x = 1, y = 1, z = 1. Значит .Пример
Слайд 6Пример
Пусть
.
Она принимает значение 1 тогда и только тогда, когда y = 0, z = 1. Значит, чему равняется переменная х – неважно, и она может принимать любые значения. Поэтому
.
Слайд 7Утверждение 1
Представление функции в виде ДНФ соответствует представлению ее единичного множества
в виде объединения единичных множеств входящих в эту ДНФ элементарных
конъюнкций.
Слайд 8Пример
Пусть функция представлена своей ДНФ.
.
Тогда ее единичное множество может быть представлено в виде:
Получилось, что
Слайд 10Утверждение 3
Если конъюнкция ДНФ функции не является простым импликантом, то можно
найти соответствующий ей простой импликант (или импликанты) и заменить им
(или их дизъюнкцией) непростой импликант.
Слайд 13Пример
Очевидно, что – это простой
импликант. Он состоит из одной буквы, и если ее вычеркнуть,
получится вырожденная конъюнкция (конъюнкция не имеющая переменных), что возможно только в случае, если .
Слайд 15Пример
то есть по-прежнему является импликантом f.
Получим
конъюнкцию
Ее единичное множество содержит 2 набора:
Значит – не простой импликант.
