Главная страница | Контакты | Случайная страница Автомобили Астрономия Биология География Дом и сад Другие языки Другое Информатика История Культура Литература Логика Математика Медицина Металлургия Механика Образование Охрана труда Педагогика Политика Право Психология Религия Риторика Социология Спорт Строительство Технология Туризм Физика Философия Финансы Химия Черчение Экология Экономика Электроника

Декартово произведение множеств

ДЕКАРТОВО ПРОИЗВЕДЕНИЕ МНОЖЕСТВ [Cartesian product] — множество А × В всех упорядоченных пар элементов (a, b), из которых a принадлежит множеству A, b — множеству B. Порядок следования пар может быть любым, но расположение элементов в каждой паре (векторе, кортеже) определяется порядком следования перемножаемых элементов. Поэтому A × B ≠ B × A, если B ≠ A

20) Понятие предиката

п -местным предикатом, определенном на множествах М₁, М₂, …, М_n, называется предложение, содержащее n переменных х₁, х₂, …, х_n, превращающееся в высказывание при подстановке вместо этих переменных любых конкретных элементов из множеств М₁, М₂, …, М_nсоответственно.

Обозначение: P(x₁, x₂, …, x_n).

Операции над предикатами:

Отрицанием предиката P(x) называется новый предикат или, который принимает значение «истина» при всех значениях, при которых предикат P(x) принимает значение «ложь», и принимает значение «ложь» при тех значениях, при которых предикат P(x) принимает значение «истина».

Конъюнкцией двух предикатов P(x) и Q(x) называется новый (сложный) предикат, который принимает значение «истина» при тех и только тех значениях, при которых каждый из предикатов принимает значение «истина», и принимает значение «ложь» во всех остальных случаях.

Дизъюнкцией двух предикатов P(x) и Q(x) называется новый (сложный) предикат, который принимает значение «ложь» при тех и только тех значениях, при которых каждый из предикатов принимает значение «ложь», и принимает значение «истина» во всех остальных случаях.

Импликациейпредикатов P(x) и Q(x) называется новый предикат, который является ложным при тех и только тех значениях, при которых одновременно P(x) принимает значение «истина», а Q(x) – значение «ложь», и принимает значение «истина» во всех остальных случаях.

Эквиваленциейпредикатов P(x) и Q(x) называется новый предикат, который обращается в «истину» при всех тех и только тех, при которых P(x) и Q(x) обращаются оба в истинные или оба в ложные высказывания.

21) Квантор – это логическая операция, которая по предикату Р(х) строит высказывание, характеризующее область истинности предиката Р(х).

Квантор всеобщности:

Пусть Р(х) – предикат, определенный на множестве М.

Под выражением понимают высказывание, истинное, когда Р(х) истинно для каждого элемента х из множества М, и ложное в противном случае.

Словесное выражение: «Для всякого х Р(х) истинно».

Квантор существования:

Пусть P(x) - предикат определенный на множестве М.

Под выражением понимают высказывание, которое является истинным, если существует элемент, для которого P(x) истинно, и ложным – в противном случае.

Словесное выражение: «Существует x, при котором P(x) истинно».

Квантор единственности:

Можно составить и такое высказывание «Во множестве X есть один и только один элемент а, такой что Р(a) - истинное высказывание».

Это высказывание обозначают: (!хÎX)Р(x)

Символ! – называют квантором единственности.

Словестное описание: «единственный», «один и только один».

22) Понятие бинарного отношения

Бинарным (или двуместным) отношением r называется любое подмножество множества упорядоченных пар.

n-арным отношением называется множество упорядоченных n-ок.

23) Отношение r на множестве Х называется рефлексивным, если для любого элемента хÎХ выполняется хr х.

Отношение r на множестве Х называется симметричным, если для любых х, уÎХ из хr у следует уr х.

Отношение r на множестве Х называется транзитивным, если для любых х, у, zÎХ из хr у и уr z следует хr z.

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

26)Понятие отображение

Пусть X, Y – произвольные множества, если каждому элементу x из множества X (x ∈ X) ставится в соответствие элемент y ∈ Y, то говорят, что на множестве X задано отображение со значениями во множестве Y.

29) Понятие подстановки

Взаимно-однозначное отображение множества {1,2,3, …,n} на само себя называется подстановкой n чисел, где n – степень подстановки.

Формула количества подстановок:

Если степень подстановки равна n, то количество подстановок равно n!

31) Произведением подстановок α и β называется новая подстановка α*β, полученная путем применения сначала подстановки α, затем подстановки β.

32) Степень подстановки:

Любое взаимно однозначное отображение множества первых натуральных чисел на себя называется подстановкой -й степени. Всякая подстановка может быть записана при помощи двух перестановок, подписанных одна под другой

Подстановка называется четной, если она содержит четное число инверсий; подстановка называется нечетной, если она содержит нечетное число инверсий.

36)Понятие графа

Графом G=G(V, U) называется совокупность двух множеств – непустого множества V (множества вершин) и множества U двухэлементных подмножеств множества V. Множество U называется множеством ребер.

Виды графов:

Если в графе допускается наличие петель, то он называется графом с петлями или псевдографом.

Если в графе допускается наличие более одного ребра между двумя вершинами, то он называется мультиграфом.

Граф G¢(V¢, U ¢) называется подграфом (или частью) графа G(V, U), если V¢ ÍV, U ¢ Í U.

Если V¢=V, то G¢ называется остовным подграфом G (остовом).

Граф называется полным, если любые две его вершины соединены ребром.

Полный граф с n вершинами обозначается через G_n.

Способы задания графа:

Граф G=(V,E) можно задать списком вершин и ребер. Можно задать и геометрически, нарисовав его на плоскости или любой другой поверхности и отождествив его вершины с точками на плоскости, а ребра с отрезками, соединяющими смежные (соседние) вершины.

37)

Путем в графе (или маршрутом в орграфе) называется чередующаяся последовательность вершин и ребер (или дуг - в орграфе) вида v₀, (v₀,v₁), v₁,..., (v_n-1,v_n), v_n.

Замкнутый путь без повторяющихся ребер называется циклом (или контуром в орграфе);

38) Степень вершины (англ. degree, также валентность, англ. valency) в теории графов — количество рёбер графа , инцидентных вершине . При подсчёте степени ребро-петля учитывается дважды.^[1

Теорема: Сумма степеней всех вершин графа есть число четное и равное удвоенному количеству ребер. При большом количестве вершин схема теряет свою наглядность и поэтому используют другой способ задания графов в виде матрицы смежностей.

39) Полный граф — простой граф, в котором каждая пара различных вершин смежна. Полный граф с вершинами имеет рёбер и обозначается . Является регулярным графом степени .

40) Эйлеровой цепью в графе G называется замкнутая цепь, содержащая все ребра графа G. К открытой эйлеровой цепи относится открытая цепь, содержащая все ребра G. Граф, содержащий эйлерову цепь, называется эйлеровым графом.

Гамильтонов путь (или гамильтонова цепь) — путь (цепь), содержащий каждую вершину графа ровно один раз. Гамильтонов путь, начальная и конечная вершины которого совпадают, называется гамильтоновым циклом. Гамильтонов цикл является простым остовным циклом. Задача определения, содержит ли данный граф гамильтонов цикл, является NP-полной

41)Понятие бинарного дерева