Функции двух переменных

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

X	X

Функции двух переменных

XY	⋂	∪	→	~	⊕	|

⋂ - коньюнкция,

∪ (+)-дизъюнкция,

→ - импликация (x→y=`x∪y), ~ эквивалентность

(x~y=(`x ⋂`y) ∪(x⋂y)),

⊕ - сумма по модулю 2, Штрих Шеффера (x|y=`x ∪`y)

Булева функция м б задана формулой. Эквивалентные формулы – формулы предста-вляющие одну и ту же фун-ю. Проверить равенство двух фун-й можно, либо сравнив значения на всех значениях переменных, либо преобра-зовав одну к другой. (F≡G)

Совершенной дизъюнктивной нормальной формой (СДНФ) называют наиболее полную форму записи логического выражения. Эта форма записи представляет собой сумму, каждое слагаемое которой является произведением всех входных аргументов или их инверсий, например: F = `A`В`С ∪ `А В`С ∪ А В`С ∪ А В С.

В некоторых случаях более удобной формой записи логич выражения является совершенная конъюнктивная нормальная форма (СКНФ). Это произведение сомно-жителей, каждый из которых является суммой всех входных аргументов или их инверсий, например: F = (`А ∪ В ∪`С ) (`А ∪ В ∪ С ) ( А ∪`В ∪ С ) ( А ∪ В ∪ С )

Алгоритм построения СДНФ:

1. Построить таблицу истинности данной булевой функции.

2. Каждому единичному знач булевой функции будет соответствовать элементарная конъюнкция , где – соответств набор значений переменных. В конъюнкции мы записываем x_i, если σ_i=1, и `x_i , если σ_i=0. Конъюнкции соединяются знаком «∪» .
3 Комбинаторика

1.Размещен с повтор из n эл-в по k местам наз-ся упоря-доченный набор длины k <a₁,…a_k>, где a_i∈{1..n}, причём м.б. a_i=a_j.

2. Размещ без повторенийиз n эл-в по k местам наз-ся упорядоч-й набор длины k <a₁,…,a_k>, где a_i∈{1..n}, причём a_i≠a_j.

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

4.Сочетания с повторениями

5.Перестановка без повторений из n элементов – это упорядоч-й набор длины n <a₁,…,a_n>, где a_i∈{1..n}, причём a_i≠a_j. P_n=n*(n-1)*…*1 =n!

6.Перестановка с повторениями

(для разбиения n объектов на k непересек-ся клаccов)

, n=n1+….+nk, ni-число объектов в i-м классе, объекты внутри кажд. класса одинаковы.

Перестановка π множества X может быть записана в виде подстановки

4 Графы

Граф G(V,E)— это совок-ть 2-х мн-в – непустого мн-ва V (вершин) и мн-ва E (ребер) неупорядоченных пар разл-х эл-в V

Ориентир-й граф G - если эл-ми мн-ва Е являются упорядоченные пары. В этом случае элементы мн-ва V назыв узлами, а эл-ты мн-ва Е – дугами. Вершины – v_i, v_j ∈V, e= (v_i, v_j) - соедин-е их ребро. число вершин в гр |V| - порядок.

Ребро – двухэлементное множ-во {v_i, v_j} из V, (Е(v_i,v_j)>0). число рёбер |E| - размер графа.

Дуга— ребро ориентир графа (упорядоч пара вершин (v,w), где v назыв-т началом, а w - концом дуги).

Смежные вершины - вершины графа u и v, соединенные ребром, т.е. {v_i, v_j}∈ Е. Смежные рёбра – рёбра, имеющие общ-ю вершину (рёбра инцидентные одной вершине).

Вершина v и ребро e инцидентны,если эта верш явл-ся одним из концов этого ребра (если ребро соед верш, то оно инцидентно этим вершинам).

Диаграмма графа – графич изображение графа (верш-точки, кружки; рёбра - линии).

Изоморфизм. Графы G(V₁,E₁) и H(V₂,E₂) изомо-рфны, если биекция f : V₁→V₂ , сохраняющая смеж-ность: в G e₁= (u, v) ∈ E₁ ⇔ в H e₂= (f(u),f(v)) ∈ E₂. В случае ор. графа эта биекция также должна сохранять ориентацию ребра. В случае взвешенного графа - вес ребра.

Изоморфизм графов явл-ся отношен эквивалентности.

Степень вершины d(v) - кол-во рёбер, инцидентных верш. v. Изолированная вершина- верш, степень кот = 0 (d(v) = 0). Висячая вершина - верш. степень кот = 1 (d(v) = 1).

Полустепень захода в ор. графе для верш v - число дуг, входящих в вершину. Обозначается d ⁺ (v).

Полустепень исхода в орграфе для вершины v - число дуг, исходящих из верш. Обозначается d ⁻ (v).

Элементы графа

H(V’,E’) - Подграфграфа G(V,E), если V’⊆V, E’⊆E

Маршрут- это чередую-щаяся послед-ть вершин и рёбер v₀,e₁,v₁,e₂,v₂,...,e_k,v_k, в кот-й любые 2 соседних элем инцидентны. Если v₀ = v_k, то маршрут замкнут, иначе открыт.

Цепь - маршрут, все рёбра кот различны. Если все верш (а значит и рёбра) различны, то такая цепь наз-ся простой. В цепи v₀,e₁,..,e_k,v_k верши. v₀ и v_k наз-ся концами цепи.

Цикл - замкнутая цепь (нач верш. совпадает с конечн).

Путь – цепь для орграфов. Контур – цикл для орграфов.

Связность. 2 верш в графе связаны, если соеди-няющая их (простая) цепь.

1) U_α⋂U_β=∅ для любых α,β∈A, таких что α≠β;

