авторефераты диссертаций БЕСПЛАТНАЯ БИБЛИОТЕКА РОССИИ

КОНФЕРЕНЦИИ, КНИГИ, ПОСОБИЯ, НАУЧНЫЕ ИЗДАНИЯ

<< ГЛАВНАЯ
АГРОИНЖЕНЕРИЯ
АСТРОНОМИЯ
БЕЗОПАСНОСТЬ
БИОЛОГИЯ
ЗЕМЛЯ
ИНФОРМАТИКА
ИСКУССТВОВЕДЕНИЕ
ИСТОРИЯ
КУЛЬТУРОЛОГИЯ
МАШИНОСТРОЕНИЕ
МЕДИЦИНА
МЕТАЛЛУРГИЯ
МЕХАНИКА
ПЕДАГОГИКА
ПОЛИТИКА
ПРИБОРОСТРОЕНИЕ
ПРОДОВОЛЬСТВИЕ
ПСИХОЛОГИЯ
РАДИОТЕХНИКА
СЕЛЬСКОЕ ХОЗЯЙСТВО
СОЦИОЛОГИЯ
СТРОИТЕЛЬСТВО
ТЕХНИЧЕСКИЕ НАУКИ
ТРАНСПОРТ
ФАРМАЦЕВТИКА
ФИЗИКА
ФИЗИОЛОГИЯ
ФИЛОЛОГИЯ
ФИЛОСОФИЯ
ХИМИЯ
ЭКОНОМИКА
ЭЛЕКТРОТЕХНИКА
ЭНЕРГЕТИКА
ЮРИСПРУДЕНЦИЯ
ЯЗЫКОЗНАНИЕ
РАЗНОЕ
КОНТАКТЫ


Pages:   || 2 | 3 | 4 | 5 |
-- [ Страница 1 ] --

Учебник по математике

Роман Добровенский

heller 2012–2014, Москва

Оглавление

Введение

5

1. Логика 7

1.1. Базовые понятия................... 7

1.2. Представление функций............... 18

1.3. Самая сложная логическая задача......... 25 1.4. Предикаты и кванторы................ 30 1.5. Теории: интуиция................... 35 1.6. Парадоксы....................... 50 1.6.1. Парадокс импликации............ 5 1.6.2. Парадокс брадобрея............. 1.6.3. Парадокс пьяницы.............. 1.6.4. Парадокс воронов............... 1.6.5. Парадокс лжеца................ 1.7. Формализм....................... 1.7.1. Язык...................... 1.7.2. Синтаксис................... 1.7.3. Семантика................... 1.8. Зачем это всё?..................... 2. Множества 2.1. Основные понятия................... 2.2. Отношения....................... 2.3. Графы.......................... Оглавление 2.4. Функции........................ 2.5. Формализм....................... 2.6. История......................... 3. Натуральные числа 3.1. Определение...................... 3.2. Позиционные системы счисления.......... 3.3. Вычислительный аспект............... 3.4. Делимость....................... 3.5. Принцип Дирихле................... 3.6. Принцип индукции.................. 3.7. Перестановки...................... 3.8. Сочетания....................... 3.9. Разбиения множеств................. 3.10. Включения-исключения............... 3.11. Двойной счёт...................... Введение Эта книга изначально замышлялась как простой учебник для новичков в математике. После первых двух глав (которые пла нировалось сделать коротким введением и обзором, но в итоге они разрослись на сотню страниц) стало понятно, что этот учеб ник понимают только единицы. Увы. Тем не менее, учебник я продолжаю писать и буду по мере возможностей его перераба тывать, чтобы сделать более доступным для понимания.

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

Учебник пишется на чистом энтузиазме, распространяется сво бодно и без ограничений.

Для скачивания всегда доступна последняя версия pdf-файла здесь: http://heller.ru/tutorial.pdf Исходные коды в L TEX могут быть скачаны на GitHub:

A http://github.com/xHellerx/Math-tutorial Учебнику всегда требуется помощь с поиском ошибок в тексте (опыт показывает, что их полно) и с общей критикой. Также требуется помощь с вёрсткой. Если вы хорошо разбираетесь в L TEX, я был бы признателен за помощь с оформлением, так A как у меня у самого с этим очень плохо. Ещё было бы полезно Оглавление распространение информации о курсе. Посоветуйте его в своём блоге, своим студентам, родителям и соседям.

Глава Логика Первая глава даёт неформальное описание основных законов ло гики. Главная цель — дать какую-то интуицию об излагаемых понятиях и о принципах логических выводов, прежде чем мы всё это формализуем и используем в конце второй главы. Если вам не особо интересны основания математики, то вы можете сразу переходить к середине третьей главы и читать более при кладные вещи, обращаясь сюда по мере необходимости как к справочнику.

Наиболее важными являются первый и четвёртый парагра фы. Остальные параграфы имеют факультативный характер и не обязательны к прочтению.

1.1 Базовые понятия Высказыванием мы будем называть любую осмысленную фразу русского языка. Например: «На улице идёт дождь», «Девки гу ляют по улице», «Вася тонировал свою шестёрку“». В рамках ” науки математической логики мы, правда, ограничимся лишь теми высказываниями, про которые можно однозначно судить, истинны они или ложны (мы можем этого не знать, но важно, что сама постановка фразы допускает однозначную трактовку высказывания).

1 Логика Истинные высказывания мы будем обозначать символом 1, а ложные — символом 0. В общем-то, нас даже не будет интере совать сам физический смысл высказывания, лишь его истин ность — справедливость всех логических законов и операций, о которых мы будем говорить, не зависит от содержания самих высказываний и оперирует лишь с понятием истинности.

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

Определим теперь простейшие логические операции (они же называются логическими связками). Пусть для начала выска зывание имеет конкретный смысл «на улице идёт дождь», а высказывание имеет смысл «на улице много машин». К этим двум высказываниям можно применить логическую связку (опе рацию) «И», и в итоге мы получим высказывание «на улице идёт дождь и много машин».

На языке математики логическая связка «И» обозначается символом, а результат применения этой связки к нашим двум высказываниям записывается как. (Научно «И» также на зывается конъюнкцией, но это знать и помнить совершенно не обязательно.) Давайте теперь рассмотрим истинность этого вы сказывания. Если это правда, что на улице много машин, и также правда, что на улице идет дождь, то и наше высказывание «на улице много машин и идёт дождь» будет правдой. Если же хотя бы одно из этих утверждений ложно, то и наша фраза бу дет ложной: если на улице нет дождя, то не является правдой и составное высказывание «на улице идёт дождь и много машин».

Определение логической связки «И» можно резюмировать сле дующей таблицей:

Подобные таблицы называются таблицами истинности. В них перечислены все возможные логические значения интересующих 1.1 Базовые понятия 0 0 0 1 1 0 1 1 Таблица 1.1. Определение логической связки «И»

нас высказываний и результат применения к ним логической связки. Что-то типа таблицы умножения.

В полной аналогии с операцией «И» можно определить следу ющие базовые операции:

— Операция «ИЛИ», она же «И/ИЛИ», она же дизъюнкция (запоминать это слово не нужно), обозначается как. Вы ражение истинно, когда истинно хотя бы одно из вы сказываний или.

— Операция «Исключающее ИЛИ», по-английски называется «eXclusive OR», или кратко «XOR». По-русски её для крат кости часто называют «ксор» или — в глагольной форме — «ксорить», хотя слово это, конечно, сленговое и совершенно непечатное. Обозначается данная операция как. Выска зывание истинно только тогда, когда истинно лишь одно из высказываний или, но не оба сразу.

— Операция «Эквиваленция». Обозначается как. Вы сказывание истинно, когда и либо одновременно истинны, либо одновременно ложны.

— Операция «НЕ», она же «Отрицание». Обозначается как ¬.

Высказывание ¬ истинно тогда, когда ложно, и наобо рот.

— Операция «Импликация», она же «Следствие». Обознача ется как. Высказывание истинно либо когда одновременно и, и истинны, либо когда ложно.

1 Логика Всё сказанное, возможно, станет более понятно, когда мы вы разим все операции одной таблицей истинности:

