Тотожна істинність формул дедуктивних умовиводів

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

Функціяназивається функцією

алгебри логіки, або булевою функцією.

Таблиця істиності (6) булевої функції від п змінних має вид:

Таблиця 6

Якщо число змінних п, то таблиця має 2^π рядків. Це відповідає усім комбінаціям змінних, які можна визначити. В кожному рядку спочатку задається набір значень змінних, а потім значення функції на цьому наборі.

Суттєві і несуттєві змінні

Таблиця 7

Для цих функцій Xi - суттєва змінна, а X₂ - несуттєва змінна. Булеві функції рівні, якщо утворюються видаленням або додаванням несуттєвих змінних. Усюди надалі булеві функції будемо розглядати з точністю до несуттєвих змінних. Це дає змогу вважати, що всі булеві функції (у даній системі функцій) залежать від однакових змінних.

Операції алгебри логіки Буля

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

Нехай дана сукупність предметів, які після перерахування можна позначити як: U = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11}. Припустимо, що перша частина предметів, як-от: 1, 2, 4, і 6, мають круглу форму. Друга частина - 2, 3, 4, 8, і 9 пофарбована в білий колір. У цьому випадку множина U має дві підмножини: A= П, 2, 4, 61. В 12, 3, 4, 8, 9}.

Вихідну множина називають фундаментальною, а підмножини А і В - просто множинами.

У результаті якісного аналізу фундаментальної множини одержимо чотири класи елементів:

Рис. 12

Графічне відображення (рис.2) операції вмикання в булевій алгебрі: Рисунок 2 показує, що множина А цілком включена в множину В.

Якщо одночасно виконуються дві умови:

У такому випадку множини А і В цілком еквівалентні.

Після визначення елементів, множин починаємо операції над ними. Графічне відображення (рис. 3) операції об’єднання в булевій алгебрі:

РисЛЗ

A={l,2,4,6} B={2,3,4,8,9}

НехайОб’єднанням охоплюються три

класи елементів _ - --

Тому, що х належить А або В, використовуємо таку форму запису:

— ___ _ — — —у _ — J_j

З погляду алгебри логіки, замість однієї змінної х зручно ввести дві логічних змінних Xi, і X₂.

Приклад

Нехай х = 7. Оскільки це число не належить ні множині А, ні множині В, то логічні значення змінних будуть. Комбінація

змінних відповідає класу Cq.

Припустимо, що вибрано число4. Воно входить як в А так і у В.

При цих значеннях функція (як показано в таблиці 8) дорівнює:

Таблиця 8

Число одиниць і нулів для функції U визначає загальне число можливих операцій на двох множинах.

Графічне відображення (рис.4) операції перетинання в булевій алгебрі:

Рис. 14

Таблиця 9

На діаграмі Ейлера-Венна (рис.6) порожня множина має вигляд:

РисЛб

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

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

Шляхом об’єднання відповідних областей C₁ можна уявити будь- яку множинну операцію, у тому числі і саме об’єднання:

Всё це поширюється і на алгебру логіки:

172

Операції стрілка Пірса і штрих Шеффера в символічній логіці

Операція стрілка Пірса визначає об’єднання двох і більш доповнених (узятих із запереченням) областей до фундаментальної множини.

Рис. 17

Мовою алгебри логіки формули операції стрілки Пірса мають вигляд:

Логічна операція штрих Шеффера (рис. 8) визначає перетинання доповнених областей до фундаментальної множини. Діаграма Ейлера- Bенна має вигляд:

Рис. 18

Таблиця істинності (10) для логічної операції стрілка Пірса має вигляд:

Таблиця 10

З таблиці видно, що:

Таблиця 11

З таблиці видно, що:

Різницею між множинами А і В називається сукупність тих елементів множини А, що не ввійшли в В:

A-B= {1,2, 4,6} - {2,3,4, 8,9} = {1,6} = Cl.

РисЛ9

Діаграма Ейлера-Венна (рис.9) для різниці множин має такий вид: Таблиця істинності (12) для різниці множин:

Таблиця 12

Рис. 20

На діаграмі видно, що при вмикання множини А в множину В. Таблиця істинності (13) має вигляд:

імплікації відбувається часткове

Таблиця 13

Рис.21

Симетрична різниця має декілька назв:

• строга диз’юнкція, що виключає альтернативу;

• сума по модулі два.

Симетричну різницю можна визначити словами: «або А, або В», тобто це логічна низка «або», але без вмикання в неї низки «і».

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

Визначається тими елементами множин AiB, що є для них загальними. Але елементи не вхідні ні в множину А, ні в множину В, також рахуються еквівалентними.

Діаграма Ейлера-Венна (рис. 12) для еквівалентності має вид:

Рис.22

Таблиця 14

2.5.2.