The growing importance of the membrane-based air separation processes results in an increasing demand for suitable polymeric membrane structures. This has spurred the interest in designing polymer structures for O2/N2 separation by employing a systematic approach. In this work, a computer-aided molecular design (CAMD)-based framework was developed to identify promising structures of polymers that can be used for air separation. To incorporate constraints in CAMD, the rough set-based machine learning (RSML) method was implemented to establish predictive models for the physical and transport properties of polymer owing to its interpretability. The deterministic rules generated from RSML would be interpreted scientifically reflecting the structure−property relationship to ensure that the molecules generated were feasible according to a scientific point of view. The most prominent rules selected were then integrated as constraints in CAMD. The relevant properties in this framework comprised of glass transition temperature (Tg), molar volume (Vm), cohesive energy (Ecoh), O2 permeability and O2/N2 selectivity. The solutions from CAMD optimisation were demonstrated in case studies. Results indicated the capability of a novel approach in identifying potential polymeric membrane candidates for air separation application that meet the permeability and selectivity requirements.