1. Множество -совокупность нескольких объектов - polpoz.ru o_O
Главная
Поиск по ключевым словам:
страница 1
Похожие работы
Название работы Кол-во страниц Размер
Управления. Поэтому остановимся на общем понятии «система». 7 760.58kb.
Какая совокупность свойств относится к среде Windows? 1 17.53kb.
«Моделирование систем» 176 1 372.85kb.
Класс (class) совокупность объектов, имеющих один или несколько характеристических... 1 49.25kb.
Садгуру Свами Вишну Дэв 9 1140.86kb.
Это легкое путешествие 1 22.02kb.
Практическая работа № Комбинирование изображений из графических примитивов 1 44.31kb.
1. Основные понятия и определения. Задачи, решаемые рнс. Классификация... 2 432.71kb.
Это совокупность сведений, сообщений, новостей о каком-нибудь событии... 1 27.74kb.
5 инновационная инфраструктура совокупность объектов инновационной... 1 95.25kb.
Функции нескольких переменных и их геометрический смысл 1 23.68kb.
Тема: Режимы работы и энергетические соотношения в цепях постоянного... 1 59.14kb.
1. На доске выписаны n последовательных натуральных чисел 1 46.11kb.

1. Множество -совокупность нескольких объектов - страница №1/1


дискретная математика

1. Множество–совокупность нескольких объектов. Примеры: N-М.натуральных чисел(1,2,3…). Z-М.целых чисел(…-2,-1,0,1,2,3…). Q-М.рациональных чисел(дроби). R-М.действительных чисел. С-М.комплексных чисел. A,B,C – множества. a,b,c – элементы множества. Способы задания М.: -перечисление элементов А={a,b,c}={b,c,a} Z={0,1,2,3...}. –указываются св-ва, которыми обладают элементы М.: Р(х) – св-во; А={хВ|Р(х)} пример: А={xN|x2-1=0}={1} если каждый элемент М.В является элементом М.А, то М.В называется подмножеством М.А BA или BA. P(A)- М.всех подмножеств М.А, если М.А содержит n элементов, то Р(А)содержит 2n элементов. , А-несобственные подмножества, все остальные наз. собственными. Пример: B={1,2,3} P(B)={,B,{1},{2},{3},{1,2},{1,3},{2,3}}. Два М. наз. равными, если они состоят из одних элементов: A=B AB,BA. Операции с М. объединение М. AB=C, где С-состоит из элем., принадлежащих хотя бы одному множеству А или В. Св-ва: AAB, BAB.пример:A={-1,2,3,5}B={-2,2,-1} AB={-2,-1,2,3,5}. пересечение М. AB=C,где С-состоит из элем., принадлежащих как А так и В. Разность М. А|В=С, где С-состоит из элем., принадлежащих А и  В.пример: A|B={x|xA, xB}.св-ва: 1.A|B=A-(AB) 2.BA(A|B)B=A. дополнение М. U-универсальное множество. A¬-дополнение к М.А. A¬=U|A.








1.коммутативность

AB=BA

AB=BA

2.Ассоциативность

(AB)C=A(BC)

(AB)C=A(BC)

3.Дистрибутивность

относительно 

относительно 




A(BC)=(AB)(AC)

A(BC)=(AB)(AC)

4.

A=A

A=

5.





6.Закон идемпотентности

AA=A

AA=A

7.

AU=U

AU=A

8.Закон де Моргана

(AB) ¬=A¬B¬

(AB) ¬=A¬B¬

9.Закон поглощения

A(AB)=A

A(AB)=A

10.Закон снятия двойного дополнения



Упорядоченное М.(Кортеж, вектор)-конечная последовательность элементов некоторого М., допускающая повторения. (a1,a2 ... an) или < a1,a2 ... an>, где n-длина корежа, аi-элемент кортежа. ()-пустой кортеж.

Прямое или декартовое произведение М. Прямым произведением М. А и ВАхВ=С, где С состоит из тех и только тех упорядоченных пар (a,b), где aA, bB. Пример: A=[a,b] B=[c,d] C=AxB

C={(a,b)|aA, bB}

