All Questions
Tagged with discrete-mathematics computer-science
716
questions
6
votes
5
answers
420
views
Need an intuitive example for how "P is necessary for Q" means "Q$\implies$P"?
I am confused about how "P is necessary for Q" means "Q$\implies$P" (source: Kenneth Rosen DMGT).
Intuitively, I interpret "P is necessary for Q" as "for Q to happen,...
- 69
0
votes
0
answers
50
views
Determining if an argument is valid using equivalence transformations
I am really struggling with this problem. I am able to mentally say that the argument is valid but unable to prove it using algebra.
The problem is:
Premise 1: (p —> q) ^ (r -> s)
Premise 2: p ...
- 21
-2
votes
2
answers
152
views
Logic equivalence question
I have a question about discrete mathematics question that I have been struggling to solve. Here is the question:
Each of the two rooms (room I and room II) contains either a lady or a tiger. If a ...
- 41
0
votes
1
answer
51
views
Formal proof for a set of closed logical sentences.
I am currently taking a course in logic for computer science and reading a book by M. R. A. Huth and M. D. Ryan, Logic in Computer Science. I came across an exercise where I understand but need help ...
- 31
1
vote
2
answers
130
views
How to formalize and prove a reasoning as propositional logic?
If both E and H are at a lecture, then A won't be there. If E is at the lecture, then H will also be there. If A is not at the lecture, then E will be there. Thus, either E but not A is at the lecture,...
- 59
1
vote
4
answers
477
views
How to show that $p∨q, q∨r, p\to ¬r ⊢ q$?
How to prove $p∨q, q∨r, p\to ¬r ⊢ q$ using natural deduction?
I don't really know how to go about it since I have 2 or statements, but here is my try.
$p∨q$ premise
$q∨r$ premise
$...
- 59
1
vote
1
answer
220
views
Design a finite state machine that performs the serial addition of three arbitrary binary numbers
Design a finite state machine (by its transition diagram) that performs the serial addition of three arbitrary binary numbers.
For a finite state machine for two binary numbers I got it, but for 3 ...
- 67
4
votes
1
answer
285
views
Printing neatly
I'm working on the following problem (which is not my actual question)
Consider the problem of neatly printing a paragraph with a monospaced font (all
characters having the same width). The input ...
- 910
0
votes
0
answers
58
views
Given $f \in \Omega(g)$, prove that $\mathcal{O}(g) \subseteq \mathcal{O}(f)$
My proof goes like this:
By definition
$f \in \{ g:\mathbb{N} \rightarrow \mathbb{R}|\exists \beta > 0 \exists n_0 \in \mathbb{N} \forall n \geq n_0 : 0 \leq f(n) \leq \beta g(n) \}$
therefore $0 \...
- 11
2
votes
4
answers
72
views
Prove $ \lg (n + 1) - 1\le h \le \lg n\implies h=\lfloor\lg n\rfloor$
For integer $n>0$ and integer $h$ prove ($lg$ means $log_2$)
$$
\lg (n + 1) - 1\le h \le \lg n\implies h=\lfloor\lg n\rfloor
$$
I'm thinking I may use $x-1<\lfloor x \rfloor \le x \le \lceil x \...
- 910
2
votes
1
answer
29
views
$(\lambda z. zy)(\lambda z. zy)$ - reducing using $\beta$ reduction and $\alpha$ conversion
Good day . I need to reduce the following expression of lambda calculus:
$(\lambda z. zy)(\lambda z. zy)$
Now, since I am having the variable $y$ in both the left and right pair of parentheses, I ...
- 893
0
votes
1
answer
40
views
Is the stable marriage problem defined for $0$ people?
When proving properties of algorithms which are supposed to solve the stable marriage problem, I find myself unable to prove them sometimes in the case of there being $0$ things to pair with each ...
- 3,019
3
votes
4
answers
685
views
Why can't well ordered sets have infinite decreasing subsequences?
Chapter 2 of Mathematics for Computer Science presents the following:
Define the set $\mathbb F$ of fractions that can be expressed in the form $\frac{n}{n+1}$. Define $\mathbb N$ as the set of ...
- 47
1
vote
1
answer
112
views
Why is a head redex always the leftmost redex?
I am studying lambda-calculus from Sorensen's book (Lectures on the Curry-Howard Isomorphism, 2006 edition), and on page 15 there is a definition of 'head redex'
in a lambda term $\lambda\vec{z}.(\...
0
votes
1
answer
31
views
How to find the location of an object moving through a graph with inputs of arcs?
I have a bidirected graph which represents rooms in a building. I have scanners set up on doorways which can detect an object moving through them (but not direction). Based on this information what ...
