67608

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

Лекция

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

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

Русский

2014-09-12

212.5 KB

3 чел.

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


 

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

49270. Использование эффекта Холла для измерения физических величин 932.6 KB
  Так как ЭДС Холла меняет знак на обратный при изменении направления магнитного поля на обратное, то Холла эффект относится к нечётным гальваномагнитным явлениям.
49273. Разработка электронной измерительной системы для контрольного приспособления для проверки расположения осей отверстий у корпусов с базированием на кулачковую оправку 1.82 MB
  На рисунке представлено контрольное приспособление кулачковой оправкой для измерения расположение осей отверстий корпуса стойки металокордовых машин. На этой оправке осуществляется также комплексное базирование корпусов.
49274. Аудит процесса управление несоответствующей продукцией ОАО «Северсталь-метиз» 1.62 MB
  Основными видами производственной и коммерческой деятельности Орловского сталепрокатного завода является выпуск и реализация метизной продукции, а именно проволоки низко и высокоуглеродистой; стальных сеток; электродов; стальных канатов; калиброванной стали
49276. Открытые горные работы. Курс лекций 1.09 MB
  В зависимости от назначения различают капитальные разрезные и специальные открытые горные выработки – траншеи. Капитальные траншеи служат для вскрытия месторождений или отдельных его участков с целью создания грузотранспортной связи рабочих горизонтов карьера с поверхностью. Разрезные траншеи проходят на каждом рабочем горизонте с целью создания первоначального фронта горных работ. Специальные траншеи служат для ограждения карьера от атмосферных вод дренажа месторождения водоотлива и хозяйственного обслуживания рабочих уступов.
49277. Методические основы проектирования карьеров 845 KB
  Выбор площади для строительства промышленного предприятия жилых домов и объектов культурнобытового назначения Кроме того ТЭО строительства карьера должно содержать следующее: характеристику карьера и анализ техникоэкономических показателей его работы; роль рассматриваемого карьера в обеспечении потребностей народного хозяйства в добываемом полезном ископаемом; горногеологическую характеристику месторождения и карьерного поля границы и запасы степень разведанности наличие попутных полезных ископаемых качества полезного...
49278. Расчет пленочных интегральных микросхем 599.65 KB
  Размер зерен менее 40 мкм. Если ограничить толщину пленки величиной 01 мкм а максимальную и минимальную площади соответственно 2Ю2 и 02 мм2 то для обеспечения диапазона емкостей 10 106 Ф требуются диэлектрические постоянные примерно равные 05 50. ТЕХНИЧЕСКОЕ ЗАДАНИЕ Рассчитать группу тонкопленочных резисторов при следующих исходных данных: bтехн=125 мкм lтехн=125 мкм Рассчитать конденсатор при следующих исходных данных: ПОЯСНИТЕЛЬНАЯ ЗАПИСКА ДЛЯ РАСЧЕТА РЕЗИСТОРОВ По формуле определяем значение оптимального сопротивления и...