Шпаргалка по дисциплине "Дискретная математика"

Вопрос 1

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

Отцом теории множества был Георгийргий Кантор (1845-1918)

Множества называются равными ,если состоят из одних и тех же элементов .

Операции .1) Дополнение к мн-ву А наз-ся мн-во эл-ов ,которые не содержатся в (не А).

2) Пересечение мн. А и В , это мн-во эл-ов принадл. И А и В. 3)Объединение мн. АиВ это мн-во эл-ов , принадлеж. К А , но не прин к В . Булевые операции над множествами 1)коммуникативность2)Ассоциативность3)Дистрибутивность

Вопрос 2

Пусть M и N два произвольных множества ,говорят ,что на М определена ф-ия f ,принимающая значения из N , если к каждому эл-ту Х из N поставлен с соответствием один эл. Y принадлежащий N f:M→N               y=f(x) f- отображение ,оператор                Если а – эл-т из М , то отв. Эл b = f(a) принадл N наз-ся его образом.  Совокупность всех тех эл-ов ,а принад N, образом которых является данный эл-т b принадл N называется прообразом  эл-та b . f в минус первой (b)         

Вопрос 3

  Множества, между которыми можно установить взаимно однозначное соответствие, называются эквивалентными или равномощными. Два конечных множества эквивалентны тогда и только тогда, когда в них одинаковое количество элементов. Поэтому естественно считать, что если одно бесконечное множество эквивалентно другому, то в нем "столько же" элементов.

                                               

 

Вопрос 3

  Множества, между которыми можно  установить взаимно однозначное  соответствие, называются эквивалентными  или равномощными. Два конечных  множества эквивалентны тогда  и только тогда, когда в них  одинаковое количество элементов. Поэтому естественно считать, что  если одно бесконечное множество  эквивалентно другому, то в нем "столько же" элементов. Мощность множество есть число его элементов . Мощность мн. А наз-ся класс всех мн-в эквивалентных мн-ву А .

Теорема мощности. Вскякое подмножество счетного множества конечно или счетно . Теорема2 Объединение счетного числа счетных мн-в счетно . Теорема 3 Всякое бесконечное мн-во А содержит подмножество В эквивалентное А . Теорема 4 Множество всех подмножеств

Вопррос 4

Высказывание – связанное предложение , о котором можно сказать истинно оно или ложно . Отрицание логического высказывания — логическое высказывание, принимающее значение «истинно», если исходное высказывание ложно, и наоборот. Конъюнкция двух логических высказываний — логическое высказывание, истинное только тогда, когда они одновременно истинны.Дизъюнкция двух логических высказываний — логическое высказывание, истинное только тогда, когда хотя бы одно из них истинно.Импликация двух логических высказываний X и Y — логическое высказывание, ложное только тогда, когда X ложно, а Y истинно. Эквивалентность двух логических высказываний — логическое высказывание, истинное только тогда, когда они одновременно истинны или ложны.

 

                          

Вопрос 5

F(x1..xn) принимающая одно из двух значений 0 или 1 от n-переменных , каждая из которых принимает одно из двух значений 0 или 1 нз-ся булевой ф-ией от n-переменных . Ф-ии от одной и двух переменных наз-ся элементарными ф-ями . С помощью них можно определить ф-ии большего кол-ва переменных . Булевая ф-ия любого числа переменной , можно задать формулой , содержащей ф-ию одной или двух переменных ,т.е посредством суперпозиции ф-ий. Булевы ф-ии одной переменной . 1)Тождественная нулю 2)Тождественная 3)Отрицание 4)Тождественная единице .

 

 

 

………………………………………………………

 

Вопрос 6                                              1) Коммутативнось (перестановка местами для Конъюн, дизъюнк, суммы по мод 2 , стрелка Пирса , штир Шеффера ) 2)Ассоциативность                           xV(yVz)=…=xVyVx . Дизъюн, конъюн,сумма по мод 2 3)Дистрибутивность (xVy)^(yVz) Конъюн,дизъюнк, суммы по мод2 4) Закон де Моргана  . НЕ(x^y)=xVy  и на оборот . 5)Двойное отрицание ( Не(не(х))=х                                          6) Выражение дизъюнкцию через импликацию  (х->y)->y = xVy         7)Выражение дизъюн через конъюн и сумму по мод 2  x1Vx2=x1^x2 + x2 ^x1            8)Выражение конъюн через Штрих Шоффера (x1 I x2) I (x1 I x2) = x1^x2                                                          9)Выражение отрицания через стрелку Пирса и сумму по мод 2        xIx=x↓x = не (x) = x + 1 = x↔0  10)Выражение дизъюнкции через

