Понятия множества
Множество - любая определенная совокупность элементов любой природы
Подмножество - Множество А называется подмножеством В тогда и только тогда, когда из элемента а А следует, что а В
Примеры множеств:
1.	Множество натуральных чисел N
2.	Множество натуральных положительных чисел N+
3.	Множество целых чисел Z
4.	Множество рациональных чисел RC…
Способы задания множеств:
1.	Перечисление элементов
2.	Характеристический предикат
3.	Порождающая процедура.
Принцип объемности.
Два множества равны тогда и только тогда, когда они состоят из одних и тех же элементов т.е. если каждый элемент одного из них является элементом другого и на оборот.

Операции над множествами.
Пересечением двух множеств А и В называется множество, которое состоит из элементов входящих в состав как А, так и В. А В = {a | a A и a B}.
Объединением двух множеств А и В называется множество, в состав которого входят те и только те элементы, которые входят в состав хотя бы одного из этих множеств. А В = {a | a A или a B}.
Разность: А \ В = {a | a A или a B}.
Симметрическая разность: А ? В = (А В) \ (А В) = {a | (a A или a B) и (a A или a B))
Эти операции называются теоретико-множественными.

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

Способы доказательства равенства двух множеств. 
Доказать что множество А включено в множество В. И наоборот.

