На головну

 Таблиці істинності функцій |  карти Карно |  Мінімізація булевої функції картами Карно |  Мінімізація методом Квайна-МакКласкі |  Перевірка тупикової ДНФ методом Петрика |  Схемних реалізація мінімізованої функції |

Базис булевих функцій. теорема Поста

  1.  Create table Постачання
  2.  Cуществованіе і єдиність подання (теорема Жегалкина)
  3.  I На шляху побудови єдиної теорії поля 6.1. Теорема Нетер і закони збереження
  4.  I. Поняття про постановку наголоси в російській мові (загальновживані слова).
  5.  I. Постановка питання
  6.  I. Постановка зігріваючого компресу
  7.  II. Які загальні фактори впливають на постановку мети виховання?

Перевіримо елементарні булеві функції, що входять до складу заданої, на освіту базису.

   Зберегти 0,  Зберегти 1,  Самодвоїстих, S  Монотонність, M  Лінійність, L
    +   +
+ +   +  
+       +

У таблиці знаком «+» позначено приналежність функції до даного класу.

Для того щоб функції становили базис, по теоремі Посту необхідно, щоб хоча б одна опція зберігала 0, хоча б одна опція зберігала 1, хоча б одна функція була самодвоїстих, хоча б одна функція була монотонної і хоча б одна опція була лінійною. З вищенаведеної таблиці видно, що даний набір функцій становить базис. Причому для базису досить перших двох функцій, тобто заперечення і диз'юнкції.

Перевіримо можливість отримання з заданої булевої функції f шляхом суперпозиції якоїсь булевої функції  . Для цього перевіримо f на приналежність класів Посту.

По таблиці істинності  , отже .

 , отже .

Побудуємо по таблиці істинності двоїсту функцію  , Значення якої можна отримати з значень функції f за допомогою инвертирования (тобто переписування в зворотному порядку) і поелементного заперечення.

f

Виходячи з таблиці істинності  , отже .

Розглянемо два набори и  . Згідно лексикографічного порядку  , але  . Тому .

Ступінь полінома Жегалкина для заданої функції f дорівнює 3, тому .

Задана функція f належить до функціонально повного в слабкому значенні класу, так як вона немонотонна і нелінійна. Тому додавання констант 0 і 1 в клас  дозволить отримати з f шляхом суперпозиції будь-яку булеву функцію .



 Нормальні форми і поліноми |  Схемних реалізація функцій методом каскадів
© um.co.ua - учбові матеріали та реферати