Зависимость и независимость высказываний

Условия независимости. Поскольку каждая булева функция может иметь два значения истинности, n булевых функций могут образовывать 2ⁿ комбинаций значений истинности. По определению, n булевых функций f₁(А, В, С,...),..., f_n(А, В, С,...) независимы, если в совокупности при всех возможных значениях аргументов А, В, С,... они могут принимать 2ⁿ комбинаций значений истинности. Следовательно, для проверки независимости функций f₁(A, В, С,...),...,f_n(А, В, С,...) необходимо по отношению к базису b[А, В, С,...] вычислить их изображающие числа

(6.5)

и проверить, образуют ли столбцы набора (6.5) 2ⁿ чисел 0, 1,..., 2 ⁿ —1; если 2ⁿ чисел имеется, то функции независимы, в противном случае — зависимы. При этом считается, что, как во всяком базисе, разряды двоичных чисел, представленных столбцами набора (6.5), возрастают вдоль столбца сверху вниз.

Пример. Установить, зависимы или независимы функции А×В+`А×`В и `B. Запишем их изображающие числа в последовательные строки:

Колонки набора представляют все возможные комбинации значений истинности, соответствующие числам 0, 1, 2, 3. Следовательно, рассматриваемые функции независимы.

Пример. Установить, зависимы или независимы функции А×В+`А×В, `В и А×`В+`А×В.

Эти функции зависимы, так как в колонках набора

содержатся числа 1, 3, 4, 6, а числа 0, 2, 5, 7 отсутствуют.

Метод нахождения явного вида логической зависимости. Чтобы найти явную форму логической связи зависимых булевых функций f₁(Л, В, С,...),...,f_n(A, В, С,...) в виде

(6.6)

поступают следующим образом. В базисе b[А, В, С] выписывают в последовательные строки изображающие числа #f₁,..., #f_n и определяют, какие числа отсутствуют в наборе столбцов (6.5), повторяющиеся значения чисел считают один раз. Столбцы набора (6.5) представляют собой комбинации значений истинности функций f₁...,f_n, при которых соответствующие элементарные произведения, составленные из f₁...,f_n, истинны. Так как #(F= 1)= # F, то, следовательно, имеющиеся в наборе (6.5) столбцы указывают номера тех колонок базиса b[f₁...,f_n], совпадающие с номерами разрядов #F(f₁...,f_n), на которых функция F истинна, т. е. в соответствующих разрядах изображающего числа #F(f₁...,f_n) должны стоять единицы.

Таким образом, изображающее число функции F(f₁...,f_n), отвечающей связи (6.6), получим, если в его разрядах относительно базиса b(f₁...,f_n), которые имеют номера отсутствующих в наборе (6.5) столбцов, поставим 0, а в остальных разрядах — 1.

Пример. Требуется установить явный вид логической зависимости функций

Вычислим по отношению к базису b[А, В, С]:

Выпишем последовательно все столбцы в этом наборе изображающих чисел как строки или соответствующие двоичные числа и укажем справа их десятичные значения: 111=7, 101 = 5, 010=2, 000 = 0, 111=7, 110=6, 001 = 1, 000 = 0.

Видим, что имеются только числа 0, 1, 2, 5, 6 и 7, а числа 3, 4 отсутствуют. Это означает, что по отношению к b[f₁, f₂, f₃] изображающее число связи F(f₁, f₂, f₃) = 1 имеет вид #F(f₁, f₂, f₃)= 1110 0111.

Так как 1110 0111 = #[(f₁ +f₂)×f₃ + (f₁+f₂)×f₃], то функции f₁, f₂, f₃ связаны соотношением (f₁ +f₂)×f₃ + (f₁+f₂)×f₃ = 1.

В справедливости последнего равенства можно убедиться непосредственно, если подставить в него выражения для f₁, f₂, f₃, записанные как функции от А, В, С. Выполним эту подстановку через изображающие числа f₁, f₂, f₃ по отношению к b[А, В, С]: