Замкнутые классы
Класс булевых функций. Определение числа самодвойственных функций. Множество всех наборов длины по отношению к операции предшествования. Теорема о функциональной полноте. Понятия многозначной логики. Дистрибутивность операции max относительно min.
| Рубрика | Математика |
| Вид | лекция |
| Язык | русский |
| Дата добавления | 18.10.2013 |
| Размер файла | 69,5 K |
Отправить свою хорошую работу в базу знаний просто. Используйте форму, расположенную ниже
Студенты, аспиранты, молодые ученые, использующие базу знаний в своей учебе и работе, будут вам очень благодарны.
Размещено на http://www.allbest.ru/
Лекция
Замкнутые классы
1) Обозначим через - класс всех булевых функций , сохраняющих константу 0, т.е. функций, для которых выполняется равенство .
При добавлении несущественной переменной равенство не меняется.
Функции, .
Количество таких функций (n - число переменных) т.к. в первой строке всегда содержит 0. (У второй половины 1).
T0 - замкнутый класс, т.к. если
, то
.
2) Обозначим через - класс всех булевых функций , сохраняющих константу 1, т.е. функций, для которых выполняется равенство .
Класс вместе с любой функцией содержит равную ей функцию.
Функции , .
Класс состоит из функций двойственных классу (следует из определения).
Поэтому все свойства класса переносятся на класс .
.
3) S - класс - класс всех самодвойственных функций, т.е. .
Функции ,
, т.к.
Для самодвойственной функции имеет место тождество
.
Тем самым на наборах и ф-я принимает противоположные значения (определяется половиной комбинаций xi). Поэтому число самодвойственных функций равно .
Докажем, что класс S замкнут. Пусть , , т.е. . Тогда
.
4. Обозначим
, , .
опр || Для 2х наборов и выполнено отношение предшествования , если .
Пример.
Очевидно, что если.
Таким образом, множество всех наборов длины n по отношению к операции предшествования является частично упорядоченным.
Опр. || функция называется монотонной, если для любых 2х наборов таких, что выполняется неравенство
.
Монотонные функции:
,
- не монотонны
Обозначим M - множество всех монотонных функций. Нужно доказать, что этот класс замкнутый.
Пусть , , .
Будем считать, что все fi зависят от x1, xn.
Пусть два набора переменных длины n, причем . Тогда,
,
следовательно
,
тогда и
.
Тем самым
.
5) L - класс всех линейных функций
О замкнутости этого класса мы упоминали ранее. Количество линейных функций .
Эти замкнутые классы не тождественны и они не полны, что следует из таблицы
|
T0 |
T1 |
S |
M |
L |
||
|
0 |
+ |
- |
- |
+ |
+ |
|
|
1 |
- |
+ |
- |
+ |
+ |
|
|
- |
- |
+ |
- |
+ |
Теорема о функциональной полноте.
Для того, чтобы система функций была полной, необходимо и достаточно, чтобы она целиком не содержалась ни в одном из 5 замкнутых классов T0, T1, S, M, L.
(Без док-ва).
Опр. Класс R из (множество всех булевых функций) называется предполным или максимальным, если для любой ф-ции f () класс полный.
В алгебре логики только 5 предполных классов: .
Пример.
система полна.
С другой стороны, удаление любой из функций приводит к неполной системе
Пример 2.
Система функций B={x1x1}, полна так как не сохраняет константы, не линейна, не самодвойственна () и не монотонна (последний ноль - после 1).
Теорема || из всякой полной в системы функций B можно выделить полную подсистему, содержащую не более 4х функций.
(Без док-ва).
Понятия многозначной логики.
Оценка погрешности.
k - знач. логика
k - катур. Число
множество значений, которые может принимать функция
опр || называется k-значной логикой, если в наборе значения переменных , где значение
Элемент функции k-значной логики
1) константы: 0,1,…,k-1
2) отрицание Роста:
3) отрицание Лукасевича:
4) Характеристическая функция Iго рода
5) Характеристическая функция 2го рода:
6)
7)
8) сумма по модулю k
9) произведение
10) усеченная разность
11)
12) Функция Вебба:
13)
Свойство функций:
выполняются свойства коммутативности и ассоциативности, дистрибутивность, умножение относительно сложения
Дистрибутивность операции max относительно min
|
x |
y |
z |
I |
II |
|
|
1 |
2 |
3 |
z |
z |
|
|
1 |
3 |
2 |
z |
z |
|
|
2 |
1 |
3 |
z |
z |
|
|
2 |
3 |
1 |
x |
x |
|
|
3 |
1 |
2 |
z |
z |
|
|
3 |
2 |
1 |
y |
y |
|
|
1 |
1 |
1 |
1 |
1 |
|
|
1 |
2 |
2 |
2 |
2 |
|
|
2 |
1 |
2 |
2 |
2 |
|
|
3 |
2 |
1 |
2 |
2 |
Дистрибутивность операции min относительно max
булевой самодвойственный предшествование дистрибутивность
Размещено на Allbest.ru
...Подобные документы
Понятие, истоки, систематизация и развитие теории групп. Множество как совокупность объектов, рассматриваемых как единое целое. Нильпотентные группы - непустые множества, замкнутые относительно бинарной алгебраической операции, их свойства и признаки.
курсовая работа [541,3 K], добавлен 27.03.2011Полнота и замкнутость системы булевых функций. Алгоритм построения таблицы истинности двойственной функции. Класс L линейных функций, сущность полинома Жегалкина. Распознавание монотонной функции по вектору ее значений. Доказательство теоремы Поста.
учебное пособие [1,3 M], добавлен 20.08.2014Формации как классы групп, замкнутые относительно фактор-групп и подпрямых произведений, методика их произведения. Операции на классах групп, приводящие к формациям. Виды простейших свойств локальной формации всех групп с нильпотентным компонентом.
курсовая работа [461,6 K], добавлен 20.09.2009Множество как ключевой объект математики, теории множеств и логики. Операции над множествами, числовые последовательности. Множества действительных чисел. Бесконечно малые и большие функции. Непрерывность функции в точке. Свойства непрерывных функций.
лекция [540,0 K], добавлен 25.03.2012Сокращенные, тупиковые дизъюнктивные нормальные формы. Полные системы булевых функций. Алгоритм Квайна, Мак-Класки минимизации булевой функции. Геометрическое представление логических функций. Геометрический метод минимизации булевых функций. Карты Карно.
курсовая работа [278,1 K], добавлен 21.02.2009Понятие алгебры логики, ее сущность и особенности, основные понятия и определения, предмет и методика изучения. Законы алгебры логики и следствия из них, методы построения формул по заданной таблице истинности. Формы представления булевых функций.
учебное пособие [702,6 K], добавлен 29.04.2009Изучение булевых функций. Алгоритм представления булевых функций в виде полинома Жегалкина. Система функций множества. Алгебраические преобразования, метод неопределенных коэффициентов. Таблица истинности для определенного количества переменных.
курсовая работа [701,9 K], добавлен 27.04.2011Определения понятия множество. Предельная точка множества, предел функции в точке. Эквивалентные, счетные и несчетные множества. Замкнутые и открытые множества. Функции на множестве. Свойства непрерывных функций на замкнутом ограниченном множестве.
курсовая работа [222,3 K], добавлен 11.01.2011Основные аксиомы и тождества алгебры логики. Аналитическая форма представления булевых функций. Элементарные функции алгебры логики. Функции алгебры логики одного аргумента и формы ее реализации. Свойства, особенности и виды логических операций.
реферат [63,3 K], добавлен 06.12.2010Основные обозначения и понятия, относящиеся к множествам, операции над ними. Объединение, пересечение и разность двух множеств и непринадлежность к нему элемента. Первая и вторая теорема Вейерштрасса, Ферма и Ролля. Вычисление интеграла вероятности.
контрольная работа [389,2 K], добавлен 12.12.2010Определение понятия множеств Г. Кантора, их примеры и обозначения. Способы задания, включение и равенство множеств, операции над ними: объединение, пересечения, разность, дополнение, их определение и наглядное представление на диаграмме Эйлера-Венна.
реферат [70,9 K], добавлен 11.03.2009Доказательство существования или отсутствия алгоритма для решения поставленной задачи. Определение алгоритмической неразрешимости задачи. Понятия суперпозиции функций и рекурсивных функций. Анализ схемы примитивной рекурсии и операции минимизации.
курсовая работа [79,5 K], добавлен 12.07.2015Описание свойств наследственных насыщенных формаций Фиттинга (замкнутые относительно произведения F-подгрупп) Шеметкова (где минимальная не F-группа является либо группой Шмидта с ненормальной циклической силовой подгруппой, либо простого порядка).
курсовая работа [204,0 K], добавлен 14.02.2010Изучение свойств критических групп и субнормальных подгрупп. Нахождение серии наследственных насыщенных формаций Шеметкова (минимальная не F-группа тут группа Шмидта, либо простого порядка) и Фиттинга (замкнутые относительно произведения F-подгрупп).
дипломная работа [272,8 K], добавлен 14.02.2010Краткое историческое описание становления теории множеств. Теоремы теории множеств и их применение к выявлению структуры различных числовых множеств. Определение основных понятий, таких как мощность, счетные, замкнутые множества, континуальное множество.
дипломная работа [440,3 K], добавлен 30.03.2011Основные свойства функций, для которых существуют пределы. Понятие бесконечно малых величин и их суммы. Предел алгебраической суммы, разности и произведения конечного числа функций. Предел частного двух функций. Нахождение предела сложной функции.
презентация [83,4 K], добавлен 21.09.2013Функциональные и степенные ряды. Разложение функций в ряды Тейлора и Макларена. Теорема Дерихле. Основные понятия в теории вероятностей. Теорема умножения и сложения вероятностей независимых событий. Формулы Бейеса, Бернулли. Локальная теорема Лапласа.
методичка [96,6 K], добавлен 25.12.2010Логика - наука о законах и формах мышления, а основное понятие алгебры логики - высказывание. Основные понятия и тождества булевой алгебры. Изучение методов минимизации булевых функций. Метод Квайна, основанный на применении двух основных соотношений.
контрольная работа [178,2 K], добавлен 20.01.2011Определение, типы и примеры отношений, способы их задания; алгебраическая и геометрическая интерпретации. Разбиение на классы и фактор-множество. Смысл отношения эквивалентности. Теорема о равносильности определений. Отношения в школьной математике.
курсовая работа [1,0 M], добавлен 01.10.2011Множеством именуется некоторая совокупность элементов, объединенных по какому-либо признаку. Над множествами определяют операции, во многом сходные с арифметическими. Операции над множествами интерпретируют геометрически с помощью диаграмм Эйлера-Венна.
реферат [15,8 K], добавлен 03.02.2009
