5.3. Решение логических задач
Для решения логических задач применяется алгебра логики или Булева алгебра.
В ее основу положено элементарное логическое высказывание, которое может быть только истинным или ложным.
Для упрощения действий элементарные высказывания обозначаются буквами, а истину и ложь логическими единицами и нулем соответственно. Тогда простые элементарные высказывания можно связать между собой с помощью логических функций и, зная, как они работают, рассчитывать их.
Основные функции (логические операции) алгебры логики следующие:
Конъюнкция (логическое умножение): в естественном языке соответствует союзу «и», обозначается &.
Конъюнкция – это логическая операция, ставящая в соответствие каждым двум простым высказываниям составное высказывание, являющееся истинным тогда и только тогда, когда оба исходные высказывания истинны.
Дизъюнкция – (логическое сложение): в естественном языке соответствует союзу «или», обозначается V.
Дизъюнкция – это логическая операция, которая каждым двум простым высказываниям ставит в соответствие составное высказывание, являющееся истинным, когда хотя бы одно из двух образующих его высказываний истинно, и ложным.
Инверсия (отрицание): в естественном языке соответствует словам «неверно, что…» и частице не, обозначается Ā.
Инверсия – это логическая операция, которая каждому простому высказыванию ставит в соответствие составное высказывание, заключающееся в том, что исходное высказывание отрицается.
Контрольный пример Задача 1.
В одной из горячих точек служили 5 офицеров: генерал, полковник, майор, капитан и лейтенант. Один из них сапер, другой – пехотинец, третий – танкист, четвертый – связист, пятый – артиллерист. У каждого из них есть сестра. И каждый из них женат на сестре своего однополчанина. Вот что еще известно об этих офицерах:
По меньшей мере, один из родственников связиста старше его по званию.
Капитан никогда не служил в Хабаровске.
Оба родственника-пехотинца и оба родственника-танкиста служили раньше в Мурманске. Ни один родственник генерала в Мурманске не был.
Танкист служил в Твери вместе с обоими своими родственниками, а лейтенант там не служил.
Полковник служил в Махачкале вместе со своими родственниками.
Танкист не служил в Махачкале. Там служил только один из его родственников.
Генерал служил с обоими своими родственниками в Хабаровске, а в Махачкале он не бывал.
Артиллерист не служил ни в Хабаровске, ни в Твери.
Определите, кто из офицеров имеет какое звание.
Решение задачи
Ясно, что каждый офицер имеет двух родственников. Один из них – брат жены, а другой – муж сестры. Обозначим для удобства каждого офицера буквой и расположим их так, чтобы соседом каждого были его родственники (рис.)
Рис. Расположение по порядку
Пусть пехотинец будет обозначен буквой А. Поскольку трое из офицеров служили в Мурманске, а двое там не были, то танкисту должна соответствовать либо буква В, либо Г. Допустим, что танкист – В. Отсюда следует (с учетом условия задачи), что А и В не служили в Мурманске и что Б – генерал. Продолжая рассуждать, приходим к выводу, что Б, В и Г служили в Твери. Поэтому лейтенантом должен быть А или Д и букве Д должен соответствовать артиллерист. Далее, либо В и Г, либо В и Б не служили в Махачкале. Следовательно, А, Д и Б либо А, Д и Г служили в Махачкале. А поскольку мы знаем, что Б не служил в Махачкале, это значит, что там служили А, Д и Г и что Д – полковник. Таким образом, А – лейтенант.
Переходим к следующему этапу решения. A, Б и В служили в Хабаровске, а Д там не служил. Нам известно, что капитан в Хабаровске не служил. Поскольку капитал не может быть Д, следовательно, ему соответствует буква Г. Далее приходим к заключению, что В – майор. Известно, что по меньшей мере один офицер должен быть старше по званию, чем связист. Следовательно, связист не может быть Б и должен быть Г, а саперу соответствует буква Б.
Таким образом, в итоге получается, что лейтенант – пехотинец, генерал – сапер, майор – танкист, капитан – связист, полковник – артиллерист.