¬ 0 0 0 0 0 1 1 0 1 0 1 1 0 1 1 0 0 1 1 0 0 1 1 1 1 0 1 0 Таблица 1.2. Сводная таблица истинности логических операций Обратите внимание на то, что в естественном языке фраза «на улице идёт дождь или много машин» не особо хорошо опре делена — непонятно, имеется ли в виду «или то, или другое»

(исключающее «ИЛИ»), или же «и то, и другое». В математике эти два смысла строго разграничены операциями и.

Также стоит уточнить смысл операции эквиваленции — она в действительности ничего не говорит о реальной связи между высказываниями, лишь об их истинности. Так, любые два заве домо ложных высказывания оказываются эквивалентны: «Ком пьютеры не умеют умножать числа» «Солнце вращается вок руг Земли». То же и с заведомо истинными высказываниями:

«Компьютеры считают лучше людей» «Земля вращается вок руг Cолнца». Это может несколько сбивать с толку поначалу, но более ясен смысл эквиваленции станет несколько позже, когда мы будем говорить о моделях.

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

1.1 Базовые понятия Используя перечисленные операции, можно задавать и доволь но сложные высказывания, например, что-то вроде такого:

(( ) ( )).

Круглыми скобками мы обозначаем порядок, в котором вы полняются операции. Если для каждого из высказываний, и определить, истинно оно или ложно, то по таблице истинно сти можно определить, истинно ли всё высказывание.

Пусть, например, истинно, в то время как и ложны. То гда, подставив вместо этих высказываний 1 и 0 в приведённую формулу и воспользовавшись правилами из таблицы истинно сти, можно установить истинность и всего высказывания:

((1 0) (0 1)) 0 = (1 0) 0 = 0 0 = 0.

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

((0 0) (0 0)) 0 = (0 0) 0 = 1 0 = 1.

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

Однако пора доказать нашу первую теорему.

Теорема 1.1. Для логических операций справедливы следующие законы:

Ассоциативность:

1. ( ) = ( ), 1 Логика 2. ( ) = ( ), 3. ( ) = ( ).

Коммутативность:

1. =, 2. =, 3. =, 4. =.

Дистрибутивность:

1. ( ) = ( ) ( ), 2. ( ) = ( ) ( ), 3. ( ) = ( ) ( ).

Двойное отрицание:

1. ¬¬ =.

Закон исключенного третьего:

1. ¬ = 1, Закон противоречия:

1. ¬ = 0, Законы де Моргана:

1. ¬( ) = (¬) (¬), 2. ¬( ) = (¬) (¬).

1.1 Базовые понятия Ещё по мелочам:

1. 1 =, 2. 0 = 0, 3. 1 = 1, 4. 0 =, 5. 0 =, 6. 1 = ¬, 7. ¬( ) = ( ), 8. ¬ = 1, 9. =, 10. =, 11. = 0, 12. (¬ ) =, 13. (¬ ) =.

Для импликации:

1. = ¬ 2. ¬( ) = ¬ 3. 4. = ( ) ( ) 5. Транзитивность: (( ) ( )) ( ) 6. ( ) (¬ ) 7. ( ) ( ) 1 Логика 8. = ¬ ¬ Доказательство. Каждую из формул я доказывать не буду, по скольку все они доказываются аналогично и я настоятельно ре комендую провести доказательство самостоятельно. Я лишь про демонстрирую на отдельных примерах, как это делается.

Подходов тут существует три:

— Интуитивный. Ассоциативность и коммутативность опера ций «И» и «ИЛИ» на самом деле очевидна. Вообще, конеч но, говорить «очевидно» в математике мы не имеем права, поскольку очевидное часто оказывается неверным и наобо рот. Однако в подобных, совсем уж тривиальных случаях, строго доказывать каждую теорему будет утомительно. Ес ли утверждение теоремы у вас не вызывает сомнения, и вы знаете, как его можно строго проверить — можно и не па риться.

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

(¬ ) = ( ¬) ( ) = 1 ( ) =.

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

К сожалению, то, что перебор нам тут помог доказать что-то — редкое исключение. Кроме как для почти тривиальных логиче ских соотношений метод перебора в математике не годится, по скольку обычно перебирать придётся слишком много значений, 1.1 Базовые понятия ( ) ( ) ( ) 0 0 0 0 0 0 0 0 0 1 1 0 0 0 0 1 0 1 0 0 0 0 1 1 1 0 0 0 1 0 0 0 0 0 0 1 0 1 1 1 0 1 1 1 0 1 1 1 0 1 1 1 1 1 1 1 Таблица 1.3. Доказательство дистрибутивности логических опе раций с чем никакой компьютер не справится. И это в лучшем слу чае — часто значений, которые придётся перебрать, будет вооб ще бесконечно много, или даже ещё больше.

Из приведённой теоремы важно выделить законы ассоциатив ности и дистрибутивности. Закон ассоциативности по сути утвер ждает, что для перечисленных операций не важно, в каком по рядке расставлять скобки и, соответственно, применять опера ции (чуть более строго мы это обсудим в третьей главе). По этой причине круглые скобки для ассоциативных операций мож но вообще опускать, и следующие выражения оказываются со вершенно равнозначны:

( ( )) = ( ) ( ) = Закон коммутативности же означает, что нам не важен поря док участвующих в выражении высказываний. В совокупности с ассоциативностью это говорит также, что мало того, что мы можем опускать скобки, мы ещё и порядок можем путать:

( ( )) =.

На фоне этого может оказаться странным поведение эквива ленции. Как легко убедиться, если построить таблицу истинно 1 Логика сти, операция эквивалентности тоже является ассоциативной:

( ) = ( ).

Тем не менее, если мы будем применять её в таком виде, опу стив круглые скобки, то результат может оказаться неожидан ным:

(1 0 0) = ((1 0) 0) = (0 0) = 1.

Это несколько противоречит интуитивному представлению о понятии «эквивалентность». Нам хотелось бы иметь возможность писать и ожидать, что данное высказывание будет ис тинным лишь в том случае, когда все три высказывания либо одновременно истинны, либо одновременно ложны. Это было бы логично.

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

= ( ) ( ).

Именно по этой причине закон ассоциативности для эквива лентности обычно не рассматривается. Такая странность возни кает из-за некоторой неточности привычного человеческого язы ка, когда мы, произнося одни и те же слова, можем иногда подра зумевать довольно разные логические операции. Это во многом сродни неточности слова «или»: из-за этого нам пришлось раз граничивать операции и. Здесь нет никакого парадокса или противоречия — это просто надо иметь в виду.

Также замечания заслуживает закон де Моргана. Он на са мом деле обобщается на любое количество высказываний. Для примера продемонстрируем простейшую ситуацию:

¬( ) = ¬( ( )) = ¬ ¬( ) = ¬ ¬ ¬.

Аналогично можно распространить этот закон на любое коли чество высказываний (даже бесконечное). Как это сделать стро го математически, мы обсудим в дальнейшем в нашем курсе, 1.1 Базовые понятия пока же можно просто попробовать развить какую-то интуицию относительно этого закона.

Пусть высказывание означает, что Тане нравятся бритые мальчики, а высказывание означает, что Тане нравятся маль чики в спортивных штанах. Предположим, однако, что Таня не дура какая-нибудь, и для неё верно высказывание:

¬( ) = «Тане не нравятся бритые мальчики в спортштанах»

(На всякий случай сообщу, что автор текста сам бреется на лысо и имеет в гардеробе зауженные спортштаны.) Приведённое высказывание, однако, не подразумевает, что Тане не подойдёт бритый мужчина в костюме, или же патлатый спортс мен — данное высказывание говорит лишь о том, что для нее неприемлемо сочетание «лысый + спортштаны». Довольно кос ноязычно, но можно всё же утверждать следующее:

«Таню устроил бы парень, который хотя бы не лысый или хотя бы не носит спортштаны».

Если вдуматься, то это ровно та же самая фраза, которую мы назвали первоначально, но она просто перефразирована. И она дословно выражается как ¬ ¬, а это как раз то, что мы ожидали получить по закону де Моргана. Если добавить к пер воначальным двум высказываниям ещё какие-то высказывания, характеризующие предпочтения Тани, то мы получим тот же закон де Моргана, но уже для многих высказываний.

