Quorum sensing (QS) is a cell-cell communication system that controls gene expression in many bacterial species, mediated by diffusible signal molecules. Although the intracellular regulatory mechanisms of QS are often well-understood, the functional roles of QS remain controversial. In particular, the use of multiple signals by many bacterial species poses a serious challenge to current functional theories. Here, we address this challenge by showing that bacteria can use multiple QS signals to infer both their social (density) and physical (mass-transfer) environment. Analytical and evolutionary simulation models show that the detection of, and response to, complex social/physical contrasts requires multiple signals with distinct half-lives and combinatorial (nonadditive) responses to signal concentrations. We test these predictions using the opportunistic pathogen Pseudomonas aeruginosa and demonstrate significant differences in signal decay between its two primary signal molecules, as well as diverse combinatorial responses to dual-signal inputs. QS is associated with the control of secreted factors, and we show that secretome genes are preferentially controlled by synergistic "AND-gate" responses to multiple signal inputs, ensuring the effective expression of secreted factors in high-density and low mass-transfer environments. Our results support a new functional hypothesis for the use of multiple signals and, more generally, show that bacteria are capable of combinatorial communication.