We report the discovery of four millisecond pulsars as part of a conti
nuing survey of the Southern Hemisphere with the Parkes radio telescop
e. Three of the pulsars, PSRs J0613-0200, J1455-3330, and J1643-1224,
are in circular orbits with low-mass (similar to 0.1-0.3 M.) companion
s. The fourth pulsar, PSR J1730-2304, has a period of 8.12 ms and appe
ars to be solitary. Based on the results of the Parkes and other surve
ys, we estimate the number of low-mass binary pulsars with luminositie
s greater than 2.5 mJy kpc(2) in the Galactic disk to be at least 40,0
00. If the lifetimes of these systems are comparable to the age of the
disk then, as a group, their birthrate is consistent with that of the
ir proposed progenitors, the low-mass X-ray binaries. The binary pulsa
rs give some support to the relation between orbital period and compan
ion mass discussed by Joss, Rappaport, and Lewis and the relation betw
een orbital eccentricity and orbital period discussed by Phinney. Thes
e results are consistent with the idea that the neutron stars have bee
n spun up by accreting matter from their companion stars.