Подобные интуитивные соображения можно придумать для любой формулы нашей первой теоремы, и хорошо бы это проде лать — это полезно. С тем же законом де Моргана я впервые столкнулся лет 10 назад (правда не в мат. логике, а в теории ве роятностей, которую я пытался читать без какой-либо начальной подготовки), и в книжке, которую я читал, всё, что о нём было сказано, что это «очевидно». Сейчас уже стыдно признаваться, но над этим «очевидным» утверждением мне тогда пришлось по ломать голову, прежде чем я смог согласиться с автором в том, что это действительно так.

1 Логика Из всего списка приведённых в теореме 1.1 утверждений ин тересно выделить те, что касаются импликации. При том, что таблица истинности для импликации может показаться довольно странной, она обладает весьма логичными свойствами, которые характерны для интуитивного понятия «следствия». Например, закон транзитивности является отражением простого логическо го закона: если из следует, а из следует, то из следует.

Аналогично равенство = ¬ ¬ означает, что если из следует, и нам известно, что ложно, то отсюда следует лож ность. Таким образом, введённое определение импликации дей ствительно в каком-то смысле отражает операцию «следствие», как мы её понимаем на интуитивном уровне. Эти идеи мы будем развивать в следующих параграфах.

Читателю же я рекомендую доказать каждую из формул при ведённой теоремы и подумать больше не над самим фактом спра ведливости формулы, а над интуитивной интерпретацией.

1.2 Представление функций В прошлом параграфе мы определили с помощью таблиц истин ности пять логических операций. Нам никто не мешает опреде лить и другие операции, задав их таблицу истинности, причём им не обязательно иметь один или два параметра — можно и больше, никто не запрещает. Для примера рассмотрим операцию (удобней, наверное, называть её функцией) с тремя параметра ми, описанную в таблице 1.4. Записывать эту операцию мы будем как (,, ). По таблице легко находить её значения при кон кретных параметрах, например: (0, 0, 1) = 0 или (1, 0, 1) = 1.

Какой физический смысл данной функции/операции? Пока никакого — мы делаем то, что мы делаем, просто потому, что мы можем это делать. В математике часто так поступают, а приме нение это всё находит позже.

Теперь давайте поймём, как определить эту же самую функ цию, выразив её через уже известные нам логические операции.

1.2 Представление функций 0 0 0 0 0 1 0 1 0 0 1 1 1 0 0 1 0 1 1 1 0 1 1 1 Таблица 1.4. Представление булевой функции с тремя парамет рами Для начала рассмотрим более простую функцию 0, которая имеет значение 1 только при наборе параметров 0 (1, 0, 1), а во всех остальных случаях её значением будет 0. Легко догадаться, что такая функция в точности представляется как:

0 (,, ) = ¬.

Рассмотрим также функцию 1 (,, ), которая принимает значе ние 1 только на наборе аргументов 1 (0, 0, 0). Её, соответственно, можно представить как:

1 (,, ) = ¬ ¬ ¬.

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

(,, ) = 0 (,, ) 1 (,, ).

Подставив сюда выражения для 0 и 1, получаем:

(,, ) = ( ¬ ) (¬ ¬ ¬).

1 Логика Продолжая рассуждать таким же образом, можно прийти и к выражению для функции, заданной выше таблицей истинно сти:

(,, ) = (¬ ¬ ¬) (¬ ¬) ( ¬ ¬) ( ¬ ).

Легко видеть, как получается такое представление: мы просто перечисляем все строки таблицы истинности, в которых функ ция принимает значение 1, соединяя параметры функции опе рацией И (если значение параметра 0, то перед ним добавля ем отрицание), а сами наборы, при которых функция истинна, соединяя операцией ИЛИ. То есть если у нас есть таблица ис тинности, всегда возможно особо не думая записать, чему эта функция равна, используя только операции И, ИЛИ и НЕ.

Такая развёрнутая форма записи функций называется дизъ­ юнктивной нормальной формой (ДНФ). Запоминать это не нуж но — за пределами этого параграфа данный термин нам боль ше не понадобится. Суть такого представления заключается в том, что функция выражается как дизъюнкция (операция ИЛИ) некоторого количества конъюнктов (параметров функции, объ единённых операцией И).

Можно получить и другое представление, если вначале выра зить по нашей схеме не саму функцию, а её отрицание:

¬ (,, ) = (¬ ¬ ) (¬ ) ( ¬) ( ).

Теперь можно взять отрицание этого выражения и, используя закон де Моргана, получить такое выражение:

(,, ) = ( ¬) ( ¬ ¬) (¬ ¬ ) (¬ ¬ ¬).

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

Новую форму записи также легко получить по таблице ис тинности, особо не задумываясь над смыслом операции — мы 1.2 Представление функций делаем всё то же самое, что и в прошлый раз, но только на этот раз перечисляем не единицы таблицы, а нули, и везде подменяем И на ИЛИ и наоборот, а вхождения параметров в нашу формулу снабжаем отрицанием.

Такая форма записи называется конъюнктивной нормальной формой (КНФ), и представляет она из себя конъюнкцию (опера ция И) некоторого количества дизъюнктов (параметров функ ции, объединённых операцией ИЛИ).

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

Рассмотрим импликацию:

0 0 0 1 1 0 1 1 Таблица 1.5. Таблица истинности для импликации Для этой операции описанные нами подходы представления функции дают следующие результаты:

ДНФ: = (¬ ¬) (¬ ) ( ) КНФ: = ¬ КНФ здесь оказывается удобнее. Также этот подход можно рассматривать как альтернативу методикам доказательств, пред ставленных в первом параграфе.

Упражнение 1.1. Запишите КНФ и ДНФ для операций «ис ключающее ИЛИ» и «эквиваленция».

1 Логика Вообще же следовать каждый раз именно такой схеме чаще всего оказывается расточительно. Если посмотреть внимательнее на таблицу истинности для, то можно заметить, что в случае истинности функция принимает истинное значение при лож ном, и значение там уже не важно. При ложности же нам важно лишь значение и не важно. С учётом этих наблюдений функция может быть записана совсем просто:

(,, ) = (¬ ¬) ( ¬) Получается гораздо красивее, чем было. Обычно в курсах ло гики значительная часть времени посвящается как раз упроще нию формул. Мы могли бы рассмотреть много примеров и типич ные приёмы, но вряд ли это окажется сильно полезно. Если вам когда-либо придётся заниматься подобной ерундой (что сомни тельно), могу лишь посоветовать подходить к задаче творчески, а не искать универсальных подходов.

Нас же сейчас из всего сказанного больше интересует принци пиальная возможность построения КНФ и ДНФ для произволь ной формулы. Из наших рассуждений непосредственно следует такая простенькая теорема:

Теорема 1.2. Любая логическая функция может быть пред­ ставлена с помощью операций «И», «ИЛИ» и «НЕ».

Данные операции можно называть базисом нашей логической системы (неформально говоря, базис — это некий набор компо нентов, из которых можно собрать любой другой объект, ого ворённый в нашей системе). Однако базис этот не единствен ный, можно придумать и другие наборы функций, через кото рые также можно будет выразить любую логическую операцию.

Примером служит следующая теорема:

Теорема 1.3. Любая логическая функция может быть пред­ ставлена с помощью операций «И», «исключающее ИЛИ» и кон­ станты 1.

Доказательство. Операции ИЛИ и НЕ можно представить че рез, и 1:

1.2 Представление функций Представление ИЛИ: = ( ) Представление НЕ: ¬ = Ну а поскольку через функции ИЛИ, НЕ и И мы можем пред ставить любую функцию, то отсюда понятно, что и через И, XOR и 1 мы также можем представить любую функцию.

Таким образом, и 1 также являются базисом нашей логи ческой системы, который часто называется базисом Жегалкина.

При работе в базисе Жегалкина оказываются удобными следу ющие соглашения о записи и названии логических операций:

1. записывается просто как и называется умножением, 2. записывается как + и называется сложением.

С этими соглашениями основные свойства логических опера ций будут выглядеть так:

1. = + +, 2. ¬ = + 1, 3. ( + ) = +, 4. =, 5. + = 0.

Эти формулы легко запоминаются и с ними оказывается очень просто работать (позже мы увидим, что такая запись и назва ния операций имеют и более глубинный смысл). Для примера выразим в базисе Жегалкина, следуя нашим соглашениям, им пликацию:

= ¬ = (1 + ) + + (1 + ) = 1 + + + + = 1 + + Здесь мы сократили +.

Упражнение 1.2. Выведите формулу для эквиваленции:

= 1 + + 1 Логика Упражнение 1.3. Выведите формулу для упомянутой ранее функции.

Упражнение 1.4. Докажите, что любая логическая функция может быть выражена с помощью лишь одной операции «штрих Шеффера», которая определяется как | = ¬( ) = 1 +.

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

0 0 ?

0 1 ?

1 0 1 1 Таблица 1.6. Неполная таблица истинности для импликации Чтобы определить значения в оставшихся ячейках, обозна ченных символом «?», необходимо рассмотреть, какими свой ствами должно обладать логическое следствие, и проверить, ка кие ограничения эти свойства накладывают на таблицу истинно сти. Самое логичное требование к импликации, которое мы уже приводили в первом параграфе — это требование транзитивно сти: «Если из следует и из следует, то из следует ».

1.3 Самая сложная логическая задача Формально это свойство записывается так:

(( ) ( )) ( ).

Если подставить в это выражение вместо и истину (1), а вместо — ложь (0), то, вычисляя (как в первом параграфе) значение истинности для логических связок, нам известных, мы сведём свойство транзитивности к следствию 0 0, и это вы ражение обязано быть истинным, если мы хотим, чтобы свой ство транзитивности выполнялось для импликации. Если теперь, зная, что (0 0) = 1, подставить вместо и истину, а вместо ложь, то мы получим, что также должно быть истинным и вы ражение 0 1. Это завершает построение таблицы истинности для импликации. Таким образом, её таблица истинности — это в некотором смысле вынужденная таблица, в противном случае импликация не удовлетворяла бы тем свойствам, которые мы ожидаем от операции логического следствия.

Упражнение 1.5. Можно было бы определить импликацию, опираясь не на свойство транзитивности, а на закон исключён ного третьего (¬ = 1) и тот факт, что эквивалентность подра зумевает в том числе и следствие: ( ) ( ). Используя эти два свойства, определите таблицу истинности для имплика ции, не используя транзитивности.

1.3 Самая сложная логическая задача В качестве примера построения логической функции, удовлетво ряющей заданным критериям, мы рассмотрим довольно безум ную задачку, которая даже имеет собственное название, и на зывается она, ни много ни мало, «Самой сложной логической задачей» («The Hardest Logic Puzzle Ever»). Её автор — извест ный логик и философ Джорд Булос.

Задача 1.1. Довелось нам повстречаться с тремя богами. Они всезнающие и могут отвечать на вопросы, которые предполага ют ответ «да» или «нет», причём один из богов всегда отвечает 1 Логика правду, один всегда врёт, а третьему вообще наплевать — он от вечает на вопросы как чёрт на душу положит. Дополнительная проблема в том, что хоть русским они и владеют, но говорить на нём ниже их достоинства. Вместо «да» и «нет» они говорят «ня» и «ми», причём что из этого что означает — неизвестно.

Такой вот божественный язык. У нас есть возможность задать этим богам три вопроса, подразумевающих ответ «да» или «нет».

Задавать вопросы можно в произвольном порядке, можно зада вать разные или одинаковые вопросы. Каждый вопрос адресу ется только одному богу. В результате после всех трёх вопросов вы должны точно указать, где бог вранья, где бог правды и где бог случая. Как это сделать?

В принципе, изложенного в курсе до сих пор материала уже достаточно для того, чтобы решить эту головоломку. Вы можете подумать над ней некоторое количество времени и лишь потом читать дальше. Либо можете сразу читать.

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

Чтобы было проще, решим для начала упрощённую версию этой задачи. Упрощения будут следующими:

1. Боги всё же отвечают по-русски, и мы можем точно интер претировать их ответ.

2. Богов всего два — бог правды и бог лжи. Случайного бога нет.

3. Нам надо выяснить истинность некоторого высказывания, задав только один вопрос.

1.3 Самая сложная логическая задача Такая упрощённая задача как-то попалась сыну моего началь ника на окружной олимпиаде по математике — только там речь шла не о богах, а о двух братьях, и у них надо было выяснить, какая дорога из двух правильная.

Обозначим через тот факт, что мы общаемся с богом правды, а через высказывание, истинность которого нам необходимо установить. Мы хотим каким-то образом реализовать функцию, представленную в таблице 1.7.

0 0 0 1 1 0 1 1 Таблица 1.7. Требуемая функция в упрощённой задаче о богах То есть мы должны получить ответ «да» лишь в том случае, когда истинно. Мы могли бы задать одному из двух богов сле дующий вопрос: «Верно ли, что истинно?». Однако нам из вестно, что если мы говорим с богом лжи ( = 0), то он на все вопросы будет давать противоположный ответ, поэтому нам надо задавать вопрос про истинность функции, которая в случае раз говора с богом лжи принимает значение, противоположное.

Обозначим её через. Её значения приведены в таблице 1.8.

0 0 0 0 1 1 1 0 0 1 1 1 Таблица 1.8. Функция, учитывающая, что один из богов врёт.

Теперь, если мы будем задавать произвольному богу вопрос «верно ли ?», то оба бога будут отвечать «да» в том и только в том случае, когда верно интересующее нас. На человеческом 1 Логика языке этот вопрос можно сформулировать так: «Верно ли, что и, и то, что ты бог правды, либо одновременно верно, либо од новременно неверно?». Сложно и косноязычно, но, тем не менее, это вполне себе ответ на нашу задачу.

Теперь понятно, как действовать и в первоначальном случае.

Теперь в качестве параметров функции ответа надо добавить ещё одно высказывание, истинное в случае, когда «ня» озна чает русское «да». В случае, когда = 0, нам надо ещё один раз подменить значения 0 и 1, чтобы ответ «ня» звучал в точности тогда, когда истинно :

0 0 0 0 1 0 0 1 1 0 0 1 0 0 1 0 1 1 1 0 1 0 0 0 0 1 0 1 1 1 1 1 0 0 0 1 1 1 1 1 Таблица 1.9. Требуемая функция для первоначальной задачи.

Теперь на вопрос «Правда ли, что верно ?», как бог прав ды, так и бог вранья будут отвечать «ня» в том и только в том случае, когда верно высказывание.

В устной форме, конечно, вопрос этот будет звучать слишком длинно и нелепо. Я приведу лишь начало вопроса: «Верно ли одновременно, что ты бог лжи, „ня“ означает „нет“ и невер но, либо что одновременно ты бог лжи, „ня“ означает „да“ и неверно, либо что одновременно...» — ну и так далее, продолжа ем словами надиктовывать ДНФ. Выглядит такой вопрос убого, но это тем не менее решение, и, согласитесь, если бы это был вопрос жизни и смерти, то вас даже такое решение устроило бы.

Приведённое выше высказывание можно упростить. Напри мер, по таблице истинности можно заметить, что = ( ) 1.3 Самая сложная логическая задача. Можно было бы задать наш вопрос, исходя из этого представ ления, и он был бы короче, но пришлось бы как-то явно оговари вать, в каком смысле мы имеем в виду эквивалентность (смот рите замечание в первом параграфе об ассоциативности импли кации и о том, что ( ) и традиционно интерпретируются по-разному).

Есть и более остроумный способ сформулировать вопрос. Опять же, проще понять этот способ, если сначала рассмотреть ситуа цию, когда боги отвечают на русском языке. Вопрос тогда будет звучать так: «Что бы ты мне ответил, если бы я спросил тебя о верности ?». С богом правды всё понятно — он бы ответил прав ду. Бог обмана же попадает с этим вопросом в ловушку — на наш вопрос он соврал бы, но именно в такой постановке вопроса он вынужден соврать ещё раз, и по правилу двойного отрицания он вынужден дать правдивый ответ.

Аналогичную идею можно использовать и когда боги отвеча ют «ня» или «ми». В этом случае вы можете задать такой вопрос:

«Если бы я тебя спросил об истинности, ответил бы ты „ня“?»

По таблице истинности вы можете убедиться в том, что ответ «ня» всегда однозначно будет указывать на истинность.

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

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

Когда мы задаём первый вопрос, всегда существует шанс, что мы задаём его богу случайности, и по его ответу мы не можем судить об истинности утверждения, которое нас интересует. Поэ тому в первую очередь нам надо узнать, какой бог не является случайным, и мы можем это сделать, задав богу вопрос о слу чайности какого-либо другого бога.

1 Логика Вопрос может звучать так: «Правда ли, что бог, на которого я сейчас показываю пальцем, случаен?» И показываем при этом пальцем на какого-то другого бога, не на того, к которому мы обращаемся. Вопрос, понятно, мы задаём не напрямую, а изво ротисто, в форме, найденной выше. Я просто уже не отвлекаюсь на мелочи, так как сейчас они и так понятны.

Если на наш вопрос о случайности бога мы получим ответ «да», мы можем однозначно сказать, что второй оставшийся бог — либо бог правды, либо бог лжи, но никак не бог случая. Дальше мы можем задавать вопросы гарантированно неслучайному бо гу, на этот раз рассчитывая на верный ответ в любом случае.

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

Когда один из неслучайных богов установлен, мы уже ему мо жем задать вопрос о случайности бога, которому мы задавали первый вопрос. Из ответа на этот вопрос мы будем точно знать, какой бог случайный, а какие два нет.

Последний, третий вопрос мы будем задавать не случайному богу о честности одного из богов. Ответ на этот вопрос оконча тельно расставит точки над тем, какой бог правдив, какой лжив, а какой случаен.

А это ровно то, что требовалось по условию задачи.

1.4 Предикаты и кванторы Определение 1.1. Множеством мы будем называть неупоря доченный набор различимых объектов, называемых элемента­ ми множества.

Например, можно рассматривать множество всех людей на Зем ле, множество предложений русского языка, множество моделей автомобилей и так далее.

Запись означает, что элемент принадлежит множе ству (является членом множества). Отрицание этого выска 1.4 Предикаты и кванторы зывания ¬( ) обозначается как и обозначает, что не принадлежит множеству.

Пара примеров:

— «Света из Иваново» «Множество людей»

— «Света из Иваново» «Множество марок автомобилей»

Рассмотрим высказывание: = «Василий Тягин — потомок Васи Квакина». На самом деле мы можем сформулировать по добные высказывания для любых двух людей, и это высказыва ние будет ложным либо истинным в зависимости от того, кого конкретно мы назвали в высказывании. Реализуем эту идею за меной конкретных имён переменными:

(, ) = «x — потомок y».

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

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

Определение 1.2. Множество называется подмножеством множества (обозначение: ), если любой элемент из содержится также и в множестве.

Например, множество всех мужчин является подмножеством множества всех людей, а множество учеников 6 «Б» класса шко лы №469 является подмножеством всех школьников, которое, в свою очередь, также является подмножеством всех людей.

Понятия подмножества и предиката находятся в тесной взаи мосвязи. С одной стороны, любой предикат определяет подмно жество: если () определён на множестве, то множество эле ментов, для которых () = 1, образует подмножество множе ства, которое обозначается как { | () = 1}.

1 Логика С другой стороны, если нам задано, то мы всегда можем определить предикат () = ( ), который будет однозначно характеризовать подмножество.

Таким образом, если — множество всех мужчин, — мно жество всех людей, то это подмножество находится во взаимно однозначном соответствии с предикатом (), который истинен тогда, когда — мужчина.

Предположим теперь, что некоторый предикат () подразу мевает, что в качестве в него можно подставлять элементы множества.

Определение 1.3. Запись, () означает, что высказы вание () истинно для всех элементов.

Определение 1.4. Запись, () означает, что существу ет такой элемент, для которого () истинно.

Символ называется квантором всеобщности, а символ кван тором существования. Само слово «квантор» переводится на ан глийский как «quantifier» (и является однокоренным с ним), ко торое в свою очередь происходит от «quantity», что переводится как «количество».

Пример 1.1. Пусть — множество людей. Предикат (, ) означает, что является предком. Тогда запись, (, ) читается как «для любого человека найдётся такой человек, что он будет предком для » или, по-людски, «У лю бого человека есть предок».

Пример 1.2. Пусть — множество ключей и — множество замков. Высказывание (, ) означает, что ключ открывает замок. Тогда запись, (, ) означает, что для каждого замка найдётся ключ.

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

1.4 Предикаты и кванторы Важно заметить, что порядок, в котором мы задаём кванторы для переменных, очень существенен. Если бы в прошлых при мерах мы поменяли порядок следования кванторов, то смысл этих записей резко бы изменился. Так, запись, (, ) означает, что существует некоторый человек, который являет ся предком для любого другого человека (то есть фактически это библейское утверждение о «первом человеке», что-то вро де Адама), а запись, (, ) означает, что существует ключ, который открывает все замки.

Эта оговорка относится лишь к случаю смены порядка для по следовательных кванторов разного вида. В то же время можно утверждать, что, например,, (, ) =, (, ) и ана логично для квантора существования. Интуитивно это можно понять из такого примера: принадлежит множеству мужчин, принадлежит множеству женщин, а (, ) обозначает, что может (теоретически) жениться на. Очевидно, что в данном случае совершенно не важно, в каком порядке мы указываем кванторы всеобщности.

Самое распространённое и часто применяемое свойство кван торов — это закон де Моргана, который на этот раз формулиру ется так:

1. ¬, () =, ¬ () 2. ¬, () =, ¬ () В принципе, для этого закона можно придумать нечто вро де доказательства. Пусть = {,,..., } — некоторое конечное множество. Тогда, очевидно, запись с кванторами можно пред ставить следующим образом:

1., () = () ()... () 2., () = () ()... () Отрицание обоих частей этих равенств и применение привыч ного нам закона де Моргана даёт нам желаемый результат.

1 Логика Проблема с этим рассуждением в том, что сами множества могут состоять из бесконечно большого числа элементов, и то гда мы не сможем так запросто расписать наш квантор. Тем не менее, правило де Моргана довольно интуитивно понятно (если вы, конечно, последовали моему совету в первом параграфе).

Например, первое правило можно словами проговорить так: если неверно, что для любого выполняется (), то существует хотя бы один, для которого этого нарушается. А это уже довольно очевидно, и поэтому правила де Моргана мы можем принять за аксиомы. А для неверующих в дальнейшем я всё же пока жу, как можно избавиться от ограничения в виде «не можем расписать квантор для бесконечного множества». Но это будет намного позже.

Упражнение 1.6. Докажите (необязательно строго, можно и интуитивным рассуждением) следующие соотношения:

1., ( () ()) = (, ()) (, ()) 2., ( () ()) = (, ()) (, ()) 3., ( () ) = (, ()) 4., ( () ) = (, ()) 5., ( () ) = (, ()) 6., ( () ) = (, ()) В качестве примера приложения этих формул докажем такую несложную теорему:

Теорема 1.4., ( () ) = (, ()).

Доказательство. Всё совершенно прямолинейно:

, ( () ) =, (¬ () ) = (, ¬ ()) = (¬, ()) = (, ()) 1.5 Теории: интуиция Упражнение 1.7. Докажите, что, ( ()) = (, ()).

Упражнение 1.8. Продемонстрируйте, что в остальных слу чаях квантор уже нельзя так запросто «выносить за скобки», то есть приведите примеры, когда отчётливо видно следующее:

1., ( () ()) = (, ()) (, ()) 2., ( () ()) = (, ()) (, ()) 3., ( () ) = (, ()) 4., ( () ) = (, ()) 1.5 Теории: интуиция В этом пункте мы попытаемся на очень неформальном интуи тивном уровне понять, в чем состоят базовые вопросы логики и откуда они возникают при рассмотрении математических тео рий, которые, на первый взгляд, не имеют непосредственного отношения к логике. Это будет очень неформальный материал, и я заранее должен оговориться, что подходы и определения, которые я буду здесь приводить, утрированы и упрощены. Аб солютная строгость нам здесь и не нужна, важно пока понять лишь принципы. Формальные определения будут даны в § 1.8.

