Записи с темой: дискретная математика (список заголовков)
11:43 

Количество отношений строгого порядка

Здравствуйте!

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

Сколько существует различных неэквивалентных отношений строгого порядка на конечном множестве альтернатив, состоящем из n элементов?

Спасибо.

@темы: Дискретная математика, Комбинаторика

21:32 

Бинарные отношения на бесконечном множестве

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

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

@темы: Бинарные отношения, Дискретная математика

23:00 

Задача по изоморфизму регулярных графов

Здравствуйте. Разбирая задачи по дискретной математике для подготовки к экзамену наткнулся на задачу, к которой не знаю как и подойти.

Условие: "Докажите, что любые два регулярных графа типа (10,8) (10 вершин, из каждой выходит по 8 ребер) изоморфны".

Подскажите, пожалуйста, как подходить к задачам такого рода и доступную литературу по этой теме.

@темы: Посоветуйте литературу!, Дискретная математика

17:10 

если `A \subseteq \delta_{f} \edge B \subseteq \rho_{f} => f (f ^{-1} (B))= B `

Здравствуйте уважаемое сообщество.

1 курс каунасского технологического университета. домашнее задание по дискретной математике

нужно доказать, что
если `A \subseteq \delta_{f} \edge B \subseteq \rho_{f} => f (f ^{-1} (B))= B `

Как следует из задания , нам даны функциональное и обратное ему соответсвие, в соответствии с определениями (6.7),
они являются однозначными, `f` и обратны`f^{-1}` и множество `A` \ в \ `delta {F} `является прототипом и
`A \subseteq ` pr`_1 G`, а множество ` B \subseteq \rho_{f}` есть образ множества `A` и `B \subseteq ` pr`_2 G`, где `G` функциональное соответствие `f`.

читать дальше
В первом случае (а) проблемы не возникет, и решение таково

поставим очерёдность рассмотрения операций
читать дальше
что должно бтть первым, а что - вторым?

Использованные определения:
читать дальше
----------------------------------------------------------
надеюсь это не будет большой наглостью с моей стороны.
сейчас работа приобрела такой видчитать дальше


заранее спасибо

@темы: Дискретная математика, Множества

04:45 

дискретная мтематика. Множества . A∩B⊆C <=> A⊆bar{B}∪C

Здравствуйте уважаемое сообщество

не получается решить задание. домашняя работа, 1 курс прикладной математики Каунасского Технологического университета

нужно доказать что

`A nn B subseteq C iff A subseteq bar{B} uu C`



попытка решения под катом

читать дальше

выражение эквивалентности значит "тогда и только тогда, когда..."

расписал обе части, но одинаковых элементов в полученных выражениях нет.

что нужно сделать дальше? помогите пожалуйста.
я сам всё сделаю, подскажите направление, пожалуйста

@темы: Множества, Дискретная математика

17:50 

Дискретная математика. Множества (A\B)\C = (A\C)\(B\C)

Здравствуйте .

Дискретная математика, домашнее задание, 1-й курс Каунасского технологического университета.

доказать что (A\B)\C = (A\C)\(B\C)

вторую часть доказал (под катом)

читать дальше

@темы: Дискретная математика, Множества

06:25 

Алгоритм Дейкстры

Здравствуйте! С помощью алгоритма Дейкстры ищу кратчайшие пути. В третьей итерации получается, что три временные вершины имеют значение 5. Возможно ли такое? Как поступать дальше?

@темы: Дискретная математика, Математическая логика, Теория графов

10:28 

Исчисление предикатов

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

@темы: Посоветуйте литературу!, Поиск книг, Математическая логика, Литература, Дискретная математика

08:19 

Дискретная математика (Вычислить КНФ)

Всем привет.
Возник вопрос по поводу КНФ
Условие задания:
Вычислить КНФ БФ от трёх переменных `((X ^^ Y) vv (Z + X)) -> Z`

Более наглядное(и удобное) изображение задания:
изображение задания

Вот таблица для этой функции:
читать дальше

1 способ
Табличный
СКНФ:
читать дальше
Получается, здесь всё? При дальнейшем упрощении будет уже ДНФ а не кнф. (не икс v Z).

2 способ
Эквивалентности
Последняя строка будет такой:
читать дальше
При дальнейшем умножении скобок, будет ДНФ.

Ну и собственно вопрос: почему ответы не сходятся? И какой из них правильный?

@темы: Дискретная математика

05:53 

Дискретная математика. Полугруппы

всем здравствуйте

1-й курс Каунасского технологического университета (Литва), бакалавриат прикладной математики

