ТЕОРЕТИЧНИ (МАТЕМАТИЧЕСКИ) ОСНОВИ
НА КОМПЮТЪРНАТА ИНФОРМАТИКА

Димитър Петров Шишков

Разглеждат се множествата изобщо, като основа на цялата математика, включително и компютърната информатика (КИ). Според нас КИ е половината от съвременната математика (М). Тя включва както дяловете на класическата М (алгебра, геометрия, топология и др.), така и (абстрактни) компютърни архитектури, формални езици и граматики, езици за програмиране (ЕП), операционни системи (ОС), информационни системи, вкл. бази от данни (БД), компютърна графика (КГ) и др.

Разгледани са и специализирани множества и множества от множества (фамилии от множества): релациите, комбинаторните множества, множеството от двете логически стойности, данните, примитивните и съставните типове данни и операциите над някои от тях (логически стойности и числа).

МНОЖЕСТВА

Всяко множество A се определя от елементите си a, b, c, ... , заградени с фигурни скоби.
То се означава с A = {a, b, c, . . . }.

Фактът, че елементът a принадлежи на множеството A, се означава с aA, а че не принадлежи с aA. Множеството без елементи се нарича празно множество и се означава с .

Множеството А може да се зададе и със свойството P(x), което имат всичките му елементи
(xA). Това се записва с А={xA|P(x)} или А={xA: P(x)}. Например множеството на естествените числа е N = {nN | n-цяло, n 1}.

Ако всички елементи на множеството A принадлежат на множеството B, се казва, че
A е подмножество на B и се записва AB, като AB означава, че има елементи на B, които не са елементи на A. Тогава се казва, че A е истинско подмножество на B. Очевидни са следните свойства:

1.A A (рефлексивност).

2.Ако A B и B A, то A = B (антисиметричност).

3.Ако A B и B C, то A C (транзитивност).

4. е подмножество на всяко множество ( A, вж. по-долу квантор на общност).

ОПЕРАЦИИ НАД МНОЖЕСТВА

Обединение или сума A B на множествата A и B е множеството, което се състои от всички елементи, които принадлежат на поне едно от множествата A и B. Обединението има следните свойства:

1.A A = A (идемпотентност).

2.A B = B A (комутативност).

3.A (B C) = (A B) C (асоциативност).

4.A A B, B A B

Сечение или произведение A B на множествата A и B е множеството, което се състои от всички елементи, принадлежащи едновременно на A и B. Сечението има следните свойства:

1.A A = A (идемпотентност).

2.A B = B A (комутативност).

3.A (B C) = (A B) C (асоциативност).

4.A B A, A B B.

Следните две свойства на операциите обединение и сечение се наричат дистрибутивност: