The classes of all lower/upper bounds on the probability of a finite union of events which are expressed only in terms of the individual event probabilities and the sums of the pairwise event probabilities are considered. The optimal lower and upper bounds in each class are given numerically by solving a linear programming (LP) problem. Furthermore, a suboptimal analytical lower bound is established by solving a relaxed LP problem, which is at least as good as an existing bound due to Kuai, et al. [1]. Note that the new lower bounds can be further improved algorithmically by optimizing them over subsets [2], [3], and can be applied to general estimation problems involving the probability of a finite union. Finally, the new lower/upper bounds are illustrated by examining the symbol and bit error rates of an uncoded communication system used in conjunction with Mary phase-shift keying (PSK) modulation over additive white Gaussian noise (AWGN) channels under maximum a posteriori (MAP) decoding.