Дискретная математика

логика
Теория автоматов
Теория формальных грамматик
Теория алгоритмов

— семинары, 40% — ответ на экзамене
Итоговая оценка
От 40

до 64 баллов — 3
От 65 до 84 баллов — 4
85 баллов и выше — 5
Семинары — самостоятельные работы, компьютерные работы, активность, индивидуальные творческие задания
Экзамен — 3 вопроса (до 10 баллов каждый), в случае «пограничного» количества баллов по Вашему желанию может быть дать дополнительный вопрос (От 0 до 10 балов)

И. А., Максимова Л. Л. Задачи по теории множеств, математической логике и

теории алгоритмов. – M.: Физматлит, 1995.
Кузнецов О. П., Адельсон-Вельский Г. М. Дискретная математика для инженера. — М.: Энергоатомиздат, 1988
Липский В. Комбинаторика для программистов. — М.: Мир, 1988
Москинова Г.И. Дискретная математика. Математика для менеджера в примерах и упражнениях: Учебное пособие. — М.: Логос, 2000

разработаны
Бернардом Больцано (1781 – 1848)
Рихардом Дедекиндом (1831 – 1916)
Георгом Кантором

(1845 – 1918)
Дальнейшее развитие
Альфред Норт Уайтхед (1861 – 1947)
Лейтзен Эгберт Ян Брауэр (1881 – 1966)
Герман Вейль (1885 – 1955)
Хаскелл Брукс Карри (1900 - )
Бертран Рассел (1872 – 1970)

нашей интуиции или интеллекта, которые можно отличить один от другого

и которые представляются как единое целое, называется множеством. Предметы, которые входят в состав множества, называются его элементами»
Через  обозначается отношение принадлежности, т.е. x  A означает, что элемент x принадлежит множеству A.
Если x не является элементом множества A, то это записывается x  A или x   A.

с одинаковыми кардинальными числами называются эквивалентными.
Множества могут быть конечными (т.е.

состоящими из конечного числа элементов) и бесконечными.
Множество мощности 0, не содержащее элементов, называется пустым и обозначается через .
Некоторое, общее для всех множеств данной мощности, надмножество, называется универсальным множеством или УНИВЕРСУМОМ и обозначается обычно как U.

они состоят из одних и тех же элементов (интуитивный принцип

объемности). Пишется A = B, если A и B равны, и A  B в противном случае.
Через  обозначается ОТНОШЕНИЕ ВКЛЮЧЕНИЯ множеств, т.е. A  B означает, что каждый элемент множества A является элементом множества B. В этом случае A называется ПОДМНОЖЕСТВОМ B, а B — НАДМНОЖЕСТВОМ A. Если A  B и A  B, то A называется СОБСТВЕННЫМ ПОДМНОЖЕСТВОМ B, и в этом случае пишем A  B.

процедурой (например, индуктивными или рекурсивными правилами).

из которых имеются кажущиеся убедительными аргументы

Наиболее резкая форма парадокса —

антиномия, рассуждение, доказывающее эквивалентность двух утверждений, одно из которых является отрицанием другого.

Рассмотрим множество всех таких множеств. Тогда: если оно не содержит

себя, то оно содержит себя
Антиномия всемогущества. Бог всемогущ, поэтому он может создать такой камень, который сам не сможет поднять. Но Бог всемогущ, поэтому он может поднять любой камень.
Парадокс «Деревенский парикмахер»

множество
A  B = {x x  A или  x  B}.
ПЕРЕСЕЧЕНИЕМ (КОНЪЮНКЦИЕЙ) множеств A и B называется множество
A  B = {x x  A

и  x  B}.
РАЗНОСТЬЮ множеств A и B называется множество
A \ B = {x x  A и  x  B}
Разность  U \ A называется ДОПОЛНЕНИЕМ множества A и обозначается через –A.
СИММЕТРИЧЕСКОЙ РАЗНОСТЬЮ множеств A и B называется множество
A  B = (A \ B)  (B \ A) 

содержащиеся в Ω. Семейство подмножеств Ω обозначаем через P(Ω); P(Ω)

— множество, все элементы которого сами являются множествами. Термин семейство понимается здесь в следующем смысле: семейство — множество, все элементы которого сами являются множествами (вместо множество множеств говорим семейство множеств).
Булеан множества — множество всех подмножеств множества

