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

Условия независимости. Поскольку каждая булева функция может иметь два значения истинности, то булевых функций могут образовывать комбинаций значений истинности. По определению, булевых функций независимы, если в совокупности при всевозможных значениях аргументов они могут принимать комбинаций значений истинности. Следовательно, для проверки независимости функций необходимо по отношению к вычислить

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

Пример. Требуется установить, зависимы или независимы функции и В.

Запишем их изображающие числа в последовательные строки:

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

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

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

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

Метод нахождения явного вида логической зависимости. Для того чтобы найти явную форму логической связи зависимых булевых функций в виде

поступают следующим образом. В базисе выписывают в последовательные строки изображающие числа и определяют, какие числа отсутствуют в наборе столбцов (5.5);

повторяющиеся значения чисел считают один раз. Столбцы набора (5.5) представляют собой комбинации значений истинности функций при которых соответствующие элементарные произведения, составленные из истинны. Так как то следовательно, имеющиеся в наборе (5.5) столбцы указывают номера тех колонок базиса совпадающие с номерами разрядов на которых функция истинна, т. е. в соответствующих разрядах должны стоять единицы.

Таким образом, изображающее число функции отвечающей связи (56), получим, если в разрядах относительно базиса которые имеют номера отсутствующих в наборе (5.5) столбцов, поставим нули, а в остальных разрядах — единицы.

Пример. Рассмотрим функции

Вычислим по отношению к :

Выпишем последовательно все столбцы в этом наборе изображающих чисел как строки или соответствующие двоичные числа и укажем справа их десятичные значения:

Видим, что имеются только числа 0, 1, 2, 5, 6 и 7, а числа 3, 4 отсутствуют. Это означает, что по отношению к изображающее число связи имеет вид

Так как функции связаны соотношением

В справедливости последнего равенства можно убедиться непосредственно, если подставить в него выражения для записанные через Выполним эту подстановку через изображающие числа по отношению к :

Прнмер [14]. Предположим, что на основе данных, полученных из разных источников, были составлены следующие высказывания:

1. Самолет с реактивным двигателем и малым радиусом действия — бомбардировщик

2. Поршневые двигатели бомбардировщиков покрыты тяжелой броней.

3. Поршневые двигатели истребителей рассчитаны на малый радиус действия.

4. Поршневые самолетные двигатели, рассчитанные на большой радиус действия, имеют легкую броню.

5. Реактивные самолеты имеют тяжелую броню.

6. Истребители представляют собой самолеты, покрытые тяжелой броней и с малым радиусом действия.

7. Легкую броню имеют или самолеты с большим радиусом действия, или истребители.

8. Тяжелую броню имеют или самолеты с поршневыми двигателями, или самолеты с малым радиусом действия.

На основе анализа этих высказываний необходимо дать ответы на следующие вопросы:

1. Все ли утверждения совместны, т. е. нет ли средн них противоречивых высказываний?

2. Если высказывания несовместны, то будем предполагать, что только одно из них неправильно. Спрашивается, может ли единственное утверждение быть отброшено, с тем чтобы оставшиеся высказывания были совместны, и если да, то какое это высказывание?

3. Зависимы ли какие-либо высказывания?

4. Не являются ли какие-либо высказывания избыточными?

5. Какие заключения можно сделать при различных предположениях об ошибочности отдельных высказываний?

В приведенных высказываниях обсуждаются только типы самолетов (истребитель или бомбардировщик), типы двигателей (реактивный двигатель или поршневой), радиусы действия (малый или большой) и вид брони (легкая или тяжелая). В соответствии с этим введем следующие обозначения для элементарных высказываний: А — самолет является истребителем; А — самолет является бомбардировщиком; В — самолет имеет реактивный двигатель; В — самолет имеет поршневой двигатель; С — самолет (двигатель) имеет большой радиус действия; С — самолет (двигатель) имеет малый радиус действия; имеется легкая броня; -имеется тяжелая броня. После этого обсуждаемые высказывания могут быть представлены в виде следующих булевых функций:

По отношению к стандартному базису

вычислим изображающие числа функций

Поскольку то в совокупности все высказывания несовместны, т. е. среди них имеются противоречивые утверждения. Таким образом, ответ на первый вопрос отрицательный.

Для ответа на второй вопрос также необходимо составить произведения изображающих чисел не включая в него числа противоречивость которых проверяется.

Если одно (любое) из высказываний (или же все эти высказывания) отбросить, то оставшиеся утверждения будут все еще противоречивы. Однако если какое-либо одно из утверждений опустить, то оставшиеся высказывания будут совместны, так как произведение изображающих чисел оставшихся высказываний имеет в некоторых разрядах единицы. Следовательно, ответ на второй вопрос будет: «одно из высказываний 5-8 ошибочно».

Для ответа на третий и четвертый вопросы заметим, что довольно легко можно установить существование 17 связей вида

из которых для дальнейшего будет существенна только зависимость и, кроме того, связи вида

Проверим, зависимы ли и другие истинные высказывания от высказываний Среди колонок набора

имеются только колонки, соответствующие числам Поэтому

Найдем все первые импликанты функции

Таким образом, функции связаны зависимостью

или

Последнее соотношение показывает, что одновременно должны выполняться

Аналогично можно получить связь

Следовательно, из утверждений только утверждения должны быть установлены, так как высказывания избыточные.

Выше было установлено, что ложное высказывание содержится среди утверждений а высказывания - истинные. Если предположить, что утверждение истинные, то вследствие зависимости между функциями все высказывания тоже должны быть истинными. Однако если

ложны, то 4 могут быть как истинными, так и ложными. Вообще говоря, можно принять, что вероятность получить верный вывод из ложных посылок, как правило, меньше, чем вероятность получить ложный вывод. Но даже если считать, что эти вероятности равны 0,5, то вероятность получить из ложных утверждений истинные выводы будет Поэтому было бы в значительной степени обоснованным одно из двух несвязанных утверждений, рассматривать как ложное.

Предположим, из дополнительных данных было установлено, что высказывание ошибочно Тогда остаются высказывания и из которых утверждения избыточные; таким образом, следует оставить только высказывания Ввиду того что эти высказывания истинны одновременно, их произведение содержит наибольшую информацию. Так как то можно сделать вывод, что противник имеет бомбардировщик с малым радиусом действия и тяжелой броней. Этот вывод не очевиден; его трудно получить из исходных высказываний, не прибегая к формальному аппарату.

Если предположить, что утверждение ошибочно, то остаются высказывания изображающее число произведения которых

Отсюда следует, что противник располагает самолетом с легкой броней, реактивным двигателем и большим радиусом действия.