We focus on a type of linguistic formal reasoning where the goal is to reason\nover explicit knowledge in the form of natural language facts and rules (Clark\net al., 2020). A recent work, named PRover (Saha et al., 2020), performs such\nreasoning by answering a question and also generating a proof graph that\nexplains the answer. However, compositional reasoning is not always unique and\nthere may be multiple ways of reaching the correct answer. Thus, in our work,\nwe address a new and challenging problem of generating multiple proof graphs\nfor reasoning over natural language rule-bases. Each proof provides a different\nrationale for the answer, thereby improving the interpretability of such\nreasoning systems. In order to jointly learn from all proof graphs and exploit\nthe correlations between multiple proofs for a question, we pose this task as a\nset generation problem over structured output spaces where each proof is\nrepresented as a directed graph. We propose two variants of a proof-set\ngeneration model, multiPRover. Our first model, Multilabel-multiPRover,\ngenerates a set of proofs via multi-label classification and implicit\nconditioning between the proofs; while the second model, Iterative-multiPRover,\ngenerates proofs iteratively by explicitly conditioning on the previously\ngenerated proofs. Experiments on multiple synthetic, zero-shot, and\nhuman-paraphrased datasets reveal that both multiPRover models significantly\noutperform PRover on datasets containing multiple gold proofs.\nIterative-multiPRover obtains state-of-the-art proof F1 in zero-shot scenarios\nwhere all examples have single correct proofs. It also generalizes better to\nquestions requiring higher depths of reasoning where multiple proofs are more\nfrequent. Our code and models are publicly available at\nhttps://github.com/swarnaHub/multiPRover\n