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


 

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

10687. Маруся - Квітка-Основяненко 16.75 KB
  Маруся Квітка-Основяненко Наум Дрот та його дружина були людьми богобоязними та праведними. В усьому вони дотримуються Божого і морального людського закону. За це Бог допомагає їм. За молитви й невпинну працю дає їм Бог донечку. Дитина теж росте слухняна покірна на ву
10688. Чорна рада - Пантелеймон Куліш - Хроніка 1663 року 20.2 KB
  Чорна рада Пантелеймон Куліш Хроніка 1663 року І Навесні двоє верхових наближалися до Києва Білгородським шляхом. Де їхали полковник Шрам із сином. Полковник був сином поволоцького попа вивчився на попа але потім пішов до козаків. Після поразки повстання полковник дес...
10689. Вовчок Марко - Максим Гримач 14.49 KB
  Вовчок Марко Максим Гримач Давно це було коли панували в Україні Польща і Московщина. Застави між державами хоч і стояли та не густо спритні люди часто перевозили Дніпром усякий крам не сплачуючи мита. Навпроти Черкас над Дніпром стояв хутір Максима Гримача. Чолові
10690. Кайдашева сімя - Нечуй-Левицький Іван 17.95 KB
  Кайдашева сімя НечуйЛевицький Іван І Село Семигори знаходиться недалеко коло Росі ховається воно в зелених садах навколо розстилаються левади. Хата Омелька Кайдаша притулилася біля однієї гори в старому садку. Старий Кайдаш сидить коло повітки та майструє одягнен...
10691. Хіба ревуть воли, як ясла повні? - Мирний Панас - Роман з народного життя 25.69 KB
  Хіба ревуть воли як ясла повні Мирний Панас Роман з народного життя ЧАСТИНА ПЕРША І Польова царівна Надворі вповні розвинулася весна вся природа буяє. В такий прекрасний весняний день дорогою від села Пісок до Ромодана йшов молодий чоловік. Він із задоволенням розг
10692. Мартин Боруля - Карпенко-Карий Іван 17.35 KB
  Мартин Боруля КарпенкоКарий Іван Мартин Боруля багатий шляхтич чиншовик той хто платить за оренду землі якомусь іншому власникові просить повіреного Трандалєва прочитати документ де вказано що Дворянскоє депутатскоє собраніє зачисляє його Борулю до дворянс
10693. Земля - Кобилянська Ольга 16.55 KB
  Земля Кобилянська Ольга Велике село Д. на Буковині. Горстка хаток притулилася до величного панського лісу. Інші розташувалися серед поля. Заможна селянка Докія занепокоєна долею своєї єдиної доньки Парасинки. Мати вже почуває себе вкрай погано батько ж страшний пият...
10694. Тіні забутих предків - Коцюбинський Михайло 15.78 KB
  Тіні забутих предків Коцюбинський Михайло Ще з народження Іван який був дев’ятнадцятою дитиною в гуцульській сім’ї Палійчуків лякав матір та родичів неприродно розумним глибоким поглядом. Де викликало в людей містичні згадки про підкинутих нечистим дітей. Змалку п
10695. Камінний хрест - Стефаник Василь 14.09 KB
  Камінний хрест Стефаник Василь Скільки у селі пам’ятають Івана Дідуха у нього завжди була одна конячина якою селянин оброблював горб що залишився йому у спадок від батька. Незрозуміло було хто з них більше тягне плуга Іван чи коняка але чоловік ніколи не кричав на