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


 

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

33932. Агрегатные индексы 18.04 KB
  Агрегатные индексы Агрегатный индекс общий индекс полученный путем сопоставления итогов выражающих величину сложного явления в отчетном и базисном периодах при помощи соизмерителей. Веса среднего арифметического и среднего гармонического индексов должны определяться исходя из соблюдения условия этого тождества. При исчислении среднего арифметического индекса объема продукции должно выполняться следующее условие: iFf=q1p0q0p0 В векторной символике средний арифметический индекс объема будет иметь вид: Jq=ip0q0p0q0=HqP0Q0 где Нq вектор...
33933. Индексы Пааше, Ласпейреса, Фишера. Их практическое применение 36.76 KB
  Этот индекс был построен по среднеарифметической формуле без применения какойлибо системы взвешивания. В XIX веке при построении индексов цен в основном по агрегатной или соответствующей ей среднеарифметической формуле статистики начинают использовать систему взвешивания. Более широкое практическое применение находят две другие их формы: в формуле Ласпейреса средняя арифметическая форма в формуле Пааше средняя гармоническая которые отражены в табл. Она устанавливает изменение цен при предположении что количества товаров неизменны...
33934. Средние индексы 11.06 KB
  Средние экономические показатели статистические показатели определяемые как средние за несколько лет по ряду экономических объектов или по всей совокупности производителей и потребителей. Следует иметь в виду что средние объемы производства доходы и расходы населения средняя заработная плата определяются как средневзвешенные по всем производственным объектам лицам и семьям работникам потребителям.
33935. Понятие статистической связи, ее виды и формы 14.3 KB
  При функциональной связи определенному значению факторного признака соответствует определенное же значение результативного признака. При статистической связи каждому значению факторного признака Х соответствует множество значений результативного признака Y причем не известно заранее какое именно. Корреляционной является статистическая связь между признаками при которой изменение значений независимой переменной Х приводит к закономерному изменению математического ожидания случайной величины Y....
33936. Методы выявления корреляционной связи. Корреляционно-регрессионный анализ 12.84 KB
  Основные статистические методы выявления наличия корреляционной связи: Сопоставление параллельных рядов метод когда ряд значений факторного признака х построенный в порядке возрастания сопоставляют с рядом соответствующих значений результативного признака у и таким образом прослеживают их взаимосвязь. Графический метод позволяет выявить наличие связи между двумя признаками с помощью поля корреляции. Установив наличие связи между признаками переходят к корреляционнорегрессионному анализу.
33937. Парная регрессия на основе метода наименьших квадратов 19.28 KB
  Для определения параметров уравнения парной регрессии используем метод наименьших квадратов. При применении этого метода для нахождения функции которая бы наилучшим образом соответствовала эмпирическим данным считается что сумма квадратов отклонений эмпирических точек от теоретической линии регрессии должна быть величиной минимальной. Критерий метода наименьших квадратов: ...
33938. Собственно корреляционные параметрические методы изучения связи 15.5 KB
  соответствия эмпирическим данным рассчитывают теоретическое корреляционное отношение η теоретический коэффициент детерминации η индекс корреляции R а для линейной формы линейный коэффициент корреляции r и линейный коэффициент детерминации r. Линейный коэффициент корреляции К.Пирсона помимо силы связи показывает и ее направление; определяется по следующей формуле: 34 Линейный коэффициент корреляции принимает...
33939. Оценка значимости корреляционной связи 13.59 KB
  Факторная дисперсия определяется по формуле: 43 где k 1 число степеней свободы для Остаточную дисперсию используя правило сложения дисперсий можно определить по формуле: 44 где n k число степеней свобод для . Число степеней свободы для общей суммы квадратов отклонений будет равно: k 1 n k = n 1....
33940. Измерение связей неколичественных переменных 13.78 KB
  Например при обследовании группы населения одного из регионов России в отчетном периоде задаются вопросы: 1й вопрос о месте проживания следует выбрать правильный ответ: 1. 2й вопрос о принадлежности к полу следует выбрать правильный ответ: 1. Представив суммарную численность ответов на каждый вопрос буквенными символами покажем как можно построить четырехклеточную таблицу которая поможет нам в дальнейших расчетах. Взаимосвязь между ответами на два вопроса социологического обследования.