-1
votes
1answer
44 views

prenex equivalence problem

Suppose: $$\forall x\exists y \phi(x,y) \to \neg \exists x\psi(x) $$ which of the following formula are prenex normal equivalence with the above formula? i didn't any idea to explain it. it's a ...
0
votes
3answers
79 views

Combination Problem Understanding

How many ways can a Doctor go to the Hospital on $5$ days of January (which has $31$ days) such that no two visits are on consecutive days? I think the solution is: $\displaystyle\binom{27}{5}$ But ...
1
vote
1answer
39 views

Partition Graph Challenging Question

I want to find in which of the following Graph, the edges cannot partitioned to triangles? Km,n,r means 3-Partite Complete Graph with m, n, and r sections. a) K7 b) K12 c) K3,3,3 d) K5,5,5 i ...
0
votes
1answer
14 views

Planner Combination Problem on Graph

I ran into a Graph Problem. Suppose G is A Planner Graph with 100 Vertices such that if connect each two Non-adjacent vertices, the resulting graph would be non-planner. what is the number of edges ...
1
vote
1answer
38 views

Perfect Matching Combination Problem

We know: A perfect matching (a.k.a. 1-factor) is a matching which matches all vertices of the graph. if we remove edges of perfect matching of a 12-Complete Graph. how many triangle remain in this ...
0
votes
1answer
46 views

Computable Set & Function

we know that i read this sentence are true? can anyone say an example for following sentence? there are a non computable set A such that
0
votes
0answers
12 views

Must the weight function be nonnegative for the greedy algorithm to be optimal for both a matroid and a greedoid?

Must the weight function be nonnegative for the greedy algorithm to be optimal for both a matroid and a greedoid? For a matroid, the codomain of the weight function is $[0,\infty)$, from Wikipedia ...
1
vote
1answer
43 views

Meaning of the characteristic polynomial of a matroid

From wikipedia The characteristic polynomial of a matroid $M$ (which is sometimes called the chromatic polynomial,[29] although it does not count colorings), is defined to be $$ p_M(\lambda) ...
0
votes
0answers
61 views

TAUTOLOGIES NP-Complete Condition

The decision problem TAUTOLOGIES is, Given $\forall x_1 \forall x_2 ... \forall x_n$ $\phi(x_1, x_2, ... x_n)$ a set of universally quantified Boolean variables and a Boolean formula ...
2
votes
2answers
56 views

Equivalent definitions for a coloop?

From wikipedia, in a matroid, An element that belongs to no circuit is called a coloop. Equivalently, an element is a coloop if it belongs to every basis. I wonder why the equivalence? From ...
0
votes
1answer
17 views

How do the dependent sets of a matroid characterize the matroid?

Wikipedia says: The dependent sets of a matroid characterize the matroid completely. The collection of dependent sets has simple properties that may be taken as axioms for a matroid. So I ...
1
vote
1answer
25 views

What kind of set system is defined to have this property?

Let $E$ be a set, and $F \in \mathcal P(E)$ has the following property: For every $x\in E$ and $Y,Z\in F$ with $x\notin Y\cup Z$, there exists $X\in F$ with $(Y\cap Z)\cup\{x\}\subseteq X$. I wonder ...
1
vote
0answers
20 views

A set system generated by a closure operator?

Given a ground set $E$, and a matroid closure operator $\tau$ on $\mathcal P(E)$, we can define a set system $(E,F)$ with $$ F := \{X \in \mathcal P(E): \forall x \in X, x \notin \tau(X-\{x\}) \}$$ ...
0
votes
0answers
29 views

Two definitions of matroid

From Wikipedia, a finite matroid $M$ is a pair $(E,F)$, where $E$ is a finite set and $F$ is a family of subsets of $E$ either with the following properties: The empty set is in $F$. if $X \in ...
0
votes
0answers
7 views

Rank feasible subset of a greedoid

From Wikipedia, given a greedoid $(E,F)$, with ground set $E$ and the class $F$ of feasible sets, A subset $X$ of $E$ is rank feasible if the largest intersection of $X$ with any feasible set has ...
0
votes
1answer
20 views

Proving the following bijection

Let $F = \lbrace S_1, S_2, \dots, S_n \rbrace$, where $S_i \subset \lbrace 1, 2, \dots, 3m\rbrace$ and define a function $f: F \to \mathbb{N}$ by $$ f(S_i) = \sum_{j \in S_i} (n+1)^{3m-j} $$ then ...
1
vote
1answer
33 views

Designing a context free grammar

