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

Обьясните, пожалуйста, как это решать
Пусть S(x, y, z) и П(x, y, z) соответственно предикаты сложения
(z является суммой x и y) и умножения (z является произведением x и y), рассматриваемые на множестве Z всех целых чисел и на множестве N0 = N  {0} целых неотрицательных чисел. Какой смысл имеют следующие формулы и на каком множестве (Z или N0) они истинны?  yx П(x, y, -x)

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

18:23 

Отношение эквивалентности. Дискретная математика.

Доброго вечера...
Есть задания:
1. Доказать, что следующие отношения являются отношениями эквивалентности на множестве натуральных чисел. Определить для них число классов эквивалентности и количество элементов в каждом таком классе.
b) x R y <=> количества разных цифр в десятичных записях х и у совпадают;
c) x R y <=> суммы цифр двоичных записей х и у равны;
d) x R y <=> для х и у совпадают максимальные простые делители;
e) x R y <=> число нулей в десятичной записи х равно числу нулей в десятичной записи у.

2. Показать, что следующие отношения являются отношениями эквивалентности на множестве слов в латинском алфавите. Определить число и мощности классов эквивалентности.
b) a R b <=> совпадают слова, получающиеся из a и b после удаления первых вхождений каждой буквы в них;
c) a R b <=> совпадают слова, получаемые из а и b после удаления всех четных вхождений всякой буквы в них.

С доказать\показать сложности у меня уже не возникают, благодаря Дилетанту. Сложность возникает с числом классов и кол-вом элементов в классе.
Вот например, если взять 1.b, то получим, что число классов = числу таких чисел? Если так, то тогда число классов бесконечно? А с элементами как быть?

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

22:44 

Принцип двойственности

Здравствуйте! С использованием принципа двойственности построить формулу, реализующую функцию, двойственную к функции `f` и убедиться в том, что полученная формула эквивалентна формуле g.
`f = x*1 vv y*(z vv 0) vv bar(x) * bar(y) * bar(z)`
`g = x*(y oplus z)`
Нашел `f`* `= (x vv 0)**(y vv z*(bar(x) vv bar(y)vv bar(z))`
Как теперь доказать, что `f`* `= g = x*(y oplus z)`?

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

19:06 

Отношения на множествах. Дискретная математика.

Всем доброго вечера.
Есть задания:
1) Определить св-ва отношения на множестве N: { (x,y) | |x+y|>=6 }
2) Определить св-ва отношения на множестве R: { (f,g) | f(x)g(x)>1}
Ребят, вообще не могу. Подходил к преподавателю - повторно объяснять отказывается. Помогите, пожалуйста.

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

00:25 

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

Нужно доказать для множеств, что
X = X;
(X = Y ) ! (Y = X);
(X = Y ^ Y = Z) ! (X = Z)

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

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

20:54 

Дискретная Математика. Множества.

Добрый вечер!
Есть такое задание: "Пусть А и В подмножества множества U. Выразить АuB, используя множества А,В,U и операцию \."
Исходя из условия, я понял, что нужно пользоваться только тремя множествами и операцией разности. Но, используя только это, у меня ничего не получилось.
Я смог это сделать только использовав операцию объединения и отрицания: (U\-A)u(U\-B).
Прошу помощи!

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

15:40 

Формализовать высказывание.

Пухлощекий_Страдалец
Счастье в секундах - маленьких, острых, щедрое к детям и скупое для взрослых...
Я подозреваю, что это ужасно просто, но я не могу додуматься.
Формализовать высказывание "Если `B!=emptyset`, `B subset A` , то `B setminus A = emptyset`".
Нужно разбить на элементарные формулы, типа `B!=emptyset - D`, `B subset A - C`. И тогда можем записать так
`D vv C ->` а вот как представить `B setminus A = emptyset`? Новой переменной или как?

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

12:07 

Булев куб

Здравствуйте, подскажите, как найти число ребер в `B^n`?

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

21:11 

Вопрос, возможно, немного глупый, но я так и не разобрался по литературе.


Что будет если подать строчку 001 на вход детерминированного конечного автомата, изображенного на картинке?

Почему то в темах нет "теории автоматов"...

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

01:54 

конечные автоматы

Med-ved
Пушист. Чешите.
Доброго времени суток! нужна ваша помощь :)
Прошу привести и объяснить способ проверки автомата на синхронизируемость, помочь разобраться с рациональными отношениями в контексте автоматов и регулярных языков.
Заранее спасибо.

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

21:04 

Лампочки

wpoms.
Step by step ...


На распределительном щите имеется `a` строк с выключателями по `b` выключателей в каждой (`a` строк и `b` столбцов), каждый выключатель соединен с лампочкой в одном из домов. При нажатии выключателя, соответствующего некоторому дому, вместе с лампочкой данного дома изменяют состояния лампочки домов, стоящих в одной строке и одном столбце с данной (включенные, гаснут, выключенные загораются).
Для каких величин `a` и `b` возможна ситуация, в которой после серии переключений окажется включена только одна лампочка?



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

00:24 

Дети

wpoms.
Step by step ...


В математическом лагере `2010^2010` детей. Каждый имеет в лагере не более трех друзей и, если `A` дружит с `B`, то `B` дружит с `A`. Начальник лагеря хочет построить детей в ряд, так чтобы между любой парой друзей стояло не более `2010` детей. Всегда ли это можно сделать?



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

22:03 

Игра

wpoms.
Step by step ...


