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


 

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

59034. Мій рідний край у думах та піснях 60 KB
  Українська мова дуже багата на казки та пісні але найхарактернішими для творчості цього народу є дума епічна поема. І над чим він тяжко в пісні плаче Що він знає а не знаєм ми. Що ж можуть розповісти дослідникові Одещини українські народні пісні та думки Багато аби ми хотіли в ті пісні вслухатися або вчитатися.
59035. Містер початкових класів. Струнко дуть солдати 29.5 KB
  Привітання учасників 10 балів 2.Кожен отримує ту кількість балів скільки разів відіжметься 4. Найбільша кількість балів 5. Перший хто склав отримує 8 балів.
59036. Сценарій виховного заходу. Масляна 51 KB
  Весна Вбігають блазні. Допоможе нам у цьому Масляна. Ведуча: Масляна Масниця Колодій одне з календарно-побутових свят яке повязане із давнім народним звичаєм проводами зими і зустріччю весни. Пісня Масляна Муз.
59037. Матеріальна культура українців 53 KB
  На сьогоднішній урок дослідницькі групи готували повідомлення у вигляді тематичних виписок за темою Матеріальна культура українців. Робота дослідницьких груп Прошу представника першої групи Господарі доповісти.
59038. Мене війна веде все далі 52.5 KB
  Перший юнак. Другий юнак Сніги Не сніги а ріллі Наорані смертю за мить. Третій юнак І руки його обгорілі Не хочуть такого кінця І зуби аж сяють білі На спаленій масці лиця Бо то ж недомріяна мрія То ж вірність його комусь Напис на танку біліє: Жди я вернусь На фоні мелодії пісні...
59039. Методична розробка заходу. Конституція України у моєму житті 45 KB
  Вихователь. Ось уже 9 років ми живемо з вами в незалежній державі, яка знаходиться в Європі, кожної весни цвіте калиновим цвітом і молодіє вербовими гілками, улітку співає соловїним голосом і шелестить достиглим пшеничним колоссям. Кожного дня вона все впевненіше стає на ноги, усе гучніше звучить її голос.
59040. Страждання і доброї звістки в поемі Анни Ахматової Реквієм 40 KB
  Ви щойно прослухали Реквієм Моцарта та рядки із твору Анни Ахматової. Визначте з якого твору ці рядки поема Реквієм Де у поемі Реквієм вони розміщені. Про це поетеса говорила у епіграфі до поеми Реквієм.
59041. Методична розробка уроку - подорожі по творчості Мацуо Басьо 50.5 KB
  Бо це справді подорож чудовою країною Японією разом з поетом-мандрівником Мацуо Басьо. І саме Мацуо Басьо був засновником поетичної школи яка створила переворот в японській літературі. Стиль Басьо панував майже 2000 років.
59042. Ми - діти твої, Україно! Сценарій шкільного свята 58.5 KB
  За бажанням і звичайно можливістю приміщення можна прикрасити національними символами Ведучий. Ведучий. Зрозуміло аудиторія дуже швидко й точно назве державну атрибутику тож Ведучий коротко підсумувавши відповіді веде далі. Ведучий.