The aim of this study is to explore mathematics teaching department students' perceptions on the concepts of proposition, theorem, and proof which are very important for daily life, mathematical literacy and studying mathematics; the common mathematical content used in constructing these concepts; and whether these constructions and content construction match each other. A survey model was used for fulfilling the aim. The data was taken from 329 first-grade mathematics teaching department students' examination papers. The students were enrolled to an Education Faculty of a state university located in the Eastern Anatolia Region of Turkey and the data was collected in the first semesters of academic years 2009-2010, 2010-2011, 2011-2012, 2012-2013 and 2013-2014. The numerical distribution of the participants across years was, respectively, 82, 46, 52, 42 and 107. The data was descriptively analysed. It was found out that the students better structured the concept of proposition (when compared to the concepts of proof and theorem) in accordance with the content construction of concepts and the mathematical expressions used in construction of the concepts of theorem and proof by the students were far away from the mathematical expressions used in the content of these concepts.