На прямоугольной доске размером `5 xx 9` играют в игру. Сначала некоторое количество дисков помещают случайным образом в квадраты доски, при этом в каждый квадрат помещают не более одного диска. Ход заключается в перемещении всех дисков из квадратов, в которых они находились, в другие квадраты, с соблюдением следующих правил:
(a) каждый диск можно переместить на один квадрат вверх, вниз, влево или вправо относительно того квадрата, в котором он находится;
(b) если диск переместили вверх или вниз в рамках одного хода, то следующим ходом его нужно будет перемещать влево или вправо;
(c) если диск переместили влево или вправо в рамках одного хода, то следующим ходом его нужно будет перемещать вверх или вниз;
(d) по завершении перемещения всех дисков в рамках одного хода ни один квадрат не должен содержать более одного диска.
Игра завершается, если нет возможности переместить все диски в рамках одного хода по указанным выше правилам. Докажите, что если в начале игры на доске разместили `33` диска, то игра в конце концов завершится. Докажите, что можно разместить на доске в начале игры `32` диска таким образом, чтобы игра могла продолжалась бесконечно.



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

23:28 

Здравствуйте! Помогите, пожалуйста, решить задачу по дискретной математике.
Задача.
Определить планарен граф или нет. Если планарен, то построить ему плоский изоморфный, если не планарен, то доказать его непланарность по теореме Портнягина-Куратовского.

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

23:22 

Теория графов и конечные автоматы

Двадцать_Семь
// иногда мне кажется, что компилятор игнорирует все мои комментарии (c)
Добрый день.
Оставили тему на самостоятельное изучение, а я ее не понимаю. Объясните, пожалуйста, как найти язык допускаемый конечным автоматом?

Автомат задан набором `({a,b},{q_1,q_2,q_3,q_4,q_5}, Q_s, Q_f)`, где {a,b} - алфавит,`Q_s` -множество начальных состояния, `Q_f` - множество конечных состояний. Запись `(i,j,a,b)` означает, что дуга (i,j), идущая из `q_i` в `q_j` имеет метки a,b:
Входы: `Q_s={1}`
Выход: `Q_s={3,4}`
Дуги: (1,5,b),(1,4,a),(2,1,b),(2,2,a),(5,4,b)
`L_0=a^m ba^n | n,m >= 0}`
1. Построить граф автомата и найти язык L, допускаемый автоматом.
Вот какой у меня получился граф:
читать дальше
У меня даже нет конкретных вопросов, потому что я не понимаю, что мне надо делать дальше(((

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

18:07 

Saiyuri-chan
Every moments and times are special.© L is so cute, you could die. Really! ©
Надо определить является ли число числом (L-R) типа.
Число

Вообще, мне хотелось бы понять, как в целом это все определяется. Я конечно прочитала, что должно быть выполнено три условия, но вот первое же действие в пособии поставило меня в тупик...
Первое действие

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

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

21:16 

СКНФ

Строю СКНФ ((y+¬x)->(y|x)((y¬x)~z) по таблице истинности и получаю: (¬x+¬y+¬z)(¬x+¬y+z)(¬x+y+¬z)(x+¬y+z)(x+y+¬z)(x+y+z). Теперь строю СКНФ с помощью эквивалентных преобразований и получаю результат, в котором пять членов совпадает, а один отличается: вместо (x+y+z) получаю (¬x+y+z). Я так понимаю, что СКНФ должна получится одинаковая. Много раз проверяю, ошибку найти не могу. Помогите пожалуйста.

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

11:44 

Графы

yoggik_wow
And I'm feeling good.
Добрый день.
Есть вот такая задачка:
Верно ли, что в вершинно k-связном графе любые k+1 вершин лежат на общей цепи?

Я нашла такую теорему, которая утверждает, что если граф k-связен, то любые k вершин принадлежат простому циклу.
Далее я отталкивалась уже от определений. Раз у нас есть k вершин в простом цикле, то это значит, что они различны. А т.к граф k-связен, то у него k+1 вершина, и эта еще одна вершина тоже будет различной (правда не до конца понятно почему). Отсюда следует, что все вершины и ребра различны, а значит это определение общей цепи.

Хотелось бы узнать, правильны ли мои рассуждения?

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

13:44 

Сколько функций содержит множество?

Дано вот такое множество :
( L - T0 ) U T1

Вот мои попытки решения :
Для начала разберемся с операциями, операция '-' - означает, что нужно найти такие элементы, которые есть только в L и только в T0...
Запишем линейное представление функции :
a0 + a1x1 + a2x2 + ... + anxn
Теперь разберемся с T0 в этой функции, для этого просто подставим заместо x - нули, и приравняем наше L к 0.
Т.е имеем :
a0 + a1 * 0 + a2 * 0 + ... + an * 0 = 0 => a0 = 0, а все остальное комбинируем как хотим -> получаем что мощность вот таких функций = 2 ^ n( ну т.е линейных, где фиксировано a0 )...
Теперь у меня возникает вопрос, а мощность множества ( L - T0 ) чему будет равна ?
Вот такие варианты есть, либо 2 ^ n, либо |L| - 2 ^ n + |T0| - 2 ^ n ???

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

15:26 

Конечные автоматы

Med-ved
Пушист. Чешите.
Доброго времени суток. Прошу помощи.
Построить автомат с выходом, который возвращает количество букв а после самой левой буквы b в слове {a,b}* по модулю 4.
И, пожалуйста, посоветуйте какие-нибудь материалы по конечным автоматам: алгоритм детерминации (детерминизации?), построение регулярного выражения по автомату.
Буду благодарен =)

к сожалению, не нашел темы "Конечные автоматы" =(

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

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

главная