Many concepts in mathematics are not fully defined, and their properties are implicit, which leads to paradoxes. New foundations of mathematics were formulated based on the concept of innate programs of behavior and thinking. The basic axiom of mathematics is proposed, according to which any mathematical object has a physical carrier. This carrier can store and process only a finite amount of information. As a result of the D-procedure (encoding of any mathematical objects and operations on them in the form of qubits), a mathematical object is digitized. As a consequence, the basis of mathematics is the interaction of brain qubits, which can only implement arithmetic operations on numbers. A proof in mathematics is an algorithm for finding the correct statement from a list of already-existing statements. Some mathematical paradoxes (e.g., Banach–Tarski and Russell) and Smale’s 18th problem are solved by means of the D-procedure. The axiom of choice is a consequence of the equivalence of physical states, the choice among which can be made randomly. The proposed mathematics is constructive in the sense that any mathematical object exists if it is physically realized. The consistency of mathematics is due to directed evolution, which results in effective structures. Computing with qubits is based on the nontrivial quantum effects of biologically important molecules in neurons and the brain.