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.
. . .
(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
1. Formulate the following statement in English and prove that it is true (for all x, a, b):
. . .
Using common precedence rules, the above statement should be interpreted as
. . .
2. Same as (1), but for the statement
. . .
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, 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":
. . .
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:
. . .
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.
