Перелік умовних скорочень

— квантор “для всіх”;

— квантор існування;

— множина дійсних чисел;

— множина додатних дійсних чисел;

N — множина натуральних чисел;

— множина цілих чисел;

або — множина цілих невід’ємних чисел;

— множина раціональних чисел;

— множина додатних раціональних чисел;

— потужність множини А;

— строге включення;

— нестроге включення;

— елемент x належить множині X;

— елемент x не належить множині X;

— універсальна множина;

— порожня множина;

— множина всіх підмножин множини X;

— об’єднання множин А і В;

— перетин множин А і В;

— доповнення множини А до універсальної;

— різниця множин А і В;

— потужність злічуваної множини (алеф нуль)

— потужність множини континуум;

— декартів добуток множин А і В;

— декартів степінь множини А;

— обернене відношення до відношення Q;

— композиція відношень Q і S;

— степінь відношення Q;

— область визначення відношення Q;

— область значень відношення Q;

— відображення;

— відношення еквівалентності;

— відношення строгого порядку;

— відношення нестрогого порядку;

— одиничний елемент;

0 — одиничний елемент відносно додавання;

1 — одиничний елемент відносно множення;

— обернений елемент до елемента x;

— обернений елемент до елемента х відносно додавання;

— обернений елемент до елемента х відносно множення;

— додавання за модулем n;

— множення за модулем n;

— інтерпретація логічної функції, двійкове слово, булів кортеж;

— кон’юнкція;

— диз’юнкція;

— заперечення;

або — еквівалентність;

— імплікація;

— сума за модулем 2;

— алгебрична структура — булева алгебра;

— алгебрична структура — алгебра Жегалкіна;

— функція, двоїста до функції ;

— клас функцій, які зберігають нуль;

— клас функцій, які зберігають одиницю;

— клас самодвоїстих функцій;

— клас лінійних функцій;

— клас монотонних функцій.

ВСТУП

У навчальному посібнику в доступній формі викладено три важливі розділи курсу дискретної математики — алгебричні структури, алгебру логіки й математичну логіку.

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

При вивченні алгебри логіки значна увага приділяється алгебрі Буля й алгебрі Жегалкіна. Ці алгебри є типовими прикладами загальної теорії про алгебричні структури. В алгебрі логіки також розглядається питання повноти системи логічних функцій і можливі підходи до розв’язання задачі мінімізації логічних функцій.

У частинах, присвячених математичній логіці, розглядаються логіка висловлювань (на прикладах кількох класичних її різновидів) і теорія предикатів першого порядку.

Потрібна для опанування матеріалу посібника математична підготовка обмежується поняттями розділу “Елементи теорії множин і відношення” і, звичайно ж, знаннями з елементарної математики за середню школу.

Усі ключові теоретичні поняття забезпечено достатньою кількістю задач і вправ, наведено завдання до модульної контрольної роботи.

Частини 1 – 4 написано М. В. Ногіним, частини 5 і 6 — Л. І. Кублій, частину 7 — авторами сумісно.

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