Головна

передповний клас функцій алгебри логіки

  1. А »,« Б »класи 2013-2014 навчальний рік
  2. Допустиме перевищення температури двигуна. класи ізоляції
  3. Категорії і класи кабельної системи
  4. Класи IP-адрес
  5. Класи адрес обчислювальних мереж
  6. Класи безпеки комп'ютерних систем
  7. Класи дієслів I головного відмінювання.

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

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

З визначення випливає, що предполний клас замкнутий.

слідство 9. В  існують тільки 5 предполних класів, а саме .

Доведення: Візьмемо довільний клас  . За слідству 8  міститься в одному з п'яти класів. нехай .

а)  , тоді  , де  , тобто  - Предполний за визначенням.

б)  , це означає що  , але  не є предполним в  , Значить пункт б) відкидається з розгляду.

3.22. Можливість виділити з будь-якої повної системи повну підсистему,
 що складається з не більше ніж 4-х функцій

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

Доведення: Згідно з теоремою 7 з системи функцій  можна виділити повну підсистему  , Що містить не більше 5 функцій, тобто , .

виявляється  , Або не самодвоїстих (випадок а пункту 1 в доведенні теореми 7), так як  , Або не зберігає одиницю і не є монотонною (випадок б пункту 1 в доведенні теореми 7):  . Тому повної буде або система  , Або система .

Теорема доведена.

 



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

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

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