Шпаргалка по "Программированию и компьютерам"

 1. Множества. Операции  с множествами.  Упорядоченное множество.  Прямое произведение  множеств.

 Множества

 Понятие мн-ва принадлежат к числу исходных матем понятий оно строго не определено.

 Множество – объединение в единое целое  вполне различимых объектов. Бывают бесконечные (математические) и конечные (нематематические). Вхождение элемента a в множество A обозначается как a Î A.

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

 Их 5:

 1) Объединение  множеств A и B состоит из элементов, принадлежащих A, и элементов, принадлежащих B, и обозначается как AÈB;

 2) Пересечение  множеств A и B состоит из элементов, принадлежащих одновременно и A и B, и обозначается как AÇB;

 3) Разность  множеств A и B состоит из элементов, принадлежащих A, но не принадлежащих B, и обозначается как A/B;

 4) Дополнение множества A состоит из элементов, принадлежащих универсальному множеству, но не принадлежащих A, и обозначается как ØA;

 5) Симметрическая  разность множеств A и B состоит из элементов, принадлежащих только A, и элементов, принадлежащих только B, и обозначается как ADB.

 Упорядоченное множество

 Упорядоченное множество (кортеж) – конечная последовательность элементов некоторого множества, т.е. совокупность, в которой каждый элемент  стоит на определённом месте. В отличие  от множеств, элементы кортежей могут  повторяться. Обозначается <a₁, a₂,…, a_n> или (a₁, a₂,…, a_n), где

• n – длина кортежа,
• a_i– i-ая компонента кортежа.

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

 Прямым  произведением 2-х мн-тв А и В  наз-ся мн-во АхВ состоящие из всевозможных упорядоченных пар (а,b) где aÎA , bÎB ( АхВ ={(а,b): aÎA, bÎB})

 Аналогично  определяется прямое произв n-множеств. 

 5. Нормальные формы  формул. Представление  логической функции  в виде формулы  алгебры логики.

 Нормальные  формы формул

• Дизъюнктивная нормальная форма (ДНФ)

 Формула называется элементарной конъюнкцией, если она представляет собой конъюнкцию (возможно, одночленную) переменных или их отрицаний. Пример: (Øx₁ & Øx₂ & x₃). Формула находится в ДНФ, если она представляет собой дизъюнкцию (возможно, одночленную) элементарных конъюнкций. Пример: (Øx₁ & Øx₂) Ú (x₂ & x₃).

• Конъюнктивная нормальная форма (КНФ)

 Формула называется элементарной дизъюнкцией, если она представляет собой дизъюнкцию (возможно, одночленную) переменных или  их отрицаний. Пример: (Øx₁ Ú Øx₂ Ú x₃). Формула находится в КНФ, если она представляет собой конъюнкцию (возможно, одночленную) элементарных дизъюнкций. Пример: (Øx₁ Ú Øx₂) & (x₂ Ú x₃).

• Совершенная дизъюнктивная нормальная форма (СДНФ)

 Формула находится в СДНФ, если:

 1) она  находится в ДНФ;

 2) в  каждую элементарную конъюнкцию входят все переменные или их отрицания, причём на i-ой позиции находится x_i или Øx_i;

 3)  все дизъюнктивные члены различны.

 Пример: (Øx₁ & x₂ & x₃) Ú (x₁ & Øx₂ & x₃).

 СДНФ  формулы определяется однозначно с  точностью до порядка дизъюнктивных  членов (теорема о единственности СДНФ).

• Совершенная конъюнктивная нормальная форма (СКНФ)

 Формула находится в СКНФ, если:

 1) она  находится в КНФ;

 2) в  каждую элементарную дизъюнкцию  входят все переменные или  их отрицания, причём на i-ой позиции находится x_i или Øx_i;

 3)  все конъюнктивные члены различны.

 Пример: (Øx₁ Ú x₂ Ú x₃) & (x₁ Ú Øx₂ Ú x₃).

 Представление логической функции  в виде формулы  алгебры логики

• Первая теорема Шеннона о представлении булевой функции.

 Пусть рассматривается k-местная функция f (x₁, …, x_k), не равная тождественно 0. Тогда существует формула алгебры логики F, определяющая функцию f и находящаяся в СДНФ. Формула F определяется однозначно с точностью до порядка дизъюнктивных членов.

 Пусть x¹ = x, x⁰ = Øx. Тогда F = Ú (x₁^s1 & … & x_k^sk) для всех (s₁, …, s_k), для которых f (s₁, …, s_k) = 1.

