La logique du premier ordre a aussi été étendu à la logique modale du premier ordre [réf. nécessaire]. La logique de la dépendance ( dependence logic) est une généralisation de la logique du premier ordre où les dépendances entre variables sont explicitement décrites dans le langage [réf. nécessaire] .
Alors que la logique propositionnelle traite des propositions déclaratives simples, la logique du premier ordre couvre en plus les prédicats et la quantification. Un prédicat prend en entrée une ou plusieurs entités du domaine du discours et en sortie, il est soit Vrai, soit Faux.
Les formules du calcul des prédicats du premier ordre sont définies par induction : si e est une formule. Une formule de la forme s'appelle un atome ou une formule atomique. Les symboles ( non ), ( et ), ( ou) et ( implique ), qui sont des connecteurs que possède aussi le calcul des propositions.
Le théorème de complétude du calcul des prédicats du premier ordre que Gödel a montré dans sa thèse de doctorat, un an avant son célèbre théorème d'incomplétude. Ce théorème énonce que toute démonstration mathématique peut être représentée dans le formalisme du calcul des prédicats (qui est donc complet ).