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


 

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

77752. ОБЩЕНАУЧНЫЕ МЕТОДЫ В ИССЛЕДОВАНИИ СИСТЕМ УПРАВЛЕНИЯ 81.5 KB
  Но успех исследования в значительной мере зависит от того каким образом по каким критериям мы выбираем методы для проведения конкретного исследования и в какой комбинации мы используем эти методы. Всю совокупность методов исследования можно разделить на две группы: Эмпирические методы построены на осмыслении практической деятельности сути и особенностей событий и ситуаций. Методы наблюдений исследования с минимальным вмешательством в исследуемые события и ситуации.
77753. СИСТЕМНЫЙ ПОДХОД В ИСУ 36.5 KB
  Система управления совокупность звеньев и связей между ними осуществляющих управление. Звенья системы управления выделяются: по специфике объему и масштабу полномочий трудоемкости работы равномерности распределения нагрузки квалификационным требованиям к персоналу информационному обеспечению возможностям территориального размещения сотрудников. Звенья составляющие систему управления отличаются главным образом комбинацией функций и полномочий управления. Звенья системы управления...
77754. СПЕЦИФИЧЕСКИЕ МЕТОДЫ ИСУ 56.5 KB
  Наиболее важными из них являются методы: исследования документов эксперимент социологические исследования тестирование коллективный анализ социометрические оценки деловые и инновационные игры имитационное моделирование. Одним из критериев выбора методов исследования является степень определенности ситуации или проблемы. Эффективность исследования по документам зависит от: состава документов их содержания формы информационной классификации.
77755. ДИВЕРСИФИЦИРОВАННЫЕ МЕТОДЫ ИСУ 82 KB
  Наблюдаются ли процессы диверсификации в области исследования? В чем они проявляются? Почему возникает потребность в диверсифицированных методах исследования? Что собой представляют диверсифицированные методы исследования? Что дают диверсифицированные методы, в чем их сильные и слабые стороны?
77756. МЕТОД СИНЕКТИКИ В ИСУ 79.5 KB
  Как мобилизовать и мотивировать творческий потенциал исследователя? Какую роль формирование группы играет в мобилизации творчества исследователя? Как социально-психологические факторы совместной деятельности исследователей влияют на результат?
77757. МЕТОДЫ ПРОЕКТИРОВАНИЯ КОНЦЕПЦИЙ 46 KB
  Методы дивергенции Дивергенция это прием расширения границ предмета исследования которое необходимо для обеспечения достаточного пространства поиска эффективного решения. К методам дивергенции можно отнести методы: обобщения литературы визуализации проблемы обсуждения анализа формулировок накопления и систематизации информации инвентаризации точек зрения и подходов анкетирования анализа ограничений. Методы трансформации Это следующий этап исследования.
77758. МЕТОД МЭТЧЕТА В ИСУ 37 KB
  Это приемы изменения как бы режимов мышления для его сознательного приспособления к целям исследования. Режимы исследования Первый режим мышления мышление по основным элементам. Течтемы средства осознания исследователем разнообразия действий которые он может предпринять на каждом из этапов исследования. потребность в исследовании; ключевая категория исследования; предварительная гипотеза; подход парадигма исследования; переключение.
77759. Учет запасов. Особенности учета давальческих материалов в строительстве 29.81 KB
  Влияние специфики строительства на учет материалов. Особенности учета давальческих материалов в строительстве. На начальном этапе деятельности любой строительной организации после всех организационных вопросов заготавливаются запасы сырья и материалов необходимые для изготовления продукции. Характерной чертой строительства является использование значительного количества строительных материалов конструкций и деталей как по их номенклатуре так и в физическом выражении.
77760. Учет расходов на оплату труда в строительстве 30.54 KB
  Учет расходов на оплату труда в строительстве. Влияние особенностей строительства на учет оплаты труда. Планирование расходов на оплату труда в строительстве. Виды и формы оплаты труда в строительстве.