I have to design a grammar over the alphabet $\sum=(a,b)$, so that $c^a(\alpha)=c^b(\alpha)$ and the second part $c^a(\alpha)\leq c^b(\alpha)$ , where $\alpha$ is a word and $c^a$ and $c^b $ are ...
1
vote
2answers
79 views

Discrete Mathematics books for Computer Science Self-study

I am an experienced software developer, want to refresh discrete math back in uni. I am looking for a book that is easy to read, contains more examples, and exercises and solutions for self study ...
1
vote
2answers
23 views

Not sure how to do Non-Homogeneous Recurrence Relations

I have a sample exam paper, and the answer is given, but I can't work out the answer from the question: Find the solution of: $a_n = \frac{1}{3}a_{n-1} + 2$ using $a_0 = 4$ Given Answer: $a_n = ...
1
vote
1answer
49 views

Confused on how an equation is reached from Concrete Mathematics

I'm reading Concrete Mathematics and trying to understand some of the equations. In particular how the author arrives to a particular solution. Given: $$L_n = \frac{n(n+1)}{2} + 1$$ the author ...
0
votes
1answer
24 views

Efficiency LL and LR parsing

My question is, is an LL parser or an LR parser more efficient (in big-O terms) ? I don't mean in terms of coding the parser, but rather in the context of the runtime of the parser. Is there a ...
0
votes
2answers
35 views

Gives regular expressions which defines regular language and what does {1,2} mean

The question is give a regular expression which defines a regular language. Question: The language over {0,1} consisting of all strings which either have length less than 3 or have 0 as their third ...
1
vote
3answers
67 views

Which discrete mathematics book to read for a software engineer?

I'm a computer science student, but I lack a good mathematics background. So I decided to start working on that. I was searching in the topic and I found that for computer science a good knowledge of ...
-1
votes
1answer
33 views

Which is a linear and homogeneous recurrence?

Which of the following choices is a linear and homogenous recurrence? $1)$ $A_n = A_{n-1} + 4A_{n-2} + 3n$ $2)$ $A_n = n + 1$ $3)$ $A_n = (A_{n-1})^2$ $4)$ $A_n = 5A_{n-1} + A_{n-2} + 3A_{n-3}$
0
votes
2answers
47 views

Recurrence Relationship Questions

Consider the recurrence defined by: $$G_0 = 0\\ G_n = G_{n-1} + 2n - 1$$ Determine what Gn is for several values of n to determine a formula for Gn. $2n$ $n$ $2n-1$ $n^2$ *I believe this one is ...
1
vote
1answer
42 views

Simple Recurrence Questions [closed]

$r$ is a real number, define a recurrence relationship for $A_n$ $$A_0 = 1\\ A_n = r\cdot A_{n-1}$$ Question: What is the value of $A_4$ $4(A{n-1})$ $r^4$ $1$ $4r$ I've pretty much eliminated ...
0
votes
0answers
19 views

(L1* ∩ L2*) = (L1 ∩ L2)* for all languages L1 and L2 over the alpabet Σ={A,B} Is it true or false and why?

plz answer me Determine whether each of the following statements is true or false. If a statement is false, give a counterexample..... 1- $(L_{1}^{*} \cap L_{2}^{*}) = (L_{1} \cap L_{2})^{*}$ for ...
0
votes
1answer
69 views

efficient algorithm to place people in a specific order

You are preparing a banquet where the guests are government officials from many different countries. In order to avoid unnecessary troubles, you are asked to check the list of international conflicts in ...
3
votes
2answers
287 views

Linear Homogeneous Recurrence Relations and Inhomogenous Recurrence Relations

I'm having some difficulty understanding 'Linear Homogeneous Recurrence Relations' and 'Inhomogeneous Recurrence Relations', the notes that we've been given in our discrete mathematics class seem to ...
1
vote
1answer
80 views

Finite state machine

I am doing discrete math, and we are studying Finite State Machines. But i am a little confuse on how to do this. Here is a question, Write a regular expression for the language, and define a finite ...
0
votes
2answers
25 views

Help with finding the generating function (with a constant )

How do you get the generating function from this formula: $8(1+x)^{7}$ I have the following formula for $(1+x)^{n}$ : $n\choose 0$ + $n \choose 1$$x^1$ + $n \choose 2$$x^2$+... +$n \choose ...
0
votes
1answer
111 views

Discrete Math: Functions and Set Questions

1) Consider the function: $f: \mathbb{R} \to \mathbb{R}$ (Real to Real Number), where $f(x)=2+x^2$, what would be all of the preimages of $3$? 1) $11$ 2) $11$, $-11$ 3) $1$, $-1$ 4) $1$ 2) Let $D ...
0
votes
0answers
72 views