Давайте для начала снова рассмотрим теорему 1.4 и попробу ем доказать её в общем виде, но несколько более абстрактно.

Итак, нам дано высказывание ( () ). Поскольку нам сказано «для любого », то давайте возьмём для начала какой нибудь конкретный элемент. Что это за элемент мы не знаем, но он вполне себе конкретен. Имеем (). Предположим далее, что нам совершенно точно известно, что () истинно.

Тогда, в этом предположении, используя импликацию, нам так 1 Логика же будет достоверно известно (по таблице истинности), что ис тинно. Обозначим тот факт, что из () мы вывели как (). Теперь трюк: мы изначально не знали что такое, мы выбрали его на самом деле произвольным образом, мы могли бы вместо него выбрать и любой другой элемент. По сути нам тут важно лишь то, что в принципе есть некоторое, для которого оказывается верно (). Из этих соображений мы можем заме нить () на, (). Теперь, () и отсюда мы можем вернуться к импликации (опять же, в соответствии с таблицей истинности): (, ()). Внимательный читатель заметит, что мы наполовину доказали теорему 1.4.

Упражнение 1.9. Докажите теорему 1.4 в обратную сторону тем же способом.

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

Тем не менее, допустить ошибку в таких рассуждениях так же довольно легко. Рассмотрим элементарное высказывание, = Поскольку мы утверждаем существование некоторых и, удо влетворяющих неравенству, то давайте возьмём конкретные зна чения и, такие что =. А теперь, поскольку мы никак не выводили предварительно, а просто взяли первое попавшееся число, не равное, то давайте заменим на :, =. Очевид 1.5 Теории: интуиция но, что это приводит к противоречию, так как если теперь взять вместо значение, то получится =, что явно не правда.

В данном примере мы допустили очевидную ошибку, закрыв глаза на то, что мы выбирали изначально не произвольным элементом, а исходя из того, чтобы оно не было равно. На практике, в более сложных и длинных рассуждениях, подобные ошибки, связанные с потерей каких-то условий, могут так быст ро и не обнаружиться. Можете ли вы с достоверностью утвер ждать, что в нашем доказательстве теоремы 1.4 мы не допустили ошибки? Ошибки там действительно нет, но у честного человека останутся сомнения.

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

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

Если обозначить высказывания греческими буквами, то лю бое доказательство теперь можно определить как последователь ность высказываний,,,...,. Эта последовательность долж на удовлетворять следующему критерию: каждое предложение доказательства должно быть логическим следствием некоторых 1 Логика предыдущих предложений. Осталось определить лишь логиче ские следствия, но это легко: каждое логическое следствие явля ется набором предложений-посылок и связанными с ними симво лом предложением-результатом, причём в качестве составных частей этих предложений выступают уже не конкретные выска зывания, а некоторые шаблонные символы, в которые мы можем подставлять произвольные предложения.

Приведём пример. Простейшим правилом вывода является пра вило, называемое дедукцией:, (если и истинно, то отсюда следует ). Рассмотрим так же правило, ¬ (если верно и известно, что ложно, то тогда отсюда следу ет, что истинно ). То что эти правила корректны, легко убедить ся по таблице истинности: если все выражения слева от знака истинны, то и выражения справа так же будут истинны. Про верка этого совершенно не сложна, и я оставляю её читателю в качестве упражнения.


Упражнение 1.10. В таблице 1.10 приведены типичные пра вила вывода. Докажите, что они сочетаются с введёнными нами до сих пор определениями логических операций.

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

В нашем примере мы получили две теоремы: и. Множество всех теорем, выводимых из заданных аксиом (включая сами ак сиомы), называется теорией.

Пример 1.3. Рассмотрим конкретный пример как можно при менять правила вывода. Возьмём за аксиому предложение ¬( ). Тут сразу напрашивается применение закона де Моргана, но 1.5 Теории: интуиция Посылка Следствие Наименование ¬¬ сокращение двойного отрицания ¬¬ введение двойного отрицания, введение конъюнкции сокращение конъюнкции введение дизъюнкции, ¬ дизъюнктивный силлогизм, сокращение эквиваленции (1), ¬ ¬ сокращение эквиваленции (2), сокращение эквиваленции (3), ¬ ¬ ¬ ¬ сокращение эквиваленции (4), теорема дедукции (1), теорема дедукции (2), modus ponens ¬, ¬ modus tollens,, анализ частных, введение эквиваленции Таблица 1.10. Типичные правила вывода у нас нет такого правила вывода поэтому нам надо его доказать.

Для удобства доказательства перенумеруем все шаги.

1. ¬( ) — это нам дано;

2. (*) ¬(¬¬) — пойдём от противного и предположим, что верно так же это;

факт наличия дополнительного предпо ложения мы отметили звёздочкой 3. (**) ¬ — введём еще второе предположение;

4. (**) ¬ ¬ — введение дизъюнкции;

5. (*) ¬¬ — поскольку строчки 2 и 4 противоречат друг дру гу, мы получаем, что было неверным предположение сто ки 3(**). Это косвенное применение правила modus tollens — из выведенного ложного утверждения мы получили, что ложна посылка;

1 Логика 6. (*) — сокращение двойного отричания;

7. (***) ¬ — сделаем теперь такое предположение (три звёз дочки);

8. (***) ¬ ¬ — введение дизъюнкции;

9. (*) ¬¬ — из противоречия 8 и 2 заключаем, что было лож ным предположение 7(***);

10. (*) — сокращение двойного отрицания;

11. (*) — введение конъюнкции для 6 и 10;

12. ¬¬(¬¬) — из противоречия 11 и 2 заключаем, что пред положение 2(*) ложно;

13. ¬ ¬ — сокращение двойного отрицания;

никаких допол нительных предположений не осталось.

Фух, мы доказали один из законов де Моргана в одну сторону.

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

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

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

Несмотря на то, что рассматриваемый нами математический аппарат появился сравнительно недавно (точную дату дать слож но, так как всё это создавалось в течение столетий), сами под ходы к аксиомам и теоремам оформились именно в таком идей ном виде ещё во времена Евклида, чья книга «Начала» стала первой известной исторической попыткой построить математи ческую теорию строго в соответствии с законами логики. После нескольких неформальных определений геометрии на плоскости, Евклид приводил 15 аксиом, которые предлагалось принять без доказательства, а далее, уже исходя из этих аксиом, выводилось шесть томов теорем.

Определения были им даны довольно невразумительные. Так, первыми двумя определениями он определял точку как «то, что не имеет никакой части» и линию как «длину без ширины». Это, вероятно, как-то отражает интуитивные представления, но не даёт ни точного определения, ни свойств. Например, Евклид, ссылаясь в этих определениях на «части», «длину» и «ширину»

сами эти понятия нигде не определяет.

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

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

Мы не будем приводить определения Евклида, так как они лишены смысла, но и не будем вводить пока собственных опре 1 Логика делений: процесс этот хоть и не слишком сложный, но долгий и кропотливый, к тому же позже мы найдём более удобный способ определить евклидову геометрию. Пока будем полагаться на ин туицию читателя о понятиях линии, окружности, пересечения, параллельности и подобном, и перейдём сразу к аксиомам.

Хотя сам Евклид приводил 15 аксиом, с современной точки зрения их можно резюмировать всего пятью следующими про стыми утверждениями (остальные аксиомы оказались избыточ ны либо были переформулированы):

1. Пусть и — две различные точки. Тогда через них можно провести единственную прямую.

2. Пусть — точка, не лежащая на прямой. Тогда из на можно опустить единственный перпендикуляр.

3. Пусть — точка, лежащая на прямой, а — некоторый отрезок. Тогда на прямой можно построить различные точки и, лежащие от на расстоянии, равном.

4. Пусть — точка и — отрезок. Можно построить един ственную окружность с центром и радиусом, равным.

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

Далее в «Началах» следует первая теорема: для любого отрез ка с концами возможно построить равносторонний треуголь ник.

Доказательство строится таким образом (см. рисунок 1.1 для наглядной интерпретации): проведём окружность с центром и радиусом, затем окружность того же радиуса, но с центром. Пусть — их точка пересечения. Поскольку обе окружности имеют один радиус, то точка отстоит от обоих точек и на одно и то же расстояние, равное отрезку. Стало быть точки, и образуют равносторонний треугольник.