ломаю зубы об дискретную математику.
делаю домашнее задание - программу генерирования полгрупп - т.е. ввожу элементы множества "a,b,c," и программа генерирует все возможные варианты квадратной матрицы-таблицы Келли, и проверяет ассоциативность и коммутативность (выбирает из них Абелевые группы)

скажите пожалуйста сколько всего полугрупп получается (чтобы я знал правильно программа работает или нет) из множетва из 2-х, 3-х, 4-х, 5-ти элементов
как посчитать количество всех возможнх вариантов таблиц Келли полугрупп?
в какой книге это можно посмотреть?

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

так например для множества [a,b,c] количество вариантов строк матриц - 3*3*3 = 27, количество всех возможгных матриц - 19683, из них полугрупп - 273. правильно ли это?

по идее я должен уловить закономерность и сделать генерацию таблиц Кэли полугрупп для большого числа элементов (типа [a,b,c,d,f,...])оптимизированно, поскольку если перебирать все варианты, то очень резко растёт время расчёта

помогите пожалуйста !!!
в какой литературе это можно посмотреть? а то так таблицы Кэли для полугрупп никто не рассматривает, по крайней мере я пока не нашёл
по идее я должен заметить закономерность в полученных полугруппах для малого числа элементов и спроецировать её для экономной генерации полугрупп для большого числа элементов (так как время счёта очень резко увеличивается уже для 5 элементов, если рассматривать все варианты)
и где это можно посмотреть или подскажите как это сделать (я постараюсь сам, но если это можно посмотреть в литературе, было бы здорово)


вот так выглядят промежуточная проверка
ну тут кусок выходного листинга для контроля



помогите пожалуйста, сессия горит. крайний срок сдачи - среда

P.S. (вопрос модераторам - я правильно спрятал под кат? - если не так, то исправлю)

@темы: Дискретная математика, Комбинаторика, Теория групп

09:32 

Дискретная математика.

IWannaBeTheVeryBest
Всем привет. Не нашел нигде, кто бы мог решить вот эти 2 задачки или хотя-бы поставить на правильный путь.
1. "Доказать, что если P - силовская подгруппа в G, то нормализаор нормализатора P равен нормализатору P"
Ну начну с того, что знаю.
Порядок конечной группы - это мощность или количество элементов этой группы. Пусть `G` — конечная группа, а `p` — простое число, которое делит порядок `G`. Подгруппы порядка `p^t` называются p-подгруппами. Выделим из порядка группы `G` примарный делитель по `p`, то есть `|G| = p^ns`, где `s` не делится на `p`. Тогда силовской p-подгруппой называется подгруппа `G`, имеющая порядок `p^n`.
Определение нормализатора группы
`N_G(P) = {g in G | gP = Pg}`
Ну я это понимаю как множество всех элементов в G которые коммутируют со всеми элементами в P.
С чего бы начать? Я просто очень слабо в этом соображаю.
Ну вот предположим, что G - группа, с какими-то рандомными элементами.
Скажем, что мощность или порядок G = 90. Простое число p = 3 делит порядок G = 3^2 * 10, где 10 не делится на 3. Таким образом у нас есть 3-подгруппа силовская, имеющая порядок 3^2. Так вот, нам надо опеделится с тем, что такое этот номализатор скажем 3-группы. Так что это? Ну это какое-то множество элементов, которые коммутируют со всеми элементами нашей 3-группы. Нормализатор нормализатора в моем представлении - это и есть наша 3-группа. Вот тут то и начинаются странности


2. "Пусть S - полугруппа эндоморфизмов End V линейного пространства V (умножение - композиция эндоморфизмов). Доказать, что любой идеал в S - главный. (т.е. порождаетсяодним элементом)"
Плииииз хоть кто-нибудь, хоть немного.

@темы: Дискретная математика, Теория групп

20:22 

Еще немного дискретной математики

blackhawkjkee
Возникли проблемы с парой вещей:

1) Как показать транзитивное замыкание на этом графе?


2) Даются числа в следующем порядке: 7 5 6 4 3 8 1
Необходимо построить двоичное дерево поиска исходя из заданных цифр.

@темы: Дискретная математика, Бинарные отношения, Теория графов

19:13 

Свойства бинарных отношений на множестве и замыкания

blackhawkjkee
У меня возник еще один вопрос по поводу свойств.
Собственно, предположим что на множестве `A = {1,2,3,4}` задано отношение `R = {(1,2),(3,4),(4,2)}`

