?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 <email@example.com> To: firstname.lastname@example.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.
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.(((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).
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
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
correctness and clarity. This is especially important for this problem, as the proof involved i revious problems.