• Вторая теорема Шеннона о представлении булевой функции.

 Пусть рассматривается k-местная функция f (x₁, …, x_k), не равная тождественно 1. Тогда существует формула алгебры логики F, определяющая функцию f и находящаяся в СКНФ. Формула F определяется однозначно с точностью до порядка конъюнктивных членов.

 Пусть x¹ = x, x⁰ = Øx. Тогда F = & (x₁^Øs1 Ú … Ú x_k^Øsk) для всех (s₁, …, s_k), для которых f (s₁, …, s_k) = 0. 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

 2. Определение графа.  Операции с графами. Связность графа, сильно связный граф. Транзитивное замыкание.

 Определение графа

 Граф – совокупность G = (V, X), где

• V = {v₁, …, v_n} – множество вершин,
• X={(v_i, v_j) | v_i, v_j Î V} – множество дуг [т.е. граф – совокупность вершин и соединяющих их дуг].

 При этом дуга (v_i, v_j) называется исходящей из вершины v_i и заходящей в вершину v_j. Петля – дуга (v, v).  Мультиграф – граф с кратными (одинаковыми) дугами. Псевдограф – граф с кратными дугами и петлями. Элементарный граф – граф без кратных дуг и петель. Неориентированный граф – граф, пары множества X которого неупорядочены [т.е. граф, вершины которого соединены двунаправленными дугами – рёбрами].

 Способы задания графа:  стрелки, в виде соответствий,  булева матрица, описание Бержа.

 Операции  с графами

• Объединение

 Объединением  графов G₁ (V₁, X₁) и G₂ (V₂, X₂) называется граф G₁ È G₂ = (V₁ È V₂, X₁ È X₂) [т.е. граф, содержащий все вершины и дуги графов G₁ и G₂].

• Пересечение

 Пересечением  графов G₁ (V₁, X₁) и G₂ (V₂, X₂) называется граф G₁ Ç G₂=(V₁ Ç V₂, X₁ Ç X₂) [т.е. граф, содержащий все вершины и дуги, принадлежащие одновременно графам G₁ и G₂].

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

 Декартовым  произведением графов G₁ (V₁, X₁) и G₂ (V₂, X₂) называется граф G₁ x G₂ = (V₁ x V₂, Г), где для каждой вершины U = (v, w) Î V: Г_u = Г_v x Г_w.

 (Г_v – образ вершины v [т.е. множество смежных с z вершин – вершин {v₁,…, v_k}, для которых существуют дуги (v,v₁),…,(v, v_k)]).

• Декартова сумма

 Декартовой  суммой графов G₁ (V₁, X₁) и G₂ (V₂, X₂) называется граф G₁ + G₂ = (V₁ x V₂, Г), где для каждой вершины U = (v, w) Î V: Г_u = {v}x Г_w È Г_v x {w}.

 Связность графа, сильно связный  граф

 Неориентированный граф G называется связным, если существует путь между любыми двумя его вершинами v_i и v_j. Ориентированный граф G называется сильно связным, если любые две его вершины v_i и v_j взаимодостижимы [т.е. существуют пути из v_i в v_j и из v_j в v_i].

 Транзитивное  замыкание

 Прямым  транзитивным замыканием вершины v называется множество вершин, достижимых из v. Обратным транзитивным замыканием вершины v называется множество вершин, из которых достижима v. 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

 3. Нагруженный граф. Пути в графе.  Нахождение минимального  пути в графах.

 Нагруженный граф

 Нагруженный граф – граф G = (V, X), для которого задана функция len: X ® R, ставящая в соответствие каждой дуге этого графа некоторое вещественное число, len(x Î X) – длина (вес) дуги x [т.е. граф, дугам которого соответствуют некоторые вещественные значения, например, их длины или веса].

 Пути в графе

 Путь [между вершинами v₁ и v_k] – последовательность v₁, x₁, v₂, x₂, …, v_k-1, x_k-1, v_k, где v_i – вершина, x_i=(v_i,v_i+1) [т.е. последовательность попарно соединённых дугами вершин]. Цикл – замкнутый путь [т.е. путь, у которого первая и последняя вершины совпадают], все дуги которого различны. Простой цикл – цикл, в котором все вершины различны. Цепь – незамкнутый путь, все дуги которого различны. Простая цепь – цепь, в которой все вершины различны. Длина пути (для ненагруженного графа) – количество дуг, входящих в этот путь. Длина пути (для нагруженного графа) – сумма весов дуг, входящих в этот путь. Минимальный путь [между вершинами v₁ и v_k] – путь, имеющий минимальную длину среди всех других путей [из v₁ в v_k].