Головна

Замикання. Властивості операції замикання.

  1. XI. Пристосування ТА ІНШІ ЕЛЕМЕНТИ, властивості. Здібностей та обдарувань АРТИСТА
  2. Активні операції комерційних банків
  3. Алгоритм операції зведення числа в ступінь по модулю.
  4. Алюміній, його властивості та застосування в техніці
  5. Амфотерними називаються такі гідроксиди, які в залежності від умов виявляють властивості яких підстав, або кислот.
  6. Арифметичні вирази і операції
  7. Армуючі матеріали і їх властивості

замкнені класи

З поняттям повноти тісно пов'язане поняття замикання і замкнутого класу.

визначення. нехай  - Деяка підмножина функцій з . замиканням  називається безліч всіх булевих функцій, які представлені у виді формул через функції безлічі  . замикання безлічі  позначається через .

Відзначимо деякі властивості замикання:

1) ;

2) ;

3) якщо  , то ;

4) якщо ми розглянемо и , и  , то .

визначення. Клас (безліч)  називається замкнутим, якщо .

приклад:

1 клас  є замкнутим класом.

2)  - Незамкнений клас, так як  , а

3)  - Незамкнений клас, так як підстановкою інших змінних ми можемо отримати з функції  функцію  , а .

Зауваження. У термінах замикання і замкнутого класу можна дати інше визначення повноти: -повна система, якщо .

3.13. класи  і їх властивості

визначення.  - Клас всіх булевих функцій , Що зберігають константу 0, тобто функцій, для яких виконано .

1)  , але .

2) .

затвердження 2. - замкнутийклас.

Доведення: Так як  , Розглянемо суперпозицію

,

де  . тоді

.

Це означає, що будь-яка суперпозиція функцій з класу зберігає константу 0, тобто клас замкнутий.

визначення.  - Клас всіх булевих функцій , Що зберігають константу 1, тобто функцій, для яких виконано .

1)  , але .

2) .

затвердження 3. - замкнутийклас.

Доведення: Так як  , То досить показати, що функція , якщо . дійсно, .



Попередня   21   22   23   24   25   26   27   28   29   30   31   32   33   34   35   36   Наступна

булеві функції | формули | Властивості елементарних функцій | Розкладання булевих функцій | Досконала д. Н. ф., досконала к. н. ф. | повні системи | Приклади повних систем | поліном жегалкіна | Единственность уявлення булевих функцій поліномами Жегалкина | Методи побудови поліномів |

© um.co.ua - учбові матеріали та реферати