Лекция №1. Тема: теория множества.

Лекция №1. Тема: теория множества.

Множество – это совокупность каких-либо элементов чего-либо, объединенных неким признаком, общим свойством, присущим всем элементам.

Например: человечество, класс, группа и т.д.

Множество можно задать словесно, перечислением.

Множество считается заданным, если:

· Перечислены все его элементы

· Либо указано свойства, которым обладают те и только те элементы, которые принадлежат данному множеству.

 

Примеры записи множества:

· Перечисление

M = {m₁, m₂ … m_n} N = 1, 2, 3,4 … 10.

· Описание множества

M = {x│P(x)} – состоит из тех элементов х, которое обладает признаком Р. Свойство Р – характеристическое.

· M = {n│n? N, n<5} – M состоит из натуральных чисел, меньше 5.

 

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

Обозначается: Ø.

Пример:

1. Множество целых решений 5<x<6 – является пустым

M = {x│x Є N, 5<x<6} = Ø

 

множество признак

 

2. Множество действительных решений уравнения пустое:

x² + 4 = 0; к = Ǿ; x² = -4. Действительного решения нет, т.е. это множество – пустое.

 

Множество конечно, если количество элементов в нем ограничено (бесконечное множество бывает счетное и несчетное).

Множество будет счетным, если его элементы можно пронумеровать (считать).

Элементы несчетного множества пронумеровать нельзя.

Из множества М можно выделить его часть (выделением нового характеристического свойства или перечислением выбранных элементов) – множества К, все элементы которого обладают таким же признаком, что и элементы множества М.

 

Пример: группу людей разбили на части и получили подмножества.

 

Множество К называется подмножеством множества М(КЄM), если для любых значений х Є К выполняется условие: х Є M.

 

Пример:

NЄZЄQЄRЄC N – натуральные числа

Z – целые числа

Q – рациональные числа

R – действительные числа

C – комплексные (a+ib)

 

Равными называются два множества, состоящие из одинаковых элементов.

Пример:

M₁ (1, 2, 3) а) б)

M ₂ (1, 3, 2)

M ₃ (3, 2, 1)

 

 

Универсальным называют множество U, состоящее из всех возможных элементов B, обладающих данным признаком, т.е. признаком, общим для всех (понятие универсального множества четко не определено).

 

Пример: множество букв, слов.

Число элементов множества А называется мощностью множества.

Обозначается: │А│,U, n (A).

 

Пример:

1. n(Ø) = 0;

2. M (1, 2, 3): n(M) = 3.

Лекции №3. Тема: основные тождества алгебры множеств.

1.

2. Коммутативность

3.

4. Ассоциативность

5.

6. Дистрибутивность

7. Закон

7а. Де Моргана

 

8. Ø Ø

9. Ø

10.

11. Ø = Ø

 

12. Закон

13. поглощения

где Ø - пустое множество

 

Пример:

M (1, 9, 12, 17, 33, 4, 16)

N (33, 22, 45, 9, 1, 20, 35)

1. вычитание: R = (12, 17, 4, 16);

2. сложение: R = (1, 9, 12, 17, 33, 4, 16, 22, 45, 20, 35);

3. произведение: R = (1, 9, 33)

 

 

Лекция №4. Тема: кортежи.

Происхождение от французского «торжественность».

 

Пусть М – конечное множество, элементами которого являются символы. Например: цифры, буквы.

Кортеж – есть упорядоченный набор (строгая последовательность) элементов множества M.

Алфавит - есть кортеж попарно различных символов, называемых буквами алфавита.

 

Рассмотрим множество состоящее из n элементов:0,1,2,…,n.

Кортежи длины m из этих элементов, обозначим M^m, тогда мощность n(M^m), есть n^m. Такие кортежи, которые называются упорядоченными наборами или векторами.

Пример: M (1,2,3,4), M (4,3,2,1) M (1,3,2,4); M ≠ M ≠ M ; т.е.если порядок расположения элементов разный, то кортежи не равны друг другу (разные).

 

Декартовое произведение множеств: Пусть заданы множества M₁,M₂,…. M_n.

Декартовым произведением этих множеств называется множество состоящие из всех кортежей (m₁, m₂….m_n) длины k₁(m_k Є M_k, 1 ≤ k ≤ n), где m₁Є M₁, m₂ Є M₂, … m_n Є M_n. Обозначается как M₁*M₂*…M_n. Произведение –

