The use of N cognitive relays to assist primary and secondary transmissions in a time-slotted cognitive setting with one primary user (PU) and one secondary user (SU) is investigated. An overlapped spectrum sensing strategy is proposed for channel sensing, where the SU senses the channel for τ seconds from the beginning of the time slot and the cognitive relays sense the channel for 2τ seconds from the beginning of the time slot, thus providing the SU with an intrinsic priority over the relays. The relays sense the channel over the interval [0, τ] to detect primary activity and over the interval [τ, 2τ] to detect secondary activity. The relays help both the PU and SU to deliver their undelivered packets and transmit when both are idle. An optimization-based formulation with quality of service constraints involving queueing delay is studied. The results show the benefits of relaying and its ability to enhance both primary and secondary performance, especially in the case of no direct link between the PU and the SU transmitters and their respective receivers. Three packet decoding strategies at the relays are also investigated and their performance is compared.