 Solution

Generate four partial-product bits with AND gates:The binary multiplication expansion is $XY=p_{00}+2(p_{10}+p_{01})+4p_{11}$. Add the two weight-two bits with a half adder, then add its carry to $p_{11}$ with a second half adder. The complete combinational logic isThus four AND gates for the partial products and two half adders suffice. Each half adder contains one exclusive or gate and one AND gate. In the largest case $3\times 3=9$, these equations produce $1001$, including the necessary fourth output bit.