The Math Forum

Search All of the Math Forum:

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

Math Forum » Discussions » Math Topics » discretemath

Notice: We are no longer accepting new posts, but the forums will continue to be readable.

Topic: Re: Discrete Math Logic Problems
Replies: 0  

Advanced Search

Back to Topic List Back to Topic List  
Angela Richardson

Posts: 42
From: UK
Registered: 6/22/11
Re: Discrete Math Logic Problems
Posted: Oct 19, 2011 5:37 AM
  Click to see the message monospaced in plain text Plain Text   Click to reply to this topic Reply

?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
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 <>
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,


(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

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

(+, ·), 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

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 ·
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

Point your RSS reader here for a feed of the latest messages in this topic.

[Privacy Policy] [Terms of Use]

© The Math Forum at NCTM 1994-2018. All Rights Reserved.