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


 

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

47838. АНАТОМИЯ, ФИЗИОЛОГИЯ, ПАТОЛОГИЯ ДЕТЕЙ С ОСНОВАМИ ГЕНЕТИКИ 857 KB
  Рост - это увеличение размеров развивающегося организма. В понятие онтогенез включают все стадии развития организма от момента оплодотворения яйцеклетки до смерти человека. отрезки времени онтогенеза каждый из которых характеризуется своими специфическими особенностями организма функциональными биохимическими морфологическими и психологическими.
47839. Система бухгалтерского учета 101 KB
  В соответствии с Федеральным законом О бухгалтерском учете N 129ФЗ от 21 ноября 1996 года бухгалтерский учет представляет собой упорядоченную систему сбора регистрации и обобщения информации в денежном выражении об имуществе обязательствах организации и их движении путем сплошного непрерывного и документального учета всех хозяйственных операций. В соответствии с действующим Законом О бухгалтерском учете бухгалтерский учет ведут все организации находящиеся на территории РФ а также филиалы и представительства иностранных организаций....
47840. Економічна сутність і методи вимірювання продуктивності 110.5 KB
  Економічна сутність і методи вимірювання продуктивності Сутність і значення продуктивності праці Розрізняють поняття продуктивність і продуктивність праці. Продуктивність - це ефективність використання ресурсів праці капіталу землі матеріалів енергії інформації під час виробництва різних товарів і надання послуг. Тому для визначення ефективності виробництва найчастіше використовують показник продуктивності праці хоча це не означає що тільки праця є джерелом продуктивності. Продуктивність праці відбиває ступінь ефективності...
47842. Лекции по электробезопасности 247.5 KB
  Длительность протекания тока (ожоги тканей тела, нагрев внутренних органов, изменение состава крови, нарушение функций центральной нервной системы, вероятность совпадения времени протекания электрического тока с фазой Т кардиоцикла)
47843. Философия. Основы философского учения 948.5 KB
  Мировоззрение его структура и основные типы Мировоззрение это система обобщенных взглядов на мир на место в нем человека и его отношение к этому миру а также основанные на этих взглядах убеждения чувства и идеалы определяющие жизненную позицию человека принципы его поведения и ценностные ориентации. Убеждения не особый вид знаний а их состояние качественная характеристика Мировоззрение включает настроения чувства переживиния составляющие его эмоциональнопсихологическую сторону и оказывающие существенное влияние на...
47844. Финансы. Учебное пособие 519 KB
  В учебном пособии представлен первый раздел Финансы где рассматриваются основные вопросы сущность и функции финансов финансовая политика финансовая система и ее звенья управление финансами организация финансового контроля. Особое внимание уделяется изучению государственных и местных финансов: бюджетное устройство РФ государственный кредит и внебюджетные фонды. Финансы выступают неотъемлемой частью рыночных отношений и одновременно важным инструментом реализации финансовой политики государства. Целью учебного...
47845. Финансы железнодорожного транспорта 95 KB
  Сущность финансов железнодорожного транспорта Централизация управления финансами на железнодорожном транспорте ВВЕДЕНИЕ Транспортный комплекс состоит из большого количества взаимосвязанных отраслей и представляет собой особую транспортную отрасль производства обладающую общностью законов развития однородностью производственных процессов и назначением создаваемой продукции. Поэтому стратегия развития транспорта должна строиться с учетом неразрывности двух его функций: как поставщика услуг необходимых для развития экономики так и...
47846. ЗАКОН ХАРДИ-ВАЙНБЕРГА 622 KB
  ЧАСТОТА ГЕНА А и а рассматриваемые аллели N количество диплоидных особей 2N количество генов D количество особей с доминантными аллелями АА Н количество гетерозиготных особей Аа R количество рецессивных особей аа D H R = N D H R структура популяции D H R доля или частота гена доля или частота гена а СЛУЧАЙНОЕ СКРЕЩИВАНИЕ структура популяции частота скрещиваний УСТАНОВЛЕНИЕ РАВНОВЕСИЯ формула теоретической популяции ; экспериментальная популяция