## Discrete Math Logic Problems

Sequences, counting (including probability), logic and truth tables, algorithms, number theory, set theory, etc.
toogood4007
Posts: 1
Joined: Wed Oct 19, 2011 4:40 am
Contact:

### Discrete Math Logic Problems

Can some help me answer through some of these questions

Problem 1) Let the following predicates be given:

. . .B(x) = "x is boring"
. . .H(x) = "x is a historical essay"
. . .E(x) = "x is expensive"
. . .M(x, y) = "x is more interesting than y"

(a) Write the following statements in predicate logic:

. . .1. All historical essays are boring.
. . .2. There are some boring books that are not historical essays.
. . .3. All boring historical essays are expensive.

(b) Write the following predicate logic statement in everyday English. Don't just give a word-for-word translation; your sentence should make sense.

. . .$\forall x.[H(x)\, \rightarrow\, \exists y.(\neg E(y)\, \wedge \, M(y, x)]$

(c) Formally negate the statement from part (b). Simplify your negated statement so that no quantifier lies within the scope of a negation.

I have finished Problem 1 part a, but the rest is a blur. I am really lost and any help will be great. Thanks. I solved Problem 1, but i have no idea how to solve problem 2,3,4.

Problem 2) In this problem, all variables range over the set of all integers. Recall that the relation a | b (read "a divides b") is defined as $a\, |\, b\, \equiv\, ''\exists c.b\, =\, a\, \dot\, d''$

1. Formulate the following statement in English and prove that it is true (for all x, a, b):

. . .$\forall a,b,x.\left(x|a\, \wedge\, x|b\, \rightarrow\, x|(a\, +\, b)\right)$

Using common precedence rules, the above statement should be interpreted as
. . .$\forall a,b,x.\left(\left(\left(x|a\right)\wedge\left(x|b\right)\right)\, \rightarrow\, \left(x|(a\, +\, b)\right)\right)$

2. Same as (1), but for the statement
. . .$\forall a,b,x.\left(x|a\, \wedge\, x|(a\, +\, b)\, \rightarrow\, x|b\right)$

3. Prove again the statement in (2), but rather than proving it from scratch, give a proof using the statement in part (1).

Problem 3) For each of the following statements:

. . .Formulate the statement in prepositional logic. You may use all of the
. . .standard logic connectives and quantifiers. You may also use integer
. . .constants (1, 2, 3, etc.), arithmetic operations (+, ×, etc.), the
. . .predicate $Odd\, \equiv\, \exists m.n\, =\, 2m\, +\, 1$, and the relation a|b.

. . .State if the statement is true or false.

. . .Prove your answer correct; i.e., prove either the statement or the
. . .negation of the statement. In all statements, the variables range of
. . .the set of nonnegative integers.

1. The product of any two odd integers is odd.

2. For any two numbers x and y, the sum x + y is odd if and only if the product x × y is odd.

3. For all integers a, b, and c, if a divides b and b divides c, then a divides c.

Problem 4) Also in this problem, all variables range over the nonnegative integers. Recall the definition of "prime":
. . .$Prime(n)\, =\, ''\left(n\, >\, 1\right)\, \wedge\, \left(\forall m.(m|n)\, \rightarrow\, (m=1)\, \vee\, (m=n)\right)'';$
i.e., a number bigger than 1 is prime if and only if it is only divisible by 1 and itself. A number is composite if it can be written as the product of smaller numbers:
. . .$Composite(n)\, =\, ''\exists a.b(a
Prove that any number bigger than 1 is prime if and only if it is not composite. You can break up your proof into two parts as follows:

. . .1. First prove that for any n > 1, if n is prime, then n is not composite.

. . .2. Next prove that for any n > 1, if n is not composite, then n is prime.

In the solution to this problem you can use (without proof) the fact that for any positive integers x and y, if x | y, then x < y. Remember that your solution will be graded both for correctness and clarity. This is especially important for this problem, as the proof involved is a bit longer than the proofs in the previous problems.

nona.m.nona
Posts: 262
Joined: Sun Dec 14, 2008 11:07 pm
Contact:

### Re: Discrete Math Logic Problems

toogood4007 wrote: i have no idea how to solve problem 2,3,4.

Have proofs not been covered in your class yet? Because that is a topic of study in its own right. If you truly "have no idea how to" proceed, then we probably cannot assist. However:

Problem 2) In this problem, all variables range over the set of all integers. Recall that the relation a | b (read "a divides b") is defined as $a\, |\, b\, \equiv\, ''\exists c.b\, =\, a\, \dot\, d''$

1. Formulate the following statement in English and prove that it is true (for all x, a, b):

. . .$\forall a,b,x.\left(x|a\, \wedge\, x|b\, \rightarrow\, x|(a\, +\, b)\right)$

Since you did Problem 1, part (b), you can at least do the "formulate" part of this exercise. Turning to the proof part, start by applying the definition: If x|a, then there exists some q so qx = a. If x|b, then there is some r so rx = b. Use substitution in "a + b", factor, and apply the definition again.

2. Same as (1), but for the statement
. . .$\forall a,b,x.\left(x|a\, \wedge\, x|(a\, +\, b)\, \rightarrow\, x|b\right)$

Apply the definition again. See where this leads.

Problem 3) For each of the following statements:

. . .Formulate the statement in prepositional logic....
. . .State if the statement is true or false.

1. The product of any two odd integers is odd.

Since you did Problem 1, part (b), you can do the "formulate" part for each of these. For this particular exercise, what have you found when you multiplied various pairs of odd integers? When you stated two generic odd integers in terms of the definition, multiplied out these expressions, and simplified, what did you get?

2. For any two numbers x and y, the sum x + y is odd if and only if the product x × y is odd.

When you added factors of odd composite numbers, what did you find?

3. For all integers a, b, and c, if a divides b and b divides c, then a divides c.

When you applied the definition, what did you find?