This question is about Boolean functions. Is it possible to express disjunction $x\lor y$ through conjunction $x\land y$ (or simply $xy$) and implication $x\to y$?
Asked
Active
Viewed 644 times
5
-
It should, since negation is expressable with implications – miraunpajaro Jun 02 '19 at 18:50
-
@miraunpajaro Negation expressable with implications? How? – jjagmath Jun 02 '19 at 19:24
-
I seem to remember implication and conjunction was functionally complete, I can't figure it out now though – miraunpajaro Jun 02 '19 at 20:52
-
Implication and conjunction are not functionally complete since they both map 1 (truth) into 1. Negation is expressible though implication as $x\to 0$, but one needs falsehood for this. The formula in the accepted answer just slipped my mind. – Evgeny Makarov Jun 02 '19 at 22:46
1 Answers
10
Yes - in fact, disjunction is expressible via implication alone: $$ x \lor y \equiv (x \to y) \to y $$
Adriano
- 41,576