General Discrete Math Help

• Oct 7th 2007, 07:19 PM
Eclyps19
General Discrete Math Help
Well I've got a pretty lengthy study guide for an exam next week and I have a few questions that I get a little stuck on... Any help, with our without an explanation (with is always best!) would be appreciated.

-------------

The converse and contrapositive of this:
x^2 = 1 → x = ±1

I'm not sure if I make everything a ¬ or just what is between the = signs. Do I make the 1 a 0? Does the 1 imply a tautology or is it simply a constant 1?

--------------

I need to write this statement using the quantifiers "for all (or for every)" and "there exists".

An integer cannot be both even and odd.

What I could muster up was "For all integers, there exists only an odd or only an even". This really doesn't make much sense, but I really couldn't get much out of it.

---------------

Negations. I never know what I need to negate... :(

Every integer is divisible by a prime. Would this be "Not every integer is divisible by a prime"?

If n is an integer, n/(n+1) is not an integer. Would this be "If n is not an integer, n/(n+1) is not an integer"? I could use an explanation for this one!

---------------

And finally....

I need to answer true or false and supply a direct proof or a counter-example to each of the following:

There exists an integer n ≠ 0 such that nq is an integer for every rational number q.

and

For every rational number q, there exists an integer n ≠ 0 such that nq is an integer.

To be honest, I can't even begin to answer these. I'm totally lost.

-------------

I know this is a lot to throw at you guys, but any help is GREATLY appreciated. I'm so horrible at math, and my teacher honestly doesn't know discrete math. He's teaching this for the first time because the school couldn't find any other teachers.

• Oct 7th 2007, 11:42 PM
Jhevon
Quote:

Originally Posted by Eclyps19
Well I've got a pretty lengthy study guide for an exam next week and I have a few questions that I get a little stuck on... Any help, with our without an explanation (with is always best!) would be appreciated.

-------------

The converse and contrapositive of this:
x^2 = 1 → x = ±1

I'm not sure if I make everything a ¬ or just what is between the = signs. Do I make the 1 a 0? Does the 1 imply a tautology or is it simply a constant 1?

"converse" and "contrapositive" refer to pretty standard modifications, they're not really something you have to wonder about.

for the statement: $\displaystyle P \implies Q$

the converse is: $\displaystyle Q \implies P$

the contrapositive is: $\displaystyle (\neg Q) \implies (\neg P)$

so for: $\displaystyle x^2 = 1 \implies x = \pm 1$

converse: $\displaystyle x = \pm 1 \implies x^2 = 1$

contrapositive: $\displaystyle x \ne \pm 1 \implies x^2 \ne 1$

Quote:

I need to write this statement using the quantifiers "for all (or for every)" and "there exists".

An integer cannot be both even and odd.

What I could muster up was "For all integers, there exists only an odd or only an even". This really doesn't make much sense, but I really couldn't get much out of it.
for every integer, n, either n is odd or n is even

Quote:

Negations. I never know what I need to negate... :(

Every integer is divisible by a prime. Would this be "Not every integer is divisible by a prime"?
the negation of "every", "for all", "for every" etc is "there exists." see here

thus, here we have: there exists an integer that is not divisible by a prime

Quote:

If n is an integer, n/(n+1) is not an integer. Would this be "If n is not an integer, n/(n+1) is not an integer"? I could use an explanation for this one!

see the link above. (there are better resources out there also, try a google search).

the negation of an implication is as follows: to negate $\displaystyle P \implies Q$ we write $\displaystyle P \wedge (\neg Q)$. (you can use "but" instead of "and" if it makes the phrase sound better)

thus we get: n is an integer and n/(n + 1) is an integer.

Quote:

And finally....

I need to answer true or false and supply a direct proof or a counter-example to each of the following:

There exists an integer n ≠ 0 such that nq is an integer for every rational number q.
False.

Proof: Fix $\displaystyle n \in \mathbb{ Z}$, $\displaystyle n \ne 0$. And choose $\displaystyle q = \frac ab$ for $\displaystyle a,b \in \mathbb { Z}$, $\displaystyle b \ne 0$, such that q is in lowest terms and $\displaystyle nq = n \cdot \frac ab = \frac {na}b \in \mathbb { Z}$. Then, $\displaystyle n = bc$ for $\displaystyle c \in \mathbb { Z}$ and $\displaystyle c \ne 0$. (and remember, $\displaystyle n$ is fixed at this value).

Now choose $\displaystyle q = \frac {x^2 + 1}{n \left( x^2 + 2 \right)}$ for $\displaystyle x \in \mathbb { Z}$.

Then $\displaystyle nq = \frac {n \left( x^2 + 1 \right)}{n \left( x^2 + 2 \right)} = \frac {x^2 + 1}{x^2 + 2} \not \in \mathbb { Z}$

QED

Quote:

For every rational number q, there exists an integer n ≠ 0 such that nq is an integer.
True.

Proof: Let $\displaystyle q$ be a rational number. then we can write $\displaystyle q = \frac ab$ for $\displaystyle a,b \in \mathbb {Z}$ and
$\displaystyle b \ne 0$. Choose $\displaystyle n = b$. then $\displaystyle n \ne 0$ and $\displaystyle nq = n \cdot \frac ab = b \cdot \frac ab = a \in \mathbb{ Z}$. thus $\displaystyle nq$ is an integer

QED
• Oct 9th 2007, 01:00 AM
Eclyps19
great! That was a huge help! Especially the last one. Appreciate it.
{"found_math": true, "script_math_tex": 0, "script_math_asciimath": 0, "math_annotations": 0, "math_alttext": 0, "mathml": 0, "mathjax_tag": 0, "mathjax_inline_tex": 1, "mathjax_display_tex": 0, "mathjax_asciimath": 0, "img_math": 0, "codecogs_latex": 0, "wp_latex": 0, "mimetex.cgi": 0, "/images/math/codecogs": 0, "mathtex.cgi": 0, "katex": 0, "math-container": 0, "wp-katex-eq": 0, "align": 0, "equation": 0, "x-ck12": 0, "texerror": 0, "url": "http://mathhelpforum.com/discrete-math/20140-general-discrete-math-help-print.html", "fetch_time": 1524554805000000000, "content_mime_type": "text/html", "warc_filename": "crawl-data/CC-MAIN-2018-17/segments/1524125946565.64/warc/CC-MAIN-20180424061343-20180424081343-00156.warc.gz", "warc_record_offset": 198562933, "warc_record_length": 4196, "token_count": 1540, "char_count": 5477, "score": 3.65625, "int_score": 4, "crawl": "CC-MAIN-2018-17", "snapshot_type": "latest", "language": "en", "language_score": 0.9502556920051575, "file_path": "/sailhome/yjruan/project/latent-lm/data/processed/finemath-4plus/finemath-4plus/train-00063-of-00064.parquet"}