По аналогии с предикатами будем называть формулы РБА общезначимыми, невыполнимым, и т.д. Например, постоянная формула - это формула, значение которой всегда равно true или всегда равно false при подстановке любых значений на место свободных переменных (если они там есть). Отличие от предикатов только в том, что в формуле может вообще не быть ни одной переменной.

Теорема 07.0 Если один или оба операнда операции следования - постоянные формулы, то A B = false.

Доказательство Возьмем таблицу истинности: № A B A B 1 false false 2 false true * 3 true false ~ 4 true true По ней видно, что если хотя бы одна из двух формул постоянна и всегда равна false, то не будет выполнено последнее условие таблицы (в строке 4). Если же хотя бы одна из двух формул постоянна и всегда равна true, то не будет выполнено первое условие таблицы (в строке 1).

Наличие зависимости между операндами - важнейшее отличие операции общего следования от материальной импликации. Эта зависимость обеспечивается наличием одноименных переменных в операндах и тем, что истинность операндов зависит от этих переменных определенным образом. Если же одноименных переменных нет, то и зависимости быть не должно. Докажем это строго.

Теорема 07.1 Если операнды операции следования не содержат одноименных свободных переменных, то A B = false.

Доказательство Если хотя бы один из операндов постоянный, то следование ложно по теореме 07.0. Поэтому остальная часть доказательства посвящена случаю, когда оба операнда переменные. Поскольку формулы A и B не содержат одноименных свободных переменных, то значения на место этих переменных можно подставлять независимо. Если бы в обоих формулах присутствовала (в качестве свободной) какая-нибудь переменная, скажем, x, то, подставив определенное значение на место x в формулу A, пришлось бы подставлять то же самое значение и в формулу B. Поскольку обе формулы переменные, то можно найти такие комбинации значений свободных переменных, при которых A = true, и такие, при которых A = false. Аналогично для B. Выберем какую-нибудь комбинацию значений a1,...an, при которой A = true, и какую-нибудь комбинацию b1,...bm, при которой B = false. Если теперь подставить комбинацию a1,..., an, b1,..., bm в формулу (A & ~B), то получим (true & ~false) = (true & true) = true. Значит, существует по крайней мере одна комбинация a1,..., an, b1,..., bm, при которой (A & ~B) = true, то есть, (A & ~B) = true, а значит, ~ (A & ~B) = ~true = false, а значит, A B = A & ~B & ~ (A & ~B) = A & ~B & false = false

Наиболее простой случай, когда между формулами есть нужная зависимость - это когда формулы одинаковы, но не постоянны. Докажем это строго.

Теорема 07.2 Если A - переменная формула, то A A = true.

Доказательство Поскольку формула A переменная, то она принимает значения как true, так и false. Возьмем какую-нибудь комбинацию переменных, при которой A = true. Тогда и условие, и следствие будут истинными. Тем самым 4-я строка таблицы истинности проверена. Теперь возьмем какую-нибудь комбинацию, при которой A = false. Тогда и условие, и следствие будут ложными. Тем самым 1-я строка таблицы истинности проверена. Мы перебрали все возможные варианты, так что два других сочетания истинности для условия и следствия невозможны, в том числе и сочетание, когда условие истинно, а следствие ложно. Тем самым 3-я строка таблицы истинности проверена. Все проверки, указанные в таблице истинности, выполнены, и мы можем сделать вывод, что A A = true.