Когда мы оцениваем алгоритмы нотацией О-большое (O(N)), мы представляем Машину Тьюринга, которая последовательно выполняет код, считывая ленту туда и обратно. Но современные микропроцессоры работают иначе: это гигантские статичные графы из миллиардов транзисторов, по которым ток пробегает практически мгновенно. Для анализа аппаратной эффективности дискретная математика использует совершенно другую метрику — Сложность булевых схем.

Математическая логика — это раздел дискретной математики, изучающий математические доказательства и вопросы оснований математики. Она формализует рассуждения, отвлекаясь от содержания утверждений и концентрируясь исключительно на их логической структуре и истинности. Первой и самой базовой ступенью математической логики является логика (исчисление) высказываний.