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


 

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

25756. Аудит расчетов с бюджетом 32.5 KB
  Налоговая инспекция имеет право перепроверить правильность представленного аудиторами заключения в случаях если ею будет установлена недоброкачественность аудита приведшая к ущемлению интересов бюджета. Аудитору необходимо проверить: правильно ли исчислены налогооблагаемые базы; правильность исчисления прибыли переходного периода; правильно ли применены ставки налогов и платежей; своевременно ли и полностью уплачены платежи в бюджет; правильно ли и обоснованно применены льготы; правильно ли ведется аналитический и синтетический...
25757. Аудит расчетов с персоналом по оплате труда 78.5 KB
  Целью аудита расчетов по оплате труда является установление соответствия применяемой в организации методики учета и налогообложения операций по оплате труда и расчетов с персоналом действующим в РФ нормативным документам. Основные задачи аудита: оценка существующей в организации системы расчетов с персоналом и ее эффективности; оценка состояния синтетического и аналитического учета операций по оплате труда и расчетов с персоналом организации в проверяемом периоде; оценка полноты отражения совершенных операций в бухгалтерском учете;...
25758. Аудит расчетов с поставщиками и покупателями 33.5 KB
  Этому участку учета свойственны определенные факторы риска обусловленные следующими причинами: отсутствие многократного контроля за первичными документами на стадии их создания и проверки как это происходит с документацией создаваемой на предприятии; сложность восстановления отсутствующих и исправления неправильно оформленных документов; большая вероятность несвоевременного поступления подтверждающих документов; отсутствие унификации значительной части первичных документов подтверждающих совершение этих операций особенно операций...
25759. Аудит учредительных документов и расчетов с учредителями организации 33.5 KB
  Задачами аудита учредительных документов являются: Изучение статуса юридического лица организации сферы деятельности и права его функционирования; Изучение наличия лицензий по видам деятельности; Проверка порядка формирования изменения уставного капитала и изучение его структуры. № 128ФЗ О лицензировании отдельных видов деятельности; Федеральный закон от 08. № 129ФЗ О государственной регистрации юридических лиц и индивидуальных предпринимателей; План счетов бухгалтерского учета финансовохозяйственной деятельности организаций...
25760. Законы пластической деформации 94 KB
  Если деформация, вызванная внешними силами, исчезает при прекращении действия внешних сил и твердое тело полностью восстанавливает свои исходные форму и размеры, то такую деформацию называют упругой. Если же при прекращении действия внешних сил твердое тело не полностью восстанавливает свои исходные форму и размеры
25761. Автоматизация бухгалтерского учета «1С: Бухгалтерия» 31 KB
  1С: Бухгалтерия универсальная программа массового назначения для автоматизации бухгалтерского учета. Программа позволяет автоматизировать ведение всех разделов бухгалтерского учета: операции по банку и кассе основные средства и нематериальные активы материалы ит. В 1С: Бухгалтерии предусмотрен как ручной ввод бухгалтерских операций так и работа от документа с автоматическим формированием проводок по различным разделам учета.
25762. Анализ эффективности капитальных вложений 28.5 KB
  Для анализа эффективности капитальных вложений используют следующие методы: 1. Метод расчета чистого приведенного эффекта. Метод расчета индекса рентабельности инвестиции. Метод расчета нормы рентабельности инвестиций.
25763. Анализ деловой активности 23.5 KB
  Качественными критериями являются: широта рынков сбыта продукции; наличие продукции поставляемой на экспорт; репутация предприятия. уровень эффективности использования ресурсов предприятия. Хозяйственная деятельность предприятия может быть охарактеризована различными показателями основными из которых являются: объем реализации продукции работ и услуг прибыль величина активов предприятия. Эта зависимость означает что экономический потенциал предприятия возрастает по сравнению с увеличением экономического потенциала объем реализации...
25764. Анализ использования оборотных средств 28 KB
  При анализе состояния предприятия большое внимание уделяется анализу интенсивности использования оборотных средств так как именно от скорости превращения их в денежную наличность зависит ликвидность предприятия. Эффективность использования оборотных средств может характеризоваться системой показателей: коэффициент опережения темпов роста объемов продукции работ и услуг над темпами роста остатков оборотных средств; увеличение реализации продукции работ и услуг на 1 рубль оборотных средств; относительной экономией или дополнительным...