Мы воспользовались понятием истинностной таблицы для определения условий, при которых некоторая формула Е общезначимa (символически |=E), и условий, при которых формула В следует из формул Al,…, Аm (символически А1, …, Am|=B). Сами таблицы использовались для иллюстрации в первоначальном доказательстве теоремы 2 и некоторых других результатов. Однако для установления того, что |= Е или A1,…,Am|=B, часто оказывается проще применять, теоремы, относящиеся к общезначимости и к отношению следования, чем вычислять таблицы истинности. Если мы хотим доказать, что не |=Е или неверно, что A1,…, Am |=B, то нам нет нужды вычислять более одной удачно подобранной строки таблицы (таблиц). И часто такую строку удается быстро нащупать, не вычисляя прочих.
Говорят, что формула Е невыполнима, или противоречива, или тождественно ложна, если столбец значений в ее таблице истинности состоит только из f. Если формула ни общезначима, ни невыполнима, то ее называют нейтральной. Таким образом, формулы распадаются на три класса, смотря.по тому, как входят t и f в их истинностные таблицы.
Формула Е невыполнима или выполнима в зависимости от того, является ли формула Ø Е общезначимой. Для установления того, что формула нейтральна, достаточно вычислить две подходящие строки.
Если все же приходится проводить много вычислений по истинностным таблицам, то и тогда полезно уметь сэкономить время, используя некоторые сокращения в записи и в вычислениях. Ведь для формулы из трех атомов требуется таблица из 8 строк, а для формулы с 12 атомами понадобилось бы 4096 строк.