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


 

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

74395. ВЫБОР ПРОВОДНИКОВ ЛИНИЙ ЭЛЕКТРОПЕРЕДАЧИ ПО УСЛОВИЮ НАГРЕВАНИЯ 223.5 KB
  Все проводники линий электропередачи должны выбираться (или проверяться) по условию нагревания. Это требование связано с тем, что для проводников воздушных и кабельных линий устанавливаются вполне определенные длительно допустимые температуры.
74396. УЧЕТ ТЕХНИЧЕСКИХ ОГРАНИЧЕНИЙ ПРИ ВЫБОРЕ ПРОВОДОВ ВОЗДУШНЫХ ЛИНИЙ И ЖИЛ КАБЕЛЕЙ 40.5 KB
  Коронирование проводов воздушных линий. Следовательно различным номинальным напряжением будут соответствовать вполне определенные минимальные диаметры проводов для которых соблюдается условие. Поскольку диаметры и площади сечения проводов в свою очередь связаны между собой то выбор проверка проводов по условию короны может быть произведен по условию где Fнм.
74397. ПУТИ ПОВЫШЕНИЯ ПРОПУСКНОЙ СПОСОБНОСТИ ЛИНИЙ ЭЛЕКТРОПЕРЕДАЧ И ЭЛЕКТРИЧЕСКИХ СЕТЕЙ 720 KB
  К таким ограничениям относятся: а предел передаваемой мощности предел линии учитывающий устойчивость параллельной работы электрических станций и узлов нагрузки...
74398. Определение оптимальной мощности компенсирующего устройства для линии 55.5 KB
  Оптимальную мощность компенсирующего устройства описывают, исходя из критерия оптимизации. В качестве которого рассмотрим приведенные затраты. Функция кривых затрат отмечена в виде
74399. Учет равномерности затрат при оптимизации развития электрической системы. Метод приведенных затрат в динамической постановке 35 KB
  Приведенные затраты в динамической постановке записываются в виде: где Θ период год к которому приводятся разновременные инвестиции и издержки чаще всего принимают первый период или год сооружения. Выражение в скобках означает приведенные затраты на интервале Т. Если таких отраслей j то динамические приведенные затраты формулируются в следующем виде: Есть несколько вариантов наилучший вариант там где min. Практическое решение заключается в выделении одного хотя не самого лучшего доминирующего критерия например ЧДД или приведенные...
74400. Чистый дисконтированный доход (ЧДД 36.5 KB
  Под ним понимают превышение суммарных денежных поступлений над суммарными затратами с учетом неравноценности эффектов относящихся к различным моментам времени. При этом дисконтированием называют приведение разновременных значений денежных потоков денежных поступлений капиталовложений и пр.
74401. ВЫБОР ВАРИАНТА РАЗВИТИЯ ЭЛЕКТРИЧЕСКОЙ СЕТИ С УЧЕТОМ НАДЕЖНОСТИ ЭЛЕКТРОСНАБЖЕНИЯ И ТРЕБОВАНИЙ ЭКОЛОГИИ 901.5 KB
  При нормативном подходе опираются на требования к обеспечению надежности электроснабжения излаженные в ПУЭ. К наиболее ответственным электроприемникам I категории отнесены такие перерыв электроснабжения которых может повлечь за собой опасность для жизни людей повреждение дорогостоящего оборудования массовый брак продукции расстройство сложного технологического процесса нарушение функционирования особо важных элементов коммунального хозяйства. К электроприемникам II категории отнесены те перерыв электроснабжения которых приводит...
74403. Строение и развитие (мегаспорогенез) зародышевого мешка 30.5 KB
  Там они делятся позднее еще два раза и на концах зародышевого мешка получается по четыре ядра. По одному ядру от каждой группы так называемые полярные ядра направляется к середине зародышевого мешка где они сливаются и образуют так называемое вторичное или центральное ядро зародышевого мешка. Вокруг трех ядер находящихся в конце зародышевого мешка ближайшем к пыльцевходу скопляется густая протоплазма и получаются три клетки голые или одетые очень тонкой белковой но не целлюлозной оболочкой.