M * M *… * M – nраз, обозначается как Mⁿ и называется n – ой степенью M.

Порядок задания множителей для декартового произведения, как для кортежей одинаков.

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

 

Пример:

M₁ = {0, 1, 2}, M₂ = {x, y, z}, M₃ = {A, Б, С}

Декартовое произведение:

M₁ * M₂ * M₃ K₁ = {(0, 1), (x, y), (A, Б)}, или К₂ = {(1, 2), (x, z), (A, C)}.

 

Отображения множеств (функций)

Отображение f множества x во множество y – это когда каждому элементу x Є X, ставится в соответствие только один элемент y Є Y.

Элемент y множества Y, соответствующий при отображении f элементу x из X называется образом элемента x. Если y = f(x), то x называется прообразом элемента y при этом отображении.

Частный случай отображения множества X в Y имеет место, если каждый элемент множества Y имеет прообраз из множества X. В этом случае отображение (f) сюръективно, (может быть случай, когда несколько элементов Y имеют один и тот же прообраз в X).

Отображение f, называется инъективным, если для каждого элемента

y Є Y существует не более 1- го прообраза, если отображение f сюръективно и инъективно, то оно называется биективным.

Пример: функций, отображающих x Є R на множество y Є R на множество

y Є R, где R – множество (бесконечное) действительных чисел.

 

1. f₁(x) = E^x – инъективно (не сюръективно)

2. f₂(x) = x*(x²-1) – сюръективно (не инъективно)

3. f₃(x) = 3x+1 – биективно

 

Лекция №5. Тема: алгебра логики (булева алгебра).

 

В основе логико – математической теории дискретной математики лежит понятие: высказывание. Это повествовательное предложение, которое интересует математика прежде всего в узком смысле: истинно оно или ложно.

 

В алгебре логики основными связками (операциями) являются следующие:

o дизъюнкция (или)

o конъюнкция (и)

o отрицание (не)

o импликация (если…, то…) →

o эквиваленция (тогда и только тогда, когда…) ↔

o штрих Шеффера (антиконъюнкция) |

o стрелка Пирса (антидизъюнкция) ↓

 

При выполнении операций существует следующий порядок:

- операции в скобках, если их нет тот операции выполняются так:

I. отрицание

II. конъюнкция

III. дизъюнкция

IV. импликация

V. эквиваленция

VI. штрих Шеффера

VII. стрелка Пирса

Конъюнкцией двух высказываний X, Y называется высказывание (функция) x y, которая истина только в том случае, когда X и Y - оба истинны.

 

x	y	X&Y

 

Дизъюнкция X и Y называется высказывание (функция) X Y, которое истинно когда хотя бы одно из X и Y истинно.

 

X	Y	X Y

 

 

Импликацией X и Y называется высказывание (функция) X→Y, которая ложна тогда, и только тогда, когда X истинно, а Y ложно, и истинна в остальных вариантах.

 

Таблица истинности для импликации

X	Y	X→Y

 

 

Эквиваленцией X иY называется высказывание X↔Y, которое истинно тогда, и только тогда, когда X и Y оба истинны или ложны, одновременно.

 

Таблица истинности для эквиваленции

 

X	Y	X↔Y

 

Штрих Шеффера (антиконъюнкция) - X│Y = X∩Y

X	Y	X│Y

 

 

____

Стрелка Пирса (антиконъюнкция) - X↓Y = XUY

 

X	Y	X↓Y

 

____

Сложение по модулю два (антиэквиваленция) - X Y = X↔Y

X	Y	X Y

 

Равносильные формулы.

 

Дизъюнктивные и конъюнктивные нормальные формы формул алгебры логики (булевой алгебры).

 

Дизъюнктивной нормальной формой (ДНФ) какой либо формулы алгебры логики называется формула, являющаяся дизъюнкцией элементарных конъюнкций.

 

Пример:

 

Формула, равносильная данной формуле алгебры высказываний и являющаяся конъюнкцией элементарных сумм (дизъюнктивных одночленов), называется конъюнктивной нормальной формой (КНФ), данной формулы.

Например:

– КНФ

 

ДНФ называется дизъюнкция конечного числа элементарных конъюнкций.

- ДНФ

 

КНФ называется конъюнкция конечного числа элементарных дизъюнкций.

- КНФ

 

Равносильные формулы:

 

1) X→Y= Y

 

(X Y) ( )

