АлгебрИчні структури

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

Частина 1. ОСНОВНІ АлгебрИчні структури

1.1. Поняття алгебри

Визначення 1.1. Алгеброю (ще кажуть: універсальною алгеброю) називають непорожню множину елементів разом з операціями, визначеними і замкненими на цій множині.

Дану непорожню множину називають носієм (або основною множиною) алгебри. Якщо носієм алгебри є множина А, а її операціями є операції , то алгебру позначають так: .

Операція є замкненою (або ще кажуть: внутрішньою) на заданій множині, якщо результат її застосування до будь-яких елементів цієї множини належить цій са́мій множині.

Алгебри можна визначати на множинах N натуральних чисел, Z цілих чисел, на множині R дійсних чисел (яка не є дискретною), множині комплексних чисел К, а також на довільних множинах і відношеннях.

Приклад 1.1. Множина з операцією звичайного додавання (+) не є алгеброю, оскільки операція додавання не замкнена на цій множині: наприклад, . Але множина з операцією додавання за модулем 5 ( ; при цьому операція додавання за модулем m визначається так: , де , , , ) утворює алгебру , оскільки дана операція замкнена на множині : наприклад, , , .

1.2. Унарні й бінарні операції

Визначення 1.2. Операцією на множині L називають функцію f, тобто відображення виду , де . Така операція однозначна. Вона також замкнута, тобто її область визначення і область значень належать множині L.

Операцію виду називають унарною, а операцію виду — бінарною. Символи операцій називають операторами.

Приклад 1.2. Прикладами унарних операцій є:

а) зміна знака на множинах Z і R: −5; −3,1415; −18,3; ;

б) операція піднесення до степеня на множинах N, Z і R: ; (–1)²; (7,8)³; ;

в) доповнення в алгебрі множин: .

Прикладами бінарних операцій є:

а) на множині R — арифметичні дії додавання (+), віднімання (–), множення ( ), ділення ( );

б) в алгебрі множин — об’єднання ( ), перетин ( ), різниця ( ), пряма сума ( ), яку ще називають симетричною різницею, декартів добуток ( ).

Бінарні операції можна записати одним із трьох способів: інфіксним (infix, яким ми звикли користуватися) — оператор ставиться між операндами; префіксним (prefix, який ще називають прямим польським записом¹) — оператор ставиться перед операндами; постфіксним (postfix, який ще називають зворотним польським записом) — оператор ставиться після операндів.

Приклад 1.3. а) Розглянемо варіанти запису бінарної операції додавання: — infix; — prefix; + — postfix.

б) Розглянемо варіанти запису алгебричного виразу: — infix; — prefix; — postfix.

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

Крім вказаних, добре відомих операцій — арифметичних дій і операцій над множинами, існує багато інших операцій.

Так, в алгебрі висловлювань, яка є найпростішою з формальних логічних теорій і в якій задано логічні операції над висловлюваннями², складні висловлювання одержують з простих за допомогою унарних і бінарних операцій (їх називають зв’я́зками): заперечення ( ), кон’юнкції ( ), диз’юнкції ( ), імплікації (→), еквівалентності ( ) та ін. Розглянемо ці операції докладніше.

Запереченням висловлювання називають висловлювання , якщо воно істинне (І), коли — хибне (Х), і хибне, коли — істинне. Таблиця істинності для заперечення проста:

Кон’юнкцією двох висловлювань А і В називають висловлювання виду , яке істинне тоді і тільки тоді, коли і одночасно істинні. Таблиця істинності для кон’юнкції має такий вигляд:

Диз’юнкцією двох висловлювань А і В, називають висловлювання виду , яке істинне, якщо хоча б одне із даних висловлювань істинне. Таблиця істинності для диз’юнкції має такий вигляд:

Імплікацією двох висловлювань А і В називають висловлювання виду , якщо воно хибне тоді і тільки тоді, коли А істинне, а В хибне. Таблиця істинності для імплікації має такий вигляд:

Еквівалентністю двох висловлювань А і В називають висловлювання , якщо воно істинне тоді і тільки тоді, коли А і В обоє істинні або обоє хибні. Таблиця істинності для еквівалентності має такий вигляд:

Розглянемо також деякі інші зв’я́зки.

Штрих Шеффера (або антикон’юнкція): . Таблиця істинності для штриха Шеффера має такий вигляд:

Стрілка Пірса (або антидиз’юнкція): . Таблиця істинності для стрілки Пірса має такий вигляд:

Сума за модулем два (або антиеквівалентність): . Таблиця істинності для суми за модулем два має такий вигляд:

На основі простого логічного аналізу, зокрема аналізу таблиць істинності, зазначимо, що імплікація двох висловлювань принципово відмінна від диз’юнкції, кон’юнкції й еквівалентності, оскільки вона несиметрична. Справді, для вказаних операцій не має значення порядок операндів (тобто, вони комутативні):

, , ,

але не еквівалентне .

Розглянемо всі імплікації, які можна утворити з двох висловлювань А і В. У таблиці істинності подано чотири імплікації:

Звідси видно, що , також .

Надалі для позначення абстрактних бінарних операцій будемо використовувати символи і .