How to express "AND" and "OR" by just using "Implies" and "Negation"?
I tried 10+ combination for AND but non of them worked out:
I tried: (X -> Y) -> ( X -> Y) , !(X -> Y) -> (X -> Y) , !(X -> Y) -> !(X -> Y) (X -> Y) -> !(X -> Y) etc.
We can cheat and use truth tables to figure it out. Truth tables for ->, !, && and || look like:
X Y X->Y ~X ~Y X && Y X || Y
T T T F F T T
T F F F T F T
F T T T F F T
F F T T T F F
We see that && has one T and || has one F. || is actually pretty close to ->; it just has the F shifted from where X is F to where X is T. When you see something like that your first thought should be to negate variables to exchange the corresponding sections of the truth table; by negating X in X -> Y, we should exchange sections of the truth table and get the values coming out the same as X && Y. Indeed,
X Y ~X ~X -> Y X || Y
T T F T T
T F F T T
F T T T T
F F F F F
That's one down. For &&, we see it's similar, except that we have one T instead of one F as ->. When you see this, thing negating the whole thing:
X Y X && Y !(X && Y)
T T T F
T F F T
F T F T
F F F T
Now we see we need to negate Y to swap the first and second rows of the truth table for ->:
X Y !Y X -> !Y !(X -> !Y)
T T F F T
T F T T F
F T F T F
F F T T F
This comes out as required. It's all a matter of seeing what you have to work with - where you're starting - and understanding where you need to get to, and then working from either or both ends to figure out the linkage. In these cases, it was convenient to think in terms of "number of Ts", but you might find something more useful depending on the scenario.