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


 

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

80332. Земельні ресурси та ефективність їх використання 145.5 KB
  Земля - головна умова існування людського суспільства і найважливіше джерело національного багатства, найперша передумова і природна основа суспільного виробництва, універсальний фактор будь-якої діяльності людини.
80333. Матеріально-технічна база в сільському господарстві 44.52 KB
  Машинотракторний парк та ефективність його використання. Транспортні засоби та ефективність їх використання. Це потребує додаткових витрат і впливає на ефективність використання матеріальнотехнічних засобів. Останні визначаються ростом і розвитком живих організмів і суттєво впливають на ефективність використання всіх інших засобів виробництва.
80334. Основні фонди та оборотні засоби сільськогосподарського підприємства 148 KB
  Амортизація основних фондів підприємства. Показники використання основних виробничих фондів підприємства. При цьому засоби праці знаходять своє вираження в основних фондах підприємства а предмети праці в оборотних фондах. До основних виробничих фондів належать такі фонди які беруть безпосередню участь у процесі виробництва і формуванні собівартості продукції.
80335. Персонал підприємства, продуктивність і оплата праці в сільському господарстві 144 KB
  Продуктивність праці і методика її визначення. Оплата праці персоналу підприємства. Із розвитком продуктивних сил чисельність працівників аграрного сектора економіки зменшується.
80336. Витрати виробництва і собівартість продукції 146.5 KB
  Вони й утворюють витрати підприємства. Тому витрати операційної діяльності виправдано трактувати як грошовий вираз ресурсів використаних виробничоспожитих у процесі виробництва і збуту продукції надання послуг виконання робіт та організації управління ним на всіх його ієрархічних рівнях. У даному випадку йдеться про поточні операційні витрати які підприємства здійснюють постійно для забезпечення безперервності виробництва.
80337. Економіка рослинництва. Економіка виробництва картоплі, овочів, плодів та ягід 66.5 KB
  Вирішальне значення для розвитку всіх галузей сільського господарства має нарощування виробництва зерна. На корм використовується і побічна продукція зернових солома полова відходи переробки зерна. Валове виробництво зерна у 2011 році 56747 тис тонн що порівняно із 1990 роком більше на 112 .
80338. Економіка тваринництва 85.5 KB
  Показниками ефективності галузі скотарства є: Технологічна ефективність: середньорічний надій молока від однієї корови; середньодобовий та річний приріст живої ваги ВРХ; затрати кормів на 1 ц молока та на 1 ц приросту живої ваги ВРХ. Економічна ефективність: трудомісткість виробництва 1ц молока та 1 ц приросту живої ваги ВРХ. собівартість виробництва 1 ц молока 1 ц приросту живої ваги ВРХ та 1 ц живої ваги ВРХ. середня ціна реалізації 1 ц молока 1 ц живої ваги ВРХ.
80339. Проектирование редуктора привода агрегатов средств наземного обслуживания 692 KB
  Основными недостатками передачи являются: большие габариты, что заставляет использовать ее исключительно для малонагруженных и высокооборотных передач; малая долговечность ремней, составляющая в среднем 1000 – 5000 часов; наличие скольжения, приводящего к непостоянству передаточного отношения.
80340. Обстеження публічно-недоступних місць, житла чи іншого володіння особи як негласна слідча (розшукова) дія 49.06 KB
  Обстеження публічнонедоступних місць житла чи іншого володіння особи як негласна слідча розшукова дія. Поняття суть мета правова основа та принципи обстеження публічнонедоступних місць житла чи іншого володіння особи. Саме тому єдиним джерелом доказової інформації є матеріали негласних слідчих розшукових дій зокрема обстеження публічнонедоступних місць житла чи іншого володіння особи. Це обумовлює необхідність детального вивчення правової основи вимог та принципів обстеження публічнонедоступних місць житла чи іншого володіння...