67608

Замкнутые классы

Лекция

Математика и математический анализ

Замкнутые классы 1 Обозначим через класс всех булевых функций сохраняющих константу 0 т. функций для которых выполняется равенство. Количество таких функций n число переменных т. 2 Обозначим через класс всех булевых функций сохраняющих константу 1 т.

Русский

2014-09-12

212.5 KB

4 чел.

Лекция № 17  (18.04.00)

Замкнутые классы

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


 

А также другие работы, которые могут Вас заинтересовать

47423. Процесс формирования и развития организационной культуры предприятия «СТОМГРУПП» 777 KB
  Предложения по развитию и укреплению культуры организации СТОМГРУПП. Одним из важнейших мотивов для исследования организационной культуры является то что традиционные методы управления организациями построенные на функциональной специализации работников и подразделений разделении труда обособленности отдельных структур организации друг от друга основанные на линейности и равновесности процессов не отвечают сложившимся в настоящем условиям. Таким образом современным организациям требуется новая идеология...
47424. ОСОБЕННОСТИ КОРРЕКЦИОННОЙ РАБОТЫ ПО РАЗВИТИЮ РЕЧИ У ДЕТЕЙ С ОНР 1.32 MB
  Исследование состояния связной речи детей старшего дошкольного возраста с общим речевым недоразвитием. Формирование связной речи у детей Библиография Введение Проблемой нашего исследования является уровень связной речи детей с общим недоразвитием речи.
47425. Кассовые операции 53.88 KB
  Виды услуг предоставляемых в отделении почтовой связи. Учет кассовых операций в отделении почтовой связи. Порядок получения сумм подкреплений денежной наличности в отделении почтовой связи. Порядок высылки сверхлимитных остатков из кассы отделения почтовой связи.
47426. Рестораны национальных кухонь в Астрахани и их использование в туристском бизнесе 946 KB
  Национальная кухня составляет важный элемент культуры региона. Туристы любят пробовать национальные блюда той страны, по которой путешествуют. Например, почти все туристы, впервые посещающие Россию, желают отведать борщ и пельмени.
47427. Специфика и приоритетные направления развития современных российско-грузинских отношений 429 KB
  Проанализировать российско-грузинские отношения в конце XX начале XXI века в трудах современных исследователей и прессе. Выявить специфику становления российско-грузинских взаимосвязей в русле национальной политики. Обозначить территориальные аспекты российско-грузинских взаимоотношений. Изучить вопросы экономического сотрудничества Грузии и России...
47428. ОЦІНКА ПРОЦЕСУ УПРАВЛЯННЯ МІЖНАРОДНОЮ МАРКЕТИНОГОВОЮ ДІЯЛЬНІСТЮ ТОВ «УНІВЕРСЛА ПРОДУКТ» 569 KB
  Для ефективного управління зовнішньоекономічною діяльністю на підприємстві потрібна відповідна умовам його роботи структура управління. На підприємствах, які беруть активну участь у зовнішньоекономічній діяльності, зовнішньоторговельний апарат існує у двох формах: як частина внутрішньовиробничої структури у вигляді зовнішньоекономічного відділу і як відносно самостійний підрозділ у вигляді зовнішньоторговельної фірми
47429. СОДЕРЖАНИЕ ФУНКЦИОНАЛЬНОГО АСПЕКТА УПРАВЛЕНИЯ ПРОЕКТОМ 208.5 KB
  Необходимо отметить что инвестиционная деятельность в современных условиях тесно связана с умением разработать эффективный инвестиционный план или проект а затем обеспечить определенные ими ограничения по ресурсам и реализовать заданный уровень качества продукции проекта. Не проводилось никакого управления на прединвестиционной и эксплуатационной фазе проекта. Практически не осуществлялось эффективного планирования на стадии реализации проекта. Отсюда сущность управления проекта обеспечить корректное выполнение поставленных целей с...
47430. Поклонение и Боговедение 561.53 KB
  Если ты спросишь, как выглядит служение Богу без Бога, то вот его описание. Огромное количество людей в храме, служения, праздники, торжества.
47431. Порядок формирования и использования резерва на возможные потери по ссудам 381 KB
  Сущность и функции кредита. Средства банка формируются за счет клиентских денег на расчетных текущих срочных и иных счетах; межбанковского кредита; средств мобилизованных банком во временное пользование путем выпуска долговых ценных бумаг и т. В первой главе основное внимание уделено сущности кредита рассмотрены функции кредита и основные принципы кредитования. Рассмотрена методика определения платежеспособности заемщика и поручителей этапы определения максимального размера кредита.