1: [5 + 5 pts]: For each part below, all the quantifiers have the same nonempty

Question

1: [5 + 5 pts]: For each part below, all the quantifiers have the same nonempty domain. Show that (a) xP(x) xQ(x) is logically equivalent to xy(P(x) Q(y)) (b) xP(x) xQ(x) is logically equivalent to xy(P(x) Q(y))

2: If it is hot today and it rained yesterday, then I will be miserable today. If it is not hot today, then I am going to play soccer. If it did not rain yesterday, it will not rain today. I am not miserable today. Therefore, it did not rain today or I am going to play soccer. (a) Model the above given conditions as logical statements. Clearly define the propositions. Also, indicate the conclusion. (b) If the reasoning is correct, prove it using the rules of inference for propositional logic.

3: Prove that at least one of the real numbers a1, a2, . . . , an is greater than or equal to the average of these numbers. What kind of proof did you use?

Explanation / Answer

3 Ans)    Let A be the average of a1,a2,...,an. That is,

A = (a1+a2+...+an) / n.

Suppose a1<A, a2<A, ..., an<A.

2 Ans)

a xC(x) D(x) F(x) • b. x(C(x) D(x)) F(x) • c. xC(x) F(x) ¬D(x) • d.¬xC(x) D(x) F(x) • e. xC(x) xD(x) xF(x) 1.4 12( 1 2 point each) • a. True • f. True (when x = 1, 1 + 1 > 2(1) is false) • g. False (when x = 0, 0 + 1 > 2 × 0 or pick any

They are not logically equivalent, you can take a proposition P(x) which is true only for some values of x and Q(x) false for all values of x. x(P(x) Q(x)) will not be true but xP(x) xQ(x) will be true because the hypothesis xP(x) is always false, and so the conditional statement is true. 1.4 44 (5 point ) They are not logically equivalent. Let us consider our domain to be integers, and define the following predicates, P(x) = x is even Q(x) = 4|x i.e. 4 is a divisor of x Clearly both the statements xP(x) and xQ(x) are false, hence xP(x) xQ(x) is true. However, there are x for which P(x) is true and Q(x) is false. So xP(x) Q(x) is false. Remark: (xP(x) Q(x)) (xP(x) xQ(x)) is true. Proof: Let us assume xP(x) Q(x). We have to show xP(x) xQ(x). Let us assume xP(x) is true. This mean for any c, P(c) is true. But xP(x) Q(x) would imply that Q(c) must be true. This mean for any c, Q(c) is true. This means xQ(x) is true. Similarly, one can show if xQ(x) is true then xP(x) is true. 46 (5 points each) (Remark: use identity laws, Table 6 in book) • a. We can prove this by considering two cases. If A is true, then xP(x) A is true. Also, P(c) A is true for any c. So x(P(x) A) is true too. Hence both sides are logically equivalent. If A is false, then xP(x) A is logically equivalent to xP(x). Also, P(c) A will be logically equivalent to p(c) for any c. So x(P(x) A) will be logically equivalent to x(P(x)). Hence, the given sides are logically equivalent. Hence both the statements are logically equivalent. • b. If A is true then (xP(x)) A is always true. Also, P(c) A is true for any c. So x(P(x) A) is true. Hence, both sides have same truth value. If A is false, then (xP(x))A is logically equivalent to xP(x). Similarly, P(c)A is logically equivalent to P(c). So x(P(x)A) is equivalent to xP(x)

Adding all of these inequalities, you get

(a1+a2+...+an) < nA,

so

(a1+a2+...+an)/n < A

or

A < A

which is a contradiction. Therefore at least one of the numbers must be >= A.

Let X be the average of the real numbers {a1,a2,...,aN}, then, X = (a1 + a2 + ... + aN)/N

Therefore,
X * N = a1 + a2 + ... + aN. (equation 1)

Now, to complete the proof by contradiction, assume that X is greater than each and every element of {a1, a2, ..., aN}.

Since X is strictly greater than a1, if I subtract X from the left side of equation 1 and I subtract a1 from the right side of equation 1, I will have:

X(N-1) < a2 + a3 + ... + aN

Again, subtract X from the left and subtract a2 from the right. As I am subtracting a larger number from the left side, the inequality will continue:

X(N-2)< a3 + ... + aN.

Continue doing this until you have subtracted X from the left side a total of N times and you have subtracted each of the a(i) from the right. You will then have:
X(N-N) < 0
or
0<0.

Since 0 is not strictly less than 0, it must follow that our assumption was in error. Our assumption was that no element of {a1, a2, ... , aN} was greater than or equal to X. Therefore, there must exist some a(i) in the given set of real numbers that must satisfy the condition that a(i) >= X.

Related Questions

Navigate

• Browse (All)
• Browse 1
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.