С замыканием `R` относительно симметричности и рефлексивности я вроде разобрался, но с остальными свойствами, такими как: антисимметричность, антирефлексивность и транзитивность, я разобраться до конца не смог.
Есть предположения насчет антисимметричности:
`R^1 = {(1,2),(3,4),(4,2);(2,4),(4,3),(2,1)}` - верно ли это?

И насчет замыкания относ-но транзитивности, вот правильное замыкание:
`R^1 = {(1,2),(3,4),(4,2);(2,3)}`

Почему `(2,3)`? Можете по-подробнее объяснить или предоставить какой-нибудь пример(желательно в той же тематике что и выше)?

@темы: Дискретная математика, Бинарные отношения

16:56 

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

blackhawkjkee
Подскажите, как будет выглядеть декартово произведение трех и более множеств? С двумя я разобрался, а вот если больше брать, то начинаю путаться.
Нигде в интернете не могу найти хотя бы элементарного примера.

Предположим, есть `A={1,2}, B={3,4}, C={5,6)`
`A` x `B = {(1,3),(1,4),(2,3),(2,4)}`
Чтобы найти `A` x `B` x `C` необходимо ли использовать уже составленное декартово произведение выше или это необязательно?

Также нашел вот такое свойство:
Количество элементов в декартовом произведении равно произведению чисел элементов множеств-сомножителей (в случае их конечности, разумеется):
`|A`×`B|=|A|*|B|.`

Как будет формулироваться подобное свойство для, например, трех множеств? `|A|*|B|*|C|?`

@темы: Дискретная математика

20:30 

Раскраска домов

wpoms.
Step by step ...


На улице Антонио сто домов, пронумерованных числами от единицы до ста. Любой дом, чей номер равен разности номеров домов, покрашенных в один цвет, покрашен в цвет отличный от цвета этих двух домов. Докажите, что на улице Антонио есть дома по крайне мере пяти разных цветов.



@темы: Дискретная математика

19:25 

Доказательство лемм

Добрый день,

В работе над курсовой работой у меня возникла потребность в доказательстве вспомогательных лемм. К сожалению, доказательство собственных теорем/лемм - самый слабый мой математический навык и я был бы благодарен за помощь в данной проблеме. Прочитал книжку Успенского про примеры математических доказательств, но ни на какие мысли это меня не натолкнуло.
Суть лемм состоит в следующем. У нас имеется модель процесса в виде сети Петри, а точнее ее развертки, которое можно рассматривать как параллельное исполнение, а также все возможные последовательные исполнения процесса. Я исследую отношения между событиями процесса: `>`: `e > e'` - если случилось событие `e'`, то `e` случилось до этого; `#`: `e # e'` - события `e` и `e'` никогда не встречаются в одном последовательном исполнении; `e || e'` - `neg (e > e') wedge neg (e' > e) wedge neg (e # e')`. Так, например, для процесса на картинке, имеем следующие последовательные исполнения: `adc`, `acd`. `cad`, `b`. Т.е. события находятся в следующих отношениях: `a || c`, `d || c`, `a > d`, `a # b`, `c # b`, `d # b`.


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

@темы: Дискретная математика, Бинарные отношения

10:03 

помогите если можно то с описанием решения

Отношение Т: «иметь один и тот же остаток при делении на 4» задано на множестве Х={6, 7, 8, 9, 10, 11, 12, 13}. Является ли оно отношением эквивалентности.

@темы: Дискретная математика

10:59 

помогите решить

задайте всеми известными способами соответствия между множествами Х={3,4,5,9} и Y={135,0,264,122} "число х является делителем числа y"

@темы: Дискретная математика

14:41 

Шарики

wpoms.
Step by step ...


В одной сумке лежит `m` шариков, в другой их `n` (`m, n > 0`). Можно выполнять две разные операции:
a) Удалить равное количество шариков из обеих сумок;
b) Удвоить количество шариков в одной из сумок.
Всегда ли возможно опустошить обе сумки с помощью конечной последовательности операций a) и b)?
Операцию b) заменяют на
b') Утроить количество шаров в одной из сумок.
Всегда ли возможно опустошить обе сумки с помощью конечной последовательности операций a) и b')?



@темы: Дискретная математика

12:19 

помогите решить

соответствия между множествами C = {1,2,3,4,5} и D={5,6,7} таково что его график состоит из пар в которых первая компонента взята из множества С а вторая из D и больше первой компаненты. Постройте граф этого соответствия , график этого соответствия в прямоугольной системе координат. Постройте граф противоположного соответствия , график противоположного соответствия в прямоугольной системе координат.

@темы: Дискретная математика, Теория графов

Не решается алгебра/высшая математика?.. ПОМОЖЕМ!

главная