2.Под Высказыванием будем понимать такое предложение, относительно которого можно говорить «истина», «ложь» (1,0). Операции с высказываниями 1) - отрицание высказывания А (ложное, когда А истинное). 2) Конъюнкция (логическое умножение)(и,а,но) A&B(AB) – высказывание, которое истина, при А-Ист. и В-Ист. 3) Дизъюнкция (или) AB – высказывание, которое ложно, при А-Ложь и В-ложь. 4) Импликация АВ(если, то) – такое высказывание, которое Ложно, при А-Ист., а В-ложь (А-посылка, В-заключение) 5) Эквивалентность (A~B)(равнозначность) – такое высказывание является истинным только при истинах А и В Аии Формулы логики высказываний: алфавитом логики высказываний наз. совокупность следующих элементов: 1.высказывательные переменные х1…хn 2. Логические связки ¬ отрицание, &, , , ~ 3) символы «( )». Слово в алфавитной логике высказываний наз. формулой, если она удовлетворяет след. Определениям: 1.любая высказывательная переменная – это формула. 2. если А и В – формулы, то (¬А),(А&В),(АВ),(АВ),(А~В) – тоже формулы. 3. только те слова являются формулой, которые удовлетворяют (1) и (2).

Для упрощения формул можно пользоваться след. Правилами: 1.внешние ( ) можно опускать, 2.знак операции & можно опускать, 3.знак отрицания ¬ считается сильнее любой другой двухместной логической связки. 4. знак & считается сильнее любой другой двухместной логической связки. 5. подформулой формулы А считается такое слово, которое в свою очередь является формулой.

Равносильность формул: Упорядоченный набор высказывательных переменных наз. списком переменных формулы А, если все переменные формулы А содержатся в данном наборе. Оценкой списка переменных формулы А наз. сопоставление каждой переменной данного списка некоторого истинного значения. Если список содержит n переменных, то оценок = 2n.
3.Предикат P(x)-функция переменного ‘x’ которое принимает значение из множества {0,1}, когда переменная ‘x’ пробегает множеств М. Множество М.- область определения Р. Множество ХМ, для которых Р(х)=1 называется областью истинности предикатов (Ip). Предикат Р(х) называется тождественно истинным, если IpПредикат Р(х) называется тождественно ложным, если Ip= -пустое множество.

N-местным Р называется функция, принимающая значения 0, 1, когда аргументы этой функции пробегают множество М. P(a1...an)высказывание, P1...хn)- переменное высказывание. Операции с предикатами:

1. P(x)&Q(x) IP&Q=IP IQ – пересечение истинных значений.

2. P(x) Q(x) IP Q = IP IQ – объединение истинности.

3. Р(х) IP¬=M|IP

4. P(x) Q(x) (M|IP) IQ

5. P(x) ~ Q(x) (P(x) Q(x))&(Q(x) P(x)); IP~Q=(IP¬ IQ) (IQ¬ IP)