А1, А2, …, Аn, …, то совокупность {А1, А2, …,

Аn, …} подмножеств называется покрытием множества A.
Если же совокупность подмножеств покрытия множества A такова, что Ai   Aj =  при i j, то совокупность {А1, А2, …, Аn, …} называется разбиением множества A, а подмножества Ai — классами этого разбиения.

Моргана

(a, b), где a — элемент A , а b

— элемент B.
Декартово или прямое произведение множеств A и B — A  B — множество всех таких упорядоченных пар элементов этих множеств.

Декартово (прямое) произведение множеств

множество
А1  А2 … An = {(а1,

а2, ..., ап) : аi  Аi, i = 1, 2, ...,n}.

Если А1 = А2 =…= An = А, то А  А … A = An

произвольное подмножество R декартова произведения A  B.

Если a 

A, b  B и (a, b)  R, то пишут также R(a, b) или aRb. Если R =  — пустое множество, то соответствие называется пустым, а если R = A  B, то соответствие называется полным.
Пусть R  A  B. Областью определения Dom R называется множество элементов a  A, для каждого из которых найдется хотя бы один элемент b  B такой, что aRb. Областью значений, или образом, Im R соответствия R называется множество элементов b  B, для каждого из которых найдется хотя бы один элемент a  A такой, что aRb. Соответствие R называется всюду определенным, если Dom R = A, и сюръективным, если Im R = B.
Для каждого a  A множество элементов b  B таких, что aRb, называется образом a относительно R и обозначается im R a. Прообразом элемента b  B относительно R называется множество элементов a  A таких, что aRb; прообраз обозначается coim R b. Ясно, что
Im R =  a  A im R a, Dom R =   b  B coim R b.

Dom R - это такие элементы а  A, для каждого

из которых найдется хотя бы один элемент b  B, такой что (a,b)  R. Dom R = {a: (a,b)  R}
Область значений (образ) соответствия Im R – это множество элементов b  B, для каждого из которых найдется хотя бы один элемент a  A такой, что (a,b)  R .

Dom R = {Лена, Петя, Маша, Вася, Женя}
Im R = {Горький, Достоевский, Лермонтов, Некрасов, Пушкин, Толстой, Фет}

(im R a) – это множество элементов b  B таких, что

(a,b)  R
Прообраз элемента b  B относительно R (coim R b) – это множество элементов a  A таких, что (a,b)  R
Im R =  a  A im R a, Dom R =   b  B coim R b.

im R Лена = {Некрасов, Фет} coim R Горький = {Петя, Женя}

соответствие, у которого Dom R = A (каждый элемент множества

А включен в соответствие). В противном случае – частично определенное.
Сюръективное соответствие – это соответствие, у которого
Im R = B (каждый элемент множества В включен в соответствие)

Частично определенное ( элемент Эллочка не имеет образа)
Сюръективное

B называется функциональным, если для любого элемента (a1, a2, …,

an) из A1  A2  …  An существует не более одного элемента b из B такого, что (a1, a2, …, an, b)  F. Если такой элемент b из B существует для некоторого (a1, a2, …, an) , то он обозначается F(a1, a2, …, an) и записывается так: b = F(a1, a2, …, an) .
В случае, если Dom(F) = A1  A2  …  An , F называется полностью определенным, когда Dom(F)  A1  A2  …  An — частично определенным или просто частичным.
Соответствие F, заданное на множествах A1, A2, …, An, B называется отображением или функцией из A1  A2  …  An в B (F: A1  A2  …  An  B), если F функциональное и полностью определенное. Соответствие F называется частичным отображением или частичной функцией, если F функциональное и частичное. Число n называют арностью функции F.

Функциональные соответствия

соответствие, у которого если элемент a  A имеет образ

при соответствии R, то он единственный элемент b  B (im Ra = ! b B)
Инъективное соответствие – это соответствие, у которого у которого если элемента b  B имеет прообраз при соответствии R, то он единственный элемент a  A (coim R b = ! a  A)

Не функциональное (т.к. im R Лена = {Некрасов, Фет} )
Не инъективное (т.к. coim R Горький = {Петя, Женя}