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


 

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

46673. Попытки осуществления политических и экономических реформ.Н.С.Хрущёв 25.38 KB
  В 55г начинается кукурузная кампания Хрущева. Лозунг Хрущева догнать и перегнать Америку. 64г со всех постов и Хрущева. Однако следует отметить и глубокую враждебность Хрущева.
46674. Пеня 25.5 KB
  Сумма соответствующих пеней уплачивается помимо причитающихся к уплате сумм налога или сбора и независимо от применения других мер обеспечения исполнения обязанности по уплате налога или сбора а также мер ответственности за нарушение законодательства о налогах и сборах. Пеня начисляется за каждый календарный день просрочки исполнения обязанности по уплате налога или сбора начиная со следующего за установленным законодательством о налогах и сборах дня уплаты налога или сбора. Пени уплачиваются одновременно с уплатой сумм налога и сбора или...
46676. Метод прогонки 29.52 KB
  Метод прогонки Метод прогонки является частным случаем метода Гаусса и применяется к системам с трехпятидиагональной матрицей см. Предполагается что Метод прогонки состоит из двух этапов: прямой прогонки и обратной прогонки. В силу сказанного основу метода прогонки составляет так называемая прогоночная формула 4.
46677. Занятость населения и рынок труда 30.78 KB
  Занятость населения и рынок труда. Эффективная занятость характеризуется использованием рабочей силы без потерь при котором получается наибольший материальный результат и указывает при каком уровне производительности труда удовлетворяется потребность населения в работе какими путями достигается полная занятость. Рынок труда сфера формирования спроса и предложения на рабочую силу. Основными субъектами рынка труда являются работодатели и наемные работники.
46678. Международная корпорация в мировой экономике 32.26 KB
  ТНК – это крупные бюрократические корпорации, которые преодолевают риск в пределах корпоративной структуры, держат под контролем огромные денежные потоки, выступают в качестве подрядчиков на государственном уровне, привлекают технологии мирового класса, а также владеют массой закрытой информации.
46679. Стабилизационная политика государства в закрытой экономике 30.73 KB
  Инструменты денежнокредитной политики Банка России: ограничения динамики кредитования; учетная дисконтная политика; операции на открытом рынке; рефинансирование коммерческих банков. Современный коммерческий банк: функции операции роль в экономике. расчетнокассовые операции. Пассивные операции это такие операции банков в результате которых происходит увеличение денежных средств находящихся на пассивных счетах или активнопассивных счетах в части превышения пассивов над активами.
46680. НЭП и его особенности 29.93 KB
  Цель принятия НЭПа была направлена: на преодоление разрухи в стране восстановление экономики; создание фундамента социализма; развитие крупной промышленности; вытеснение и ликвидацию капиталистических элементов; укрепление союза рабочего класса и крестьянства. Вводилось ограничение на прибыль; разрешение наёмного труда аренды земли предприятий; возрождение кредитной системы был воссоздан Госбанк образован целый ряд специализированных банков;...