Search All of the Math Forum:

Views expressed in these public forums are not endorsed by NCTM or The Math Forum.

Topic: Re: Discrete Math Logic Problems
Replies: 0

 Angela Richardson Posts: 42 From: UK Registered: 6/22/11
Re: Discrete Math Logic Problems
Posted: Oct 19, 2011 5:37 AM

?x means "for all x"
? means "there exists"
¬ means "not"
? means "and"
A?B means "if A is true then B is true"

b) For any historical essay, there is something more interesting and not
expensive.
c) There is at least one historical essay for which there is nothing more
interesting that is not expensive.
2. reads "if a is a multiple of x and b is a multiple of x then a+b is a
multiple of x".

----- Original Message ----
From: John <discussions@mathforum.org>
To: discretemath@mathforum.org
Sent: Wednesday, 19 October, 2011 4:45:29
Subject: Discrete Math Logic Problems

Can some help me answer through some of these questions I have finished Problem
1 part a, but the rest is a blur. Some of these will be similar to problems on
my midterm and I want to be prepared. Any help will be great.

Problem  1

Let the following predicates be given. The domain is that of all books.
? 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  give just a

word-for-word translation; your sentence should make sense.
?x.[H (x) ? ?y.(¬E(y) ? 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.

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 ? ??c.b = a · c?.

1. Formulate the following statement in English and prove that it is true (for
all x, a, b):
?a, b, x.(x|a ? x|b ? x|(a + b)).
(Using common precedence rules, the above statement should be interpreted as ?a,

b,

x.(((x|a)?(x|b))
(x|(a + b))).)
2. Same as (1), but for the statement ?a, b, x.(x|a ? x|(a + b) ? x|b)

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 the language of prepositional logic.  You may use
all the standard

logic
connectives and quantifiers.  You may also use integer constants (1,2,3 etc.),
arithmetic

operations
(+, ·), the predicate Odd(n)? ?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 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)=  ?(n > 1) ? (?m.(m|n) ? (m = 1) ? (m = n))?,  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)= ??a, b.(a < n) ? (b < n) ? (n = a ·
b)?.
Prove that any number bigger than 1 is prime if and only if it is not composite.

You can break up

your proof in 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 of this problem you can use (without  a proof ) the fact that
for any positive

integers x, 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 i
revious
problems.