2) X↔Y=

(X Y) ( )

 

3) Закон Де Моргана ;

4)

5) X↓Y=

 

Примеры:

1.

2.

 

Совершенные СДНФ и СКНФ

Нормальные формы (ДНФ) (КНФ) называются совершенными (СДНФ, СКНФ), если в каждой элементарной дизъюнкции (конъюнкции) представлены все переменные, входящие в данную формулу, сами, либо с отрицанием.

 

Существует ДНФ (X Y) (

 

Примеры:

СДНФ –

CКНФ -

Карта Карно

Пример:

_ _ _ _

1. F = f(XYZ) = XYZ XYZ X YZ XYZ

Варианты Х	Варианты Х, Z
	_ _ YZ	_ YZ	YZ	_ YZ
X
_ X

 

_ _

1) (XYZ XYZ) = YZ(X X) = YZ

_ _ _ _ _ _

2) (XYZ XYZ) = YZ(X Z) = YZ

_ _ _ _ _ _

3) F = f(XYZ) = XYZ XYZ XYZ XYZ = YZ YZ = Y(Z Z) Y –минимизированная функция.

 

_ _ _ _ _ _ _ _ _ _ _ _ _

2. F = ABCD ABCD ABCD ABCD ABCD ABCD

 

	_ _ СD	_ CD	CD	_ CD
_ AB
_ AB
AB
_ AB

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

_ _ _ _ _ _ _ _ _ _

1) (ABCD ABCD) = ABD(C C) = ABD

_ _ _ _ _ _

2) (ABCD ABCD) = ABD(C C) = ABD

_ _ _ _ _ _ _ _ _ _

3) (ABCD ABCD) = ABC(D D) = ABC

_ _ _ _ _ _

4) f(ABCD) = ABD ABD = AD(B B) = AD

_ _ _

5) f(ABCD) = AD ABC – минимизированная функция

 

	_ _ x3x4	_ x3x4	x3x4	_ x3x4
_ _ x1x2
_ x1x2
x1x2
_ x1x2

_ _ _ _ _ _ _ _

3. F = x₁x₂x₃x₄ x₁x₂x₃x₄ x₁x₂x₃x₄ x₁x₂x₃x₄

__{___}_ __{__} __{_}_ _ _ _ _ _

1) (x₁x₂x₃x₄ x₁x₂x₃x₄) = x₂x₃x₄ (x₁ x₁) = x₂x₃x₄

__{_} __{_} _ _ _

2) (x₁x₂x₃x₄ x₁x₂x₃x₄) = x₂x₃x₄ (x₁ x₁) = x₂x₃x₄

_ _ _ _ _{_}_ _

3) F = (x₂x₃x₄ x₂x₃x₄) = x₂x₄ (x₁ x₁) =x₂x₄ – минимизированная функция.

 

 

Теорема Поста.

Операции по модулю два, основные законы:

 

1) x₁ x₂ = x₂ x₁ - коммутативность

2) (x₁ x₂) x₃ = x₁(x₂ x₃) - ассоциативность

3) для конъюнкции:

x_1*(x₂ x₃) = x_1* x₂ x_1* x₃ - дистрибутивность

4) операции с конъюнкцией:

_ _

x x = 0, x 0 = х, x 1 = х, x x = 1

_____ _ _

5) x₁ x₂ = x₁ x₂ = x₁ x₂

_ _

6) x₁ x₂ = x_{1 *} x₂ x_{1 *} x₂

 

Теорема:

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

Любая функция булевой алгебры может быть представлена, и притом единственным образом, с помощью многочлена Жегалкина вида:

_n

F = a_ix_ix_j

^{i, j = 0}

Многочлен Жегалкина булевой функции одной переменной:

1) F(A) = a₁ a₁A

2) F(X) = a₀ a₁X

3) F(Я) = a₀ a₁Я

4)

Многочлен Жегалкина булевой функции двух переменных:

1) F(A, B) = a₀ a₁A a₂B a₁₂ AB

2) F(x₁, x₂) = a₀ a x₁ a₂ x₂ a₁₂ x₁ x₂

 

Многочлен Жегалкина булевой функции трёх переменных:

1) F(x₁, x₂, x₃) = a₀ a x₁ a₂ x₂ a₃ x₃ a₁₂ x₁ x₂ a₁₃ x₁ x₃ a₂₃ x₂ x₃ a₁₂₃ x₁ x₂ x₃

 

 

 

 

 

 

