🗊Презентация Функционально замкнутые классы. Специальные классы булевых функций

Категория: Математика
Нажмите для полного просмотра!
Функционально замкнутые классы. Специальные классы булевых функций, слайд №1Функционально замкнутые классы. Специальные классы булевых функций, слайд №2Функционально замкнутые классы. Специальные классы булевых функций, слайд №3Функционально замкнутые классы. Специальные классы булевых функций, слайд №4Функционально замкнутые классы. Специальные классы булевых функций, слайд №5Функционально замкнутые классы. Специальные классы булевых функций, слайд №6Функционально замкнутые классы. Специальные классы булевых функций, слайд №7Функционально замкнутые классы. Специальные классы булевых функций, слайд №8Функционально замкнутые классы. Специальные классы булевых функций, слайд №9Функционально замкнутые классы. Специальные классы булевых функций, слайд №10Функционально замкнутые классы. Специальные классы булевых функций, слайд №11Функционально замкнутые классы. Специальные классы булевых функций, слайд №12Функционально замкнутые классы. Специальные классы булевых функций, слайд №13Функционально замкнутые классы. Специальные классы булевых функций, слайд №14Функционально замкнутые классы. Специальные классы булевых функций, слайд №15Функционально замкнутые классы. Специальные классы булевых функций, слайд №16Функционально замкнутые классы. Специальные классы булевых функций, слайд №17Функционально замкнутые классы. Специальные классы булевых функций, слайд №18Функционально замкнутые классы. Специальные классы булевых функций, слайд №19Функционально замкнутые классы. Специальные классы булевых функций, слайд №20Функционально замкнутые классы. Специальные классы булевых функций, слайд №21Функционально замкнутые классы. Специальные классы булевых функций, слайд №22Функционально замкнутые классы. Специальные классы булевых функций, слайд №23Функционально замкнутые классы. Специальные классы булевых функций, слайд №24Функционально замкнутые классы. Специальные классы булевых функций, слайд №25Функционально замкнутые классы. Специальные классы булевых функций, слайд №26Функционально замкнутые классы. Специальные классы булевых функций, слайд №27Функционально замкнутые классы. Специальные классы булевых функций, слайд №28
Скачать

Содержание ▲

Вы можете ознакомиться и скачать презентацию на тему Функционально замкнутые классы. Специальные классы булевых функций. Доклад-сообщение содержит 28 слайдов. Презентации для любого класса можно скачать бесплатно. Если материал и наш сайт презентаций Mypresentation Вам понравились – поделитесь им с друзьями с помощью социальных кнопок и добавьте в закладки в своем браузере.

Слайды и текст этой презентации

Слайд 1


Функционально замкнутые классы
Описание слайда:
Функционально замкнутые классы

Слайд 2


Специальные классы булевых функций Американский математик Эмиль Пост ввел в рассмотрение следующие замкнутые классы булевых функций: Функции, сохраняющие константу ноль T0 ; Функции, сохраняющие константу один T1; Самодвойственные функции S ; Монотонные функции  M ; Линейные функции  L .
Описание слайда:
Специальные классы булевых функций Американский математик Эмиль Пост ввел в рассмотрение следующие замкнутые классы булевых функций: Функции, сохраняющие константу ноль T0 ; Функции, сохраняющие константу один T1; Самодвойственные функции S ; Монотонные функции  M ; Линейные функции  L .

Слайд 3


Класс функций, сохраняющих константу 0 Определение. Говорят, что функция сохраняет константу 0, если f(0,0,…,0)=0 Примеры: f(x,y)=x⊕y f(x,y)=x·y
Описание слайда:
Класс функций, сохраняющих константу 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
Описание слайда:
Класс функций, сохраняющих константу 1 Определение. Говорят, что функция сохраняет константу 1, если f(1,1,…,1)=1 Примеры: f(x,y)=x~y f(x,y)=x·y

Слайд 5


Двойственность Пусть f(x1, x2, …, xn ) – булева функция. Двойственной к ней называется функция  f*, которая на противоположных наборах имеет значения, противоположные значениям функции f.
Описание слайда:
Двойственность Пусть f(x1, x2, …, xn ) – булева функция. Двойственной к ней называется функция  f*, которая на противоположных наборах имеет значения, противоположные значениям функции f.

Слайд 6


Класс самодвойственных булевых функций Определение. Булева функция f(x1,…,xn)  самодвойственна   (принадлежит классу S), если она равна двойственной себе, то есть f(x1, …, xn) = f*(x1, …, xn) Пример: f(x,y,z)=xy+yz+xz
Описание слайда:
Класс самодвойственных булевых функций Определение. Булева функция 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
Описание слайда:
Пример самодвойственной функции f(x,y,z)=xy+yz+xz

Слайд 8


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

Слайд 9


Функционально замкнутые классы. Специальные классы булевых функций, слайд №9
Описание слайда:

Слайд 10


Сравнимые наборы Два набора и называются сравнимыми ( ), если
Описание слайда:
Сравнимые наборы Два набора и называются сравнимыми ( ), если

Слайд 11


Класс монотонных функций Определение. Булева функция f(x1, …, xn) называется монотонной (принадлежит классу M), если для любой пары наборов α и β таких, что α β, выполняется условие монотонности: f(α)≤ f(β)
Описание слайда:
Класс монотонных функций Определение. Булева функция f(x1, …, xn) называется монотонной (принадлежит классу M), если для любой пары наборов α и β таких, что α β, выполняется условие монотонности: f(α)≤ f(β)

Слайд 12


