Precise discrimination of tumor from normal tissues remains a major roadblock for therapeutic efficacy of chimeric antigen receptor (CAR) T cells. Here, we perform a comprehensive in silico screen to identify multi-antigen signatures that improve tumor discrimination by CAR T cells engineered to integrate multiple antigen inputs via Boolean logic, e.g., AND and NOT. We screen >2.5 million dual antigens and ∼60 million triple antigens across 33 tumor types and 34 normal tissues. We find that dual antigens significantly outperform the best single clinically investigated CAR targets and confirm key predictions experimentally. Further, we identify antigen triplets that are predicted to show close to ideal tumor-versus-normal tissue discrimination for several tumor types. This work demonstrates the potential of 2- to 3-antigen Boolean logic gates for improving tumor discrimination by CAR T cell therapies. Our predictions are available on an interactive web server resource (antigen.princeton.edu).