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

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

Прямым произведением множеств X u Y называется множество, состоящее из всех тех и только тех пар, первая компонента которой Х, а вторая Y.

X*Y

Пример:

X = {a,b} Y = {1,2,3}

X*Y={<a,1>,<a,2>,<a,3>,<b,1>,<b,2>,<b,3>}

X*Y Y*X

(*) X1,X2,…Xn

Прямым произведением множества (*) называется множество, состоящее из всех тех и только тех картежей длины l, первая компонента которой Х1, вторая Х2... и n Xn,Это множество обозначается: X1*X2*…*Xn = {<x1,x2,…xn>| x1 X1……}

Отношения, бинарные отношения.

Рассмотрим вспомогательное понятие картеж.

Упорядоченная пара <x,y> интуитивно определяется, как совокупность, состоящая из 2-х элементов х Х и y Y, расположенных в определённом порядке.

Две пары <x,y> u <U,V> равны тогда и только тогда, когда x=U, y=V

<1,z> <z,1>

Картеж или упорядоченный набор n элементов x1 X1, x2 X2…. xn Xn обозначается <x1,x2,x3…xn> и по определению есть <<x1,x2,x3….xn-1>,xn>.

Два картежа и :

=<x1,x2…..xn>

=<y1,y2….ym> равны тогда и только тогда, когда n = m и (x1=y1 X1

x2=y2 X2)

Число n – называется длинной картежа, а элементы xi – итой проэкцией (координата компоненты картежа).

Операции над отношениями.

1. Для бинарных отношений обычным образом определены все теоретико-множественные операции: , ,\, ,+,*

2. Обратное отношение: обратным (инверсным) отношением называется отношение

={<x,y>| <y,x> }

3. Композиция отношений:

а) X*Y

Z*Y

Композицией двух бинарных отношений и называется отношение X*Y, которая определяется следующим образом:

= ={<x,y>| x X, y Y и Z x y и z y}

б) Композиция отношений на множестве X:

= ={<x,y>| , что x z и z y}

Замечание:

Композиция отношений на множестве X порождает понятие: степень отношения

= ^2 = ^3 ^n= ^n-1

 

Понятие функции. Инъективные, биективные, суръективные функции. Композиция и обращение функций.

Бинарное отношение f называется функцией, если <x,y> f и <x,z> f y=z.

Замечание:

1) Если Df=X,а Rf Y, то говорят что функция f задана на множестве Х со значениями во множестве Y и осуществляет отображение X в Y.

f:X Y

2)Если f функция, то вместо <x,y> f пишут y=f(x), где y-образ элемента x, при отображении f, а x-прообраз элемента y.

Lx={<x,x>| x X} Lx: x X Lx(x)=x

Пусть задана f: x y:

-Функция (отображение f) называется инъективной, если х1,х2, y из того, что y=f(x1), y=f(x2) x1=x2

-Функция называется суръективной, если для всякого y существует такое х, что y=f(x)

-Функция называется биективной, если f одновременно: инъективна и суръективна.

Замечание: Если существуeт функция f: x y, то говорят, что f – осуществляет взаимное однозначное соответствие, между множествами X и Y, а f: x X называется подстановкой.

Можно доказать следующие утверждения:

- композиция 2-х функций, есть функция.

- композиция 2-х биективных функций, есть биективная функция.

- отображение f: x y имеет обратное отображение f : y x тогда и только тогда, когда f – биекция.

 

Бинарные отношения на множестве Х. Рефлексивность, симметричность, транзитивность бинарных отношений на множестве Х.

n – арным отношениями между элементами множеств x1,x2,x3…..xn называется произвольное подмножество их прямого произведения x1*x2*…..*xn

x1*x2*x3….xn

Бинарным (двуместным) отношением между 2 множествами x и y, называется произвольное подмножество их прямого произведения.

x*y

Замечания:

1. Если x=y, то говорят, что -есть отношение на множестве Х.

x*х

2. Множество х называется множеством области отправления, а y множеством области прибытия бинарного отношения.

3.Тот факт, что x X, y Y находиться в отношении , т.е <x,y> будем записывать в виде x y

