数学上、「完全」 というのは 「真・偽を証明できる」 という意味であり、「不完全」 というのは 「真も偽も証明できない （証明する公理的手続きがない）」 という意味です。そして、「完全性定理」 では、トートロジー を判断するための公理的手続きがあることを証明されて、「不完全性定理」 では 「完全」 な論理を使った公理系 （無矛盾な公理系） のなかに真とも偽とも証明できない命題を作ることができることが証明されています。真とも偽とも証明できない命題のことを 「決定不能命題 （あるいは、独立命題）」 と云います。

　トートロジー というのは、同語反復ということであって、例えば 「善人は、善い人である」 というように、主語が述語と同一概念から成る命題のことであって、定義上の虚偽ですが、「論理」 上では、真偽いかんにかかわらず真と 「解釈」 されるという恒真性のことをいい、命題論理学において ウィトゲンシュタイン が導入し普及した概念です。トートロジー の反対概念が恒偽 （つねに偽） です。恒偽というのは、（2値論理では） 例えば矛盾律 （A ∧ ¬A、A および A でない） のことです。

　「完全性定理」 では、トートロジー の意味論的完全性が対象になっていて、トートロジー は証明可能であるということです。言い替えれば、「定理」 の集合と恒真の集合は一致する、すなわち 定理であれば恒真であり、かつ恒真であれば定理であるということです。つまり、「論理」 は完全であるということです。いっぽう、「不完全性定理」 で証明されたことは、「論理」 を使った無矛盾な公理系 （「理論」） では、決定不能命題 （独立命題） が存在するということです。つまり、「理論」 は不完全であるということです。