Bitwise operations: using bitwise operations on bitstrings to find combinations

I'm not sure how one would go about solving this problem from my discrete math book. Here is the problem : Show how bitwise operations on bit strings can be used to find these combinations of ...
0
votes
1answer
26 views

Provide a Proof of Inequalities for the Given Problem

Let A be known as a graph. By definition an independent set S is a group of vertices (could be 0 vertices, or could be all vertices) of A where there are no two vertices from S that are adjacent in ...
0
votes
1answer
90 views

Planar and Euler's Formula Question

If a connected planar graph has four regions and six vertices, how many edges will the graph have? (I believe the answer is 8 but I'm not positive) 1) 9 2) 8 3) 6 4) 7 Graph A = ({a,b,c,d,e,f,g}, ...
0
votes
1answer
94 views

Bipartite Graphs and Trees Questions

Which of the claims below is not equivalent to the rest? 1) Every cycle in a graph "B" has an even length 2) Graph "B" is bipartite 3) Graph "B" has two components that are connected. 4) Graph "B" ...
0
votes
0answers
34 views

An independent set of vertices $\times$ the chromatic number $\ge$ the number of vertices

$A$ is a graph. By definition an independent set $S$ is a group of vertices (could be 0 vertices, or could be all vertices) of $A$ where there are no two vertices from $S$ that are adjacent in graph ...
0
votes
2answers
45 views

Discrete Math graph question?

How many edges would I need to add to $K_{n,m}$ to make it complete (instead of bipartite)? (n,m --> n+m) I know that $K_n$ has $\frac{n(n-1)}{2}$ edges and $K_{n,m}$ has $nm$ edges, but I can't ...
3
votes
1answer
181 views

“Opposite” of idempotent operation?

What is the adjective given to a mathematical operation/expression on a variable whose new value can only be described in terms of that variable's existing value? Sequential operation? Example: i = ...
0
votes
1answer
88 views

Graph Coloring Question

Given T(n) as a star graph with n edges. (Basically T(n) is a graph that has one vertex u in the center, and from u there is one edge to each vertex v1,...,vn.) It is easily know that star-graphs are ...
1
vote
1answer
35 views

Proof that such a Turing machine cannot be constructed…

Prove there can be no Turing machine $M^*$ that takes input $n$ and: i. halts printing 1 if $M_n$ halts on input 1 ii. halts printing 0 if $M_n$ doesn't halt on input 1 Intuitively I can see why ...
2
votes
0answers
41 views

Iteratively Replacing Substrings

This problem came up while I was helping someone. Informally, we have a string of characters and a "rule" which replaces a specific string with another one, and we repeat this rule until we can no ...
0
votes
1answer
81 views

Graph Theory - Introduction Questions [closed]

I have a couple of questions that are probably SUPER easy for anybody that has studied graph theory but are confusing the hell out of me. I know it may be inconvenient to help me but I have a test ...
3
votes
3answers
71 views

Is $L = \{(x,y,z) | x+y=z\}$ a regular language?

Suppose $x,y,z$ are coded as decimal or their binary representations in an appropriate DFA. Is $L$ regular? My intuition tells me that the answer is no, because there are infinitely many combinations ...
0
votes
2answers
153 views

Tough Turing machine multiple choice questions

I'm having a tough time deciding whether my answers for these questions are correct. Can anyone help me agree on something? They seem pretty easy, but I've found that they're actually difficult. ...
4
votes
1answer
110 views

Is Cartesian Product same as SQL Full Outer Join?

Is Cartesian Product same as Full Outer Join found in Relational Database SQL? I ask because I am taking a Discrete Mathematics course and I just want a better understanding of how what I am studying ...
2
votes
4answers
661 views

What is the difference between discrete and continuous mathematics?

I am studying computer science and this has me absolutely flummoxed. The definition I can find is that discrete data is countable and that continuous is uncountable. Examples are given stating that ...
3
votes
2answers
131 views

What will I be doing?

I'm a freshman studying discrete mathematics B.sc. It's easy to google ''typical mathematician jobs'' and get an idea of what mathematicians do for a living, but what sort of jobs can I expect to work ...
1
vote
2answers
35 views

binary representation shrinkage question

Suppose for a given number $n$, every operation is to add $+$ signs arbitrarily into its binary representation. Repeat this process $K$ times. Prove: It is always possible to reduce the number to ...
0
votes
1answer
50 views

How to prove such program is uncomputable

We say that two programs are equivalent if they give the same output on every input. Prove that it is impossible to write a computer program that takes as input two pieces of code, code1 and code2, ...