6. Операция с кванторами: Квантор общности хР(х)-высказывание, которое истинно Р(х) –истина для любого хМ. Квантор существования хР(х)-высказывание которого истина, если найдется хотя бы один хМ, для которого Р(х)=1. Операция перехода от Р(х) к хР(х), хР(х) называется операцией связывания переменной или навешивание квантора на переменную. Переменная на которую навешивается квантор наз. связанной переменной. Свободная – переменная на которую не навешен квантор. Навешивание квантора на одноместный предикат, делает его высказыванием или нульместным предикатом. Кванторы можно навешивать на n-местные предикаты, при этом выражения в скобки. х(P(x)&Q(x)). Выражение на которое навешивается квантор наз. обл. действ. Квантора. Навешивание квантора на n-местный предикат делает его (n-1) местным. Формулы логики предикатов(ФЛП): алфавит ЛП состоит из нескольких символов: 1. х1…хn – предметные переменные 2. P,Q,R... – символы предикатов. 3. &,,,~,¬ - логические символы. 4. , - символы кванторов. 5. ( ). ФПЛ – называется слово, которое удовлетворяет след. определению: 1) если Р – символ предикатов, а х1…хn – предм. перем., то Р(х1…хn) – наз. атомарной формулой. 2) если Р(х) – формула, то Р¬(х) – тоже формула. 3) если А,В – формулы, причем нет такой переменной, которая была бы в одной свободной, а в другой связанной, тогда (A&B),(AB),(AB),(A~B) – тоже формулы. 4) Пусть А(х) – формула, причем х – свободная переменная, тогда хА(х) – тоже формула. (пример: х1х3 Р(х1 х2 х3)&Q(х1 х3)) Основные равносильности ЛП: 1) все равносильности логики высказываний. 2) перенос квантора через отрицание (хР(х))¬=х(Рх)¬; (х Р(х))¬= х(Рх)¬. 3) вынос квантора за скобки (А(х) – формула, х- свободная переменная, В – формула, х – не содержится) хА(х) В х(А(х) В); хА(х) В х(А(х) В); хА(х)&В х(А(х)&В); хА(х)&В х(А(х)&В), если В зависит от х, то х(А(х)&В(х)) хА(х)&х В(х)); х(А(х) В(х)) хА(х) хВ(х)); х(А(х)&В(х)) хА(х) & хВ(х)); хА(х) хВ(x) х(А(х)В(x)); 4) Одноименные кванторы можно менять местами хуА(х,у)ухА(х,у);

5) переименование связанной переменной хР(х)уР(у)

4. Граф – совокупность двух множеств С=(V,x), где V – множество вершин, х – множество x = {{v,w}|v,wV}, {v,w} – ребро (дуга) графа {v,v} – петля. В х {v,w} – одинаковы, они называются кратными или параллельными. Граф, в котором имеются кратные ребра называется мультиграфом. Мультиграф, в котором имеются петли, называется псевдографом. Если на ребрах графа задана ориентация тогда граф называется орграфом. Ребра орграфа называются дугами и обозначаются (v,w). Матричное задание графа: Матрица смежности графа G=(v,x) наз. квадратич. Матр. A(G)={aij}nxn , где n- кол-во вершин, элементы которой равны ‘1’ если ребро {vi,wi} x и ‘0’, если такого ребра нет. Аналогично определяется матрица смежности орграфа. Если между вершинами существует дуга или ребро, то вершины смежные. Два ребра или две дуги смежные, если они имеют общую вершину. Если вершина V является началом или концом дуги(ребра)Х, то V,Xинцидентны. Матрица инцидентности графа наз. прямоугольная матр. B(G)={bij}nxm, где n – кол-во вершин, m – кол-во ребер. bij = 1, если vixi – инцидентны, и = 0, если нет. Для орграфа так же, только bij = -1, если vi – начало дуги xi, bij = 1, если vi – конец дуги xi, bij = 0, если vi и xi не инцидентны. Матрица инцидентности может быть построена для мультиграфа (ориент. и неориентир.) и неориентированного псевдографа. Для ориентированных Г. – 3-я форма представления: D=(V,Г), где V- множество вершин, Г – отображение множества вершин в себе. Граф называют связанным, если для любых двух его вершин существует маршрут их соединяющий. Сильносвяз. Орграф – если для любых его вершин сущ. путь (вершины взаимодостижимы). Компоненты связанности (сильной) графа (орграфа) наз. его связанным (сильно). Транзитивное замыкание для нахождение сильной связанности. - множество вершин орграфа D в которые можно попасть из вершины V, используя пути, длина которых не больше n. - Т.з. - множ. вершин в которые можно попасть из вершины V. - обратное Тр.з. – множество вершин, из которых можно попасть в V. Алгоритм: 1) выберем произвольную вершину UV, p=1, p – счетчик связанности. 2) найдем прямое Т.з. 3) 4) - пересечение = Vp – множество вершин, образующих P-ую связанность, которая содержит вершину V.

5) Исключим Vp – множество вершин из матрицы смежности орграфа, в оставшейся матрице выберем произвольную вершину V2, p=p+1, и переходим к шагу 2, если вершин не осталось, то р – число компонент связанности.


izumzum.ru