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


 

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

79094. Легаты и фидеикомиссы. Виды легатов. Ограничения легатов. Универсальный фидеикомисс 23.62 KB
  Виды легатов. Ограничения легатов. Различалось несколько видов легатов. Наиболее существенным было различие легатов pervindictionem и легатов perdmntionem.
79095. Литтеральные договоры и реальные договоры. Заем и ссуда. Различие между этими договорами. Договор хранения его виды. Характер обязательств по договорам ссуды и хранения. Закладной договор 44.38 KB
  обязательство в этом случае устанавливается не только простым соглашением consensus но и передачей вещи res; нельзя требовать возврата от того кто ничего не получал. деньги зерно вино и тому подобные вещи определенные родовыми признаками. получающий юридическую силу лишь с того момента когда на основании соглашения сторон последовала передача res вещи;б предмет договора денежная сумма или известное количество других вещей определенных родовыми признаками весом числом мерой;в эти вещи передаются заимодавцем в собственность...
79096. Наследование по завещанию. Порядок составления. Условия действительности. Содержание завещания. Обязательная доля. Назначение наследника 23.27 KB
  Завещание по римскому праву это не просто всякое распоряжение лица своим имуществом на случай смерти а лишь такое которое содержало назначение наследника. Назначение наследника должно было быть в самом начале завещания и без него завещание не имело юридической силы. Завещание это односторонняя сделка выражающая волю лишь одного лица завещателя. На практике это позволяло завещателю в любой момент и без какихлибо ограничений отменить или изменить составленное им ранее завещание.
79097. Наследование по закону. Реформы претора. Наследование по закону в период империи 30.68 KB
  То обстоятельство что завещание получит действительное значение лишь при условии если назначенный в нем наследник согласится принять наследство не делает завещания договором ибо выражение воли наследника имеет место не при совершении завещания как например согласие одаряемого при дарении а только после смерти завещателя как совершенно самостоятельный отдельный от завещания акт. Некоторые лица хотя и имели testmenti fctio pssiv но не могли получать наследство полностью или в части если не отпадает обстоятельство признаваемое по...
79098. Общие положения о древнеримской семье. Агнатское и когнатское родство 18.89 KB
  Семья в древнейший известный нам период римской истории представляет тип промежуточной патриархальной семьи объединявшей под властью главы семьи pterfmilis жену детей других родственников кабальных а также рабов. Глава семьи и властелин древнейшей семьи домовладыка единственный полноправный гражданин квирит термин производимый многими исследователями от греческого kueros власть т. имеющий власть.С образованием государства внутри рода происходит имущественная дифференциация; власть внутри рода попадает в руки наиболее богатых...
79099. Опека и попечительство. Завещательная опека 21.41 KB
  Опека рассматривалась в Древнем Риме как обязанность лица и поэтому отказаться от исполнений обязанностей опекуна можно было только по уважительной причине. Если не было завещательной опеки и невозможно было установить законную опекуна назначал претор при участии трибунов учреждаемая опека. Особенности учреждаемой опеки: согласия малолетних на установление подобной опеки не требовалось; опекун должен был проживать в округе претора назначающего опе кунство; предварительно узнавали о нравственном поведении будущего опекуна; не...
79100. Определение деликта. Характер и объем ответственности 21.63 KB
  Различались частные и публичные деликты. Публичные деликты посягали на государственные интересы а частные на права и интересы отдельной личности. В настоящем курсе рассматриваются только частные деликты. Основные отличия деликтного обязательства от договорного: основание возникновения не договор а правонарушение; не допускалось правопреемство в отношении должника; штрафная ответственность возлагалась не солидарно на каждого из должников а кумулятивно то есть суммировалась по числу ответчиков и могла быть взыскана с каждого в полном...
79101. Определение обязательства. Основания возникновения обязательств. Классификация обязательств. Сделки. Контракты и пакты 24.8 KB
  Римское право определяло обязательство как правовые оковы в силу которых мы принуждаемся чтонибудь исполнить согласно законам нашего государства . В позднейший период обязательство стало рассматриваться как юридическое отношение между двумя лицами в силу которого одно из них именуемое кредитором имеет право требовать от другого лица именуемого должником исполнения чеголибо в свою пользу. В отличие от вещного права обязательство связывает только тех лиц которые в нем участвуют и поэтому кредитор может предъявить иск не ко всем а...
79102. Особые средства преторской защиты. Понятие исковой давности 19.33 KB
  Помимо предоставления исков преторы пользуясь принадлежащей им властью так называемым imperium оказывали иногда защиту особыми средствами своими безусловными в противоположность формуле иска непосредственными распоряжениями хотя с течением времени и здесь преторы в некоторых случаях перешли на путь условных распоряжений. С течением времени по мере увеличения числа дел претор стал давать интердикты без проверки фактов в виде условного распоряжения если подтвердятся факты на которые ссылается заявитель и тогда интердикты с...