Вопрос 6                                              1) Коммутативнось (перестановка местами для Конъюн, дизъюнк, суммы по мод 2 , стрелка Пирса , штир Шеффера )  2)Ассоциативность                           xV(yVz)=…=xVyVx . Дизъюн, конъюн,сумма по мод 2 3)Дистрибутивность (xVy)^(yVz) Конъюн,дизъюнк, суммы по мод2 4) Закон де Моргана  . НЕ(x^y)=xVy  и на оборот . 5)Двойное отрицание ( Не(не(х))=х                                          6) Выражение дизъюнкцию через импликацию  (х->y)->y = xVy         7)Выражение дизъюн через конъюн и сумму по мод 2  x1Vx2=x1^x2 + x2 ^x1            8)Выражение конъюн через Штрих Шоффера (x1 I x2) I (x1 I x2) = x1^x2                                                          9)Выражение отрицания через стрелку Пирса и сумму по мод 2        xIx=x↓x = не (x) = x + 1 = x↔0  10)Выражение дизъюнкции через стрелку Пирса (x1↓ x2 )↓ (x1↓ x2) = x1Vx2 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Вопрос 7

Конъюнкция одночлена от перем. х 1…х2 назы-ся конъюнкцией этих переменных Дизъюктивным одночленом от переменной х1..х2 наз-ся дизъюнкция этих переменных . Формула равносильная данной формуле алгебры высказываний и являющейся дизъюнкцией элементарных конъюктивных одночленов наз-ся дизъюктивной нормальной формой .  Пример :

 

Формула равносильная данной формуле алгебры высказывания и являющаяся конъюнкцией элементарных дизъюктивных одночленов наз-ся конъюктивной нормальной формой данной формулы . Алгоритм Построения 1)Избавиться от всех логических операций , содержащихся в формуле ,Заполнив их основными : Конъюн, Дизъюнк , Отрицание

 

2)Заменить знаки отрицания  3)избавиться  от знаков двоичного отрицания 4)Применить , если нужно к операциям конъюнкции и дизъюнкции и формы поглощения .

 Билет 8

СДНФ(СКНФ) данной формулы алгебры высказывания ,наз-ся такая ее днф(кнф) , которая удовлетворяет след. Свойствам : ДНф(КНФ) не содержит одинаковых конъюн(дизъюн) 2)Ни одна кон(диз)не содержит двух одинаковых переменных 3)Ни одна из конъюн(дизъюн)не содержит одновременно некоторую переменную и ее отрицание 4)Каждая кон(диз) СКНФ(СДНФ) содержит либо переменную Хi , либо ее отрицание для всех переменных ,входящих в ф-лу.                     СДНФ: f(X)=1,не(0) СКНФ : f(x)=0,не (1)

 

 

 

Билет 9

Многочлен Жегалкина называется многочлен ,являющийся суммой по мод2 , константы и различных одночленов ,в которых каждая из переменных входит не выше ,чем в первой степени .1 способ A + B = АВ V AB , A+1=A , A+A=0 , A+0=A 2)Способ f(x,y,z)=a0+a1x+a2y+a3z+a12xy+ a13xz+a23yz+a123xyz  

 

Билет 10

Предикат – это ф-ия принимающая значение истинны или лжи ,в зависимости от значения переменных . Пример: Выраж.x=x^2 является предикатом,так как оно истинно при Х=1 и ложно во всех остальных  случаях .            Множества,на котором предикат принимает только истинные значения наз-ся областью истинности предиката I от р    Существуют некоторые логические операторы (кванторы), применение которых к предикатам превращает последние в ложные или истинные высказывания .      Выражение «для всех Х» называется квантором всеобщности и обознач. Символом :    ∀Х                     Выражение «СУществуеи Х ,такое ,что…» наз-ся квантором существования и обознач ∃ Х «Существует только одно такое Х» Обознач символом ∃!х- единственный квантор существования  

 

 

 

 

 

 

 

 

 

Билет 11

Функция F , G равносильны ,если принимают одинаковые значения на новом наборе свободных переменных                                       2)F и G равносильны на множ Мю,если они принимают одинаковые знач на мн-ве Мю   3)F и G равносильны в логике предикатов ,если они равносильны на всех мн-вах .  . 

 

 

 

 

…………………………………………………..

Билет 12