_ _ _ _ _ _ _ _ _ _ _

F = (x₁ x₂ x₃) (x₁ x₂ x₃) (x₁ x₂ x₃) = (x₁ x₂ x₃) (x₁ x₂ x₃)

_ _ _ _ _ _ (x₁ x₂ x₃) = (x₁ x₂) (x₃ x₃) (x₁ x₂ x₃) = (делаем замену x₁ = x₁ 1, x₂ = x₂ 1) = ((x₁ 1) (x₂ 1)) (x₁ (x₂ 1) x₃) = =x₁x₂ x₂ x₁ 1 x₁x₂x₃ x₁x₂ x₂x₃ x₁x₃ =

= 1 x₁ x₂ x₁x₂ x₂x₃ x₁x₃ x₁x₂x₃.

 

Теорема Поста.

 

Для того, чтобы система булевых функций {f₁, f₂,… f_n} была полной, необходимо и достаточно, чтобы для каждого из классов Т₀, Т₁, S L M начиналась функция f_i не принадлежащая этому классу.

Т₀ - класс функций сохраняющих 0;

Т₁ - класс функций сохраняющих 1;

S - класс самодвойственных функций;

L - класс линейных функций;

M – класс монотонных функций.

 

Множество булевых функций называется функционально-замкнутым, если вместе с функциями из данного класса оно содержит также все их суперпозиции.

Система булевых функций {f₁, f₂,… f_n} называется полной, если любая из этих функций (f_i) может быть выражено через другие функции с помощью суперпозиции, например:

f₃ = f₁ + f₂ f₁ + f₂ - f₄

f₁ = f₃+f₅+f₆ - f₇ - f₈

 

(f_1, f_1, … f_n; f₁ + f₂; f₁ + f₃)

 

Примеры важнейших замкнутых классов:

Т₀ : f(0, 0, 0) = (0 0) (0 0 0) = (0 1) (0 0 1) = 0;

Т₁: f(1, 1, 1) = 1 (1 1) (1 1 1) = 1 (0 1) (0 1 1) = 1.

Лекция №12. Тема: Кванторы.

 

1. Квантор общности Ұ – «любое, для каждого»

Ұ х (Z(x)) – для любого х существует Z(x).

2. Квантор существования - «существует»: (Z(x))

Например, «для каждого х существует y, равный х²» записывается так:

Ұх (y = х²).

Переменная, к которым относиться квантор называется связанным.

Примеры применения кванторов:

1) х*х = х² Ұ (х)(х*х = х²) = истинно (1)

2) х+2 = 7 Ұ (х)(х+2 = 7) = ложь (0)

 

Пусть A и B формулы алгебры логики, причем нет таких переменных, которые были бы связанны в одной формуле и свободны в другой, тогда:

A = x₁ x₂ x₃, B = x₁ x₂ x₃

(A B), (A B), (A → B), (A ↔ B) – тоже формулы.

 

Правила переходов от одних формул к другим:

o перенос квантора через отрицание. Пусть А – формула, где х – свободная переменная, тогда

_ _ _

Ұх (А(х)) ≡ х (А(х))

_ _

х (А(х)) ≡ Ұх (А(х))

 

Перенос квантора через отрицание.

________ ___

(Ұх)(Ұ(х)) ≡ ( х)V(х)

____

х(V(х)) ≡ (Vх)(V(х))

 

Вынос квантора за скобки:

( х)(V(х) B) ≡ х(V(х)) B

( х)(V(х) B) ≡ ( х)(Vх) B

(Vх)(V(х) B) ≡ (Vх)(V(х)) B

(Vх)(V(х) B) ≡ (Vх)(V(х) B)

 

 

Исчисление предикатов.

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

 

 

Аксиомы исчисления:

1) А → (B → А)

2) (А→ (B → C)) → ((А → B) → (A → C)

_ _ _

3) (B → А) → ((B → А) → (A → C))

4) (V x₁)A(х_i) → A(х_j), где A(х_i) не содержит x_j

5) A(х_i) → ( x_j) A(х_i), где A(х_i) не содержит x_j

 

Примеры графов

1) 3)

 

2)

 

4)

 

5) 6)

Пусть на плоскости задано некоторое множество вершин V и дуг R. Графом называют бинарное отношение множеством V и R или иначе f V → R. Здесь f отображение инциденции.

 

