Ставлення конгруентності дозволяє визначити так звану фактор-структуру, носієм якої

в) лише рефлексивність.

3.Елемент

називається мінімальним, якщо звипливає, що

а) ін'єкцією; б) сюр'єкцією; в) бієкцією.

Розділ III. Булеві функції.

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

Булевою або логічною функцією відnзмінних називається функція

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

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

(неx) і тотожні0та1.

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

Перелічимо найважливіші їх;

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

диз'юнкція (логічне ,,АБО”)

;

імплікація (слідування)

,

еквівалентність

.

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

x1 x2

x1

x2

Зауважимо, що

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

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

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

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

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

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

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

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

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

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

слід.

Калькулятор

Сервіс безкоштовної оцінки вартості роботи

1. Заповніть заявку. Фахівці розрахують вартість вашої роботи
2. Розрахунок вартості прийде на пошту та по СМС

Номер вашої заявки

Зараз на пошту прийде автоматичний лист-підтвердження з інформацією про заявку.

---