2) , U_α - называется блоками разбиения данного множества X.

Покрытие подмножества или пространства X - это представление его в виде объединения множеств {V_α}, α∈A, . Чаще всего рассматривают открытые покрытия, т.е. предполагают что все {V_α} являются открытыми множествами.

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

Пусть даны два множества X и Y . Прямое произведение мн-ва X и мн-ва Y есть такое множество X × Y , элем кот-го являются упорядоченные пары для всевозможных x∈X и y∈Y.

Бинарным отношением на множестве M называется подмножество R декартова квадрата M×M (т. е. подмножество множества всех упорядоченных пар элементов из M).

Свойства бинарных отношений:

1) рефлексивность

<x,x>∈R, ∀x∈R

2) симметричность

<x,y>∈R, <y,x>∈R

3) транзитивность

<x,y>∈R, <y,z>∈R ⇒ <x,z>∈R

4) линейность

Отношение эквивалентности (~) на множестве X - это бинарное отношение, для которого выполнены следующие условия: рефлексивность, симметричность, транзитивность.

Классом эквивалентности С(а) , элемента «а» , наз-ся подмножество элементов, эквивалентных «а».

Бинарное отношение R на множестве X называется отношением порядка, если имеют место

1) Транзитивность:

∀x∀y∀z(xRy⋂yRz⇒xRz)

2) Антисимметричность:

∀x∀y (xRy⋂yRx⇒x=y).

Алгоритм построения СКНФ:

1. Построить таблицу истинности данной булевой функции.

2. Каждому нулевому знач булевой функции будет соответствовать элемен-тарная дизъюнкция

