• Гідрологія і Гідрометрія
• Господарське право
• Економіка будівництва
• Економіка природокористування
• Економічна теорія
• Земельне право
• Історія України
• Кримінально виконавче право
• Медична радіологія
• Методи аналізу
• Міжнародне приватне право
• Міжнародний маркетинг
• Основи екології
• Предмет Політологія
• Соціальне страхування
• Технічні засоби організації дорожнього руху
• Товарознавство продовольчих товарів

Закони булевої алгебри

Самостійна робота №2,3

Булеві функції та їх основні властивості

Комп'ютерні обчислення природно розглядати як деякі інформаційні перетворення, на вхід яких подаються ланцюжки бітів, які перетворюються відповідно до тієї чи іншої формули. Однією з простих моделей комп'ютерних обчислень є комбінаційна схема, яка складається з більш простих обчислювальних елементів. Важливою рисою комбінаційних схем є те, що вони не мають внутрішньої пам'яті. Відповідно до цього, перетворення, яке реалізується комбінаційною схемою, розглядається як деяка логічна, або булева, функція, яка, в свою чергу, складається з більш простих булевих функцій.

Визначення.

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

Булеві функції тісно пов'язані з логікою. Дійсно, з точки зору класичної логіки висловлювання може бути істинним (наприклад, Київ - столиця України) або хибним (наприклад, Волга впадає у Чорне море). "Істина" позначається через 1, "хибність" - через 0. Тоді більш складні висловлювання можна описувати за допомогою апарату булевих функцій. Тому булеві функції мають іншу назву - логічні функції.

Булеву функцію можна задати двома основними способами:

1. через булеві вирази; булевий вираз визначає явну формулу, за якою можна обчислити функцію при даних значеннях змінних;

2. за допомогою таблиці істинності; таблиця істинності - це таблиця, яка ставить у відповідність кожній комбінації аргументів певне значення.

Якщо булева функція має n аргументів, то існує 2n їх комбінацій, і , відповідно, 2 в степені 2n функцій.

Для одного аргументу існують 4 булеві функції, практичне значення має одна з них - заперечення, або зв'язка НЕ. Заперечення x позначається як ¬x , а таблиця істинності цієї функції має вигляд

x ¬x

0 1

1 0

Існує 4 можливих комбінацій двох аргументів, і, відповідно, 16 різних булевих функцій з двома аргументами. Розглянемо найважливіші з них:

* кон'юнкція (зв'язка І, логічне множення); приймає значення 1 тоді і тільки тоді, коли обидва аргументи приймають значення 1. Кон'юнкція змінних x та y позначається як x ۸ y; знак ۸, як правило, опускається.

Таблиця істинності має вигляд:

x y x ۸ y

0 0 0

0 1 0

1 0 0

1 1 1

* диз'юнкція (зв'язка АБО, логічне додавання); приймає значення 1 тоді і тільки тоді, коли хоча б один з аргументів приймає значення 1. Диз'юнкція змінних x та y позначається як x ۷ y.

Таблиця істинності має вигляд:

x y x ۷ y

0 0 0

0 1 1

1 0 1

1 1 1

* тотожність або еквівалентність; позначається як x ≡ y:

x y x ≡ y

0 0 1

0 1 0

1 0 0

1 1 1

* заперечення тотожності, або додавання за модулем 2, або зв'язка XOR.

x y x XOR y

0 0 0

0 1 1

1 0 1

1 1 0

* імплікація, позначається як x → y.

x y x → y

0 0 1

0 1 1

1 0 0

1 1 1

* заперечення кон'юнкції, або штрих Шефера ( | );

* заперечення диз'юнкції, або стрілка Пірса (↑).

За домовленістю, кон'юнкція має більш високий приоритет, ніж диз'юнкція (так само, як звичайне множення має більш високий приоритет, ніж звичайне додавання).

Поняття кон'юнкції та диз'юнкції можна узагальнити на випадок довільної кількості аргументів.

Визначення.

Кон'юнкцією n булевих аргументів називається логічна функція, яка приймає значення 1, якщо всі її аргументи дорівнюють 1, і 0 - в будь-якому іншому випадку (тобто якщо хоча б один з аргументів дорівнює 0).

Визначення.

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

Важливе значення мають правила перетворень для булевих виразів.

* Основні з них мають такий вигляд:¬0 =1;

¬1 =0;

* закони поглинання:

x ۷ 0 =x;

x ۸ 1 =x;

x ۷ 1 =1;

x ۸ 0 =0;

* закон подвійного заперечення:

¬¬x =x;

* ідемпотентність:

x ۷ x =xx =x;

* закон виключеного третього:

¬x ۷ x =1;

¬x • x =0;

* комутативність:

x ۷ y =y ۷ x;

xy=yx;

* асоціативність:

(x ۷ y) ۷ z =x ۷ (y ۷ z);

(xy)z =x(yz);

* дистрибутивність:

x ۷ (yz) =(x ۷ y)(x ۷ z);

x(y ۷ z) =xy ۷ xz;

* правила де Моргана:

¬(x ۷ y) = ¬x • ¬y;

