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


 

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

46380. Исследование резонансных явлений 683 KB
  Определение параметров реальной катушки индуктивности. Электрическая схема экспериментального определения параметров реальной катушки индуктивности. Измеряя напряжение на Uдоб на добавочном резисторе и Uк на катушке индуктивности Rk Xk произвести с помощью цифрового вольтметра Vц попеременно включая его к зажимам добавочного резистора и катушки индуктивности. Для вычисления параметров реальной катушки индуктивности необходимо воспользоваться данными измерений а также следующими формулами: Активное сопротивление всей цепи определяется по...
46381. Расчет токов короткого замыкания 2.49 MB
  Определить начальный сверхпереходный и ударный ток а также наибольшее действующее значение полного тока в месте повреждения при трехфазном коротком замыкании в узле К1; остаточное напряжение на выводах генератора и нагрузки а также начальный сверхпереходный ток в генераторе; периодическую слагающую тока в месте повреждения в произвольный момент времени при трехфазном коротком замыкании в узле К1; фазные значения тока и напряжения в месте повреждения при однофазном коротком замыкании в узле К2 а также фазные значения напряжения на...
46382. ИСТОРИЯ НИДЕРЛАНДОВ 13.28 MB
  ШатохинаМордвинцева ИСТОРИЯ НИДЕРЛАНДОВ Высшее образование Оглавление Предисловие ДРЕВНЕЙШИЙ И АНТИЧНЫЙ ПЕРИОДЫ ИСТОРИИ НИДЕРЛАНДОВ Глава 1 Этапы заселения Глава 2 Романизация и ее границы СРЕДНИЕ ВЕКА Глава 3 Раннее Средневековье V XI вв.: Нидерланды под властью Бургундии Глава 6 Культура Нидерландов конца XIV XV в Глава 7 Нидерландская живопись XV XVI вв. Начало освободительной борьбы Глава 10 Нидерландская революция и освободительная война Глава 11 Культура и наука Нидерландов XVI в НОВОЕ ВРЕМЯ Глава 12 Республика Соединенных...
46383. Организация, нормирование и оплата труда. Учебное пособие 663.5 KB
  Рассматриваются теоретические основы организации и нормирования труда на предприятиях железнодорожного транспорта; методы изучения трудовых процессов и затрат рабочего времени; принципы нормирования труда на основных видах работ, характерных для предприятий железнодорожного транспорта; система нормирования труда на железнодорожном транспорте; тарифная система заработной платы...
46385. Бухгалтерский и налоговый учет в строительстве. Учебное пособие 362.5 KB
  ПБУ 2 94 Учет договоров контрактов на капитальное строительство; Руководство Минстроя РФ по составлению договоров подряда на строительство в РФ; ПБУ 10 99 Расходы организации ; ПБУ 9 99 Доходы организации; МСФО 11 Договоры подряда; Глава 25 НК РФ и Методические рекомендации по применению главы Расходы подрядчика связанные с получением заключением договоров на строительство которые могут быть отдельно выделены и существует уверенность в том что договор будет заключен могут относиться к данному договору и...
46387. ТРАКТОРЫ И АВТОМОБИЛИ 993 KB
  Эффективные показатели двигателя Основные параметры цилиндра и двигателя. Тепловой баланс двигателя.Построение теоретических характеристик двигателя
46388. ИСПЫТАНИЕ ОБРАЗЦА НА РАСТЯЖЕНИЕ 361 KB
  Статической вязкостью называется способность материала поглощать энергию идущую на деформирование образца.2 При испытании образца рис.1 на испытательной машине получают первичную диаграмму растяжения в координатах: нагрузка удлинение образца рис.