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


 

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

68794. Расчёт трёхфазного силового масляного двухобмоточного трансформатора 2.79 MB
  Трансформатором называется статистическое электромагнитное устройство, имеющее две или более индуктивно связанных обмоток и предназначенное для преобразования посредством электромагнитной индукции одной или несколько систем переменного тока в одну или несколько других систем переменного тока.
68795. Анализ реализации продукции для улучшения деятельности предприятия (на примере ОАО «Новогрудский маслодельный комбинат») 335.5 KB
  Согласно Закону о предприятиях в Республике Беларусь предприятия самостоятельно планируют свою деятельность на основе договоров заключенных с потребителями продукции и поставщиками материально-технических ресурсов и определяют перспективы...
68796. Реконструкция зданий и сооружений 55.5 KB
  Единственной рациональной альтернативной сносу являются модернизация и реконструкция рассматриваемых зданий методами градостроительного преобразования и переустройства которые должны быть произведены с учётом экономических социально функциональных технических эстетических и экологических...
68797. Прибыль предприятия как цель его функционирования 188.5 KB
  Использование средств производства работниками материальной сферы обеспечивает выпуск промышленной продукции. Для выявления финансового результата необходимо сопоставить выручку с затратами на производство и реализацию которые принимают форму себестоимости продукции.
68798. Технология изготовления металлических деталей светильника и его сборка 204.5 KB
  Для изготовления настольной лампы необходимы листы трубки и провода. Холодная штамповка нашла широкое применение на светотехнических заводах и различают следующие ее виды: 1 вырубку когда из листовой заготовки вырезается деталь заданного контура; 2 пробивку когда в заготовке детали производится...
68800. Маркетинговое исследование рынка сахара в городе Омске 189.26 KB
  Целью данного маркетингового исследования является изучение рынка сахара в городе Омске, ассортимента и предпочтений потребителей. Для достижения этой цели, необходимо решить следующие задачи: Изучить сущность маркетинговых исследований; Разработать опросный лист и провести опрос...
68801. Расчет передающего устройства магистральной радиосвязи 6.62 MB
  Мощность сигнала в нагрузке – 18 кВт Диапазон рабочих частот – 3 – 9 МГц Нагрузка – несимметричная, широкополосная сопротивлением 50 Ом Модуляция – А3J – однополосная телефония с подавленной несущей. Передача одноканальная. В возбудителе содержится синтезатор с шагом рабочих частот – 60 Гц.
68802. Устройства генерирования и формирования сигналов 4.71 MB
  Мощность которую должен обеспечивать один модуль выходного каскада можно оценить по формуле: ; Вт где КПД выходной колебательной системы и КПД систем сложения мощностей; M число модулей в выходном каскаде. Каждый двухтактный ГВВ модуля выходного каскада должен выделять мощность 1235 4 = 30875 Вт.