Applying the AND operator to these two searches (which is Search B) will hit on the documents that are common to these two searches, which is Document 4.Ī similar evaluation can be applied to show that the following two searches will both return Documents 1, 2, and 4: Similarly the search "(NOT dogs)" will hit on Documents 1 and 4. So the negation of that search (which is Search A) will hit everything else, which is Document 4.Įvaluating Search B, the search "(NOT cats)" will hit on documents that do not contain "cats", which is Documents 2 and 4. ![]() To evaluate Search A, clearly the search "(cats OR dogs)" will hit on Documents 1, 2, and 3. Document 4: Contains neither "cats" nor "dogs". Document 3: Contains both "cats" and "dogs". The corpus of documents containing "cats" or "dogs" can be represented by four documents:ĭocument 1: Contains only the word "cats". Search A: NOT (cats OR dogs) Search B: (NOT cats) AND (NOT dogs) De Morgan's laws hold that these two searches will return the same set of documents: Consider a set of documents containing the words "cats" and "dogs". the overbar is the logical NOT of what is underneath the overbar.ĭe Morgan's laws commonly apply to text searching using Boolean operators AND, OR, and NOT.In set theory and Boolean algebra, these are written formally asĪ ∪ B ¯ = A ¯ ∩ B ¯, A ∩ B ¯ = A ¯ ∪ B ¯, is the logical AND, ![]() Where "A or B" is an " inclusive or" meaning at least one of A or B rather than an " exclusive or" that means exactly one of A or B. The complement of the intersection of two sets is the same as the union of their complements.The complement of the union of two sets is the same as the intersection of their complements.The negation of a conjunction is the disjunction of the negations.The negation of a disjunction is the conjunction of the negations.The rules can be expressed in English as: The rules allow the expression of conjunctions and disjunctions purely in terms of each other via negation. They are named after Augustus De Morgan, a 19th-century British mathematician. ![]() In propositional logic and Boolean algebra, De Morgan's laws, also known as De Morgan's theorem, are a pair of transformation rules that are both valid rules of inference.
0 Comments
Leave a Reply. |