, где – соответств набор значений переменных. В дизъюнкции мы записываем x_i, если σ_i=0, и `x_i, если σ_i=1. Дизъюнкции соединяются знаком «⋂».

Пусть имеется некоторый набор K, состоящий из конечного числа булевых функций. Суперпозицией функций из этого набора называются новые ф-ии, получ с помощью конечного числа применения двух опе-раций; (можно переименовать любую переменную, вход в функцию из K; вместо любой переменной можно поставить функцию из набора K или уже образованную ранее суперпозицию). Суперпозицию еще иначе называют сложной функцией.

Пример: Если дана одна фун-я х|y (штрих Шеффера), то ее суперпозициями, будут след-ующие функции x|x, x|(x|y), x|(y|z) и т. д.

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

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

Теорема Поста. Система булевых функций F является полной тогда и только тогда, когда она не содержится ни в одном из классов T₀, T₁, L, M, S. Т.е необх и дост, чтобы в него входили функции, не принадлежащие ∀ из классов.

Т₀ – это набор всех тех логич функций, которые на нулевом наборе принимают значение 0 (класс фун-й, сохраняющих 0);

Т₁ – это набор всех логич функций, кот-е на единичном наборе принимают значение 1 (класс фун-й, сохраняющих единицу) L – класс линейных функций М – класс монотонных функций S – класс самодвойственных функций

,

где {x₁,…,x_n}={ y₁,…,y_n }=X и π(x_i) = y_i.

Взаимнооднозн-я функция π: X→X наз-ся подстановкой на X.

Пусть есть подстановка π которая тождественна на всём мн-ве X, кроме подмн-ва {x₁,…,x_l}.

Циклом длины l называется посл-ть {x₁,…,x_l}, такая что , π(x_i) = x_i+1. для 0≤i<l.

Биномиальные коэффиц — коэфф-ты в разложении (1 + x)ⁿ по степеням x

Зн-е бином-го коэф-та определено для всех целых чисел n и k.

Бином Ньютона - это формула где – бином-е коэф-ты, n-неотриц.цел. число.

Бином-й коэфф-т явл-ся обобщением числа сочетаний , которое определено только для неотриц-х целых чисел n, k.

Св-ва:

1.

2.

3.

Тождество позволяет расположить бином-е коэфф-ты для неотриц-х n, k в виде треугольника Паскаля, в котором каждое число равно сумме двух вышестоящих.
Граф в кот все вершины связны наз-ся связным.

Компоненты связности графа — некоторое мн-во вершин графа такое, что для ∀ 2-х вершин из этого мн-ва путь из одной в др-ю, и не пути из верш этого мн-ва в вершину не из этого мн-ва.(max по включению связный граф) (классы эквивал-ти по отношению к связности). Число компопнет связности К(G). Связный граф -К(G) = 1 Несвязный - К(G)>1.Ор. граф наз-ся сильно связным, если любые 2 его вершины сильно связаны. вершины s и t сильно связаны, если ориентир-й путь из s в t и из t в s. Сильно связными компонентами орграфа наз-ся его max сильно связные подграфы. Длина маршрута - кол-во рёбер в маршруте (с повторен-ми). Если маршрут M = v₀,e₁,v₁,e₂,v₂,...,e_k,v_k, то длина M = k . Расстояние м/у верш– длина кратч-шей цепи.

Диаметр гр- max расстояния м/д верш-ми для всех пар верш.Условный радиусграфа G относит вершины “c” опред формулой: , V(G) – мн-во вершин. d(x,y) – расстояние м/у вершинами x и y.Радиус графа - опред-ся как наим-й из усл. радиусов графа.

Виды графов

Тривиальный граф - граф, состоящий из 1 вершины.

Пустой граф - граф, не содержащий ребер.

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

Двудольный граф - граф, у кот такое разбиение мн-ва вершин на 2 части (доли), что смежными яв-ся только вершины из разных долей.

Полный двуд-й гр– двуд-й гр, у кот.любые 2 вершины, входящие в разные доли, смежны.

Операции над графами

Дополнением графа G(V1,E1) наз-ся граф H(V2,E2): V1=V2, E2={ }. (к G доб-ть E2 -G полный)

Объединение графов F и G - граф где и . Объединение дизъюнктное, если Ø.

Соединение графов G₁ и G₂ где V(G1)⋂V(G2)=Ø и E(G1)⋂E(G2)=Ø – граф G=G₁+G₂ : V(G)=V(G1)∪V(G2) и

Удаление вершины v из гр G - граф G\v, содержащий все вершины G, кроме v, и все ребра G, не инцидентные v.

Удаление ребра e из графа G - граф G \ e, содерж все верш и все ребра графа G за исключением e.Добавление ребра e в G- граф G + e, полученный соединением ребром e 2-х несмежных вершин G. Добавление вершины - преобразование графа G в граф G + v

Дерево- связный неориентированный граф, не содержащий циклов.

5. Алгоритмы на графах

Представление графов в памяти ЭВМ ] n - число вершин, а m – ребер в G

Матр смежности- матрица A(G) размером n x n, эл-т A_ij кот-й = 1, если вершины v_i и v_j смежны (соединены дугой или ребром), и = 0 в противном случае. Для неориент графа мат.см. есть симметричная матр с нулями на главной диагонали. В м.с. для мультиграфов и псевдографов (i,j)-й элемент равен числу ребер, соединяющих вершины v_i и v_j (при этом петля считается как два ребра).М.с. определяет граф (орграф, мультиграф, псевдограф) с точностью до изоморфизма. Объем памяти О(n²)

Матрица инцидентности- матрица I(G) размером n x m, элемент A_ij которой = 1, если верш v_i инцид ребру e_j в неор графе или если v_i - начало дуги e_j в ориен; = -1, если вершина v_i - конец дуги e_j (только для ор графов), и = 0 в остальных случ. М.и. опред-т граф с точностью до изоморфизма. ОП=О(nm)

Список смежности- для ∀ верш графа хранит список верш, смежных с ней. Предс-тавление графа с помощью списочной стр-ры, отраж смежность верш и состоящей из массива указателей на списки смежных вершин. ОП=O(n+m)

Массив рёбер (дуг) – это массив, в кот ребра хранятся парами верш, кот-е они соед.

Это наиболее понятный, но достаточно неудобн способ хранения графа. Большой плюс - легко вводить дополн хар-ки ребер. ОП=О(2m)