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


 

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

18085. Программирование ввода-вывода в Java 276.5 KB
  Лабораторная работа 8 Программирование вводавывода в Java 1. Цель работы Целью работы является приобретение навыков использования потоков вводавывода в программах на языке Java. 2. Состав рабочего места 2.1. Оборудование: IBMсовместимый персональный компьютер...
18086. Использование потоков в Java 104.5 KB
  Лабораторная работа 903 Использование потоков в Java 1. Цель работы Целью работы является приобретение навыков работы с потоками при программировании на языке Java. 2. Состав рабочего места 2.1. Оборудование: IBMсовместимый персональный компьютер ПК. 2.2. Про
18087. Цивільний захист, конспект лекцій 699 KB
  Навчальна дисципліна «Цивільний захист» є нормативною дисципліною, що включається в навчальні плани як самостійна дисципліна обов’язкового вибору. Вона зберігає свою самостійність за будь - якої організаційної структури вищого навчального закладу.
18088. Технология программирования на языке Java. Работа с массивами в Java 561.5 KB
  Лабораторная работа 4 Технология программирования на языке Java. Работа с массивами в Java 1. Цель работы Целью работы является приобретение навыков программирования с использованием операторов управления и массивов в языке программирования Java. 2. Состав рабоч
18089. ОСНОВИ ЗАКОНОДАВСТВА УКРАЇНИ ПРО ОХОРОНУ ПРАЦІ 79.5 KB
  ОСНОВИ ЗАКОНОДАВСТВА УКРАЇНИ ПРО ОХОРОНУ ПРАЦІ Тема 1.1. ЗМІСТ ЦІЛІ І ЗАДАЧІ ОХОРОНИ ПРАЦІ Навчальні питання лекції Місце і роль охорони праці в трудовій діяльності нашого суспільства. Законодавчі та нормативноправові акти з охорони праці. Основні п
18090. ПРАВОВЕ РЕГУЛЮВАННЯ ОХОРОНИ ПРАЦІ 70 KB
  Тема 1.2. ПРАВОВЕ РЕГУЛЮВАННЯ ОХОРОНИ ПРАЦІ Практичне заняття 2 години. Навчальні питання занять: Гарантії прав громадян з охорони праці. Нормування праці і відпочинку. Трудова дисципліна. Література: Законодавство України про охорону праці // Зб...
18091. ОХОРОНА ПРАЦІ ЖІНОК, НЕПОВНОЛІТНІХ, ТА ІНВАЛІДІВ 72.5 KB
  Тема 1.3 ОХОРОНА ПРАЦІ ЖІНОК НЕПОВНОЛІТНІХ ТА ІНВАЛІДІВ Лекція 2 години Навчальні питання лекції: Охорона праці жінок. Охорона праці неповнолітніх. Охорона праці інвалідів.. Література: Законодавство України про охорону праці // Збірни
18092. МЕДИЧНЕ ЗАБЕЗПЕЧЕННЯ ОХОРОНИ ПРАЦІ 56 KB
  Тема 1.4 МЕДИЧНЕ ЗАБЕЗПЕЧЕННЯ ОХОРОНИ ПРАЦІ Практичне заняття 2 години Навчальні питання занять: Види медичного забезпечення охорони праці. Порядок організації і проведення медичних оглядів. Права та обовязки підприємств і працівників щодо медичног...
18093. СОЦІАЛЬНИЙ ЗАХИСТ ПРАЦІВНИКІВ 119 KB
  Тема 1.5. СОЦІАЛЬНИЙ ЗАХИСТ ПРАЦІВНИКІВ Лекція 2 години. Навчальні питання лекції: Державне соціальне страхування. Соціальний захист громадян на ринку праці. Регулювання трудових відносин Література: Законодавство України про охорону праці //...