Головна

 Www.msta.ru |  Визначення та позначення. |  Операції над множинами. |  Потужність безлічі. |  Пряме твір множин. |  Тест 1. |  Бінарні відносини. |  Функції. |  Алгебраїчні структури і морфізм. |  Спрощення д. Н. ф. |

Визначення та основні властивості.

  1.  B.1.1 Основні положення
  2.  E. підрахунку суми балів, визначення індексу ПМА за формулою.
  3.  ER-модель бази даних. Основні нотації зображення ER-моделі.
  4.  I Основні категорії педагогіки
  5.  I Розрахунок витрат для визначення повної собівартості вироби (роботи, послуги), визначення рентабельності його виробництва
  6.  I. Яке визначення найбільш повно виражає сутність програмованого навчання?
  7.  I. Основні положення

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

Булеві функції від однієї змінної f (x) чотири:  (Не x) І тотожні 0 и 1 .

Булевих функцій від 2 змінних 16 .

Перерахуємо найважливіші з них;

- Кон'юнкція (логічне ,, і "), що позначається  або просто ;

- Диз'юнкція (логічне ,, або ") ;

- Імплікація (проходження) ,

- еквівалентність ~ .

Наведемо таблицю, що задає 4 зазначених функції (таблицю істинності):

x1 x2 x1x2 x1 x2 x1®x2 x1~ x2
 0 0
 0 1
 1 0
 1 + 1

Зауважимо, що и  , Тобто виконані закони де Моргана. Взагалі, булевої функції від змінних можна поставити у відповідність підмножина тих довічних наборів, на яких вона дорівнює 1. Тим самим встановлюється ізоморфізм між безліччю підмножин 2n - Елементного безлічі з операціями об'єднання, перетину і доповнення і безліччю булевих функцій від n змінних з операціями диз'юнкції, кон'юнкції і заперечення. Тому безліч булевих функцій від n змінних з трьома перерахованими операціями є булевої алгеброю з усіма наслідками, що випливають звідси властивостями.

Зауважимо, що імплікація і еквівалентність можуть бути виражені через диз'юнкцію кон'юнкцію і заперечення

що безпосередньо може бути перевірено за допомогою таблиці істинності.

Крім того, еквівалентність може бути виражена через імплікації наступним чином

що цілком відповідає звичним уявленням про те, що х1 еквівалентно х2, Якщо х1 тягне х2 і х2 тягне х1.

булева функція  називається двоїстої до функції f (x, ..., xn), F * * = f. якщо f * = f , то f називається самодвоїстих. Диз'юнкція і кон'юнкція двоїсті одна одній.

На безлічі двійкових наборів довжини n відношення порядку

 вводиться наступним чином:

Якщо вважати набори характеристичними векторами підмножин n-елементного безлічі, то це відношення на множині наборів відповідає впорядкованості підмножин по включенню.

Булева функція f називається монотонної, якщо з  слід .

 



 тест II |  Диз'юнктивна і Кон'юнктивна нормальні форми
© um.co.ua - учбові матеріали та реферати