На языке предикатов можно описать далеко не все, хотя и многое. Но даже в этом ограниченном пространстве подчас приходится применять хитрости и уловки, которые бы больше пристали ремеслу или искусству. Хотя об'яснения, в конце концов, обычно бывают строго формальные.
Вот некоторые «классические примеры».
Если мы желаем сказать на языке предикатов «Все студенты отличники», то рекомендуется конструкция
" ДЛЯ ВСЕХ иксов справедливо: ЕСЛИ икс студент, ТО икс отличник"
Но если хотим сказать «Некоторые студенты отличники», то это следует записать
" ДЛЯ НЕКОТОРЫХ иксов справедливо: икс студент И икс отличник" Конструкция ЕСЛИ…, ТО в данном случае не подходит. И вот почему: стоит затесаться в компанию одному иксу-нестуденту и он сделает этот предикат истинным, даже если там нет ни одного отличника!
И еще высказывание «Собакам и кошкам вход воспрещен».
Конструкция
" ДЛЯ ВСЕХ иксов справедливо: ЕСЛИ икс – собака И икс – кошка, ТО иксу вход запрещен"
Ясно что таких иксов, которые бы были одновременно собакой и кошкой не существует! Как, впрочем, и таких игреков. Поэтому
" ДЛЯ ВСЕХ иксов справедливо: ЕСЛИ икс – собака ИЛИ икс – кошка, ТО иксу вход запрещен"
И список таких фокусов-выкрутасов можно продолжать долго. До бесконечности. Но, главное, во-время остановиться и понять, что если бы даже придумать другую логику, в которой не было бы этих проблем, то получится логика, в которой будут другие проблемы, скорее всего существенно большие. А мы даже не трогали таких заморочек, присущих естественным языкам, как синонимы, омонимы, метафоры, гиперболы и т.д и т.п. Одни идиомы, кто знает, чего стоят!… Так что «братания» языка логики с естественным языком не предвидится и в самой отдаленной перспективе, даже когда планета Земля начнет остывать…

Лекция 10. АКСИОМАТИЧЕСКИЕ ТЕОРИИ

Если алгебра логики и дает образец логического мышления, то уж очень специфический. Строгие логические рассуждения и близко от такого образца не лежали. Создавать (абсолютно) строгие логические (то есть абсолютно логичные) системы позволяет дедуктивный подход. Не путать с «дедуктивным методом» Шерлока Холмса. У Холмса, или скорее у Конан-Дойля, явно были проблемы с логикой, коль скоро он путал дедукцию с индукцией…
ДЕДУКТИВНЫЙ подход, называемый еще АКСИОМАТИЧЕСКИМ , это подход от общего к частному. От аксиом (постулатов) к теоремам (следствиям). Аксиоматическая теория строго задана, если строго сформулирован (задан) язык теории, ее аксиомы и правила вывода. Стоит хотя бы в одной из этих трех составляющих «дать слабину» и строгой теории как не бывало!
Знаменитая (одна из первых) аксиоматическая теория – геометрия Эвклида худо-бедно обеспечила строгость только в одном компоненте – в постулатах. Но язык, на котором проводятся доказательства в геометрии даже через тысячелетия, как и строгость самих доказательств не выдерживают критики. Это не более, чем неоднозначный метафорическо-аллегорический язык и правдоподобные рассуждения. Потому-то нередки случаи, когда опровергаются «доказанные» теоремы. Собственно, почти вся математика, за исключением сравнительно малюсенького раздела из логики аксиоматических систем, покоится (лучше звучит – зиждется) на правдоподобных рассуждениях и порядочности доказывающих.

Так что образцовая безупречно строгая теория задается на языке предикатных формул. (Мы здесь зареклись использовать формулы, поэтому остается полагаться на собственную честность).
Аксиомами об'являются некоторые из формул. В жизни мы также об'являем законами (аксиомами) не все фразы, которые можно ввернуть в той или иной ситуации, а лишь некоторые, которые мы решили считать таковыми… Законы (Аксиомы) это вопрос веры, а иногда целесообразности. Они недоказуемы! Если доказуемы, то это уже теоремы!

Существование Бога недоказуемо! Иначе это была бы теорема. А из каких, простите, более первичных понятий такую «теорему» выводить прикажете?!…

Закон всемирного тяготения недоказуем. Мы просто ему поверили, поскольку надоело проводить эксперименты по падению тел, в ожидании, когда с ними произойдет что-нибудь оригинальное.
Выводы в теории тоже следует формализовать, поскольку каждому в жизни встречались люди, которые «убедительно» доказывали какую-нибудь чушь.
Кстати, самое знаменитое правило вывода в математической логике ( modus ponens ) удручает своей очевидностью и даже примитивностью. Проиллюстрировать его можно так: Пусть в системе есть утверждения
" ЕСЛИ хорошая погода, ТО мы гуляем" и
«Хорошая погода» тогда в соответствии с modus ponens выводимо утверждение
«Мы гуляем»

