Explanation Given information: Let A be a set with a partial order relation R and let S be a set of strings over A . Concept used: A relation ≺ _ on S is defined as follows: For any two strings in S , a 1 a 2 a 3 ... a m and b 1 b 2 b 3 .... b n where m and n are positive integers. If m ≤ n and a i = b i for all i = 1 , 2 , 3 , ..... , m then a 1 a 2 a 3 , .... a m ≺ _ b 1 b 2 .... b n . If for some integer k with k ≤ m , k ≤ n and k ≥ 1 , a i = b i for all i = 1 , 2 , 3 , .... , k − 1 and a k ≠ b k but a k R b k then a 1 a 2 , ...... , a m ≺ _ b 1 b 2 , .... , b n If ε is the null string and s is any string in S , then ε ≺ _ s . Proof: To prove ≺ _ is reflexive: Let s be any string in S . If s = ε , then s ≺ _ s by ( 3 ) . Suppose s ≠ ε . Let s = a 1 a 2 a 3 , ...... , a m . Then m ≤ m and a i = a i for all i = 1 , 2 , 3 , .... , m . Therefore, by ( 1 ) s = a 1 a 2 a 3 .... a m ≺ _ a 1 a 2 a 3 ......... a m = s s ≺ _ s Hence, ≺ _ is reflexive. To prove ≺ _ is antisymmetric: Let s = a 1 a 2 a 3 ...... a m ∈ S and t = b 1 b 2 b 3 ...... b m ∈ S such that s ≺ _ t and t ≺ _ s . Suppose i be the least positive integer such that a i ≠ b i . Since s ≺ _ t and t ≺ _ s therefore, a i R b i & b i R a i Since R is partial order relation on A , therefore a i R b i & b i R a i implies that a i = b i

5th Edition

ISBN: 9781337694193

Author: EPP, Susanna S.

Publisher: Cengage Learning,

See similar textbooks

Concept explainers

Statements and Logic

Logic is the analysis of general patterns of thoughts without regard to any specific sense of context.

Videos

Question

Chapter 8.5, Problem 12ES

To determine

To prove:

≺_ is a partial order relation.

Expert Solution & Answer

Want to see the full answer?

Check out a sample textbook solution

See solution

Chapter 8.5, Problem 11ES

Chapter 8.5, Problem 13ES

Students have asked these similar questions

x4 -289 Consider the function f(x) = 2 X-17 Complete parts a and b below. a. Analyze lim f(x) and lim f(x), and then identify the horizontal asymptotes. x+x X--∞ lim 4 X-289 2 X∞ X-17 X - 289 lim = 2 ... X∞ X - 17 Identify the horizontal asymptotes. Select the correct choice and, if necessary, fill in the answer box(es) to complete your choice. A. The function has a horizontal asymptote at y = B. The function has two horizontal asymptotes. The top asymptote is y = and the bottom asymptote is y = ☐ . C. The function has no horizontal asymptotes. b. Find the vertical asymptotes. For each vertical asymptote x = a, evaluate lim f(x) and lim f(x). Select the correct choice and, if necessary, fill in the answer boxes to complete your choice. e

Explain why lim x²-2x-35 X-7 X-7 lim (x+5), and then evaluate lim X-7 x² -2x-35 x-7 x-7 Choose the correct answer below. A. x²-2x-35 The limits lim X-7 X-7 and lim (x+5) equal the same number when evaluated using X-7 direct substitution. B. Since each limit approaches 7, it follows that the limits are equal. C. The numerator of the expression X-2x-35 X-7 simplifies to x + 5 for all x, so the limits are equal. D. Since x²-2x-35 X-7 = x + 5 whenever x 7, it follows that the two expressions evaluate to the same number as x approaches 7. Now evaluate the limit. x²-2x-35 lim X-7 X-7 = (Simplify your answer.)

A function f is even if f(x) = f(x) for all x in the domain of f. If f is even, with lim f(x) = 4 and x-6+ lim f(x)=-3, find the following limits. X-6 a. lim f(x) b. +9-←x lim f(x) X-6 a. lim f(x)= +9-←x (Simplify your answer.) b. lim f(x)= X→-6 (Simplify your answer.) ...

Chapter 8 Solutions

Discrete Mathematics With Applications

Ch. 8.1 - If R is a relation from A to B, xA , and yB , the...Ch. 8.1 - Prob. 2TY Ch. 8.1 - Prob. 3TY Ch. 8.1 - Prob. 4TY Ch. 8.1 - If R is a relation on a set A, the directed graph...Ch. 8.1 - As in Example 8.1.2, the congruence modulo 2...Ch. 8.1 - Prove that for all integers m and n,m-n is even...Ch. 8.1 - The congruence modulo 3 relation, T, is defined...Ch. 8.1 - Define a relation P on Z as follows: For every...Ch. 8.1 - Prob. 5ES

Knowledge Booster

Learn more about

Need a deep-dive on the concept behind this application? Look no further. Learn more about this topic, subject and related others by exploring similar questions and additional content below.