Граф называется ориентированным, если указано направление дуг и неориентированным, если такое направление не указано.

Граф называется петлёй, если его начало и конец совпадают.

Под графом G_a графа G называется граф, который входит в лишь часть вершин графа G вместе с дугами их соединяющими.

Частным графом G_в графа G называется граф, который входит в лишь часть дуг графа G вместе с вершинами их соединяющими. (Карта шоссейных дорог – это граф. Дороги Саратовской области – это подграф, а главные дороги – это частный граф, где вершины называются смежными, если существует соединяющая их дуга. Два смежных ребра имеют общую вершину).

Степенью (валентностью) вершины называется число инцидентных ей рёбер.

Кратностью пары вершин называется число соединяющих их ребер или дуг.

Граф, состоящий из изолированных вершин, называется нульграф.

Теорема

В графе G(V, R) сумма степеней всех его вершин – число четное равное удвоенному

n

числу ребер графа: deg(V_i) = 2m, где n =│V│ - число вершин,

i= 1 m =│R│ - число ребер графа

 

Вершина называется четной/нечетной, если её степень – четная/нечетная.

Ориентированные графы изображаются так:

V₂ V₂

V₁ V₃ V₁ V₃

 

Неориентированный граф – ребро, цепь, цикл;

Ориентированный граф – дуга, путь, контур.

 

Ребро (дуга) – отрезок, соединяющий две вершины.

Цель (путь) – последовательность ребер (дуг).

Цикло (контур) – конечной длины цель (путь), у которой начальная и конечная вершины совпадают.

 

Граф называется связанным, если любые две его вершины можно соединить цепью.

Граф сильно связан, если для любых двух вершин х_i ≠ х_j существует путь, идущий из х_i и х_j.

Граф, который не является связанным, может быть разбит на конечное число связанных графов, называемых компонентами связанности.

 

V₃ V₃

- G(V, R) – граф V₂ V₄ - G_а(V, R) – подграф

V₁ V₅ графа G

У графа может быть несколько подграфов.

Граф G называется полным, если любые две его различные вершины напрямую соединены как минимум одним и ребром.

V₃

V₁ V₅ _

Дополнением графа G(V, R) называется граф G(V, R) с теми же вершинами V, что и граф G и имеющие те и только те ребра R, которые необходимо добавить в графу G, чтоб он стал полным.

Граф с кратными ребрами не имеет дополнения.

 

G(V, R)

V₂ V₃

- граф _

G(V,R) -

V₁ V₄

Маршрут – это последовательность ребер неориентированного графа, когда вершина предыдущего ребра совпадает с следующего ребра.

Число ребер маршрута называется его длиной.

В маршруте одно и тоже ребро может встретиться несколько раз; если ребра встречаются один раз, то маршрут называется цепью.

В ориентированном графе маршрут называется путь – упорядоченная последовательность дуг ориентированного графа, соединенных последовательно.

§ Направление каждой дуги должно совпадать с направлением пути. Путь навстречу дуги невозможен.

§ Не одна дуга пути не должна встречаться дважды.

 

 

Лекция №1. Тема: теория множества.

Множество – это совокупность каких-либо элементов чего-либо, объединенных неким признаком, общим свойством, присущим всем элементам.

Например: человечество, класс, группа и т.д.

Множество можно задать словесно, перечислением.

Множество считается заданным, если:

· Перечислены все его элементы

· Либо указано свойства, которым обладают те и только те элементы, которые принадлежат данному множеству.

 

Примеры записи множества:

· Перечисление

M = {m₁, m₂ … m_n} N = 1, 2, 3,4 … 10.

· Описание множества

M = {x│P(x)} – состоит из тех элементов х, которое обладает признаком Р. Свойство Р – характеристическое.

· M = {n│n? N, n<5} – M состоит из натуральных чисел, меньше 5.

 

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

Обозначается: Ø.

Пример:

1. Множество целых решений 5<x<6 – является пустым

M = {x│x Є N, 5<x<6} = Ø

 

множество признак

 

2. Множество действительных решений уравнения пустое:

x² + 4 = 0; к = Ǿ; x² = -4. Действительного решения нет, т.е. это множество – пустое.

 

Множество конечно, если количество элементов в нем ограничено (бесконечное множество бывает счетное и несчетное).

Множество будет счетным, если его элементы можно пронумеровать (считать).

Элементы несчетного множества пронумеровать нельзя.