При всей своей примитивности это правило вывода имеет решающее достоинство. Оно очевидно для всех. Очевиднее не бывает! А если в системе есть еще и утверждение:
" ЕСЛИ мы гуляем, ТО обязательно заблудимся" то с учетом ранее выведенного
«Мы гуляем» получим
«Обязательно заблудимся»
Видите, как далеко можно зайти маленькими очевидными шажками! Существует много и других правил вывода, но все имеют обязательное свойство – очевидность. Эта очевидность позволяет далее использовать эти правила абсолютно формально. То есть результат вычисляется. Такие символьные вычисления называются ИСЧИСЛЕНИЯМИ .
Есть еще один подход к аксиоматике, когда основной упор делается именно на правила вывода. Такие системы (почему-то) называются системами естественного вывода, намекая на то, что в них собраны базовые естественные правила логических рассуждений.

Логики резвились меж собой до тех пор, пока не был сформулирован подход к созданию аксиоматических систем под названием ПРИНЦИП (МЕТОД) РЕЗОЛЮЦИ . Он очень способствовал продвижению логики в широкие народные массы.
С одной стороны, активизировались работы по использованию компьютеров для реализации логического вывода и работы по искусственному интеллекту в частности. А с другой стороны, на этой основе был создан язык ПРОЛОГ .
Это совсем другое программирование, нежели традиционное процедурное. Это даже не программирование в обычном смысле слова, коль скоро здесь программист не пишет алгоритм решения задачи. Он описывает логические зависимости «мира», в котором существует задача. На основе описанной логики «мира» система (машина) сама создает алгоритм в процессе поиска решения!

Это только кажется, что аксиоматические системы – это сложно. Любой может напридумывать их сколько угодно. Более простым делом вам вряд ли приходилось заниматься.
Например, в качестве языка можно об'явить любые «слова» из последовательности буквы Я.
Букву Я об'явим аксиомой.
Правило вывода будет удваивать букву Я.
То есть сходу придумана теория, в которой выводимы любые последовательности (слова), состоящие из буквы Я.
Я ЯЯ ЯЯЯ… ЯЯЯЯЯЯЯЯЯЯЯЯЯЯЯЯЯЯЯЯЯЯЯЯЯЯЯЯЯЯЯЯ…
И все бы хорошо, только такая строго заданная теория мало что дает создателю, кроме радости созидания. Поэтому встает вопрос целесообразности, смысла. Той самой семантики… Здесь логики заняли очень( ! ) интересную позицию.
Коль скоро логика не интересуется смыслом высказываний, а лишь их истинностью, то ее (истинность) и об'явили смыслом высказываний. Вдумайтесь, смысл высказывания, например, «Газ при нагревании расширяется» не в том, что это отражение физического закона, а в том что оно истинно. Следовательно, точно такой же смысл( ! ) имеет высказывание «Никита Михалков – кинорежиссер». То есть его смысл в том, что оно тоже истинное.
Дальше – больше. Язык предикатов – это существенное расширение языка высказываний и обычным образом перебрать все случаи даже в простейшей ситуации, вроде «Икс любит кашу», не всегда возможно. Тем более, что речь может идти и о бесконечностях. Для решения проблем семантики в этом случае прибегают к теории моделей. Но это теория также, в конечном итоге, упирается в «смысл» типа истинно-ложно.

Возвращаясь к аксиоматическим теориям следует сказать, что в математике «практический смысл» имеют лишь такие теории, в которых можно выводить только истинные формулы. И нельзя ложные.
Одна ложная формула «уничтожает без остатка» любую аксиоматическую теорию.
Наша теория, созданная из буквы Я, не привязана к понятию истинности. Поэтому она бессмысленна, как бессистемная перестановка детских кубиков.
С кубиками все ясно. Но проблемы аксиоматических теорий на этом не исчерпываются. Пожалуй самым фундаментальным открытием в этой сфере следует считать доказанную Геделем ТЕОРЕМУ О НЕПОЛНОТЕ . Оказывается, в сколько-нибудь сложной аксиоматической системе (посложнее, чем кубики, но достаточно даже арифметики) существуют формулы, которые нельзя ни доказать, ни опровергнуть. Может в этом причина, что не все школьные задачки имеют решения?!
Так что, создавая свои аксиоматические теории помните, что они должны обладать какими-то полезными свойствами. А такие теории создавать уже не так-то просто. Хотя создать свою собственную математику может каждый!
Известно высказывание одного крупного математика: «Преимущество аксиоматизации – это преимущество воровства перед честным трудом».

Лекция 11. ТЕОРИЯ АЛГОРИТМОВ

Теория алгоритмов не учит «составлять» алгоритмы. Она занимается более важным вопросом. Основная задача классической теории алгоритмов – это ответ на вопрос: «Можно ли (вообще) для задач данного типа построить алгоритм?». Говоря более наукообразно: «Являются ли задачи данного типа алгоритмически разрешимыми»?
Это связано с тем, что, во-первых, не для всех задач возможно создать алгоритмы их решения. А, во-вторых, чтобы сделать математически строгий вывод о невозможности построить алгоритм, надо иметь строгое (формальное) определение самого алгоритма. Но понятие АЛГОРИТМА относится к фундаментальным неопределяемым понятиям. В вопросе об алгоритме у нас собачья позиция. Понимать понимаем, а сказать не можем. Если где-то встречаете «определение» алгоритма, то там, что ни слово – то аллегория…

Из этого тупика был найден нетривиальный выход. Понятие алгоритма заменили строго формализованными математическими моделями. Среди самых известных рекурсивные функции, машины Тьюринга и нормальные алгорифмы Маркова.
Эти математические модели выступают в роли «конкретизаций понятия алгоритма». То есть длительная практика подтверждает так называемый тезис Черча, который можно пересказать так:
Для любой алгоритмически разрешимой задачи можно построить рекурсивную функцию (машину Тьюринга, нормальный алгорифм Маркова). И наоборот, для задач, для которых нельзя построить перечисленные конкретизации, не существует алгоритма решения.

РЕКУРСИВНЫЕ ФУНКЦИИ основаны на той идее, что исходные данные и возможные результаты решения любой задачи можно пронумеровать. Для чего, естественно, достаточно множества натуральных чисел (целых положительных чисел, начиная с нуля). А далее базовыми об'являются функции, возможность выполнить (вычислить) которые не вызывает сомнений.
НУЛЬ– ФУНКЦИЯ – это функция, которая дает значение ноль для любого значения аргумента. Реализовать эту функцию может не только ребенок. Можно посадить попугая и подучить его на любой вопрос о значении функции кричать «Ноль!».
ФУНКЦИЯ СЛЕДОВАНИЯ дает следующее, по сравнению с аргументом, значение. Для пяти это шесть, для миллиона – миллион один. Можно бы было сказать, что здесь надо просто прибавлять 1.
Но операции сложения у нас пока нет!
ФУНКЦИЯ ВЫБОРА АРГУМЕНТА . Это вообще забавная даже для первоклассника функция, содержащая в своем имени номер аргумента. Если у вас есть несколько аргументов, то эта функция в качестве значения возьмет значение указанного в ней аргумента. Например, функция выбора третьего из Иванова, Петрова и Сидорова, которых мы ранее пронумеровали, например, как 22, 13 и 49, даст значение 49.
Эти три базовых функции могут использоваться далее в качестве исходного материала для создания более сложных функций с помощью трех операторов: суперпозиции, примитивной рекурсии и наименьшего корня.
Известный хорошо еще со школы ОПЕРАТОР СУПЕРПОЗИЦИИ позволяет вместо аргумента подставлять функцию… «Игла в яйце, а яйцо в ларце»…
Дольше словами описывать ОПЕРАТОР ПРИМИТИВНОЙ РЕКУРСИИ . Но если поднатужиться, то можно понять. Этот оператор позволяет построить новую функцию из двух функций, одна из которых имеет на один аргумент меньше, а другая на один аргумент больше.
Значение создаваемой функции для нулевого значения выбранного аргумента приравнивается к функции, не имеющей как раз этого аргумента. Значение же создаваемой функции для всех прочих
(ненулевых) значений выбранного аргумента приравнивается другой функции, зависящей (напрягитесь!) от тех же аргументов, кроме выбранного; от ПРЕДЫДУЩЕГО значения выбранного аргумента и от создаваемой функции от предыдущего значения выбранного аргумента.

Ну как тут не пожалеть о формулах.
Хотя, на самом-то деле мы со школы сталкиваемся с такого рода функциями, но, как тот герой, только на старости лет узнаем, что говорим прозой. Приведем построение с помощью рекурсии всем известной двухместной функции умножения икс на игрек (считая выбранной переменной игрек).
Функцию умножения икс на ноль можно выразить через нуль-функцию от икс, которая обеспечит нам желанное значение – ноль.
Функцию умножения икс на игрек (отличный от нуля) можно выразить через функцию сложения икса со значением функции умножения икса на предыдущее значение игрека… То есть мы выразили умножение через сложение.
Здесь следует сделать два замечания. Считаем, что к этому моменту доказана рекурсивность используемой здесь функция сложения. И второе, при умножении икс на игрек в нашем распоряжении функция от трех аргументов. Но, применив проектирующую функцию мы избавимся от среднего аргумента, коль скоро он нам здесь не нужен. Нам ведь дозволено заниматься подбором из возможного!
1 2 3 4 5 6 7 8