Can we express C(x,y) and R(x,y) using binary conjunction, disjunction and negation?
Since negation and one of conjunction or disjunction is sufficient to express all binary functions, the answer is definitely yes. Let us start with the easy one.
If you observe C(x,y), the only time it returns one is when x = 1,y = 1. This means that a simple conjunction will do the trick. In other words, C(x,y) = xy.
R(x,y) is also kind of easy, as it is “exclusive-or”. The exclusive-or operator is usually denoted as ⊕. One can define R(x,y) = x ⊕ y.
However, exclusive-or is not one of the “commonly used” gates in logic design. As a result, it is often avoided. If you observe R(x,y), it is true iff x and y are different. As a result, one can also define R(x,y) = x + y.
In conclusion, we can express the carry and result of a binary add in simple binary operators.