Свойства:

1. Рефлексивонсть:

x*х называется рефлексивным, если x X x х или (<x,x> )

2. Симметричность:

x*х называется симметричной, если x,y X x y y x или (<x,y> <y,x> )

3.Транзитивность:

x*х называется транзитивным, если x,y,z X из того, что x y и y z –

x z (<x,y> и <y,z> след <x,z> )

Отношение эквивалентности. Класс эквивалентности.

Отношение рефлексивное, симметричное и транзитивное одновременное на множестве Х называется отношением эквивалентности.

Классом эквивалентности порождённым элементом «х» называется подмножество множества Х, которое состоит из тех «у є х», которое состоит из «у є х» для которых «х ро у».

 

Двойственность. Закон двойственности. Пример.

Замечание: будем рассматривать формулы, которые содержат только логические связки ͞, V, &

Связки V, & назовем двойственными друг к другу. Формулы А и А˟ называются двойственными, если одна получена из другой одновременной заменой связок V, & на двойственную к ним.

Утверждение: )

– высказывательная переменная (или отрицание высказ. Переменной)

Закон двойственности

Если формулы А и В равносильны, то и двойственные к ним А˟ и В˟ равносильны тоже.

А=В => А*=В*

Пример.

А= (͞х₁&х₂& х₃)V(х₁ & ͞х₂) V х₃

А*= (͞х₁Vх₂V х₃)&(х₁ V ͞х₂) & х₃

 

Тождественно-истинные и тождественно-ложные формулы. Выполнимость и опровержимость формул. Пример. Правильные рассуждения.

Пусть формула А зависит от списка переменных <х₁, …, х_n>

Формула А называется тождественно-истинной (ложной), если на любых оценках списка переменных формула А принимает значение И (Л).

Формула А называется выполнимой (опроверженной), если существует такая оценка списка переменных, на которой формула А принимает значение И(Л).

1)АV ͞А

2)А>A

3)A>(B>A)

4)A~A

5)((A>B)&A)>B

6)((A>B)& ͞B)> ͞A

7)((A>B)&(B>C))>(A>C)

8)(A>B)~(͞B > ͞A)

 

Отношение логического следования. Правильные рассуждения. Примеры.

Пусть формулы А и В зависят от списка переменных <х₁, …, х_n>. Говорят, что формула В логически следует из формулы А тогда, когда их импликация – тождественная формула.

А | = В <=>A>B = И

Замечание:

1)Если В| = А, то говорят, что В выводима из А (А|- В), А\В)

2)Тождественно-истинная формула всегда выводима.

Правильные рассуждения.

В рассуждения, выводя одно высказывание из другого, мы пользовались законами логики. Тождественно истинные формулы логики высказываний выражают законы логики. Разумеется законы логики выражающиеся средствами логики высказываний не исчерпывают все законы логики использующиеся в рассуждениях. Законы логики высказываний могут служить основой лишь для тех выводов, в которых учитывается структура элементарных высказываний. Отвлекаясь от такого рассуждения, т.е. заменяя в нём элементарные высказывания высказывательными переменными мы получаем следующую схему вывода(умозаключения):

 

Формула

,причем различные значения n соответственно различные кортежи i(Ɛi₁ … Ɛi_n)

Формулы

Любая булева функция представлена СДНФ т.е. виде

f(х₁, х₂ … х_n) = V (x₁^Ɛi & x₂^Ɛi &… & x_n^Ɛi)

<Ɛi₁, Ɛi₂ …Ɛi_n>

F(Ɛi₁, Ɛi₂ …Ɛi_n) =1

 

Представление булевых функций формулой логики высказываний в СДНФ и в СКНФ. Примеры.

Рассм кортеж из нулей и единиц <ε1,ε2,...,εn>

Xiεi = xi, если εi=1; xi, если εi=0; Xiεi = 1 тогда и только тогда, когда Xi = εi;

Теорема(о разложении булевой ф-ции): каждая булева функция f(x1,x2,...,xn) (n≥1), не равная тождественно нулю может быть представлена в виде:

f(x1,x2,...,xn)=∨i=12^n(&j=1nXεij&f(εi1, εi2,..., εin)) причем различным значениям i соответствуют различные кортежи < εi1, εi2,...,εin))

Следствие: любая булева функция представима в СДНФ, т.е. в виде

f(x1,x2,...xn)= ∨(Xεi11& Xεi22&... Xεinn), где

<εi1,εi2,...,εin> - оценка

<f(εi1,εi2,...,εin)> - значение оценки

Замечание: Аналогично доказывается теорема о представлении булевой функции в виде:

&i=12^n(∨j=1nxj1-εij∨f(εi1,εi2,...,εin))

следствием из которой является формула

&(x11-εi1∨x21-εi2∨...xn1-εin), где

<εi1,εi2,...,εin>

f(εi1,εi2,...,εin) =0

Рассм пример булевой функции и найдем СДНФ и СКНФ

Для СДНФ - выделяем участки списка, где функция приняла значение 1

f(x1,x2)=(x1&x2)∨(x1&x2)∨(x1&x2) - СДНФ

Для СКНФ - берем оценку и вычитаем из единиц 11-10=01, возводим в степень оценки(более подробно см семинар 8-ое задан

№ x1 x2 f(x1,x2)

ие)

f(x1,x2)=x1∨x2 - СКНФ

К слову f(x1,x2)=x1⊃x2

 

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

О: Система булевых функций {f1,f2,...,fm} из множества всех булевых функций называется полной, если любая булева функция может быть выражена через функции с помощью суперпозиций (подстановки функций в функцию)

 

k0={f1(x1,....,xn),f2(x1,...,xn),....,fm(x1,...xn)}

 

Функция f называется суперпозицией ранга 1(элементарной суперпозиций) функции f1,...,fm, если f может быть получено одним из след. способов:

1) из какой нибудь функции fi, переименованием переменной xj.

f(x1,x2,...,xj,...xn)

2) подстановкой некоторой функции fl, где l=1,2,...,n вместо какого нибудь аргумента xj, взятого из множества k0

f(x1,x2,...,fl(x1,...,xn),...xn)

Суперпозиция ранга 1 образует класс функций k1. Суперпозиция ранга r образует класс функций kr. Класс kr строится с помощью элементарных суперпозиций над классом kr-1

Суперпозициями функциями из k0 называются функции входящие в один из классов k0,k1,k2,...,kr.

Теорема: Пусть даны 2 системы булевых функций:

1) F={f1,f2,...fm) ①

2) G={g1,g2,...,gl) ②

относительно которых известно, что 1ая система полна и каждая её функция fi выражается через функции системы ② в виде формулы, тогда и вторая система полна.

z=z(f1,f2,...,fm)=z(f1(g1,...,gl),...fm(g1,....,gl))=R(g1,...,gl)

Примеры

1. {,&} - испытуемая ②

{,∨,&} - ①

Выразим x1∨x2=(x1∨x2)=(x1&x2)

 

2. {, ∨} ②

x1&x2=(x1&x2)=(x1∨x2)

{∨,&} - не выйдет

 

3. {|} - ②

{,&} - ①

x=x|x

x1&x2=(x1|x2)|(x1|x2)

 

30. Полнота системы {+, ∙, 1}. Многочлены Жегалкины. Приведение любой булевой функции к многочлену жегалкина.

{+, ∙, 1}, где ∙=&

О: Булевы функции записанные в этой системе в виде многочлена называются многочленами Жегалкина.

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

1) Законы коммутативности

x1+x2=x2+x1;

x1∙x2=x2∙x1;

2) Законы асоциативности

x1+(x2+x3)=(x1+x2)+x3

x1(x2∙x3)=(x1∙x2)x3

3) x1(x2+x3)=x1x2+x1x3 - закон дистрибутивности

4) 0+х=х

5) 0∙х=0

6) 1∙х=х - действие с единицей

и двух специальных правил:

7) х+х=0

8) х∙х=х

