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


 

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

31891. Методические рекомендации, планы семинарских занятий и темы контрольных работ по философии 198.5 KB
  Андреев Одобрены на заседании кафедры философии. кафедрой философии С. 2005 Введение При усвоении дисциплины студент должен иметь программу по философии в которой отражены цели задачи требования к уровню усвоения содержания дисциплины приведена основная и дополнительная литература по всем темам курса контрольные вопросы для подготовки к экзамену.
31892. Задания и методические указания для выполнения курсовых работ по дисциплине «Основы маркетинга» 77.5 KB
  Шапошников Одобрена на заседании кафедры менеджмента и маркетинга. Методические указания к написанию курсовой работы Главное условие успешного овладения студентами знаниями в области дисциплины Основы маркетинга заключается в самостоятельной систематической работе. При высоком уровне знаний проявленных при защите курсовой работы и другим контрольным мероприятиям а также на практических занятиях по дисциплине Основы маркетинга студент может быть освобожден от экзамена.
31893. Статистика. Задания к контрольным работам по дисциплине «Статистика» и методические указания для их выполнения 510 KB
  Группировкой называется расчленение множества единиц изучаемой совокупности на группы по определенным существенным для них признакам. Группировка выявляющая взаимосвязи между изучаемыми явлениями и их признаками называется аналитической группировкой. После определения признака положенного в основание группировки определяют количество групп на которые разбивают исследуемую совокупность. Число групп зависит от задач исследования типа группировки вида признака положенного в основание группировки численности совокупности степени вариации...
31894. ЭКОНОМИЧЕСКИЙ АНАЛИЗ 366.5 KB
  При изучении данной дисциплины и выполнении курсовой работы студенты должны быть знакомы с вопросами экономической статистики экономики предприятия бухгалтерского учета финансов предприятия изучаемыми на предыдущих курсах. Объектом изучения дисциплины выступает финансовохозяйственная деятельность предприятия соответственно курсовая работа направлена на выявление проблем в финансовохозяйственной деятельности определение резервов использования ресурсов и формулирование мероприятий по их реализации. Цель курсовой работы по дисциплине...
31896. Визначити максимальну температуру електричного дроту 99.5 KB
  Всередині труб рухається гарячий газ із середньою температурою tpiд1 а ззовні повітря що нагрівається із середньою температурою tpiд2.3: Номер варіанта. Сталевий зливок покладено до нагрівальної печі iз температурою середовища tpiд тривалість нагріву  початкова температура зливку t0.5: Номер варіанта S1 мм S2 мм S3 мм tpiд C  год.
31897. Электрический привод системы Г-Д 1.31 MB
  Номер варианта Закон изменения момента сопротивления рабочей машины Мсм Нм Момент инерции рабочей машины Jм в долях от момента инерции двигателя кгм2 Тип двигателя и способ его питания 8 800 60 Постоянного тока от генератора постоянного тока Примечание: Характер момента сопротивления реактивный. Требуемую перегрузочную способность двигателя. Средняя температура нагрева изоляции двигателя не должна превышать допустимую.4 Предварительная мощность двигателя рассчитывается по нагрузочной диаграмме и тахограмме рабочей машины.