Anorexia nervosa is associated with impaired cognitive flexibility and central coherence, i.e., the ability to provide an overview of complex information. Therefore, the aim of the present study was to evaluate EEG features elicited from patients with anorexia nervosa and healthy controls during mental tasks (valid and invalid Aristotelian syllogisms and paradoxes). Particularly, we examined the combination of the most significant syllogisms with selected features (relative power of the time–frequency domain and wavelet-estimated EEG-specific waves, Higuchi fractal dimension (HFD), and information-oriented approximate entropy (AppEn)). We found that alpha, beta, gamma, theta waves, and AppEn are the most suitable measures, which, when combined with specific syllogisms, form a powerful tool for efficiently classifying healthy subjects and patients with AN. We assessed the performance of triadic combinations of “feature–classifier–syllogism” via machine learning techniques in correctly classifying new subjects in these two groups. The following triads attain the best classifications: (a) “AppEn-invalid-ensemble BT classifier” (accuracy 83.3%), (b) “Higuchi FD-valid-linear discriminant” (accuracy 75%), (c) “alpha amplitude-valid-SVM” (accuracy 83.3%), (d) “alpha RP-paradox-ensemble BT” (accuracy 85%), (e) “beta RP-valid-ensemble” (accuracy 85%), (f) “gamma RP-valid-SVM” (accuracy 85%), and (g) “theta RP-valid-KNN” (accuracy 80%). Our findings suggest that anorexia nervosa has a specific information-processing style across reasoning tasks in the brain as measured via EEG activity. Our findings also contribute to further supporting the view that entropy-oriented, i.e., information-based features (the AppEn measure used in this study) are promising diagnostic tools (biomarkers) in clinical applications related to medical classification problems. Furthermore, the main EEG-specific frequency waves are extremely enhanced and become powerful classification tools when combined with Aristotle’s syllogisms.