In this manuscript we propose an easily scalable true all-optical AND logic gate for pulsed signal operation based on band-gap transmission within nonlinear realistic air-hole type coupled photonic crystal waveguides (C-PCW). We call it "true" all-optical AND logic gate, because all AND gate topologies operate with temporal solitons that maintain a stable pulse envelope during the optical signal processing along the different C-PCW modules yielding ultrafast full-optical digital signal processing. We directly use the registered (output) signal pulse as new input signal between multiple concatenated nonlinear C-PCW modules (i.e. AND gates) to setup a multiple-input true all-optical AND logic gate. Extensive full-wave computational electromagnetic analysis proves the correctness of our theoretical studies and the proposed operation principle of the multiple-input AND logic gate is vividly demonstrated for realistic C-PCWs.