Функционально замкнутые классы. Специальные классы булевых функций, слайд №12
Описание слайда:

Слайд 13


Класс линейных функций Определение. Булева функция называется линейной (принадлежит классу L), если ее полином Жегалкина линеен.
Описание слайда:
Класс линейных функций Определение. Булева функция называется линейной (принадлежит классу L), если ее полином Жегалкина линеен.

Слайд 14


Функционально замкнутые классы. Специальные классы булевых функций, слайд №14
Описание слайда:

Слайд 15


Функциональная полнота системы булевых функций
Описание слайда:
Функциональная полнота системы булевых функций

Слайд 16


Определение ФПС Определение. Множество функций N называется функционально полной системой (ФПС), если любая булева функция представима суперпозицией функций из N
Описание слайда:
Определение ФПС Определение. Множество функций N называется функционально полной системой (ФПС), если любая булева функция представима суперпозицией функций из N

Слайд 17


Примеры ФПС Пример 1. Множество N1={&,+,–} является функционально полной системой, так как любую булеву функцию, кроме константы 0, можно представить совершенной ДНФ, то есть суперпозицией функций из N1 а константу 0 – формулой xx . Пример 2. Множество N2={&,,1} является ФПС, так как любую булеву функцию можно представить полиномом Жегалкина, то есть суперпозицией функций из N2, а константу 0 – формулой 11
Описание слайда:
Примеры ФПС Пример 1. Множество N1={&,+,–} является функционально полной системой, так как любую булеву функцию, кроме константы 0, можно представить совершенной ДНФ, то есть суперпозицией функций из N1 а константу 0 – формулой xx . Пример 2. Множество N2={&,,1} является ФПС, так как любую булеву функцию можно представить полиномом Жегалкина, то есть суперпозицией функций из N2, а константу 0 – формулой 11

Слайд 18


Теорема о двух функционально полных системах Теорема. Если даны два множества N1 и N2 булевых функций и известно, что N1 – функционально полная система, а каждая функция из N1 представима суперпозицией функций из N2, то N2тоже является функционально полной системой.
Описание слайда:
Теорема о двух функционально полных системах Теорема. Если даны два множества N1 и N2 булевых функций и известно, что N1 – функционально полная система, а каждая функция из N1 представима суперпозицией функций из N2, то N2тоже является функционально полной системой.

Слайд 19


Пример. N1={&,+,–}, N2={&, –}. Как показано ранее, N1 – ФПС. Конъюнкция и инверсия содержатся в N2, а дизъюнкция представима суперпозицией функций из N2: x+y = x+y = x·y , значит, N2 – ФПС.
Описание слайда:
Пример. N1={&,+,–}, N2={&, –}. Как показано ранее, N1 – ФПС. Конъюнкция и инверсия содержатся в N2, а дизъюнкция представима суперпозицией функций из N2: x+y = x+y = x·y , значит, N2 – ФПС.

Слайд 20


Задание: Докажите, что система функций {, v} является полной. Задание: Докажите, что система функций {, v} является полной.
Описание слайда:
Задание: Докажите, что система функций {, 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)
Описание слайда:
Доказательство 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
Описание слайда:
Стрелка Пирса (ИЛИ-НЕ) – x1 ↓ x2

Слайд 24


Теорема Поста Теорема (о полноте). Для того, чтобы система булевых функций Д была полной, необходимо и достаточно, чтобы она целиком не содержалась ни в одном из пяти замкнутых классов T0, T1, S, M, L.
Описание слайда:
Теорема Поста Теорема (о полноте). Для того, чтобы система булевых функций Д была полной, необходимо и достаточно, чтобы она целиком не содержалась ни в одном из пяти замкнутых классов T0, T1, S, M, L.

Слайд 25


Таблицы Поста В тех задачах, где требуется выяснить, является ли данная система {f1 f2, …, fn} булевых функций  полной, будем составлять таблицы, которые называются таблицами Поста. Данные таблицы имеют следующий вид.
Описание слайда:
Таблицы Поста В тех задачах, где требуется выяснить, является ли данная система {f1 f2, …, fn} булевых функций  полной, будем составлять таблицы, которые называются таблицами Поста. Данные таблицы имеют следующий вид.

Слайд 26


Пример. Выяснить, являются ли следующие системы булевых функций полными. Являются ли следующие системы булевых функций базисами. Пример. Выяснить, являются ли следующие системы булевых функций полными. Являются ли следующие системы булевых функций базисами.
Описание слайда:
Пример. Выяснить, являются ли следующие системы булевых функций полными. Являются ли следующие системы булевых функций базисами. Пример. Выяснить, являются ли следующие системы булевых функций полными. Являются ли следующие системы булевых функций базисами.

Слайд 27


Функционально замкнутые классы. Специальные классы булевых функций, слайд №27
Описание слайда:

Слайд 28


Базис Определение. Полная система функций называется базисом пространства булевых функций, если любое собственное подмножество данной системы функций уже не является полным. Другими словами, базис – это минимальная (но не по количеству, а в смысле отношения включения) полная система булевых функций. Теорема. Всякий базис пространства булевых функций содержит не более четырёх функций.
Описание слайда:
Базис Определение. Полная система функций называется базисом пространства булевых функций, если любое собственное подмножество данной системы функций уже не является полным. Другими словами, базис – это минимальная (но не по количеству, а в смысле отношения включения) полная система булевых функций. Теорема. Всякий базис пространства булевых функций содержит не более четырёх функций.

Скачать

Похожие презентации
Mypresentation.ru
Загрузить презентацию