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


 

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

54985. Видоизменение побегов 657 KB
  Методы и приемы: словесный (рассказ с элементами беседы), практический, логический (проведение сравнений корневища, клубня, луковицы); установление общих признаков, организационный – выполнение лабораторной работы.
54986. З початкової школи в основну: проблеми наступності 104 KB
  Перехідний період з початкової школи в основну позначається на всіх учасниках освітнього процесу: учнів педагогів батьків адміністрації школи фахівців психологопедагогічної служби. Скоротити перехідний період пом'якшити пов'язані з ним фактори негативного характеру допомагає педагогічному колективу спеціально розроблена програма Спадкоємність яка створена з метою координації більш ефективної організації навчальновиховного процесу і психологопедагогічного супроводу учнів випускників початкової школи при переході їх в середню...
54987. МУЗИКА ЯК МОВА ПОЧУТТІВ 138 KB
  Мета (для вчителя): збагатити художньо – естетичний досвід школярів, розвивати асоціативне мислення, формувати художньо – естетичні ціннісні орієнтири; стимулювати творче мислення учнів; вчити розрізняти елементи музичної мови, збагатити знання про музику як мову почуттів, поглибити знання про засоби музично виразності в музиці, в живописі, в літературі;...
54988. ПРЯМІ І НЕПРЯМІ ПОДАТКИ 73 KB
  Мета заняття: продовжити знайомство з податками, вивчити види податків: прямі та непрямі; розвинути інтерес до предмету і процесу навчання в цілому. Мета заняття: Освітня - розглянути сутність та види податків.
54989. ПОДАТКОВА СИСТЕМА 50 KB
  Мета заняття: Навчальна: поглибити уявлення про роль податкових методів залучення коштів до Державного бюджету України; сформувати та поглибити знання про сутність функцій, які виконують податки; навчити здійснювати аналіз податків за класифікаційними ознаками;
54990. Подготовка граждан Российской Федерации к военной службе 26.5 KB
  Обязательная подготовка к военной службе осуществляется при проведении военных сборов в ходе которых гражданин получает необходимые знания в области обороны. Что предусматривает добровольная подготовка гражданина к военной службе Добровольная подготовка гражданина к военной службе может включать в себя: занятия военноприкладными видами спорта; овладение военноучетными специальностями; военную подготовку в образовательных учреждениях среднего полного общего образования и в образовательных учреждениях начального и среднего...
54991. Подготовка конспекта урока как форма квалификационного испытания 216 KB
  При проведении предлагается инструкция содержащая цель работы тему урока по которой должен быть составлен конспект критерии оценки. Время предоставляемое на написание конспекта урока составляет 3 часа. Конспект урока должен быть связан с освоением новой темы нового учебного материала.
54992. Потребление и сбережение. Факторы, определяющие уровень и динамику потребления, и сбережения 18.45 KB
  Изменение величины потребления вследствие изменений в доходе называется предельной склонностью к потреблению, т. е. это отношение любого изменения в потреблении к тому изменению в величине дохода, которое привело к изменениям потребления.
54993. Подготовка учителя к уроку истории. Тематическое и поурочное планирование. Определение целей урока 68.5 KB
  Годовой план – расположение учебного материала по четвертям. Чтобы составить годовой план, учитель должен изучить учебную программу, учесть число недель в каждой четверти и число учеников в каждом классе. При составлении годового плана учитель должен предусмотреть определенный резерв времени