Теория множеств и отношений

Для задания множеств применяют 2 способа [7]:

· перечисление элементов множества;

· задание способа конструирования множества.

Упорядоченные множества называют кортежами (векторами).

В алгебре множеств применяются операции над множествами:

· объединение множеств;

· пересечение;

· разность (эта операция двухместная);

· дополнение (эта операция тоже двухместная);

· разбиение;

· декартово (прямое) произведение.

Отношения на множествах лежат в основе реляционного исчисления и применяются в наиболее распространенных в настоящее время реляционных базах данных.

Частные случаи отношений:

· отношения эквивалентности;

· отношения порядка и др.

Нечеткие множества – основа для нечеткой логики и нечеткой математики.

Исчисление высказываний (логика Буля)

Формализация силлогистики (логики Аристотеля), выполненная Дж. Булем, привела к появлению исчисления высказываний (булевой логики) [11]. В логике Буля сложные высказывания представляются в виде ППФ – правильно построенных формул логики.

Дж. Булем были введены также простейшие функции алгебры логики - конъюнкция, дизъюнкция, отрицание, импликация, эквивалентность и др. Простейшие и более сложные булевы функции описываются таблицами истинности. В исчислении высказываний (одной из дедуктивных систем) к формулам (сначала к аксиомам) применяют правила вывода (правило отделения, правило резолюции и др.) и получают цепочку выводов.

В алгебре логики действуют ряд законов, таких как переместительный, сочетательный, законы де Моргана, законы поглощения и др.

Булевы функции могут быть представлены в дизъюнктивной (ДНФ), конъюнктивной (КНФ) нормальной форме, в совершенной ДНФ (СНДФ) или совершенной КНФ (СКНФ). Эти формы используются при синтезе логических схем ЭС, в том числе при программировании ПЛИС.

Теория алгоритмов

Интуитивное понятие алгоритма подкрепляется эмпирическими свойствами алгоритмов:

· дискретность;

· детерминированность;

· массовость;

· результативность.

Существуют так называемые алгоритмически неразрешимые проблемы (задачи), например проблема самоприменимости (парадокс брадобрея) и др.

К способам представления алгоритмов относят:

· словесное описание алгоритма;

· схемное описание;

· псевдокоды;

· языки программирования.

Наиболее важными критериями оценки и сравнения алгоритмов являются следующие:

· быстродействие алгоритма;

· точность алгоритма;

· временная сложность.