This is not true for classical logic, because AND can be written using NOT and OR using DeMorgan's law.
OR alone is insufficient because you still need NOT (or AND and ⊥). You can also encode sum-like behavior using negation and products (a continuation consuming a pair of continuations).