Following the last few exercises, you might begin to think that any query can be rewritten without duplication. Can it? Consider a unary predicate that is built up from the predicates P(x) and Q(x)...

Following the last few exercises, you might begin to think that any query can be rewritten without duplication. Can it? Consider a unary predicate that is built up from the predicates P(x) and Q(x) and the propositional symbols {True, False,∧, ∨,¬, ⇒}. Decide whether the following claim is true or false, and prove your answer

Modern web search engines allow users to specify Boolean conditions in their queries. For example, “social OR networks” will return only web pages containing either the word “social” or the word “networks.” You can view a query as a predicate Q; the search engine returns (in some order) the list of all pages p for which Q(p) is true. Consider the following queries:

A: “java AND program AND NOT computer”

B: “(computer OR algorithm) AND java”

C: “java AND NOT (computer OR algorithm OR program)”