1.5 Теории: интуиция c a b Рис. 1.1. Построение равностороннего треугольника Вроде бы вполне себе наглядное и очевидное доказательство, какие к нему могут быть вопросы? На самом деле это доказа тельство некорректно. Если вместо рассуждений на пальцах на чать рассуждать более строго (например, на языке логики или около того), то окажется, что у нас возникнет проблема: мы не сможем никак доказать, что окружности с центрами в точках и вообще пересекутся. Это кажется очевидно нашей интуиции, но из сформулированных аксиом доказать этого не получится.

Когда мы сталкиваемся с ситуацией, когда мы не можем дока зать ни утверждение, ни его отрицание, вариантов тут может быть три:

1. мы просто не смогли найти пока доказательство, так как это может быть сложно;

2. что-то не так с нашей логикой, возможно нам не хватает правил вывода;

3. что-то не так с нашими аксиомами, возможно их слишком мало и их надо дополнить.

Я сразу могу сказать, забегая вперёд, что в случае евклидовой геометрии проблема именно в аксиомах: их недостаточно. Пока 1 Логика мы не сможем этого доказать, но мы к этой теме ещё вернёмся в последующих главах.

Уточним теперь понятие «что-то не так». Для примера введём такую систему аксиом:

1. Любые две прямые пересекаются ровно в одной точке;

2. Через любые две точки проходит ровно одна прямая;

3. Существуют четыре точки такие, что они не лежат на од ной прямой.

Это довольно расплывчатые и странные аксиомы. Например, первая аксиома утверждает, что параллельных прямых не суще ствует. Тем не менее эти аксиомы не лишены смысла. Их можно интерпретировать, например, как аксиомы геометрии, которую мы наблюдаем на плоских изображениях (фото, картины) про странства. На фото возникает это странное свойство: любые две прямые пересекаются (см. рис. 1.2). Если рассмотреть, напри мер, фото железной дороги, уходящей за горизонт, то на картин ке две колеи сольются на горизонте в одну точку. В физическом мире они конечно не сливаются, но фотография создаст иллю зию этого. Такая геометрия (называемая в науке проективной) вполне имеет право на существование, и очень широко применя ется, например, в компьютерной трёхмерной графике, не говоря уже о чисто научных применениях.

1.5 Теории: интуиция Рис. 1.2. В бесконечности прямые пересекаются на фото Рис. 1.3. Плоскость Фано С другой стороны, мы можем отойти от привычного интуи тивного определения линий и пространства, и рассмотреть кон струкцию, изображённую на рис.1.3, которая называется плос костью Фано. Эта «плоскость» состоит всего из семи точек и семи линий. Каждая линия состоит из трёх точек. Очевидно, что такое построение не имеет ничего общего с первой нашей интерпретацией в виде фотографий (и даже с нашей интуицией о пространстве и линиях в нём), но простым перебором всех воз можных вариантов легко убедиться, что эта «плоскость Фано»


удовлетворяет всем трём нашим аксиомам.

1 Логика Рассматривая теперь плоскость Фано и фотографию, мы мо жем обнаружить, что хотя эти две картинки совершенно не по хожи друг на друга, у них есть общие теоремы. Один такой про стейший пример демонстрирует следующее упражнение:

Упражнение 1.11. Докажите, что из сформулированных ак сиом можно вывести, что существуют четыре линии, не пересе кающиеся в одной точке.

Есть, однако, и утверждения, которые в различных интерпре тациях будут отличаться. Самое очевидное касается количества точек: на фотографии их бесконечно много, а вот на плоскости Фано их всего семь. А раз какое-то утверждение может быть либо верным, либо неверным в зависимости от интерпретации, то мы можем понять, что это утверждение из заданных аксиом вывести невозможно.

Схожим образом мы докажем в дальнейшем и невозможность доказательства первой теоремы Евклида из его аксиом: мы предъ явим две интерпретации его аксиом, и в одной интерпретации близколежащие окружности будут пересекаться, а в другой нет.

Это очень важный приём, так как он даёт нам однозначный от вет на вопрос о том, что это именно наши аксиомы неполны, а не что-то ещё. Мы готовы сформулировать теперь такие опреде ления:

Определение 1.5. Система аксиом называется неполной, если существует предложение такое, что из аксиом невозможно вы вести ни ни ¬.

Определение 1.6. Система аксиом называется полной, если для любого предложения можно вывести либо, либо ¬.

Опять же, забегая вперёд, могу порадовать читателя: практи чески все полезные аксиоматические системы являются непол ными. Об этом будет сказано в третьей главе, и мы даже дока жем, что простейшая школьная арифметика не полна и полной быть никак не может (мы даже предъявим целый набор теорем, которые невозможно ни доказать ни опровергнуть).

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

Определение 1.7. Структурой называется такое множество предложений, что для любого предложения либо, либо ¬.

Структуры могут быть интересны иногда сами по себе и связа ны с рядом задач (например, по заданной структуре найти аксио мы, которые её породили, желательно автоматически с помощью компьютера), но нами будут использоваться лишь в неотрывной связи с конкретными теориями. Желание увязать структуру с теорией приводит к следующему определению:

Определение 1.8. Моделью теории называется такая струк тура, что для любого верно, что. Множество всех моделей теории обозначается как Mod.

Определение 1.9. Теория называется удовлетворимой, если она обладает моделью. В противном случае она называется неудо­ влетворимой.

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

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

1 Логика Определение 1.10. Предложение называется синтаксически истинным в теории (обозначение ), если его возможно вывести в данной теории пользуясь правилами вывода.

Определение 1.11. Предложение называется семантически ис­ тинным в теории (обозначение |= ), если оно истинно в любой модели данной теории.

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

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

Обычно в качестве правил вывода используются правила, при ведённые в таблице 1.10, а также четыре правила для кванторов:

обобщение и переход к частному для кванторов и. Послед ние правила относительно сложны и мы сформулируем их строго в § 1.7, пока что можно думать о них интуитивно как в начале этого параграфа.

Теорема Гёделя о полноте. Указанный набор правил вывода полон.

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

Доказывать теорему о полноте мы не будем, это доказатель ство довольно нетривиально (хоть принципиально и не сложно) и выходит за рамки данной книги. Вы можете найти его в любом подробном учебнике по логике либо в статьях в Интернете. Для практических нужд достаточно лишь знать ту логику, о которой мы до сих пор говорили, и о возможной неполноте отдельных формальных систем не задумываться, хотя чистые математики рассматривают и другие виды логики.

Многие операции, которые мы до сих пор рассматривали с точки зрения таблиц истинности и синтаксиса, можно так же рассмотреть и с точки зрения семантики. В качестве примера возьмём импликацию:

Определение 1.13. Операцией импликации называется такая операция, истинность которой эквивалентна выражению Mod(, ) Mod(, ).

Здесь под Mod(, ) понимается множество всех моделей тео рии, дополненной предложением.

Упражнение 1.12. Докажите, что приведённое утверждение порождает ровно те же значения истинности, которые мы при водили в §1.1.

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

Определение 1.14. Теория называется противоречивой, если в ней выводимы одновременно некоторое высказывание и ¬. В противном случае теория называется непротеворечивой.

Теорема 1.5. В противоречивой теории любое предложение синтаксически истинно.

Доказательство. Пусть мы вывели и ¬ и хотим вывести. Из истинности вытекает истинность (для истинности «или»

1 Логика достаточно, чтобы истинным было одно из двух высказываний, а первое высказывание, как мы знаем, истинно). Однако теперь из того, что истинно ¬ и мы получаем, что истинно так же и.

Это довольно странно выглядит, но на самом деле это нор мально: противоречивая теория на то и противоречивая, что она не соотстветствует здравому смыслу. Очевидно так же, что про тиворечивая теория не может иметь модели, а следовательно и интерпретации. При построении аксиоматических систем мы должны всеми силами стараться доказать, что аксиоматика, с которой мы работаем, не протеворечива. Опять же, я могу за ранее обрадовать читателя: вторая теорема Гёделя о неполноте утверждает, что для большинства полезных аксиоматик непро тиворечивость доказать невозможно. Об этом мы кратко пого ворим в третьей главе.

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

