Спирина, М.С. Дискретная математика

будут здоровы (Н — множество здоровых людей) и помещение будет соответствовать противопожарным нормам (событие F), но если заболеет не более 7 чел., то им есть замена (£,). В каком слу­ чае концерт не состоится? Запишем сначала простые высказывания: 1: D е Н — здоров дирижер; 2: V/ е {1, 80} Л/, е Н — здоровы оркестранты; 3: F — помещение соответствует противопожарным нормам; 4: | {/1 М, е ( # } I < 7 — заболевших не более семи; 5: V/ е {1, 7}: 3 ^ е Н — каждому заболевшему есть дублер на замену. Тогда К эквивалент­ но 1 - 2 • 3 - 4 • (4 -> 5). Вспоминая введение дизъюнкции через отрицание и импликацию 4 - > 5 = 4 v _5 h далее раскрывая_скобки, получим К = 1 • 2 • 3 • 4 5. Поэтому A ' = l v 2 v 3 v 4 v 5 . Строя отрицания к каждому простому:_1 : й г Я - заболеет дирижер; 2 : 3 / 6 {1, ..., 80}: А/^г Н\ 3 : F\ 4 : 1{/1А/, г Я} | > 7 — заболеют более семи человек; 5 :3 / е {1, ..., 7}: 5} г Я — существуют неза­ менимые позиции в оркестре или дублер также болен. Поэтому концерт отменят, если заболеет дирижер, или помещение будет пожароопасным, или заболеют более семи оркестрантов, или за­ болевшему нет замены. Поскольку уважающие себя оркестры имеют группу дублеров, а пожароопасность везде одна и та же, то прак­ тически отмены обусловлены болезнью дирижера и вероятность отмены симфонического концерта примерно равна вероятности отмены сольного концерта. Общезначимость. Как известно, в логике предикатов и высказы­ ваний формула считается общезначимой тогда и только тогда, ког­ да она выводима. Но если в логике высказываний мы можем про­ цесс доказательства провести за конечное число шагов и заранее знаем конечный результат, то в логике предикатов такой уверен­ ности у нас нет. В исчислении предикатов доказано, что всякая выводимая формула тождественно-истинна, т.е. общезначима, и наоборот. Наиболее важная прикладная задача логики предикатов заключается в поиске эффективной процедуры обоснования рав­ носильностей, в ней применяемых. В настоящее время разработан ряд методов, позволяющих стандартизировать обоснование равно­ сильностей. Но в отличие от логики высказываний логика преди­ катов неразрешима, так как невозможно указать алгоритм установ­ ления истинного значения формул для многоместных предикатов (п * 1). Однако логика одноместных предикатов, наиболее полно соответствующая логике исчисления высказываний, разрешима. Практика последних десятилетий XX в. показывает, что логи­ ка высказываний является эффективным инструментом для ре­ шения как гуманитарных, так и многих технических задач. На­ пример, при конструировании и оснащении ЭВМ инженерам и программистам вместо того чтобы работать с контактными схе­ мами, достаточно произвести необходимые известные логиче­ ские операции. Однако логики высказываний недостаточно для 9 Дискретная математика 241