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


 

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

35013. Естественный уровень безработицы 24.5 KB
  Это нормально если часть людей не работает потому что вынуждены поменять профессию или место работы. Меры государственной поддержки безработных сводятся к двум основным направлениям: социальной защите людей оставшихся без работы и содействие трудоустройству. Как правило его получают лица зарегистрированные на бирже труда имеющие стаж работы и вносившие определенное время взносы в фонд занятости. Биржи ведут учет свободных рабочих мест и граждан обращающихся по вопросам трудоустройства информируют граждан и работодателей...
35014. Инфляция: сущность, виды, причины и источники 32.5 KB
  Зародившись на денежном рынке вирусы инфляции затем проникают дальше поражая другие части хозяйственного организма. Различают следующие виды инфляции: открытая и подавленная сбалансированная и несбалансированная ожидаемая и неожидаемая инфляция. Этот тип инфляции характерен для стран с рыночной экономикой. В условиях подавленной инфляции цены весьма далеки от реальных изменений потребностей и спроса что способствует хроническому недопроизводству товаров пользующихся спросом.
35015. Причины инфляции 34.5 KB
  Именно они лежат в основе инфляции спроса и инфляции предложения или издержек. При инфляции спроса спрос опережает предложение возникает избыток денег по отношению к количеству товаров растут цены. Это весьма знакомый для нашей страны вариант инфляции.
35016. Взаимосвязь инфляции и безработицы. Кривая Филлипса 25.5 KB
  Пытаясь искусственно добиться высокого уровня занятости соответственно сокращения безработицы государство выходит за максимально допустимые рамки вмешательства в рыночные процессы. В современных рыночных системах занятость становится подлинно полной и эффективной только тогда когда уровень безработицы близок к естественной норме а она как известно никак не может быть равна нулю. Все эти действия носят сугубо инфляционный характер ведут к сохранению по существу лишних рабочих мест поддержанию противоестественного уровня занятости...
35017. Деньги: сущность, функции, виды 38 KB
  Возникновение денег есть исторический процесс в основе которого лежит развитие товарного обмена. Функции денег. Сущность денег полнее проявляется в их функциях: меры стоимости средства обращения.
35018. Кредитно-денежные системы. Банки 26.5 KB
  Депозиты представляют собой все виды денежных средств переданных в банк их владельцами на временное хранение с предоставлением права использовать эти деньги для кредитования. Депозит до востребования это текущий лицевой счет с которого вкладчик может снять деньги в любое время. Срочные Депозиты это счета с которых вкладчик обязуется не брать деньги до истечения определенного срока. В связи с этим и банк может вкладывать полученные им в распоряжение деньги тоже лишь на определенный срок поэтому кредиты всегда выдаются лишь на...
35020. Операции банка 25 KB
  Операции банка делятся на пассивные по привлечению свободных денежных средств в банк и активные по размещению ссуд и кредитованию клиентов. Процент за предоставленные кредиты бывает выше чем за привлеченные вклады что представляет одну из составляющих прибыли банка. Кроме того банк организует операции по учету векселей. Банк покупает вексель удерживая из обозначенной на нем суммы учетный процент что также составляет прибыль банка на этой операции.
35021. Мультипликатор Депозитный 18.33 KB
  Денежные агрегаты Показателями структуры денежной массы являются денежные агрегаты. Денежными агрегатами называются виды денег и денежных средств отличающиеся друг от друга степенью ликвидности возможностью быстрого превращения в наличные деньги. В разных странах выделяются денежные агрегаты разного состава. Денежные агрегаты представляют собой иерархическую систему каждый последующий агрегат включает в свой состав предыдущий.