СПОСОБЫ ПРЕДСТАВЛЕНИЯ БУЛЕВЫХ ФУНКЦИЙ МНОГОЧЛЕНАМИ ЖЕГАЛКИНА.

1 способ

1. Преобразуем булеву функцию в булеву функцию заданную в системе {,&}

2. Заменяем х=х+1, &=∙

3. Применяем 8 правил алгебры Жегалкина, находим его многочлен.

2 способ

1. Находим СДНФ

2. Заменяем дизъюнкцию на f=∑⊕(x1εi1∙....∙xnεin)=Fi+Φi^

3. Применяем 8 правил и находим многочлен Жегалкина

Пример 1-ого способа:

x1∨x2=(x1∨x2)=(x1&x2)=(x1+1)(x2+1)+1=x1x2+x2+x1+1+1=x1x2+x1+x2.

Пример 2-ого способа:

х1∨х2=(x1&x2)∨(x1&x2)∨(x1&x2)=(x1&x2)+(x1&x2)+(x1&x2)=(x1+1)x2+x1(x2+1)+x1x2=x1x2+x2+x1x2+x1+x1x2=x1x2+x2+x1

 

Ориентированные и неориентированные графы. Основные понятия.

ОРИЕНТИРОВАННЫЕ ГРАФЫ.(ОРГРАФЫ)

Пусть Х не пустое множество, а Х2=Х×Х - множество всех его пар.

О: Пара <Г,Х>=G называется ориентированным графом (орграфом), где Г-произвольное подмножество множества Х2 (Г⊆Х2)

Элементы х∈Х называются вершинами, а пара <X,Y>∈Г дугами орграфа.

Замечание: тройку множеств <Г,Х,Y>, где Г⊆Х,Y называют многозначным отображателем из множества Х во множестве У. Обозначают Г:Х+Y.

При этом, если х∈Х, то множество Г(х)={y∈Y|<x,y>∈Г}⊆Y называют образом элемента х, а Г-1(y)={x∈X|<x,y>∈Г}⊆X называют прообразом y.

Если А⊆Х, то Г(А)=∨х∈АГ(х) - это образ множества А

А⊆Y, то Г-1(А)=∨y∈AГ-1(А) - это прообраз мн-ва А

Пусть задан орграф G=<Г,Х>

1. если y∈Г(х), т.е. <x,y> дуга, то говорят что она исходит из вершины х и заходит в у.

2. Дуга называется инцидентной в вершине х, если она заходит в х или исходит из х.

3. Дуга <x,х> называется петлей.

4. Вершина, не имеющая инцидентных дуг называется изолированной. Две вершины называются смежными, если существует дуга инцидентная им обоим.

Пути в орграфе.

О1: Последовательность дуг орграфа такая что начало каждой последующей дуги совпадает с концом предыдущей называется путем.

О2: Путь у которого начало первой дуги совпадает с концом последней называется замкнутым путем, или контуром.

О3: Путь (контур) называется элементарным, если все его вершины различны за исключением первой и последней.

О4:Путь (контур) называется простым, если все его дуги различны.

Примеры:

1) <x1,x2> <x2,x5> <x5,x4> - не контур, но простой эл-ый путь.

2) <x1,x2> <x2,x3> <x3,x1> - эл-ый простой путь, контур.

3) <x1,x2> <x2,x5> <x5,x4> <x4,x2> <x2,x3> <x3,x1> - контур, простой, не эл-ый

4) <x1,x2> <x2,x3> <x3,x1> <x1,x2> <x2,x3> <x3,x1> - не простой, не эл-ый, контур

5) <x1,x2> <x2,x5> <x5,x4> <x4,x2> <x2,x3> - не путь

НЕОРИЕНТИРОВАННЫЕ ГРАФЫ

Пусть Х-непустое множество. Х(2) - мн-во всех 2-х элементарных подмножеств множества Х.

Пример: Х={1,2,3}. X(2)={{1,2},{1,3},{2,3}}

О: Пара <Q,X>=G, где Q произвольное подмножество множества Х (Q⊆X) называется неориентированным графом. Элементы х∈Х - вершинами, а элементы {x,y}∈Q - (неупорядоченные пары) - ребрами.