В логике предикатов ф-ии могут иметь нормальную форму ,те существуют любые эквивалентные нормальные формы представления любых предикатных формул . При этом ,используя равносильности алгебры высказываний и логики предикатов можно привести к  нормальной форме . В логике предикатов различают два вида нормальных форм : Приведенную( Если она содержит только операции конъюн,дизъюн,а операции отрицания отнесена к элементарным формам ) и предваренную ( в ней кванторные операции либо полностью отсутствуют , либо они используются после всех операций алгебры логики     ,те  ПНФ формулы логики имеет вид (*х1)(*х2)…(*xn)A(x1,x2,…,xn),  n<m, где под символом *х понимается один из кванторов ∀Хi или∃ Х   , а формула А кванторов не содержит .                     

 

 

 

 

 

Билет 13

Пара (V(G),E(G))- называется простым графом ,если V(G)-непустое конечное множество элементов ,называемых вершинами , а E(G)-конечноeконечное множество неупорядоченных пар пар различных элементов из V(G) ,называемых ребрами . В простом графе данную пару вершин может соединить не более чем одно ребро .                                            Маршрутом в графе G  называется последовательность вершин и рёбер вида v0.e1,v1,e2…vn,en,vn . Вершины V0 называют началом ,а vn – концом маршрута . Если они равны ,то маршрут называют замкнутым . Число n наз-ют длинной маршрута .                         Цепь, простая цепь , цикл . Маршрут ,в котором все ребра попарно различны называется цепью . Замкнутый маршрут , являющийся цепью,называется называется циклом . Маршрут ,в котором все вершины различны , называется простой цепью .Цикл ,в котором все вершины кроме первой и последней попарно различны наз-ся простым циклом Граф наз-ся связанным ,если любая пара его вершин связана .Полный граф – в котором каждая пара различных вершин смежна .Смежность- понятие ,используемое в отношении только двух ребер , либо только двух вершин : Два ребра , инцидентные одной вершине ,называются  смежными ; две вершины ,инцидентные одному ребру также наз-ся смежными .   

 

 

 

 

 

 

 

 

Билет 14

Ориентированный граф- граф, ребрам которого присвоено направление. Направленные ребра именуются также дугами . Связанность . Маршрутом в орграфе называют чередующуюся вершин и дуг вида U0(U0,U1)U1(U1,U2)U2…Un                         Длинна маршрута – кол-во дуг в нем . Путь есть маршрут  оргграфе , без повторяющихся дуг , простой путь – без повторяющихся вершин . Если сущ-ет путь из одной вершины в другую , то вторая достижима из первой .     Контур есть замкнутый путь .        Орграф сильно связанный , или просто сильный ,еслли все его вершины взаимно достижимы . Односторонне связанный ,или просто односторонний ,если для любых двух вершин, по крайней мере одна достижима  из другой  .Слабосвязанный или просто слабый , если при игнорировании направления дуг получается связанный( мульти) граф . 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Билет 15

Объединением    графов   G1 и G2      называется граф G=G1uG2, множество вершин которого есть объединение множеств вершин графов G1  и G2, а множество ребер является объединением множеств ребер  этих графов . Пересечением графов G1 и G2  называется граф G=G1пересеченный с G2 , множество вершин которого пересечены  , и также множество ребер .                                      Суммой по мод2 графов G1  и G2 называется граф G=G1 + G2, порожденный на множестве ребер  , т. е. на множестве ребер, присутствующих либо в G1 , либо вG2 , но не принадлежащих их пересечению.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Вопрос 16 .

Цикл называется эйлеровым , если он содержит все ребра графа. Цепь называется Эйлеровой , если она содержит все ребра графа . Граф наз-ся Эйлеровым,если в нем найдется Эйлеров цикл . Связанный граф яв-ся Эйлеровым тогда и только тогда ,когда он не сожержит вершин не четной степени . Цепь , содержащая все ребра графа, наз-ся квазиэйлеровой . Граф явл-ся квазиэлеровым ,если в нем не более двух вершин нечетной степени . В квазиэйлеровом графе существующие у него две вершины нечетной степени всегда будут яв-ся концами любой эйлеровой цепи . Если в графе ровно К вершин имеют нечетную степень , то его можно разложить на не менее чем К/2 попарно реберно-непересекающихся цепей .     Цикл наз-ся гамильтоновым ,если он проходит через каждую вершину графа ( за исключением крайней ) в точности один раз . цепь наз-ся гамильтоновой ,если она проходит через каждую вершину в точности один раз . Гамильтонов цикл и гамельтонова цепь всегда яв-ся простыми . Они могут не содержать всех ребер графа .Граф наз-ся гамельтоновым , если он обладет гамельтоновм циклом . Граф наз-ся квазигамельтоновым , если он обладает гамельтоновой цепью .  

 

 

 

 

 

 

 

 

 

 

 

Билет 17

Дерево – это связный ациклический граф . Связность означает наличие путей между любой парой вершин , цикличность – отсутствие циклов и то ,что между парами вершин имеется только по одному пути .     Ориентированное дерево – ациклический оргграф , в котором только одна вершина имеет нулевую степень захода ,(  в нее не ведут дуги ) а , все остальные вершины имеют степень захода 1 (в них ведет ровно по одной дуге ) Вершина с нулевой степенью исхода (из которой не исходят ни одна дуга ) наз-ся концевыми вершинами или листьями .               Дерево не имеет кратных ребер и петель .                                                      Любое дерево с n вершинами содержит  n-1 ребро . Более того ,конечный связанный граф является деревом тогда , и тольок тогда , когда В – Р =1 , В- число верш, Р- число ребер .                          Граф яв-ся деревом тогда и т т ,когда любые две различные его вершины можно  соединить единственной простой цепью . Любое дерево однозначно определяется расстоянием между его концевыми вершинами . Любое дерево яв-ся двудольным графом .               Любое дерево , множество вершин которого не более ,чем счетное , явлся-ся планарным графом . Для любых трех вершин дерева, пути между парами этих вершин имеют ровно одну общую вершину .  

 

 

 

 

 

 

 

 

 

 

Билет 18

Представим, что дан граф. Обозначаем первое множество с1, и этому множеству принадлежит х1, а остальные принадлежат к с2.смотрим, к какой переменной мы можем перейти, находим минимальное расстояние, и ту переменную на которой оно реализуется перебрасываем в с1