The following seems like a bug. Now, it could be that Logic is not built to handle such requests, in which case it should die gracefully, instead of giving funny answers.
> Logic[BooleanSimplify]((x > 3) &and ¬ (y > 5) &or (y > 5));

                (5 < y) &or ((3 < x) &and ¬(5 < y))

and yet
> Logic[BooleanSimplify](a &and ¬ b &or b);

                               a &or b

Please Wait...