This work presents the intelligent tutoring system, EvoLogic, developed to assist students in problems of natural production in propositional logic. EvoLogic has been modeled as a multiagent system composed of three autonomous agents: interface, pedagogical and specialist agents. It supports pedagogical strategies inspired by the theory of example-based learning based on the use of an automated model tracing mechanism. This mechanism eliminates the necessity of the teacher to manually design every possible interaction between students and EvoLogic. It also includes several examples for each propositional rule. A specific study carried out with a set of 10 exercises taken from a real-world scenario is then presented to evaluate EvoLogic's performance and compare it to that of an earlier ITS (Heráclito) developed for the same purpose. The study showed that EvoLogic was able to provide different (and correct) solutions for the exercises analyzed. By having these solutions available, the model tracing mechanism was able to follow the students' steps, providing help that was consistent with the line of reasoning pursued by each student. A direct comparison between EvoLogic and Heráclito, which operates using one single line of reasoning for each theorem proof, showed that the model tracing mechanism of EvoLogic was more accurate in guiding students in the exercises. In addition to this positive outcome, EvoLogic's model tracing mechanism is novel in its use of genetic algorithms to build solutions on the fly for propositional logic exercises started by the students.