67608

Замкнутые классы

Лекция

Математика и математический анализ

Замкнутые классы 1 Обозначим через класс всех булевых функций сохраняющих константу 0 т. функций для которых выполняется равенство. Количество таких функций n число переменных т. 2 Обозначим через класс всех булевых функций сохраняющих константу 1 т.

Русский

2014-09-12

212.5 KB

2 чел.

Лекция № 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


 

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

53819. Координатна площина 6.62 MB
  На екрані з’являється слайд Кожна команда формулює питаннящоб відповіддю було це поняття. Якщо команда ставить правильно запитання і знаходить буквувона більше не бере участь. Кожна команда повинна знайти одну з букв. В залежності від того яку букву одержить команда вчитель регулює подальші дії.
53820. Определение географических координат (6 класс) 51 KB
  Далее объясняю как определить географическую широту места на карте или глобусе что такое географическая долгота. Обозначить на карте местонахождение базы точкой а направления промысловых судов от базы до их конечных пунктов стрелками. На карте или глобусе определите какой это остров Мадагаскар. На контурной карте полушарий подписать его название.
53821. Загальна характеристика рудних та нерудних корисних копалин України 115.5 KB
  Найбільший за площею вугільний басейн Дніпровський буровугільний Найбільший за запасами вугілля Донецький Найменша глибина залягання пластів Дніпровський буровугільний Найменший за площею ЛьвівськоВолинський Найбільша глибина залягання Донецький Найпотужніші пласти кам’яного вугілля Донецький Значний відсоток коксівного вугілля ЛьвівськоВолинський Гра Увага тест на уважність я називаю корисні копалини учні родовища Нафта Кам’яне вугілля Торф Природний газ Буре вугілля Горючі сланці. Дайте...
53822. Производственный и финансовый риски, их взаимосвязь с производственным и финансовым левереджем 27.5 KB
  Производственный риск обусловлен структурой активов, в который фирма решила вложить свой капитал. Этот риск определяется многими факторами: отраслевыми и региональными особенностями бизнеса, конъюнктурой рынка, национальными традиции
53823. Подвижные игры в детском саду 165.5 KB
  Какое значение имеют подвижные игры Докажите на конкретных примерах. Подвижные игры имеют неоценимое значение во всестороннем развитии личности: 1. В процессе игры двигательная активность детей вызывает деятельное состояние всего организма усиливает процессы обмена веществ повышает жизненный тонус.
53824. Виды дивидендной политики 30 KB
  Дивиденд – это часть прибыли, которую получают акционеры по имеющимся у них акциям. В соответствии с НК «Дивидендом признается любой доход, полученный акционером (участником) от организации при распределении прибыли
53825. Упражнения для развития орфографической зоркости учащихся 63 KB
  Задания: выписать из текста слова где есть мягкие согласные; выписать в 2 столбика слова: а с глухими согласными на конце; б со звонкими согласными на конце. записать слова на букву р т м о и т.; записать слова в алфавитном порядке; записать слова с мягким знаком на конце слова в середине слова; привести примеры с ударением на 1 слоге на 2ом и т.; Догадайся что за словоигра: сорока ворона овес овощи огород из словаря выписать слова на данную тему; чайнворды: с т а к а н а р ц и с с о б с у б о т в а...
53826. Изменение имен прилагательных по родам 29 KB
  Минутка красивого письма на доске показ аяое какие буквы соединения будем писать чем отличаются прописываю на доске Словарь: какую группу слов повторяли дома на доске слова но из каждого слова потерялась буква дети устно называют букву учитель вставляет яблко кпуста гурец грох млина записать в три столбика Жен.Изучение нового материала на доске картинки земляника арбуз яблоко.
53827. Комплексний підхід у корекційній роботі з попередження та подолання вад усного і писемного мовлення учнів 51.5 KB
  Актуальність знань щодо процесу розвитку мовлення дітей визначається завданням гуманізації виховання створенням оптимальних умов для найповнішого розкриття їхніх потенційних можливостей як суб’єкта спілкування та предметно – практичної діяльності. Головні положення лінгвістичних напрямів і напрямів які досліджують спілкування та мовлення як окремий випадок комунікативної діяльності визначають нові завдання щодо практики й теорії мовленнєвого розвитку дітей: потребу показати комплексний підхід до вивчення мови як засобу взаємодії...