Search All of the Math Forum:
Views expressed in these public forums are not endorsed by
Drexel University or The Math Forum.
|
|
|
|
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.
|
|
|
|