¬(xy) = ¬x ۷ ¬y

Два булевих вирази вважаються рівними, якщо їх таблиці істинності співпадають. Існує два основні способи перевірки рівності двох булевих виразів: за допомогою таблиць істинності і за допомогою тотожних перетворень. Очевидно, що таблиця істинності може бути побудована для будь-якого булевого виразу.

Функціонально повні системи булевих функцій

Визначення.

Система булевих функцій V називається функціонально повною, якщо для будь-якого булевого виразу знайдеться булевий вираз, який дорівнює даному, і містить лише функції з V. Іншими словами, система булевих функцій називається функціонально повною, якщо будь-яку булеву функцію можна виразити за допомогою функцій, які входять до складу цієї системи. Відомо досить багато функціонально повних систем булевих функцій. Фундаментальна теорема Поста, яка вивчається в курсі дискретної математики, встановлює необхідні і достатні умови функціональної повноти.

Найбільш відомою і вживаною функціонально повною системою є система, що складається з трьох функцій: кон'юнкції, диз'юнкції та заперечення. Особливе місце цього набору пов'язано з тим, що існує простий стандартний алгоритм вираження будь-якої булевої функції за допомогою цих трьох функцій; алгоритм полягає у побудові на основі таблиці істинності досконалої диз'юнктивної нормальної форми.

Можна навести інші приклади функціонально повних систем, такі як:

* кон'юнкція та заперечення;

* диз'юнкція та заперечення;

* тотожний нуль, тотожна одиниця, кон'юнкція, додавання за модулем 2;

* імплікація та тотожний нуль.

Існують функціонально повні набори, кожний з яких містить єдину функцію. Такими функціями є штрих Шефера та стрілка Пірса.

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

Cистема булевих функцій, яка містить кон'юнкцію, диз'юнкцію та заперечення, є функціонально повною, і існує загальновживаний (хоч і не завжди оптимальний з точки зору часу виконання) алгоритм представлення будь-якого булевого виразу через ці функції. Алгоритм складається з двох частин:

* побудова таблиці істинності для заданого виразу;

* побудова за таблицею істинності досконалої диз'юнктивної нормальної форми.

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

Визначення.

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

Булевий вираз записаний у диз'юнктивній нормальній формі, якщо він являє собою диз'юнкцію елементарних кон'юнкцій.

Диз'юнктивна нормальна форма від n змінних називається досконалою, якщо кожна елементарна кон'юнкція містить всі змінні, можливо з запереченням.

Зазначимо, що крім диз'юнктивних нормальних форм, широко застосовуються нормальні форми іншого типу - кон'юнктивні.

Нарешті розглянемо метод побудови ДДНФ за таблицею істинності.

Оскільки ДДНФ, що будується, є булевим виразом, який відповідає заданій таблиці істинності, він повинен приймати значення 1 при тих і тільки тих наборах значень аргументів, при яких у таблиці істинності стоїть 1.

Нехай заданий деякий набір значень: змінні x1, …, xn приймають значення відповідно s1, …, sn. Елементарна кон'юнкція, яка залежить від змінних x1, …, xn, при даних значеннях аргументів може дорівнювати 1 в одному і тільки одному випадку: якщо аргументи, що дорівнюють 0, входять до неї під знаком заперечення, а ті, що дорівнюють 1 - без знака заперечення. Іншими словами, єдина елементарна кон'юнкція, яка при x1= s1, … , xn= sn дорівнює 1, має вигляд y1…yn, де yi= ¬xi при si= 1 і yi= xi при si= 0. Далі, оскільки таблиця істинності дорівнює 1 при декількох наборах значень аргументів, вона повинна являти собою диз'юнкцію усіх відповідних елементарних кон'юнкцій.

Приклад. Побудуємо ДДНФ за такою таблицею істинності:

x y z f(x, y, z)

0 0 0 0

0 0 1 0

0 1 0 1

0 1 1 1

1 0 0 1

1 0 1 0

1 1 0 0

1 1 1 1

До ДДНФ повинно увійти чотири елементарні кон'юнкції, які відповідають наборам, при яких функція приймає значення 1 (вони обведені рамками). Відповідно до цього ДДНФ матиме вигляд

¬xy¬z۷¬xyz۷x¬y¬z۷xyz

Читайте також:

1. IV. Закони ідеальних газів.
2. Аграрні закони України
3. Алгоритм знаходження ДДНФ (ДКНФ) для даної булевої функції
4. База управлінських рішень і закони організації.
5. Булеві теореми та закони
6. Види, типи і форми професійного спілкування. Основні закони спілкування. Стратегії спілкування.
7. Визначення добутку на множині цілих невід’ємних чисел, його існування та єдиність. Операція множення та її основні властивості (закони).
8. Визначення суми на множині цілих невід’ємних чисел, її існування та єдиність. Операція додавання та її основні властивості (закони).
9. Газові закони
10. Газові закони. Суміш газів.
11. Гіпотези, які не відхиляються в експерименті, перетворюються на компоненти теоретичного знання про реальність: факти, закономір­ності, закони.
12. Грошовий обіг і його закони

Переглядів: 2814