Основные тождества алгебры множеств (с доказательством).
1.	А В = В А, А В = В А. (коммутативность)
2.	А (В С) = (А В) С, А (В С) = (А В) С. (ассоциативность)
3.	А (В С) = (А В) (А С), А (В С) = (А В) (А С). (дистрибутивность)
4.	А А` = U, A A` =  .
5.	A  =A, A U = A.
6.	A A = A, A A = A.
7.	А (A B) = A, А (A B) = A.
8.	A U = U, A   =  
9.	( )` = U, U` =  , (A`)` = A
10.	(А В)`= А` В`

Понятия бинарного отношения
Произвольное подмножество множества A1xA2x…An называется отношением, заданным на множествах А1, А2, …, Аn. Если А1=А2=…=Аn=А, то отношение R называется n-арным отношением на множестве А. При n=1 отношение унарное, при n=2 отношение бинарное, при n=3 отношение тернарное.

Обратное отношение, композиции отношений.
Отношение R-1, заданное на множестве ВхА называют обратным к R, если R-1 = {(b,a) | aRb}.
Отношение R*R1 заданное на АхС называют произведением или суперпозицией отношений R и R1, если R*R1 = {(a,c) | a А, с С и ( b B)(aRb и bR1c).

Способы задания бинарных отношений.
1.	Перечисление.
2.	Указание характеристического свойства.
3.	Стрелочные диаграммы.
4.	Графический.

Свойства бинарных отношений.
1.	(R1 R2)* = R1*R R2*R, R1 R2 => R1*R R2*R.
2.	(R-1)-1 = R, R R1 => R-1 R1-1.
3.	(R*R1)-1 = (R1-1)*(R-1).
4.	(R R1)-1 = (R-1) (R1-1).
5.	(R*R1)*R2 = R*(R1*R2).

Специальные бинарные отношения
Отношение эквивалентности
Бинарное отношение R, заданное на множестве А, называется отношением эквивалентности или эквивалентностью на А, если для любых элементов a, b, c из А справедливо:
1.	aRa (рефлексивность)
2.	aRb => bRa (симметричность)
3.	из aRb и bRc следует aRc (транзитивность)
Отношение порядка.
Бинарное отношение 0, заданное на множестве А, называется частичным порядком на А, если для любых элементов a, b, c из А справедливо:
1.	a0a (рефлексивность)
2.	из a0b и b0c следует a0c (транзитивность)
3.	a0b и b0a => a=b (антисимметричность)
Бинарное отношение a на множестве X называется отношением порядка, если оно транзитивно и антисимметрично.
Транзитивное и иррефлексивное отношение называется отношением строгого порядка.

Разбиение множества.
Всякое отношение эквивалентности R, определенное на множестве А, задаёт разбиение множества А на классы.
Свойства разбиения.
Между разбиениями множества на классы и отношениями эквивалентности, заданными на этом множестве, существует взаимно однозначное соответствие.
Всякое разбиение множества А на классы задаёт на множестве А отношение эквивалентности.
Числа Стерлинга и числа Белла.
Число Стерлинга - число разбиений n-множества на k-блоков
Число Белла - сумма чисел Стирлинга от нуля до k

Определение графа. 
Графом G(V,E) называется совокупность двух множеств - непустого множества V (множество вершин) и множества Е неупорядоченных пар различных элементов множества V (Е - множество ребер)
Неупорядоченная пара вершин называется ребром, упорядоченная пара - дугой.
Типы графов.
Полный граф - граф, у которого любые две вершины смежные.
Регулярные или однородные графы - граф, все вершины которого имеют одну и ту же степень.
Кубический или трех валентный граф - регулярный граф степени 3.
Полностью несвязанный или пустой граф - граф, у которого множество ребер пусто.
Платонов граф - граф, образованный вершинами и ребрами пяти правильных многогранников - Платоновых тел: тетраэдра, куба, октаэдра, додекаэдра и икосаэдра.
Двудольный граф - граф, в котором существует такое разбиение множества его вершин на два класса, при котором концы каждого ребра лежат в разных классах.
Ориентированный граф - граф G=(V,E), если E V2, то есть вершины его ребер упорядочены.
Способы задания графов.
1.	Графический
2.	Описание множеств вершин V и множеств ребер Х
3.	Матричный

Понятия маршрута на графе.
Маршрутом в заданном графе G = (V,E) называется конечная последовательность его ребер вида (v0,v1),(v1,v2),…,(vk-1,vk).
Маршрут - последовательность вершин v0,v1,…,vk графа G = (V,E), соединяющая вершины v0 и vk.
Одна и та же вершина может быть начальной, конечной и внутренней. Число рёбер (дуг) в маршруте (пути) называется длиной маршрута (пути). Маршрут (путь) называется замкнутым, если его начальная вершина совпадает с конечной. Не замкнутый маршрут (путь), в котором все рёбра (дуги) попарно различны, называется цепью. Цепь, в которой все вершины попарно различны, называется простой. Замкнутый маршрут (путь), в котором все рёбра (дуги) попарно различны, называется циклом (контуром). Цикл, в котором все вершины попарно различны, называется простым.
Алгоритм Терри поиска маршрута в связном графе.
Алгоритм поиска маршрута в связанном графе G, соединяющего заданные вершины v и w О V, где v ? w.
1.	Идя по произвольному ребру, всякий раз отмечать направление, которое оно прошло.
2.	Исходя из некоторой v' , всегда следовать только по тому ребру, которое не было пройдено или было пройдено в противоположном направлении.
3.	Для всякой вершины v', отличной от v отмечать первое заходящее в v' ребро, если v' встречается первый раз.
4.	Исходя из некоторой вершины v', отличной от v по первому заходящему ребру идти лишь тогда, когда нет других возможностей.

Минимальные пути.
Расстояние между вершинами u и v - длинна кратчайшего маршрута, соединяющего вершины u и v, и обозначается d(u,v).

Понятие связности.
Граф называется связанным, если произвольные две его вершины связаны маршрутом.
Максимальный связный подграф графа называется компонентом связности.
Матрица сильной связности.
Матрицей сильной связанности орграфа D называется квадратная матрица S(D)=[sij] порядка n, у которой sij=1, если вершина vi достижима из vj и одновременно vj достижима из vi, sij=0 в противном случае. Пусть G=(V, X) граф. Матрицей связанности графа G называется квадратная матрица S(G)=[sij] порядка n, у которой sij=1, если j = i или существует маршрут соединяющий vi и vj, sij=0 в противном случае.

Изоморфизм графов.
Пусть G = (V,E) и H = (V1,E1) - графы и h: V>V1 - взаимно однозначное соответствие (т.е. |V|=|V1|). Отображение h - изоморфизм графов G и H, если для любых вершин u и v графа G их образы h(u) и h(v) смежные в графе H тогда и только тогда, когда u и v смежные в G. Если такое отображение h существует, то графы G и H - изоморфны.
Графы (орграфы) изоморфны тогда и только тогда, когда их матрицы инцидентности можно получить одну из другой произвольными перестановками строк и столбцов.
Критерии планарности.
Если в графе имеется подграф, сводимый к либо полному графу с пятью вершинами, либо к полному двудольному графу 3 на 3, то граф НЕ ПЛАНАРЕН. Если таких подграфов нету - тогда планарен.

Предмет комбинаторики.
Подсчитать число возможных способов размещения некоторых предметов конечного множества или число всех возможных способов выполнения определенного действия из конечного множества таких действий.
Основные правила комбинаторики.
Пусть необходимо выполнить последовательно k действий. Если первое можно выполнить n1 способами, второе - n2 способами и т.д. до k-го действия, которое можно выполнить nk способами, то все k действий можно выполнить n1*n2*…*nk способами.
Для размещения с повторениями:
Каждое (n,k) - размещений с повторениями является упорядоченной последовательностью длиной в к. Причем 1-й элемент может быть выбран n-способами k-й тоже n способами. По правилу произведения получим nk.
Основные комбинаторные объекты.
1.	Система подмножеств множества
2.	Размещение элементов множества
3.	Перестановки элементов множества
4.	Сочетание элементов множества
5.	Разбиение множества

Размещения элементов с повторениями и без.
Произвольное k-элементное подмножество множества А называется комбинацией, или выборкой. Упорядоченное k-элементное подмножество множества А, все элементы которого различны, называется размещением без повторений, а любое упорядоченное k-элементное подмножество множества А, все элементы которого не обязательно различны, называется размещением с повторением.
Количество размещений без повторения равно  =  =  = n*(n-1)*…*(n-k+1).
Количество размещений c повторениями равно  = nk.

Перестановки.
Упорядоченные множества, которые отличаются одно от другого только порядком своих элементов, называются перестановками.
Оценки для n!
 > , где  =  
 < 

Сочетания элементов с повторениями. Число возможных сочетаний с повторениями.
Не упорядоченная (n,k)-выборка с повторениями.  = + k-1

Сочетания элементов без повторений. Число возможных сочетаний без повторений.
Не упорядоченная (n,k)-выборка без повторений.  = 

Разбиение множества.  Число возможных разбиений.

Формула включений и исключений.
|A B|=|A|+|B|-|A B|

Высказывания.
Высказыванием называется утверждение, о котором можно определенно сказать, истинно оно или ложно. Если высказывание истинно, то говорят, что его значение истинности равно единице. Если же высказывание ложно, - его значение истинности равно нулю.
Логические операции.
Логическое отрицание или инверсия некоторой логической переменной, например переменной А, это также логическая переменная, принимающая значение обратное значению переменной А, и обозначаемая как  .
Дизъюнкция (логическое сложение) или функция ИЛИ (OR) - это функция, которая истинна тогда, когда истинна хотя бы одна из ее переменных(\/).
Конъюнкция (логическое умножение) или функция И (AND) - это функция, которая истинна тогда, когда все ее переменные одновременно истинны (/\).
Функция (штрих) Шеффера или функция И-НЕ  - это функция, которая ложна тогда, когда все переменные истинны.
Функция (стрелка) Пирса (Вебба) или функция ИЛИ-НЕ - это функция, которая истинна только тогда, когда все переменные ложны.
Импликация или функция ЕСЛИ-ТО (IF-THEN) это функция, которая ложна тогда и только тогда, когда x1 истинно и x2 ложно. Аргумент х1 называется посылкой, а х2 - следствием.
Исключающее ИЛИ (XOR) - это функция, которая обозначается знаком ?. Эта операция, реализует функцию неравнозначности, т.е. фактически реализуется процедура суммирования по модулю 2, которая обозначается знаком ?
Все рассмотренные операции являются элементарными.

0 0 1 1 х
0 1 0 1 у
0 0 0 1 /\
0 1 1 1 \/
0 1 1 0 ?
1 0 0 0 ?
1 0 0 1 ~
1 1 0 1 >
1 1 1 0 |

Способы задания булевых функций. Примеры.
Представление (описание) функции на словах.
Например: функция трех аргументов принимает значение 1, если два любых аргумента или все три равны 1. Во всех остальных случаях функция рвана 0.
Табличный способ.
Для представления логической функции можно использовать, так называемый, табличный способ, когда функция представляется своей таблицей истинности.
Обычно в таблице истинности столбец с номером набора не приводится.
Алгебраический или аналитический способ. Табличный способ максимально наглядный, но в случае сложных функций алгебры логики достаточно некомпактный. Проще выглядит аналитическая запись в виде формул.

Равносильность формул.
Формулы А и В равносильны если на любой оценке списка переменных они принимают одинаковые значения. 
Основные равносильности алгебры логики.
1.	Коммутативность a b b a
2.	Идемпотентность a a a
3.	Ассоциативность (a b) с a (b с)
4.	Дистрибутивность (a b) с (a с) (b с)
5.	Законы поглощения a a (a b)
6.	Снятие двойного отрицания   a
7.	Законы де Моргана    
8.	Расщепление a (a b) (a  )
9.	Взаимосвязь логических связок a~b    

Способы доказательства равносильности двух формул.
1.	C помощью таблицы истинности.
2.	Путем рассуждения.
Доказательство равносильности законов де Моргана.
Строим таблицу истинности

Понятия тавтологии
Пусть формула А зависит от списка переменных <x1, x2, …, xn>, тогда
Формула А тавтология (тождественно истинная), если на любых оценках списка переменной она принимает значение «истина».
Формула А выполнима, если на некоторых оценках списка переменой она принимает значение «истина».
Формула А тождественно ложная, если на любых оценках списка переменной она принимает значение «ложь».
Формула А опровержимая, если на некоторых оценках списка переменой она принимает значение «ложь».

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

Алгоритм приведения формул  булевых функций к ДНФ (КНФ).
Шаг 1. Все подформулы A вида B C (т.е. содержащие импликацию) заменяем на \/C или на .
Шаг 2. Все подформулы A вида  B~C (т.е. содержащие эквивалентность) заменяем на (A/\B)\/ или на  .
Шаг 3.  Все отрицания, стоящие над сложными подформулами, опускаем по законам де Моргана.
Шаг 4. Устраняем все двойные отрицания над формулами.
Шаг 5. Осуществляем раскрытие всех скобок по закону дистрибутивности конъюнкции относительно дизъюнкции для ДНФ или по закону дистрибутивности дизъюнкции относительно конъюнкции для КНФ.

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

Теорема о приведении к ДНФ.
Для любой формулы А можно найти формулу В, находящуюся в ДНФ, такую что, А В

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

Теорема о приведении к КНФ. 
Для любой формулы А можно найти формулу В, находящуюся в ДНФ, такую что, А В


СДНФ: определение и примеры. Способы построения СДНФ.
Совершенной дизъюнктивной нормальной формой (СДНФ) называется такая дизъюнктивная нормальная форма, каждый конъюнктивный член которой содержит все переменные, либо их отрицания.
Построение СДНФ (по табл. ист.)
1.	Построить таблицу истинности
2.	Взять те наборы, где f=1, элементы набора соединить конъюнкцией (/\), причем: если переменная = 1, то берем переменную, если =0, то ее отрицание
3.	Соединить конъюнкции (/\) дизъюнкциями (V)

Теорема о единственности СДНФ.
Если В1 и В2 - СДНФ для А1, то В1 и В2 могут отличатся только порядком своих дизъюнктивных членов

СКНФ: определение и примеры. Способы построения СКНФ.
Совершенной конъюнктивной нормальной формой (СКНФ) называется такая конъюнктивная нормальная форма, каждый дизъюнктивный член которой содержит все переменные, либо их отрицания.
Построение СКНФ (по табл. ист.)
1.	Построить таблицу истинности
2.	Взять те наборы, где f=0, элементы набора соединить дизъюнкцией (V), причем: если переменная = 0, то берем переменную, если =1, то ее отрицание
3.	Соединить дизъюнкции (V) конъюнкциями (/\)

Теорема о единственности СКНФ.
Если В1 и В2 - СКНФ для А1 , то В1 и В2 могут отличатся только порядком своих конъюнктивных членов

Полные системы функций.  Определение и  примеры. Способы выявления полноты системы.
Система булевых функций {f1, f2, … , fn} называется полной, если любая булева функция может быть выражена в виде суперпозиции этих функций. Из равносильностей следует, что все логические операции могут быть выражены через операции конъюнкции, дизъюнкции и отрицания. Поэтому система функций {?, &, V} является полной. Также полными являются следующие системы функций:
а)?{?,  V}; б) {?, &}; в) {?, ?}.

Полином Жегалкина.
Всякая булева функция может быть представлена в виде полинома Жегалкина:
f(x1, x2,…,xn)=a0 a1x1 … anxn anx1x2 … a2n-1x1x2…xn, где a0,a1,…,an,…, a2n-1 {0,1}, где знак   обозначает сложение по модулю 2.
Алгоритм построения полинома Жегалкина.
1.	Построить таблицу истинности данной булевой функции.
2.	Каждому единичному значению булевой функции будет соответствовать конъюнкция   … , где ( , , …,  ) - соответствующий булев набор. Конъюнкции соединяются знаком  
3.	Заменить выражения   по формуле:  =xi 1. Раскрыть скобки и привести подобные слагаемые по правилу: x x=0.