Презентация Функционально замкнутые классы. Специальные классы булевых функций онлайн
На нашем сайте вы можете скачать и просмотреть онлайн доклад-презентацию на тему Функционально замкнутые классы. Специальные классы булевых функций абсолютно бесплатно. Урок-презентация на эту тему содержит всего 28 слайдов. Все материалы созданы в программе PowerPoint и имеют формат ppt или же pptx. Материалы и темы для презентаций взяты из открытых источников и загружены их авторами, за качество и достоверность информации в них администрация сайта не отвечает, все права принадлежат их создателям. Если вы нашли то, что искали, отблагодарите авторов - поделитесь ссылкой в социальных сетях, а наш сайт добавьте в закладки.
Оцените презентацию от 1 до 5 баллов!
- Тип файла:ppt / pptx (powerpoint)
- Всего слайдов:28 слайдов
- Для класса:1,2,3,4,5,6,7,8,9,10,11
- Размер файла:146.77 kB
- Просмотров:88
- Скачиваний:0
- Автор:неизвестен
Слайды и текст к этой презентации:
№1 слайд
Содержание слайда: Функционально замкнутые классы
№2 слайд
Содержание слайда: Специальные классы булевых функций
Американский математик Эмиль Пост ввел в рассмотрение следующие замкнутые классы булевых функций:
Функции, сохраняющие константу ноль T0 ;
Функции, сохраняющие константу один T1;
Самодвойственные функции S ;
Монотонные функции M ;
Линейные функции L .
№3 слайд
Содержание слайда: Класс функций, сохраняющих константу 0
Определение. Говорят, что функция сохраняет константу 0, если f(0,0,…,0)=0
Примеры:
f(x,y)=x⊕y
f(x,y)=x·y
№4 слайд
Содержание слайда: Класс функций, сохраняющих константу 1
Определение. Говорят, что функция сохраняет константу 1, если f(1,1,…,1)=1
Примеры:
f(x,y)=x~y
f(x,y)=x·y
№5 слайд
Содержание слайда: Двойственность
Пусть f(x1, x2, …, xn ) – булева функция. Двойственной к ней называется функция f*, которая на противоположных наборах имеет значения, противоположные значениям функции f.
№6 слайд
Содержание слайда: Класс самодвойственных булевых функций
Определение. Булева функция f(x1,…,xn) самодвойственна
(принадлежит классу S), если она равна двойственной себе, то есть f(x1, …, xn) = f*(x1, …, xn)
Пример: f(x,y,z)=xy+yz+xz
№7 слайд
Содержание слайда: Пример самодвойственной функции
f(x,y,z)=xy+yz+xz
№8 слайд
Содержание слайда: Алгоритм распознавания самодвойственной функции, заданной таблицей истинности
для проверки самодвойственности булевой функции можно не получать двойственную ей функцию в явном виде, а лишь сравнивать значения исходной функции на противоположных наборах.
Функция самодвойственна, если и только если на противоположных наборах принимает противоположые значения.
№9 слайд
Содержание слайда:
№10 слайд
Содержание слайда: Сравнимые наборы
Два набора и называются сравнимыми ( ), если
№11 слайд
Содержание слайда: Класс монотонных функций
Определение. Булева функция f(x1, …, xn) называется монотонной (принадлежит классу M), если для любой пары наборов α и β таких, что α β, выполняется условие монотонности: f(α)≤ f(β)
№12 слайд
Содержание слайда:
№13 слайд
Содержание слайда: Класс линейных функций
Определение. Булева функция называется линейной (принадлежит классу L), если ее полином Жегалкина линеен.
№14 слайд
Содержание слайда:
№15 слайд
Содержание слайда: Функциональная полнота системы булевых функций
№16 слайд
Содержание слайда: Определение ФПС
Определение. Множество функций N называется функционально полной системой (ФПС), если любая булева функция представима суперпозицией функций из N
№17 слайд
Содержание слайда: Примеры ФПС
Пример 1. Множество N1={&,+,–} является функционально полной системой, так как любую булеву функцию, кроме константы 0, можно представить совершенной ДНФ, то есть суперпозицией функций из N1 а константу 0 – формулой xx .
Пример 2. Множество N2={&,,1} является ФПС, так как любую булеву функцию можно представить полиномом Жегалкина, то есть суперпозицией функций из N2, а константу 0 – формулой 11
№18 слайд
Содержание слайда: Теорема о двух функционально полных системах
Теорема. Если даны два множества N1 и N2 булевых функций и известно, что N1 – функционально полная система, а каждая функция из N1 представима суперпозицией функций из N2, то N2тоже является функционально полной системой.
№19 слайд
Содержание слайда: Пример. N1={&,+,–}, N2={&, –}.
Как показано ранее, N1 – ФПС. Конъюнкция и инверсия содержатся в N2, а дизъюнкция представима суперпозицией функций из N2:
x+y = x+y = x·y , значит, N2 – ФПС.
№20 слайд
Содержание слайда: Задание: Докажите, что система функций {, v} является полной.
Задание: Докажите, что система функций {, v} является полной.
№21 слайд
Содержание слайда: Существует функционально полная система, состоящая из одной булевой функции.
Существует функционально полная система, состоящая из одной булевой функции.
№22 слайд
Содержание слайда: Доказательство
x1 | x2 = x1 v x2 или x1 | x2 = x1 & x2
Тогда x1 = x1 & x1 = x1 | x1
x1 + x2 = x1 + x2 = x1&x2 = x1 | x2 = (x1 | x1) | (x2 | x2)
x1 & x2 = x1 & x2 = x1 | x2 = (x1 | x2) | (x1 | x2)
№23 слайд
Содержание слайда: Стрелка Пирса (ИЛИ-НЕ) – x1 ↓ x2
№24 слайд
Содержание слайда: Теорема Поста
Теорема (о полноте). Для того, чтобы система булевых функций Д была полной, необходимо и достаточно, чтобы она целиком не содержалась ни в одном из пяти замкнутых классов T0, T1, S, M, L.
№25 слайд
Содержание слайда: Таблицы Поста
В тех задачах, где требуется выяснить, является ли данная система {f1 f2, …, fn} булевых функций полной, будем составлять таблицы, которые называются таблицами Поста. Данные таблицы имеют следующий вид.
№26 слайд
Содержание слайда: Пример. Выяснить, являются ли следующие системы булевых функций полными. Являются ли следующие системы булевых функций базисами.
Пример. Выяснить, являются ли следующие системы булевых функций полными. Являются ли следующие системы булевых функций базисами.
№27 слайд
Содержание слайда:
№28 слайд
Содержание слайда: Базис
Определение. Полная система функций называется базисом пространства булевых функций, если любое собственное подмножество данной системы функций уже не является полным.
Другими словами, базис – это минимальная (но не по количеству, а в смысле отношения включения) полная система булевых функций.
Теорема. Всякий базис пространства булевых функций содержит не более четырёх функций.
Скачать все slide презентации Функционально замкнутые классы. Специальные классы булевых функций одним архивом:
