Курс лекций Часть I автор: Крапивина И. В. Валуйки 2008
| Вид материала | Курс лекций |
- Г. Валуйки Белгородской области, 647.06kb.
- Курс лекций часть 2 Тюмень 2006 удк 159 01 Михеева Е. М., Фалько Г. В. Психология:, 2034.37kb.
- Курс лекций для студентов идпо специальностей «Юриспруденция», 3911.79kb.
- Курс лекций для студентов идпо специальностей «Юриспруденция», 2986.57kb.
- Курс лекций Часть II учебное пособие рпк «Политехник» Волгоград, 1175.06kb.
- Курс лекций Часть 2 Составитель: кандидат экономических наук Г. Н. Кудрявцева Электроизолятор, 1210.68kb.
- М. К. Мамардашвили Современная европейская философия (XX век) Курс лекций, 421.49kb.
- Краткий курс лекций по медицинской паразитологии Часть Клещи, 643.33kb.
- Курс лекций по дисциплине история экономических учений москва 2008, 5434.7kb.
- Курс лекций москва 2008, 1185.38kb.
3.7. Кодирование символьной информации. Алфавитное неравномерное двоичное кодирование. Префиксный код. Код Хаффмана При этом как следует из названия, символы некоторого первичного алфавита (например, русского) кодируются комбинациями символов двоичного алфавита (т.е. 0 и 1), причем, длина кодов и, соответственно, длительность передачи отдельного кода, могут различаться. Длительности элементарных сигналов при этом одинаковы (  0=1=). За счет чего можно оптимизировать кодирование в этом случае? Очевидно, суммарная длительность сообщения будет меньше, если применить следующий подход: тем буквам первичного алфавита, которые встречаются чаще, присвоить более короткие по длительности коды, а тем, относительная частота которых меньше – коды более длинные. Но длительность кода – величина дискретная, она кратна длительности сигнала передающего один символ двоичного алфавита. Следовательно, коды букв, вероятность появления которых в сообщении выше, следует строить из возможно меньшего числа элементарных сигналов. Построим кодовую таблицу для букв русского алфавита, Очевидно, возможны различные варианты двоичного кодирования, однако, не все они будут пригодны для практического использования – важно, чтобы закодированное сообщение могло быть однозначно декодировано, т.е. чтобы в последовательности 0 и 1, которая представляет собой многобуквенное кодированное сообщение, всегда можно было бы различить обозначения отдельных букв. Проще всего этого достичь, если коды будут разграничены разделителем – некоторой постоянной комбинацией двоичных знаков. Условимся, что разделителем отдельных кодов букв будет последовательность 00 (признак конца знака), а разделителем слов – 000 (признак конца слова – пробел). Довольно очевидными оказываются следующие правила построения кодов:
Длительность передачи каждого отдельного кода ti, очевидно, может быть найдена следующим образом: ti = ki • , где ki – количество элементарных сигналов (бит) в коде символа i. В соответствии с приведенными выше правилами получаем следующую таблицу кодов:Таблица 1.
Теперь по формуле можно найти среднюю длину кода K(2) для данного способа кодирования:  Поскольку для русского языка I1(r) =4,356 бит, избыточность данного кода, составляет: Q(r) = 1 - 4,356/4,964  0,122;это означает, что при данном способе кодирования будет передаваться приблизительно на 12% больше информации, чем содержит исходное сообщение. Аналогичные вычисления для английского языка дают значение K(2) = 4,716, что при I1(e) =4,036 бит приводят к избыточности кода Q(e) = 0,144. Рассмотрев один из вариантов двоичного неравномерного кодирования, попробуем найти ответы на следующие вопросы: возможно ли такое кодирование без использования разделителя знаков? Существует ли наиболее оптимальный способ неравномерного двоичного кодирования? Суть первой проблемы состоит в нахождении такого варианта кодирования сообщения, при котором последующее выделение из него каждого отдельного знака (т.е. декодирование) оказывается однозначным без специальных указателей разделения знаков. Наиболее простыми и употребимыми кодами такого типа являются так называемые префиксные коды, которые удовлетворяют следующему условию (условию Фано): Неравномерный код может быть однозначно декодирован, если никакой из кодов не совпадает с началом (префиксом 1) какого-либо иного более длинного кода. Например, если имеется код 110, то уже не могут использоваться коды 1, 11, 1101, 110101 и пр. Если условие Фано выполняется, то при прочтении (расшифровке) закодированного сообщения путем сопоставления со списком кодов всегда можно точно указать, где заканчивается один код и начинается другой. Пример 1. Пусть имеется следующая таблица префиксных кодов:
Требуется декодировать сообщение: 00100010000111010101110000110 Декодирование производится циклическим повторением следующих действий:
Применение данного алгоритма дает:  Доведя процедуру до конца, получим сообщение: «мама мыла раму». Таким образом, использование префиксного кодирования позволяет делать сообщение более коротким, поскольку нет необходимости передавать разделители знаков. Однако, условие Фано не устанавливает способа формирования префиксного кода и, в частности, наилучшего из возможных. Способ оптимального префиксного двоичного кодирования был предложен Д.Хаффманом. Построение кодов Хаффмана мы рассмотрим на следующем примере: пусть имеется первичный алфавит A, состоящий из шести знаков a1 …a6 с вероятностями появления в сообщении, соответственно, 0,3; 0,2; 0,2; 0,15; 0,1; 0,05. Создадим новый вспомогательный алфавит A1, объединив два знака с наименьшими вероятностями (a5и a6) и заменив их одним знаком (например, a(1)); вероятность нового знака будет равна сумме вероятностей тех, что в него вошли, т.е. 0,15; остальные знаки исходного алфавита включим в новый без изменений; общее число знаков в новом алфавите, очевидно, будет на 1 меньше, чем в исходном. Аналогичным образом продолжим создавать новые алфавиты, пока в последнем не останется два знака; ясно, что число таких шагов будет равно N – 2, где N – число знаков исходного алфавита (в нашем случае N = 6, следовательно, необходимо построить 4 вспомогательных алфавита). В промежуточных алфавитах каждый раз будем переупорядочивать знаки по убыванию вероятностей. Всю процедуру построения представим в виде таблицы:  Теперь в обратном направлении поведем процедуру кодирования. Двум знакам последнего алфавита присвоим коды 0 и 1 (которому какой – роли не играет; условимся, что верхний знак будет иметь код 0, а нижний – 1). В нашем примере знак a1(4) алфавита A(4), имеющий вероятность 0,6 , получит код 0, а a2(4) с вероятностью 0,4 – код 1. В алфавите A(3) знак a1(3) с вероятностью 0,4 сохранит свой код (1); коды знаков a2(3) и a3(3), объединенных знаком a1(4) с вероятностью 0,6 , будут уже двузначным: их первой цифрой станет код связанного с ними знака (т.е. 0), а вторая цифра – как условились – у верхнего 0, у нижнего – 1; таким образом, a2(3) будет иметь код 00, а a3(3) – код 01. Полностью процедура кодирования представлена в следующей таблице:  Из самой процедуры построения кодов легко видеть, что они удовлетворяют условию Фано и, следовательно, не требуют разделителя. Средняя длина кода при этом оказывается: K(2) = 0,3·2+0,2·2+0,2·2+0,15·3+0,1·4+0,05·4 = 2,45 Для сравнения можно найти I1(A) – она оказывается равной 2,409, что соответствует избыточности кода Q = 0,0169, т.е. менее 2%. Код Хаффмана важен в теоретическом отношении, поскольку можно доказать, что он является самым экономичным из всех возможных, т.е. ни для какого метода алфавитного кодирования длина кода не может оказаться меньше, чем код Хаффмана. Применение описанного метода для букв русского алфавита дает следующие коды (для удобства сопоставления они приведены в формате табл.1):
Средняя длина кода оказывается равной K(2) = 4,395; избыточность кода Q(r) = 0,00887, т.е. менее 1%. Таким образом, можно заключить, что существует метод построения оптимального неравномерного алфавитного кода. Не следует думать, что он представляет число теоретический интерес. Метод Хаффмана и его модификация – метод адаптивного кодирования (динамическое кодирование Хаффмана) – нашли широчайшее применение в программах-архиваторах, программах резервного копирования файлов и дисков, в системах сжатия информации в модемах и факсах. 3.7.1. Равномерное алфавитное двоичное кодирование. Байтовый код В этом случае двоичный код первичного алфавита строится цепочками равной длины, т.е. со всеми знаками связано одинаковое количество информации равное I0. Передавать признак конца знака не требуется, поэтому для определения длины кодовой цепочки можно воспользоваться формулой: K(2)  log2N. Приемное устройство просто отсчитывает оговоренное заранее количество элементарных сигналов и интерпретирует цепочку (устанавливает, какому знаку она соответствует). Правда, при этом недопустимы сбои, например, пропуск (непрочтение) одного элементарного сигнала приведет к сдвигу всей кодовой последовательности и неправильной ее интерпретации; решается проблема путем синхронизации передачи или иными способами, о которых пойдет речь в ссылка скрыта. С другой стороны, применение равномерного кода оказывается одним из средств контроля правильности передачи, поскольку факт поступления лишнего элементарного сигнала или, наоборот, поступление неполного кода сразу интерпретируется как ошибка.Примером равномерного алфавитного кодирования является телеграфный код Бодо, пришедший на смену азбуке Морзе. Исходный алфавит должен содержать не более 32-х символов; тогда K(2) = log2 32 = 5, т.е. каждый знак содержит 5 бит информации. Условие N  32, очевидно, выполняется для языков, основанных на латинском алфавите ( N = 27 = 26+”пробел”), однако в русском алфавите 34 буквы (с пробелом) – именно по этой причине пришлось «сжать» алфавит (как в коде Хаффмана) и объединить в один знак «е» и «ё», а также «ь» и «ъ», что видно из таблицы 3.1. После такого сжатия N = 32, однако, не остается свободных кодов для знаков препинания, поэтому в телеграммах они отсутствуют или заменяются буквенными аббревиатурами; это не является заметным ограничением, поскольку, как указывалось выше, избыточность языка позволяет легко восстановить информационное содержание сообщения. Избыточность кода Бодо для русского языка Q(r) = 0,129, для английского Q(e) = 0,193.Другим важным для нас примером использования равномерного алфавитного кодирования является представление символьной информации в компьютере. Чтобы определить длину кода, необходимо начать с установления количество знаков в первичном алфавите. Компьютерный алфавит должен включать:
Получаем, что общее число символов N 148. Теперь можно оценить длину кодовой цепочки: K(2) log2148 7,21. Поскольку K(2) должно быть целым, очевидно, K(2)= 8. Именно такой способ кодирования принят в компьютерных системах: любому символу ставится в соответствие цепочка из 8 двоичных разрядов (8 бит). Такая цепочка получила название байт, а представление таким образом символов – байтовым кодированием.Байт наряду с битом может использоваться как единица измерения количества информации в сообщении. Один байт соответствует количеству информации в одном символе алфавита при их равновероятном распределении. Этот способ измерения количества информации называется также объемным. Пусть имеется некоторое сообщение (последовательность знаков); оценка количества содержащейся в нем информации согласно рассмотренному ранее вероятностному подходу (с помощью формулы Шеннона) дает Iвер, а объемная мера пусть равна Iоб; соотношение между этими величинами вытекает Iвер IобИменно байт принят в качестве единицы измерения количества информации в международной системе единиц СИ. 1 байт = 8 бит. Наряду с байтом для измерения количества информации используются более крупные производные единицы:
Использование 8-битных цепочек позволяет закодировать 28=256 символов, что превышает оцененное выше N и, следовательно, дает возможность употребить оставшуюся часть кодовой таблицы для представления дополнительных символов. Однако недостаточно только условиться об определенной длине кода. Ясно, что способов кодирования, т.е. вариантов сопоставления знакам первичного алфавита восьмибитных цепочек, очень много. По этой причине для совместимости технических устройств и обеспечения возможности обмена информацией между многими потребителями требуется согласование кодов. Подобное согласование осуществляется в форме стандартизации кодовых таблиц. Первым таким международным стандартом, который применялся на больших вычислительных машинах, был EBCDIC (Extended Binary Coded Decimal Interchange Code) – «расширенная двоичная кодировка десятичного кода обмена». В персональных компьютерах и телекоммуникационных системах применяется международный байтовый код ASCII (American Standard Code for Information Interchange – «американский стандартный код обмена информацией»). Он регламентирует коды первой половины кодовой таблицы (номера кодов от 0 до 127, т.е. первый бит всех кодов 0). В эту часть попадают коды прописных и строчных английских букв, цифры, знаки препинания и математических операций, а также некоторые управляющие коды (номера от 0 до 31). Ниже приведены некоторые ASC-коды:
Вторая часть кодовой таблицы – она считается расширением основной – охватывает коды в интервале от 128 до 255 (первый бит всех кодов 1). Она используется для представления символов национальных алфавитов (например, русского или греческого), а также символов псевдографики. Для этой части также имеются стандарты, например, для символов русского языка это КОИ–8, КОИ–7 и др. Как в основной таблице, так и в ее расширении коды букв и цифр соответствуют их лексикографическому порядку (т.е. порядку следования в алфавите) – это обеспечивает возможность автоматизации обработки текстов и ускоряет ее. В настоящее время появился и находит все более широкое применение еще один международный стандарт кодировки – Unicode. Его особенность в том, что в нем использовано 16-битное кодирование, т.е. для представления каждого символа отводится 2 байта. Такая длина кода обеспечивает включения в первичный алфавит 65536 знаков. Это, в свою очередь, позволяет создать и использовать единую для всех распространенных алфавитов кодовую таблицу. 3.7.2. Алфавитное кодирование с неравной длительностью элементарных сигналов. Код Морзе В качестве примера использования данного варианта кодирования рассмотрим телеграфный код Морзе («азбука Морзе»). В нем каждой букве или цифре сопоставляется некоторая последовательность кратковременных импульсов – точек и тире, разделяемых паузами. Длительности импульсов и пауз различны: если продолжительность импульса, соответствующего точке, обозначить , то длительность импульса тире составляет 3 , длительность паузы между точкой и тире , пауза между буквами слова 3, пауза между словами (пробел) – 6. Таким образом, под знаками кода Морзе следует понимать: « » – «короткий импульс + короткая пауза», « » – «длинный импульс + короткая пауза», «0» – «длинная пауза», т.е. код оказывается троичным.Свой код Морзе разработал в 1838 г., т.е. задолго до исследований относительной частоты появления различных букв в текстах. Однако им был правильно выбран принцип кодирования – буквы, которые встречаются чаще, должны иметь более короткие коды, чтобы сократить общее время передачи. Относительные частоты букв английского алфавита он оценил простым подсчетом литер в ячейках типографской наборной машины. Поэтому самая распространенная английская буква «E» получила код «точка». При составлении кодов Морзе для букв русского алфавита учет относительной частоты букв не производился, что, естественно, повысило его избыточность. Как и в рассмотренных ранее вариантах кодирования, произведем оценку избыточности. По-прежнему для удобства сопоставления данные представим в формате табл. 3.1. Признак конца буквы («0») в их кодах не отображается, но учтен в величине ki – длине кода буквы i.  Среднее значение длины кода K(3) = 3,361. Полагая появление знаков вторичного алфавита равновероятным, получаем среднюю информацию на знак равной I(2) = log23 = 1,585 бит. Подставляя эти данные, а также для русского алфавита I1(1) = 4,356 бит, получаем: Q(r) = 1 – 4,356/(3,361 – 1,585) 0,182т.е. избыточность составляет около 18% (для английского языка 15%). Тем не менее, код Морзе имел в недалеком прошлом весьма широкое распространение в ситуациях, когда источником и приемником сигналов являлся человек (не техническое устройство) и на первый план выдвигалась не экономичность кода, а удобство его восприятия человеком.3.7.3. Блочное двоичное кодирование Вернемся к проблеме оптимального кодирования. Пока что наилучший результат (наименьшая избыточность) был получен при кодировании по методу Хаффмана – для русского алфавита избыточность оказалась менее 1%. При этом указывалось, что код Хаффмана улучшить невозможно. На первый взгляд это противоречит первой теореме Шеннона, утверждающей, что всегда можно предложить способ кодирования, при котором избыточность будет сколь угодно малой величиной. На самом деле это противоречие возникло из-за того, что до сих пор мы ограничивали себя алфавитным кодированием. При алфавитном кодировании передаваемое сообщение представляет собой последовательность кодов отдельных знаков первичного алфавита. Однако возможны варианты кодирования, при которых кодовый знак относится сразу к нескольким буквам первичного алфавита (будем называть такую комбинацию блоком) или даже к целому слову первичного языка. Кодирование блоков понижает избыточность. В этом легко убедиться на простом примере. Пусть имеется словарь некоторого языка, содержащий n = 16000 слов (это, безусловно, более чем солидный словарный запас!). Поставим в соответствие каждому слову равномерный двоичный код. Очевидно, длина кода может быть найдена из соотношения K(2) log2n 13,97 = 14. Следовательно, каждому слову будет поставлена в соответствие комбинация из 14 нулей и единиц – получатся своего рода двоичные иероглифы. Например, пусть слову «ИНФОРМАТИКА» соответствует код 10101011100110, слову «НАУКА» – 00000000000001, а слову «ИНТЕРЕСНАЯ» – 00100000000010; тогда последовательность:000000000000110101011100110000000000000001, очевидно, будет означать «ИНФОРМАТИКА ИНТЕРЕСНАЯ НАУКА». Легко оценить, что при средней длине русского слова K(r) = 6,3 буквы (5,3 буквы + пробел между словами) средняя информация на знак первичного алфавита оказывается равной I (2) = K (2) / K (r) = 14/6,3 = 2,222 бит, что почти в 2 раза меньше, чем 4,395 бит при алфавитном кодировании. Для английского языка такой метод кодирования дает 2,545 бит на знак. Таким образом, кодирование слов оказывается более выгодным, чем алфавитное. Еще более эффективным окажется кодирование в том случае, если сначала установить относительную частоту появления различных слов в текстах и затем использовать код Хаффмана. Подобные исследования провел в свое время Шеннон: по относительным частотам 8727 наиболее употребительных в английском языке слов он установил, что средняя информация на знак первичного алфавита оказывается равной 2,15 бит. Вместо слов можно кодировать сочетания букв – блоки. В принципе блоки можно считать словами равной длины, не имеющими, однако, смыслового содержания. Удлиняя блоки и применяя код Хаффмана теоретически можно добиться того, что средняя информация на знак кода будет сколь угодно приближаться к  .Однако, несмотря на кажущиеся преимущества, применение блочного и словесного метода кодирования имеет свои недостатки. Во-первых, необходимо хранить огромную кодовую таблицу и постоянно к ней обращаться при кодировании и декодировании, что замедлит работу и потребует значительных ресурсов памяти. Во-вторых, помимо основных слов разговорный язык содержит много производных от них, например, падежи существительных в русском языке или глагольные формы в английском; в данном способе кодирования им всем нужно присвоить свои коды, что приведет к увеличению кодовой таблицы еще в несколько раз. В-третьих, возникает проблема согласования (стандартизации) этих громадных таблиц, что непросто. Наконец, в-четвертых, алфавитное кодирование имеет то преимущество, что буквами можно закодировать любое слово, а при кодировании слов – можно использовать только имеющийся словарный запас. По указанным причинам блочное и словесное кодирование представляет лишь теоретический интерес, на практике же применяется кодирование алфавитное. РАЗДЕЛ IV. ЭЛЕМЕНТЫ МАТЕМАТИЧЕСКОЙ ЛОГИКИ 4.1. Искусство логического мышления В процессе всей своей деятельности, человеку приходится разрешать различные проблемы и задачи. Самая суть нашего мыслительного процесса заключается в поиске решений. И конечно хотелось бы находить нужные решения, по возможности быстро. Однако очень часто наши рассуждения идут в неверном направлении, и мы приходим к ошибочному выводу. Приходится возвращаться к тому, с чего начинали и искать решение в другом направлении. Наш ум берясь за задачу видит сразу много путей для рассуждения, из которых большинство ошибочны, но ум об этом не знает и проверяет их все, пока не наткнётся на верный. Конечно, есть люди, обладающие настолько сильной интуицией, что они видят правильное направление рассуждений сразу. Однако интуиция, средство не вполне надёжное. Когда мы принимаем решение интуитивно, всегда остаётся ощущение неуверенности. Поэтому ещё древние мыслители пришли к идее, что неплохо бы правильный ход рассуждений вычислять. Изобрести бы что-то вроде формул, в которых вместо чисел использовались бы рассуждения. Идея очень хорошая, и её пытались реализовать многие философы и математики. В полной мере это на сегодня не удалось. Однако удалось установить, что правильный ход рассуждений подчиняется определённым законам, знание которых помогает значительно сократить путь к истине. Кроме того, существуют методы ведения рассуждений, используя которые мы можем мыслить более эффективно. Постепенно образовалась наука ( называемая логикой ) целью которой было открытие законов правильного мышления и разработка методов мышления. Любая наука, начинается с точного определения понятий с которыми она имеет дело. Определим основные понятия и мы: Посылка - это утверждение, из которого мы исходим в своих рассуждениях. Следствие - это утверждение являющееся результатом наших рассуждений. Умозаключение - это мыслительный процесс, в котором из одного или нескольких суждений, делается заключение. Гипотеза - это утверждение, истинность которого требуется доказать. Противоречие - это ситуация, когда в процессе наших рассуждений получились два взаимоисключающих утверждения. Суждение - это единица мышления. Основные законы: Закон тождества. Всякий предмет, есть то, что он есть. Что это означает: Если мы, в своих рассуждениях, используем какое - либо понятие, то на любом этапе рассуждений, это понятие должно означать одно и тоже. Иногда за соблюдением закона тождества надо специально следить. Например, при использовании многозначных слов. Нарушение закона может завести в тупик. К примеру, понятием энергии часто обозначаются совершенно разные явления. Например, физическая энергия и психическая энергия. Если мы опустим, тот факт, что это два разных явления, то законы, которым подчиняется физическая энергия, можно будет автоматически переносить на явления связанные с проявлением психической энергии, что и будет ошибкой. Приведём более простой пример: Предположим, вы изучили правила дорожного движения принятые в России. Закон тождества говорит, что правила принятые в России, это совсем не те правила, которые приняты во Франции. Если же вы пренебрежёте законом тождества, то будучи во Франции вы рискуете попасть в аварию. Закон противоречия. Ход рассуждений не должен быть противоречивым. На этом законе основан метод доказательства утверждений, так называемый метод "От противного". Применение метода рассматривается ниже в задачах о принцессах. Суть его заключается в следующем правиле. В начале рассуждений, мы принимаем некоторое утверждение за истину. Если мы будем рассуждать, не нарушая правила и законы логики, то на любом шаге наших рассуждений должны получаться только истинные утверждения. Если же мы когда либо получим ложное утверждение, то это будет означать, что исходное утверждение не может быть истинным. Закон исключенного третьего. Если есть два суждения и одно исключает другое, то одно из них истина, а другое ложь. В реальной жизни это не всегда так. Приведём пример: Первое утверждение "Я пользуюсь методами математической логики каждый день моей жизни.", второе утверждение "Я никогда не пользуюсь методами математической логики". Очевидно, что они противоречат друг другу, однако они вполне могут оказаться одновременно ложными. Например, если вы специалист по математической логике, то вы должны часто пользоваться её методами, но вряд ли они нужны вам каждый день вашей жизни. Закон исключенного третьего предназначен для использовании в области точных наук, в которых такие ситуации не встречаются или встречаются достаточно редко. Закон достаточного основания. Любое утверждение должно быть обосновано. Закон кажется очевидным. Совершенно естественно, что каждое утверждение должно быть или аксиомой или выводится из утверждения, истинность которого не вызывает сомнений. Однако в реальной практике мы часто делам свои заключения из утверждений, чья истинность сомнительна, или пользуемся неправильно составленными умозаключениями. Методы мышления Пользуясь законами, можно строить методы правильного мышления. Их существует довольно много, но мы приведём в качестве примера только два из них. Дедукция: Это метод рассуждений, при котором некоторые истинные утверждения берутся в качестве посылок. Затем с помощью умозаключений из этих посылок получаются выводы, которые в свою очередь становятся посылками для следующих умозаключений. Получается цепочка умозаключений, в начале которой находится некоторое количество очевидных утверждений, а в конце утверждения, истинность которых уже далеко не очевидна, если не знать всей цепочки. Очень яркий литературный пример использования дедуктивного метода это герой А. Конан-Дойля Шерлок Холмс. Конечно, применение дедукции Холмсом далеко от математической точности и строгой критики рассказы о нём не выдерживают, но суть метода в рассказах Конан-Дойля демонстрируется очень наглядно. Метод приведения к противоречию: Существо данного метода состоит в построении такой цепочки рассуждений от исходной посылки, чтобы она привела или наоборот не привела к противоречию. Если мы получим противоречие (не нарушая законов логики), то это будет означать ложность исходной посылки. В книге Смаллиана есть масса примеров того, как используя данный метод можно решать задачи. В качестве примера приведём следующую задачу: К королю некоего малоизвестного королевства, очень часто приезжали различные принцы свататься к принцессам, которых у того короля было довольно много. Каждого из них надо было как то проверять, а так как принцев было много, то король решил поставить процесс на поток. Он подводил принца к дверям в комнаты и предлагал открыть одну из них. Причем в комнатах он помещал тигров и принцесс. Принц должен был угадать в какой комнате принцесса. Что бы это не было простое гадание, ему выдавалась дополнительная информация, анализируя которую он мог точно узнать где принцесса, а где тигр. Приведем одну задачу с решением в качестве примера. В этом испытании на дверях комнат были следующие таблички:
Кроме того, принцу было сказано, что на одной табличке написана правда, а на другой нет. Начнем рассуждения. Для каждой из табличек возможны только два варианта, либо ложь, либо истина. Рассмотрим с этой позиции табличку на первой комнате. Табличка на первой двери истинна. Тогда табличка на второй двери ложна. А так как табличка на второй двери утверждает, что в одной из комнат находится принцесса, то из её ложности следует, что принцессы там нет, что приходит в противоречие с истинностью первой таблички. Таким образом, мы, предположив, что табличка на первой двери истинна пришли к противоречию. Табличка на первой двери ложна. Тогда табличка на второй двери истинна. Из ложности первой таблички следует, что принцесса находится в комнате 2, а тигр в комнате 1. Из истинности второй табличке следует, что в одной из комнат есть принцесса и в одной из комнат есть тигр. Эти утверждения не противоречат друг другу, следовательно вторая ситуация непротиворечива и чего в свою очередь следует что принцесса находится во второй комнате. Задача для самостоятельного решения:
Дополнительно было известно следующее: Если в первой комнате находится принцесса, то утверждение на табличке истинно, если же там тигр, то утверждение ложно. Относительно правой комнаты все было наоборот: утверждение на табличке ложно, если в комнате находится принцесса, и истинно, если в комнате сидит тигр. |
2=52 букв латинского алфавита (с учетом прописных и строчных);