1.6 Парадоксы Рассмотрим теперь несколько известных парадоксов классиче ской логики.

1.6 Парадоксы 1.6.1 Парадокс импликации Обычно этот парадокс излагается так. Таблица истинности для импликации утверждает, что из ложного высказывания следует любое другое произвольное высказывание: 0 всегда истинно, каким бы ни было. В соответствии с этим определением по идее оказываются справедливы следующие высказывания:

— Из того, что Луна квадратная, следует, что деревья умеют летать.

— Из того, что Жанна д’Арк — первый космонавт, следует, что Путин — краб.

— Из того, что небо твёрдое, следует, что апельсины оранже вые.

Это всё полнейший бред, но он тем не менее идеально соотно сится с таблицей истинности для импликации.

Можно привести и другую интерпретацию импликации: легко убедиться, что тавтологией также является высказывание ( ). Здесь по сути утверждается, что любое истинное выска зывание следует из любого другого произвольного высказывания (неважно, верного или нет). Так, например, верно следующее:

— Вращение Земли вокруг Солнца следует из непогрешимо сти патриарха.

— Смертность всех людей следует из того, что в 98-м году был дефолт.

Одним словом, бред. А если ввести в поиск по Интернету фра зу «парадоксы импликации», то можно и не такое найти.

Собственно, никакого особого парадокса тут, конечно, нет. Все высказывания, которые мы привели выше, взяты с потолка. Мы не определили никак интерпретацию нашей логики, с которой мы работаем, а первичный смысл импликации всё же семанти ческое следование. Если мы рассматриваем импликацию просто 1 Логика по таблице истинности, вырвав из контекста интерпретаций, то она уже представляет собой не более чем арифметическую опе рацию с ноликом и единичкой, и искать в ней какой-то особый смысл — довольно глупое занятие.

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

Эта историческая последовательность и привела к «парадоксу импликации». Как мы показали в § 1.2, таблица истинности для импликации продиктована необходимостью соблюсти свойство транзитивности. Однако до того момента, как математики раз вили концепцию теорий и моделей, попытки увязать логически формулы с высказываниями на человеческом языке приводили к таким парадоксам.

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

Чтобы увидеть, что парадокса не произойдёт, будет уместно вспомнить про понятие выводимости: из противоречивой теории (когда одновременно предполагались верными и и ¬, отку да в общем-то по введению конъюнкции следует высказывание ¬ = 0) мы показали, что возможно вывести любое про извольное высказывание. Другое дело, что как стало понятно в прошлом параграфе, для такой теории не будет никакой модели — подобная теория является противоречивой.

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

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

1.6 Парадоксы 1.6.2 Парадокс брадобрея В некотором царстве, в некотором государстве, живёт брадо брей — такой мужик, который бреет бороды только тем, кто не бреется сам, а тем кто сам бреется, он бороды не бреет. Вопрос:

а кто бреет самого брадобрея?

Допустим, брадобрей сам бреется. Но, будучи брадобреем, он не должен брить тех, кто бреется сам, то есть брить себя не должен. Если же допустить, наоборот, что он не бреется сам, то он должен себя брить, как человека, который сам не бреется.

Парадокс.

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

, (), (¬(, ) (, )) Однако поскольку снабжён квантором, мы в качестве можем взять любое значение, в том числе и. Тогда в скобках получится такое выражение:

¬(, ) (, ) Это условие всегда ложно, и значит изначальное высказыва ние тоже всегда ложно. Таким образом само условие задачи ока зывается противоречивым и нереализуемым (не имеющим моде ли) — такого города и такого брадобрея просто не может суще ствовать в принципе, даже в теории.

А значит, что и любые последующие вопросы, какими бы они ни были, в том числе вопрос «Кто бреет брадобрея?», физически не имеют смысла. Мы это строго доказали.

1.6.3 Парадокс пьяницы Теорема. В любом баре найдётся такой посетитель, что если он пьёт, то пьют и все остальные посетители.

1 Логика Теорема кажется абсурдной — пить теоретически может любое количество людей, без каких либо условий. Однако, эту теорему легко доказать.

Доказательство. Введём предикат (), означающий, что пьёт. Тогда условия теоремы можно сформулировать следую щим образом:, ((), ()). Данное выражение оказы вается всегда истинным, что легко увидеть, если рассмотреть две ситуации: когда в баре пьют все, и когда кто-то все же не пьёт.

Если пьют все, то, () и доказывать нечего. Если же в баре кто-то не пьёт, то найдётся такой, что выражение () ока жется ложным, а из ложного утверждения следует любое утвер ждение. Следовательно, приведённая нами формула оказывает ся всегда истинна.

В чем подвох? На первый взгляд может показаться, что под вох в импликации и это только разновидность первого нашего парадокса. Однако это не так — импликация здесь используется вполне законно, придраться к импликации тут негде — рассуж дения первого парадокса здесь не пройдут.

Реальная причина парадокса в том, что формулировка теоре мы как бы подразумевает, что есть некий один человек, который является причиной всеобщего пьянства, причём это происходит каждый раз. В формулировке же, используемой при доказатель стве теоремы, говорится лишь об одном моменте времени и не говорится ни о какой систематичности. Если бы люди собрались выпить в баре в следующий раз, то теорема осталась бы вер ной, но выбор человека, который «если пьёт, то пьют все», был бы уже другим. Наша теория, доказанная выше, ровным счётом ничего не утверждает про завтрашний или вчерашний день.

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

1.6 Парадоксы 1.6.4 Парадокс воронов Рассмотрим следующее высказывание: «Все ворны чёрные». о Легко увидеть, что данное высказывание эквивалентно высказы ванию «Если объект не чёрный, то он не может быть вороной».

На языке логики это символизируется тавтологией = ¬ ¬ и в общем-то довольно очевидно.

Представим, однако, себя натуралистами-исследователями, ко торые путешествуют по свету и пытаются ответить на вопрос:

«Являются ли все вороны чёрными, или все же есть цветные?»

Увидеть сразу всех ворон у нас не получится, мы можем видеть только какую-то незначительную долю всех живущих ворон. Од нако логично, что чем больше чёрных ворон в разных уголках планеты мы видим, тем больше мы убеждаемся в том, что и все вороны вообще — чёрные.

Возьмём теперь наше эквивалентное черноте всех ворон вы сказывание «Если объект не чёрный, то он не может быть воро ной». Оно равнозначно прошлому высказыванию, и из него как бы следует, что чем больше мы видим не чёрных, а цветных объ ектов, которые не являются воронами, тем больше должна расти в нас уверенность в том, что все вороны чёрные. То есть даже если мы увидели миллионы апельсинов и яблок, то мы должны делать какие-то выводы о цвете ворон.

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

В данной ситуации следовало бы применять теорию вероятно стей. Интересно, что даже используя теорию вероятностей, мы 1Я не знаю, так это или не так с биологической точки зрения, но для целей математики предположим, что это так.

1 Логика можем прийти к тому же самому результату: наблюдение боль шого числа цветных объектов должно убеждать нас в черно те всех ворон. Другое дело, что степень нашей убеждённости в этом случае будет расти не с той же скоростью. При наблюдении чёрной вороны наша убеждённость будет расти довольно значи тельно, а вот при наблюдении зелёного яблока убеждённость в черноте ворон должна расти настолько несущественно, что ей можно вообще пренебречь.

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

Иначе легко прийти к ложным выводам.

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

Предположим себе такой сюжет для научно-фантастической книжки: существует два мира, населённых птичками. В одном мире вороны встречаются крайне редко. Например, их всего нес колько штук на всю планету, и все они чёрные. А во втором мире ворон летает миллионы, но среди них есть всё же одна белая.

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

Таким образом, при некотором уточнении постановки задачи мы вообще смогли вывернуть наизнанку все наши выводы.



Pages:   || 2 | 3 | 4 | 5 |
 





 
© 2013 www.libed.ru - «Бесплатная библиотека научно-практических конференций»

Материалы этого сайта размещены для ознакомления, все права принадлежат их авторам.
Если Вы не согласны с тем, что Ваш материал размещён на этом сайте, пожалуйста, напишите нам, мы в течении 1-2 рабочих дней удалим его.