Элементарные функции алгебры логики

ЭЛЕМЕНТЫ ТЕОРИИ МНОЖЕСТВ

Понятие множества является неопределяемым, оно считается интуитивно заданным. Каждое множество состоит из объектов, которые в дальнейшем называются элементами множества. Множества обычно обозначаются большими буквами: А, Х и т.д. Элементы же множеств, как правило, обозначают маленькими буквами: а, х и т.д. Для записи того, что а является элементом множества А, применяется значок (символ принадлежности). Пишут: и говорят, что элемент а принадлежит множеству А. В случае, когда а не является элементом множества А, пишут . Множество может содержать как конечное, так и бесконечное число элементов, соответственно говорят, что множество конечно или бесконечно.

Интуитивный принцип объемности Кантора: множества А и В считаются равными , если они состоят из одних и тех же элементов.

Пример. Рассмотрим множества:

А = {множество всех положительных четных целых чисел},

В = {множество всех положительных целых чисел, представимых в виде суммы двух положительных нечетных целых чисел},

C = {2,4,6},

D = {2,6,4}.

Из принципа объемности следует, что справедливы равенства А = В и С = D.●

Для некоторых множеств существуют стандартные обозначения:

Æ – пустое множество, т.е. множество, не имеющее ни одного элемента;

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

Z – множество целых чисел;

Q – множество рациональных чисел;

R – множество действительных чисел.

Операции над множествами

Определение. Говорят, что множество А включено в множество В, и пишут АÍВ, если для любого элемента аÎА справедливо аÎВ.

Пример. Очевидны следующие включения N Z Q R. ●

Операция включения множеств обладает следующими свойствами:

Замечание. Необходимо различать символ принадлежности Î и символ включения Í. Символ принадлежности не обязан удовлетворять тем же свойствам, что и символ включения. Так, например, 1 Î Z, Z Î {Z}, однако 1 Ï {Z}.

1. Объединением множеств А и В называется множество АÈВ, состоящее из тех элементов, которые принадлежат хотя бы одному из множеств А или В:

АÈВ = {x хÎА либо хÎВ}.

2. Разностью множеств А и В называется множество А\B, состоящее из тех и только тех элементов х, которые принадлежат множеству А и не принадлежат множеству В:

А\B ={х хÎА и хÏВ}.

3. Пересечением множеств А и В называется множество АÇВ таких элементов х, которые принадлежат как множеству А, так и множеству В:

АÇВ = {х хÎА и хÎВ}.

Операции над множествами могут быть распространены на любое число множеств.

Если ВÍА, то разность множеств А\B называют еще дополнительным множеством к В.

Операции над множествами хорошо иллюстрируются диаграммами Венна.

Теорема. Для любых множеств A, B, C справедливы равенства

(Свойства 1, 2, 3, 1', 2', 3' называются соответственно свойствами ассоциативности, коммутативности и дистрибутивности).

В случае, когда все рассматриваемые множества заведомо принадлежат одному и тому же множеству U, это множество называют универсумом.

Множество U\А называется дополнением множества А и обозначается .

.

Теорема. Для множеств и из универсума U справедливы законы де Моргана:

.

Пример. А Ç Æ= Æ Þ А È U = U; АÈÆ=А Þ А Ç U = А.●

Произведение множеств

Определение. Пусть А и В - множества. Произведением множеств А и В называется множество всех упорядоченных пар (а, в), где аÎА и вÎВ. Произведение обозначается А´В.

А´В={(a,b) ÎA и bÎ B}.

Произведение двух множеств часто называют прямым произведением. Заметим, что произведение n множеств А обозначается через Аⁿ .

Примеры.1) Если А = {a, b}, Е = {0, 1}, то

А´Е = {(a, 0), (a, 1), (b, 0), (b, 1)},

Е´A ={(0, a) (0, b), (1, a), (1, b)},

2) Пусть R´R. В этом случае получаем множество, обозначаемое R² и являющееся плоскостью с декартовой системой координат (по этой причине произведение множеств часто называют декартовым произведением).

3) Пусть [a, b], [c, d] – отрезки прямой. Тогда [a, b]´[c, d] – прямоугольник на плоскости.●

Основные понятия комбинаторики

Комбинаторика–раздел математики, изучающий способы подсчета числа элементов в конечных множествах.

Пусть .

1. Система подмножеств множества

Пример. .

, , , , , , , .●

Число подмножеств равно .

2. Размещение элементов из по k – упорядоченное подмножество из k элементов, принадлежащих .

Пример. , .

, , , , , .

Число размещений равно .

3. Перестановки элементов множества – упорядоченные подмножества из п элементов множества .

Пример. .

, , , , , .

Число перестановок равно .

4. Сочетание элементов из по k – неупорядоченное подмножество из k элементов, принадлежащих .

Пример. , .

, , .

Число сочетаний равно .

5. Разбиение множества – неупорядоченная система из непустых подмножеств множества , обладающая свойствами:

1) ,

2) .

Правило произведения. Если объект может быть выбран способами и после каждого из таких выборов объект , в свою очередь, может быть выбран способами, то выбор « и » в указанном порядке может быть осуществлен способами.

Правило суммы. Если объект может быть выбран способами, а объект – другими способами при условии, что одновременный выбор и невозможен, то выбор « или » можно осуществить способами.

ФУНКЦИИ АЛГЕБРЫ ЛОГИКИ

Элементарные функции алгебры логики

Введем обозначения ; – прямое произведение n сомножителей, т.е. .

Определение. Всюду определённой булевой функцией назовём отображение

.

Так как множество конечно, то задать отображение означает задать множество наборов из и для каждого набора указать его образ в .

Пример. Пусть , тогда { , , , }. Отображение может быть задано, например, так: ; , , .

Тем самым задана функция , которую можно записать в виде таблицы:

Таблица, задающая функцию , называется таблицей истинности для этой функции.

Функции одной переменной:

1. – константа нуль

Равенство функций

Определение. Переменная х_i называется существенной переменной функции алгебры логики , если существуют такие значения что

.

В противном случае переменная x_i называется фиктивной. Наборы, отличающиеся лишь одной переменной x_i, называются соседними по x_i.

Пример.

Для функции – фиктивная переменная, т.к. , , т.е. не существует наборов и таких, что .

Для функции и являются фиктивными переменными. – фиктивная переменная, так как не существует наборов и таких, что . Если , то , если , то . Аналогично доказывается, что – тоже фиктивная переменная.●

Пусть является фиктивной переменной для функции . Тогда ее можно удалить из таблицы истинности, вычеркнув все строки вида или, наоборот, все строки вида и столбец для переменной . При этом получим таблицу для некоторой функции . Будем говорить, что функция получена из функции путем удаления фиктивной переменной или получена из путем введения фиктивной переменной .

Определение. Функции и называются равными, если можно получить из путем добавления или удаления фиктивной переменной.

Принцип двойственности

Определение. Функция называется двойственной к функции , если .

Пример. Константа 0 двойственна к 1:

Определение. Если , то называется самодвойственной.

Если – самодвойственная, то , т.е. на противоположных наборах функция принимает противоположные значения.

Пример3.Покажем, что – самодвойственная функция.

Теорема (о двойственных функциях). Если двойственна к , то двойственна к .

Теорема (о принципе двойственности). Если функция задана некоторой формулой, то, чтобы получить двойственную функцию, надо в этой формуле все знаки функций заменить на двойственные, 0 на 1, 1 на 0.

Не нашли, что искали? Воспользуйтесь поиском по сайту: