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: 9780357097717

Author: EPP

Publisher: CENGAGE L

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

O să vă imaginea și date compune o problemă 42 31 1 0 9

Find the largest interval centered about x = 0 for which the given initial value problem has a unique solution. y" + (tan x)y = ex, y(0) = 1, y'(0) = 0

The table below shows the acreage, number of visitors, and total revenue of state parks and recreational areas in Massachusetts, New York, and Vermont in 2010. State Acreage (in thousands) Visitors (in thousands) Revenue (in thousands) Massachusetts 350 35,271 $12,644 New York 1,354 56,322 $85,558 Vermont 69 758 $10,969 Select the three true statements based on the data in the table. A. Vermont had the highest revenue per acre of state parks and recreational areas. B. Vermont had approximately 11 visitors per acre of state parks and recreational areas. C. New York had the highest number of visitors per acre of state parks and recreational areas. D. Massachusetts had approximately 36 visitors per acre of state parks and recreational areas. E. New York had revenue of approximately $63.19 per acre of state parks and recreational areas. F. Massachusetts had revenue of approximately $0.03 per acre of state parks and recreational areas.

Chapter 8 Solutions

DISCRETE MATHEMATICS WITH APPLICATION (

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.