We describe a method for automatically extracting symbolic compositional rules from music corpora. Resulting rules are expressed by a combination of logic and numeric relations, and they can therefore be studied by humans. These rules can also be used for algorithmic composition, where they can be combined with each other and with manually programmed rules. We chose genetic programming (GP) as our machine learning technique, because it is capable of learning formulas consisting of both logic and numeric relations. GP was never used for this purpose to our knowledge. We therefore investigate a well understood case in this study: dissonance treatment in Palestrina’s music. We label dissonances with a custom algorithm, automatically cluster melodic fragments with labelled dissonances into different dissonance categories (passing tone, suspension etc.) with the DBSCAN algorithm, and then learn rules describing the dissonance treatment of each category with GP. Learning is based on the requirement that rules must be broad enough to cover positive examples, but narrow enough to exclude negative examples. Dissonances from a given category are used as positive examples, while dissonances from other categories, melodic fragments without dissonances, purely random melodic fragments, and slight random transformations of positive examples, are used as negative examples.