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: 288
Joined: Sun Dec 14, 2008 11:07 pm
Contact:

Re: Discrete Math Logic Problems

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.