Замечание: неориентированные графы можно изучать как графы симметричных бинарных отношений.

Подграфом графа G называется G’, если X’⊂X, Q’⊂Q (Г’⊂Г), а в случае если X’=X, то подграфом называют частичным графом.

О1: Цепью неориентированного графа называется последотельность ребер, которая может быть перемещена в путь введением соответствующей ориентации на её ребрах.

О2: Циклом называется цепь у которой 1-ая вершина совпадает с последней.

О3: Цепь (цикл) называется элементарной, если некоторая вершина встречается в ней не более одного раза.

О4: Цепь (цикл) называется простой, если некоторой ребро встречается в ней не более одного раза.

 

37.Матричное задание графа. Матрицы сложности и инциденций. Цикломатическая матрица.

G=<Г,х>, |x|=n, x={

Пример:

 

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

– называется степенью вершины.

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

1 – существует ребро.

0 – в остальных случаях.

Степень – число инцыдентных вершине рёбер.

Матрица инциденций:

G=<Г,х>, |x|=n, |Г|=N, x={

Пусть граф не имеет петель.

Замечание: для неориентированного графа инциденты определяются следующим образом:

Цикломатическая матрица:

G=<Q,x> - неор. граф.

n- вершины, N – ребра.

- простые элементарные циклы, преобразуем в орграф:

Алгоритм Форда

Помечаем вершину xi индексом λi; Полагаем a=x6 и присваиваем ей λ6, причем λ0=0, а все остальные вершины помечаем λj=∞.

Помечаем <xi,xj> для которой λi- λj˃l(xi,xj), затем заменяем индекс λj на индекс λ/J; λ/J= λi+ l(xi,xj)< λj

Продолжаем процесс до тех пор пока не перестанут уменьшаться индексы.

Предположим что алгоритм Форда выполним, тогда λn= λρ0.

Среди дуг будет та по которой алгоритм Форда применим:

λn- λρ1= l(x ρ1, xn)

λ ρ1- λρ2= l(x ρ1, x ρ1)

…………………

λ ρk- λ0= l(x 0, x ρk)

________________ (сложим все эти равенства)

λ n= l(x 0, x ρk…………. x n).

Возьмем x 0, x k1…………. x n предположим что он короче чем тот который мы нашли по алгоритму Форда: Λ0, λк1……………………………………………. λкn, -индексы присвоены по алгоритму Форда, где выполняется:

Λk1- λ0≤ l(x 0, xr1)

λ k2- λk1≤ l(x k1, x k2)

…………………

λ n- λks≤ l(x ks, x n)

________________ (сложим все эти равенства)

λ n≤l(x 0, x k…………. x n). значит метод Форда минимальный путь.

Алгоритм Форда-Беллмана.

Замечание: он позволяет по таблице значений λ(к)i (i=1…..n), (k=0,1……..n-1) и матрицы длин дуг нагруженного орграфа определить минимальный путь из вершины а в любую достижимую вершину, причем из всех возможных путей он выделяет путь с наименьшим числом дуг.

λ(к)i=

Замечание: к=0,1…………….n-1, λ1(к)=0; λ(0)i=∞, i=2,3…….n.

Матрицу весов С опишем следующим образом

Cij=

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

λ(к+1)j=

Цикломатическая (контурная) матрица и матрица инциденций. Законы Киргофа. Уравнение контурных токов. Примеры.

Матрица инциденций.

Пусть задан граф G имеет N дуг и ребер и не имеет петель:

G=<Г, х>; │х│=n; Х={x1………xn}; │Т│=N; =││Sij││;

(-1 -если j дуга инцидентная i и вершина заходит в нее.

Sij= (1 -если j дуга инцидентная i и вершина исходит из нее.

(0 -если j дуга не инцидентная i и вершина.

Замечание: для неориентированного графа Sij определяется:

1-если j ребро инциденции i вершины

0- в противном случае

Sij =

 

Цикломатическая матрица.

G=<Q, х>;(n- вершины; N-ребра) граф в котором μ1, μ2,……………………,μк – простые элемент циклы графа. Преобразуем неориентированный граф в ориентированный

задав произвольную ориентацию на его ребрах, введем матрицу .Элементы матрицы: Примеры.

в - матрица инциденций.

 

Законы Киргофа

1 закон - SI=0; S= [I1…………IN}]T

2 закон- BU=0; B=[U1…………UN}]T

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

Как известно, любая электрическая цепь, состоящая из Р рёбер (ветвей, участков) и У узлов, может быть описана системой уравнений в соответствии с 1-м и 2-м законами Кирхгофа. Число уравнений в такой системе равно Р, из них У–1 уравнений составляется по 1-му закону Кирхгофа для всех узлов, кроме одного; а остальные Р–У+1 уравнений – по 2-му закону Кирхгофа для всех независимых контуров. Поскольку независимыми переменными в цепи считаются токи рёбер, число независимых переменных равно числу уравнений, и система разрешима.

Существует несколько методов сократить число уравнений в системе. Одним из таких методов является метод контурных токов.

Метод использует тот факт, что не все токи в рёбрах цепи являются независимыми. Наличие в системе У–1 уравнений для узлов означает, что зависимы У–1 токов. Если выделить в цепи Р–У+1 независимых токов, то систему можно сократить до Р–У+1 уравнений. Метод контурных токов основан на очень простом и удобном способе выделения в цепи Р–У+1 независимых токов.

Метод контурных токов основан на допущении, что в каждом из Р–У+1 независимых контуров схемы циркулирует некоторый виртуальный контурный ток. Если некоторое ребро принадлежит только одному контуру, реальный ток в нём равен контурному. Если же ребро принадлежит нескольким контурам, ток в нём равен сумме соответствующих контурных токов (с учётом направления обхода контуров). Поскольку независимые контура покрывают собой всю схему (т.е. любое ребро принадлежит хотя бы одному контуру), то ток в любом ребре можно выразить через контурные токи, и контурные токи составляют полную систему токов.

 

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

Прямым произведением множеств X u Y называется множество, состоящее из всех тех и только тех пар, первая компонента которой Х, а вторая Y.

X*Y

Пример:

X = {a,b} Y = {1,2,3}

X*Y={<a,1>,<a,2>,<a,3>,<b,1>,<b,2>,<b,3>}

X*Y Y*X

(*) X1,X2,…Xn

Прямым произведением множества (*) называется множество, состоящее из всех тех и только тех картежей длины l, первая компонента которой Х1, вторая Х2... и n Xn,Это множество обозначается: X1*X2*…*Xn = {<x1,x2,…xn>| x1 X1……}

Отношения, бинарные отношения.

Рассмотрим вспомогательное понятие картеж.

Упорядоченная пара <x,y> интуитивно определяется, как совокупность, состоящая из 2-х элементов х Х и y Y, расположенных в определённом порядке.

Две пары <x,y> u <U,V> равны тогда и только тогда, когда x=U, y=V

<1,z> <z,1>

Картеж или упорядоченный набор n элементов x1 X1, x2 X2…. xn Xn обозначается <x1,x2,x3…xn> и по определению есть <<x1,x2,x3….xn-1>,xn>.

Два картежа и :

=<x1,x2…..xn>

=<y1,y2….ym> равны тогда и только тогда, когда n = m и (x1=y1 X1

x2=y2 X2)

Число n – называется длинной картежа, а элементы xi – итой проэкцией (координата компоненты картежа).

Операции над отношениями.

1. Для бинарных отношений обычным образом определены все теоретико-множественные операции: , ,\, ,+,*

2. Обратное отношение: обратным (инверсным) отношением называется отношение

={<x,y>| <y,x> }

3. Композиция отношений:

а) X*Y

Z*Y

Композицией двух бинарных отношений и называется отношение X*Y, которая определяется следующим образом:

= ={<x,y>| x X, y Y и Z x y и z y}

б) Композиция отношений на множестве X:

= ={<x,y>| , что x z и z y}

Замечание:

Композиция отношений на множестве X порождает понятие: степень отношения

= ^2 = ^3 ^n= ^n-1