Головна

Лемма про немонотонної функції

  1. II. функції
  2. II. ФУНКЦІЇ
  3. II. ФУНКЦІЇ
  4. II. функції ІТС
  5. II. ФУНКЦІЇ ЦУП
  6. Адвокат і його функції
  7. активаційні функції

Лемма 4. якщо , То з неї шляхом підстановки констант 0 і 1 і функції  можна отримати функцію .

Доведення: нехай , Тоді знайдуться 2 набору , такі, що при .

Так як  , то .

нехай набори и  розрізняються в перших  розрядах, де  , тобто

Розглянемо функцію .

 так як при .

,  це означає, .

Лема доведена.

3.20. Теорема про повноту в Р2

Теорема 7. система функцій з  сповнена  вона цілком не міститься ні в одному з п'яти замкнутих класів .

Доведення: необхідність  . нехай  повна, тобто  . Припустимо, що  , де  один з 5 перерахованих класів. Тоді в силу властивостей замикання і замкнутості  маємо  , Протиріччя.

достатність  . нехай  не міститься цілком ні в одному з п'яти зазначених класів, значить в  функції  . Отже, з системи  виділимо підсистему  , Яка також цілком не міститься ні в одному з п'яти зазначених класів. Будемо вважати, що всі ці функції залежать від одних і тих же змінних .

I. Побудова констант 0 і 1 за допомогою функцій .

Розглянемо  . Можливі два випадки:

а) .

нехай .

візьмемо ;  - Друга константа.

б) .

нехай .

Розглянемо  . Так як ми маємо  , То по лемі 3 ми можемо отримати константу  . використовуючи константу и  можемо отримати іншу константу .

II. побудова функції  за допомогою констант 0 і 1 і  . Це випливає з леми 4.

III. побудова  за допомогою констант  . Це здійснюється на основі лем 1 і 2.

Таким чином, за допомогою формул над  (А значить і над  ) Реалізували функції . .

Теорема доведена повністю.

З доведення теореми 7 слід

слідство 8. Всякий замкнутийклас  функцій з  такий, що  , Міститься принаймні в одному з класів .



Попередня   27   28   29   30   31   32   33   34   35   36   37   38   39   40   41   42   Наступна

Приклади повних систем | поліном жегалкіна | Единственность уявлення булевих функцій поліномами Жегалкина | Методи побудови поліномів | II. Метод невизначених коефіцієнтів. | Замикання. Властивості операції замикання. | Лінійні функції і їх властивості | принцип подвійності | Самодвоїстих функції, їх властивості | Лемма про несамодвойственной функції |

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