In this paper, we present a plasmonic model system for the realization of ultrafast all-optical NOT, AND, OR, and XOR gate operations using linear interference effects in dielectric crossed waveguide structures. The waveguides for the surface plasmon-polaritons are produced by a simple but highly accurate microscopic lithographic process and are optimized for single mode operation at an excitation laser wavelength of 800 nm. The functionality of the presented structures is demonstrated using sub-30 fs laser pulses from a mode locked titanium:sapphire laser. Using leakage radiation microscopy we show ultrafast SPP switching and logic operations of one basic structure consisting of two crossed waveguides with an additional output waveguide along the bisecting line of the input waveguides. The individual gates are realized on a footprint of 10 µm × 20 µm. Experimental investigations are supported by finite-difference time-domain simulations, where good agreement between experimental results and numerical simulations is obtained. To exploit the high precision of the fabrication method and its huge potential for realizing functional complex plasmonic circuitry we experimentally demonstrate a half-adder structure and its operation by combining and cascading several plasmonic waveguide components and logic gate elements on an area of only 10 µm × 28 µm.