Logic Question
-
Is this statement true:
(a && b) || (c && d) = a && d && (b || c)
-
No. The simplest aspect to look at is that, on the left side a can be either true or false and the statement can still be true. On the right side, a must be true for the statement to be true.
-
It was my mistake. Google doesn't allow parenthesis. If you type:
(bill Clinton) OR (george bush)
into the regular search bar, you're probably expecting to get a count
of pages that mention one or the other - note that the and is implied,
so that query is (a and b) or (c and d)
If you click the advanced search button, google fills the advanced search boxes as follows:
Find results with all these words: bill bush
Find results with at least one of these words: Clinton george
When you click search on the advanced page, google puts you back over on simple search and fills the text box with:
Bill bush Clinton OR george
Which is equivalent to: a and d and (b or c)
The whole thing threw me off until I realized that google had thrown
away my parenthesis in the original query. It doesn't SHOW you
that it's throwing them away, but it obviously does. The original
query was actually:
a and b or c and d
which is indeed:
a and d and (b or c)
Anyway, you want to know why I'm asking this question, here's
why. I have implemented a search function for a website. It
correctly parses logical operators such as "and" "or" "not" etc. and
also recognizes quotation marks. Unlike google, mine also handles
arbitrary levels of nesting, so you can search for (a and b) or (c and
(d or e)) (note that this isn't a particularly useful query, but
whatever).
I have now been asked to implement an "advanced search" function.
I already pointed out that it doesn't get much more advanced than what
I've already got. When people say, "advanced search" what they
actually mean is, "do what google does, give me text boxes
appropriately labeled for AND words and OR words."
This is easy to do, but what I WANT to do is let you switch back and
forth between advanced and simple and intelligently populate the text
boxes - just like google does. The problem I have is handling
parenthesis when going from simple to advanced. Here one of many
use cases that causes problems.
Input from simple search: (a and b) or (b and c)
Output - advanced search form
Text box: Find articles with ALL these words: (empty)
Text box: Find articles with ANY of these words: (a and b) (b and c)
If just seems to me that this is really going to confuse a lot of people, and I'd rather not do that.
Where I stand right now, after thinking about this for just a few
hours, is that I will not allow a user to go to advanced mode if they
start in simple mode. I guess that google already thought of
this, and that was why they didn't implement parenthesis.
-
It looks like what they're doing (based on your example) is simple word-based parsing of the statement. BTW, you can enclose a phrase in quotes to make it "literal"... So for example "Bill Clinton" OR "George Bush". I think... :) But back to what I was saying. They looked at the original search phrase and broke it down as follows: Bill (Clinton OR George) Bush.
-
like I said, they disregard parenthesis.
And yes, you can enclose words in quotes. I wanted an example of
(a and b) or (c and d). I did not want an example of "a b" or "c
d"
-
@tofu said:
like I said, they disregard parenthesis.
And yes, you can enclose words in quotes. I wanted an example of
(a and b) or (c and d). I did not want an example of "a b" or "c
d"
Doh. Looks like they disregard operator precedence too, as the ANDs should have been evaluated before the OR
-
This calls for a logic table. It really debunks the situation well.
-
@mickeyreiss said:
This calls for a logic table. It really debunks the situation well.
What do you mean, "debunks?"
-
@tofu said:
@mickeyreiss said:
What do you mean, "debunks?"This calls for a logic table. It really debunks the situation well.
Debunks a claim anyone would have made that
(a && b) || (c && d) = a && d && (b || c)
might be true [for all possible boolean values of {a-d}].
Because it would seem that Google makes that claim, but apparently it's really just a not-so-correct search expression parser.
-
@dhromed said:
Because it would seem that Google makes that claim, but apparently it's really just a not-so-correct search expression parser.
well, google throws away parenthesis. Once they do that, what's left is evaluated correctly as per the rules of logic.
-
Anyway, surely a search for:
"bill clinton" or "george bush"
would get better results?
-
yes, I'm sure it would.
I know how to operate a search engine, thank you. You don't
understand the point of my question because you did not read the thread
or did not understand what you read. I don't care about Bush or
Clinton. I care about how google converts a simple search to an
advanced search because I'm a programmer and I had to impliment that
exact same feature. This thread is not about searching.
This thread is (was) about lexical parsing, producing data structures
from search strings.
jesus fucking christ
-
@tofu said:
Input from simple search: (a and b) or (b and c)
Output - advanced search form
Text box: Find articles with ALL these words: (empty)
Text box: Find articles with ANY of these words: (a and b) (b and c)
If just seems to me that this is really going to confuse a lot of people, and I'd rather not do that.To me, this is an issue of interface design. Obviously, if the user types something into simple search, clicks advanced search, and then clicks search without modifying anything, it should return the exact same results as if the user types something in simple search and just clicks search. Anything else just wouldn't make sense.
So, you should be thinking of ways of altering the user interface in order to make your program's logic easier to understand. Off the top of my head, I'd say changing "words" to "terms" would be a good start. "(a and b)" isn't a word, but it *is* a term. Calling it a word can only lead to confusion.
