«М. Т. Омар Комлогия Утверждено Ученым советом университета Караганда 2009 УДК 16 ББК 87.4:32.973 О57 Рекомендовано Научно-техническим советом КарГТУ Рецензенты: Егоров В.В., профессор кафедры ОТД и МТО КарГУ им Е.А. ...»

МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РЕСПУБЛИКИ КАЗАХСТАН

КАРАГАНДИНСКИЙ ГОСУДАРСТВЕННЫЙ ТЕХНИЧЕСКИЙ УНИВЕРСИТЕТ

М. Т. Омар

Комлогия

Утверждено Ученым советом университета

Караганда 2009

УДК 16

ББК 87.4:32.973

О57

Рекомендовано Научно-техническим советом КарГТУ

Рецензенты:

Егоров В.В., профессор кафедры ОТД и МТО КарГУ им Е.А. Букетова, доктор педагогических наук.

Брейдо И.В., заведующий кафедрой АПП КарГТУ, профессор, доктор технических наук.

Халманов Х.Ж., профессор кафедры прикладной математики и информатики КарГУ им. Е.А. Букетова, доктор технических наук.

Омар М.Т.

О57 Комлогия: Монография/М.Т. Омар; Карагандинский государственный технический университет. - Караганда: Издательство КарГТУ, 2009. - 152 с.

ISBN 9965-04-262- Комлогия – логика, построенная на языке компьютера, определяется как третья стадия развития логики после первой философской и второй математической, наследующая задачи обеих своих предшественниц и позволяющая работать как с рассуждениями, так и с вычислениями. Комлогия начинается с языка, построения высказываний и непрерывного ввода понятий, которые представляются в виде определений, являющихся как замещающими, так и содержательными. В книге представлены введения в компьютерные теории: категорий, логики и групп. Построены структуры целочисленных логик. Изложена логика среды программирования Win32ForthIDE.

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

ББК 87.4:32. УДК © Омар Марс Танзилулы, ISBN 9965-04-262- © Карагандинский государственный технический университет,

ОГЛАВЛЕНИЕ

Я только следую тому, что открывают мне.

Коран Предисловие

Введение………………………………………………………………………… 1 Стрелки или введение в компьютерную теорию категорий

1.1 Воздействие………………………………………………………………… 1.2 Объект

1.3 Порядки действий

1.4 Интерактивная система программирования…………………………….. 1.5 Простейшая программа…………………………………………………... 1.6 Стрелочное представление программы…………………………………. 1.7 О стрелках в теории категорий……………………………

2 Язык или введение в семантику компьютерных систем

2.1 Слово

2.2 Выбор компьютерного языка

2.3 Отображения языков

2.4 Дедуктивное построение программы

2.5 Определение слов………………………………………………………… 2.5.1 Форма определения в математике…………………………………...... 2.5.2 Определение слова в машинных кодах

2.5.3 Определение через двоеточие

3 Функция или введение в синтаксические конструкции

3.1 Понятие функции

3.2 Непосредственные вычисления

3.3 Арифметические функции

3.4 Текстовые функции

3.5 Квантор счётного цикла

4 Высказывание или введение в компьютерную логику

4.1 Запись высказывания

4.2 Простейшие высказывания

4.3 Формулы

4.3.1 Синтаксис и семантика

4.3.2 Тавтология и противоречие

4.3.3 Условные выражения

4.3.4 Логические следствия

4.4 Правила вывода

4.4.1 Эквивалентные формулы………………………………………………. 4.4.2 Цепное правило

4.4.3 Правило резолюции

4.4.4 Modus ponens

4.5 Немного о предикатах

4.5.1 Понятие предиката

4.5.2 Флаги

4.5.3 Предикат-свойство

4.5.4 Предикат-отношение

4.5.5 Применение логических функций к предикатам

5 Целочисленная логика…………………………………………………….. 5.1 Выбор отрицания………………………………………………………… 5.1.1 NOT……………………………………………………………………... 5.1.2 Шаблон инвертирования………………………………………………. 5.2 Вложенные, перекрывающиеся и параллельные логики……………… 5.3 Троичная логика………………………………………………………….. 6 Элементы стековой комбинаторики………………………………………. 6.1 Стек данных………………………………………………………………. 6.2 Стековые операции………………………………………………………. 6.3 Примеры записи определений…………………………………………… 6.3.1 Арифметические операции…………………………………………….. 6.3.2 Битовые операции………………………………………………………. 6.3.3 Целочисленная булева алгебра………………………………………... 7 Введение в компьютерную теорию групп………………………………... 7.1 Перестановки и подстановки……………………………………………. 7.2 Разложение подстановок, циклы, транспозиции……………………….. 8 Логика среды программирования…………………………………………. Приложение 1………………………………………………………………... Приложение 2………………………………………………………………... Приложение 3………………………………………………………………... Приложение 4………………………………………………………………... СПИСОК ИСПОЛЬЗОВАННЫХ ИСТОЧНИКОВ……………………….. Предисловие В дореволюционной русской гимназии логика была обязательным предметом. В Советском Союзе логика была введена как школьный предмет в 1947г. и после 1953г. была отменена. Логика входит в цикл базовых дисциплин при подготовке философов, юристов и положена в основу образования при подготовке математиков и специалистов по информационным системам в Удмуртском государственном университете.

основополагающей дисциплиной при подготовке специалистов по информатике, вычислительной технике и программированию, информационным системам, математическому и компьютерному моделированию. Но здесь возникает сакраментальный вопрос, который очень остро поставлен А.С. Карпенко в работе “Предмет логики в свете основных тенденций ее развития” [Карпенко, 2006]. Приведём этот абзац полностью.

«На самом деле вопрос стоит глубже: насколько обучение логике помогает думать логически? Например, в работе [Nisbett, Fong, Lehman and Cheng, 1987] показано, что стандартный курс логики для аспирантов совершенно не эффективен. Более того, в работе [Wason, 1966] показано, какие чудовищные ошибки делаются при рассуждениях, использующих истинностные таблицы. Заметим, что истинностные таблицы представляют классическую логику высказываний. Этот эксперимент вызвал огромное число работ, проверяющих различные гипотезы относительно причин этих ошибок (см. [Manktelov and Over, 1990]). Еще менее удовлетворительным, отмечает Ходжес, является компьютерное обучение логике такими наиболее известными программами, как «Tarski’s World» и «Hyperproof».

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

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

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

Введение Комлогия – логика, построенная на языке компьютера. Исходные семантики и синтаксис компьютерного языка определяются командами процессора и, расширяясь, транслируются в языки программирования, используя архитектуру аппаратных средств, словари, операционные и поисковые системы.

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

Отличительные особенности комлогии по сравнению с её предшественницами:

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

2. Отсутствуют неявные предположения, хотя и могут быть спрятаны в применяемые определения и операции.

3. Всё проверяется и строго показанный результат соответствия реальности не требует содержательной перепроверки при применении.

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

5. Точность задаётся и не возникает проблем с её уточнением.

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

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

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

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

Математическая логика, которая также называется символической и теоретической, начинается с исчисления высказываний и ядром её является теория доказательств. Комлогия начинается с языка, определения и построения высказываний и непрерывного ввода понятий. Ядро комлогии – слово. Методы – дедуктивное построение и показательство.

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

1.1 Воздействие Самым важным понятием является понятие действия.

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

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

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

На экране монитора сигналы отображаются символами, картинками, словами, предложениями.

Вопросы для самопроверки 1. Что такое воздействие?

2. Как будет изображаться воздействие?

3. Дайте определение сигналу.

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

Окружающая среда воздействует на объект. Воздействие, оказываемое на объект из внешней по отношению к нему среды, показано стрелкой слева от объекта и названо «Вход». В теории систем компонентами входа является то, что обрабатывается объектом. В кибернетике воздействие, подаваемое на вход, называют входным воздействием.

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

В теории систем рисунок, изображающий объект, показывает процесс, который носит название «вход-выход», так как он переводит вход в выход.

Способность переводить данный вход в данный выход, называется свойством данного процесса.

взаимодействующих объектов более низкого уровня, образует систему.

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

Вопросы для самопроверки.

1. Как определяется объект в теории систем?

2. Что является компонентами входа объекта в теории систем?

3. Что называется выходом процесса в теории систем?

4. Чем обусловлено название «вход-выход» для процесса?

1.3 Порядки действий Информатика как самостоятельная наука сформировалась лишь в последние 50 лет, она в 10 раз моложе физики и в 100 раз – математики.

Сложить. Вычесть. Умножить. Разделить. Это всё то, что мы называем операциями. Являются вопросы: что с чем сложить, из чего что вычесть, что на что умножить, что на что разделить? Тогда нужно указать то, что мы называем операндами, то есть теми объектами, над которыми производятся названные бинарные операции. Если вначале указывается операция, а вслед за ней идут операнды, над которыми производится эта операция, то такой порядок действий называется префиксным (prefix). Но допустят ли, идущие вслед за операцией, операнды саму эту операцию на компьютере? Если речь идёт о целых числах, то может быть, вы вообще желаете записать число, выходящее за пределы разрядной сетки ячейки компьютера.

Десять сложить. Из десяти вычесть. Десять умножить. Десять разделить.

Итак, имеется один операнд, имеется операция. Требуется второй операнд.

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

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

Соответственно порядком действий различаются и представляющие их записи, как: префиксная, инфиксная и постфиксная.

В. П. Дьяконов [Дьяконов, 1992, с.15]: “Рассмотрим следующее выражение 3·(2+5).

Лишь многовековая привычка к такой алгебраической форме записи ведёт к тому, что её нелогичность не бросается в глаза явно. Однако стоит попытаться осмысленно прочитать эту строку, как нелогичность операции станет очевидна. Действительно начнём: введём число 3 и умножим его на… (тут выясняется, что мы не знаем, на что умножать и какие действия будут далее проведены). Придётся отложить это на потом и заняться выяснением того, что будет введено далее и т. д. На разгадку всех этих вопросов ЭВМ затрачивает время и аппаратные ресурсы.

С позиции логики лучше заранее иметь операнды, с которыми будут производиться операции, а затем уже указать сами операции. Например, так (знак умножения обозначим как *):

Тут вначале вычисляется 2 + 5 = 7, а затем результат умножается на 3”.

А.Н. Колмогоров [Колмогоров, 1988, c.250]: “Известно, что выражение «пять взять четыре раза» еще долго кажется детям более понятным, чем «пять умножить на четыре»”.

Вопросы для самопроверки 1. Определите порядки действий для унарных операций: x, SinX, lnx.

2. Определите порядки действий для бинарных операций: + 3 2, 3 + 2, 3 2 +.

1.4 Интерактивная система программирования На всякий звук свой отклик в воздухе пустом родишь ты вдруг.

Обозначив буквой S элементарную систему программирования, изобразим её в виде объекта:

Рисунок 1.2 - Элементарная система программирования На рис. 1.2. - “en”, взятое в угловые скобки в виде над входной стрелкой слева, не набирается, а показывает нажатие клавиши Enter; слово “ok” над выходной стрелкой справа сигнал о том, что нажатие клавиши Enter принято элементарной системой программирования, независимо от того набрали вы программу или нет, но если вы её набрали, то она должна быть правильной, иначе “ok” не выйдет. Если ваша программа принята, то она включается в систему программирования. Обозначив буквой P вашу программу, порядок подключения изобразим рисунком 1.3.

Рисунок 1.3 – Интерактивная система программирования Следовательно, согласно порядку подключения, вначале должно выйти слово "ok", означающее, что система программирования готова к приёму программы;

затем после набора программы P, посылаем сигнал, нажав клавишу Enter.

Если система программирования S принимает программу P, то на выходе системы S появляется ещё один сигнал "ok", который по обратной связи позволяет нам включать в систему новую программу. Под обратной связью понимается связь, направленная от выхода к входу.

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

Вопросы для самопроверки 1. Расшифруйте аббревиатуры и “ok”.

2. Что означает интерактивность?

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

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

Пока эти доказательства не даны, соответствующая теория попросту не существует как научная теория.

Программа – это последовательность указаний, определяющих порядок действий над данными, которые должны быть выполнены компьютером для получения результата. Рассмотрим простейшую программу: восемь на два разделить, результат вывести на экран монитора. Разложим эту простейшую программу на элементарные действия или инструкции: ввести восемь - 8, ввести два - 2, разделить /, вывести результат -.

(в последнем случае: набирается точка и нажимается клавиша Enter).

Если среда программирования принимает набранное, то после каждого ввода выйдет слово “ok”. Пронумеруем действия-инструкции и запишем их построчно:

Рисунок, изображающий объекты вместе со связывающими их стрелками, называется диаграммой. Последний рисунок – пример коммутативной диаграммы, в которой один путь, выходящий из a и через b приходящий в c, можно заменить путём, непосредственно ведущим из a в c. Коммутативность означает, что оба пути приводят к одному и тому же результату. Объекты, обозначенные буквами a, b и c, либо различные области, либо одна область с различными состояниями, в любом случае они отличаются друг от друга.

Знаком 1t обозначим стрелку, у которой выход равен входу и назовём её единичной или тождественной стрелкой. В указаниях её роль исполняет, ибо если ничего не набирая, нажмёте клавишу Enter, то при наличии на входе слова “ok”, на выходе также появляется слово “ok”. Начало и конец единичной стрелки находятся в одной области. Если вводить в рассмотрение единичные стрелки, то можно заметить, что композиция укрупняет указания.

Например, проводя композицию для указаний, приведённых на рис. 1.4, можно заметить, что единичная стрелка смещается слева направо. Указания, приведённые на рис. 1.4, обозначим: первое 8 через f 1t, второе 2 через g 1t и построим композицию fg 1t : 8 2, которая вместе с числами содержит и единичную стрелку. Пробел между числами необходим для того, чтобы поместить их в разные ячейки памяти. Следовательно, в этом примере композиция, убрав одну единичную стрелку, вводит пробел для различения чисел.

Рассмотрим теперь три стрелки:

Пусть связи между их областями определений и значений дают возможность построить стрелку, выходящую из a и входящую в d. Тогда на Затем, применив к стрелке fg стрелку h, построим композицию fgh, а применив стрелку f к стрелке gh, построим композицию fgh, что показано на нижеприведённом рисунке.

Указания простейшей программы, соответствующие композициям стрелок, следующие:

Композиция последовательно направленных указаний подчиняется ассоциативному закону: fgh = fgh Эти две композиции имеют одинаковые области определения (a) и области значений (d), одинаковые выходы для одинаковых входов. Ассоциативный закон позволяет опустить символ композиции и обозначить композицию просто посредством записи символов стрелок рядом: fgh. Тогда можно дать аксиоматическое определение построения программ, которое с точностью до перефразировок повторяет определение категории [Голдблатт, 1983, с.36-37], [Букур, Деляну, 1972, с.9], [О.Т. Марс, 1998].

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

Теория категорий в математике изучает свойства отношений между математическими объектами, не зависящие от внутренней структуры объектов.

Стандартным способом описания утверждений теории категорий являются коммутативные диаграммы. Коммутативная диаграмма — это ориентированный граф, в вершинах которого находятся объекты, а стрелками являются морфизмы или функторы, причём результат композиции стрелок не зависит от выбранного пути. Например, аксиомы теории категорий можно записать с помощью диаграмм. Морфизм категории – неопределяемое понятие, играющее роль отображения одной математической сущности в другую.

Функтор – отображение одной категории в другую, согласованное со структурой категории.

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

Вопросы для самопроверки 1. Что такое области: определений, значений и связь между ними?

2. Что означают «композиция», «коммутативность» и «ассоциативность»?

3. Постройте коммутативную диаграмму для четырёх стрелок.

4. Что означает функтор?

5. Дайте определение слову «программа».

6. Что такое указание?

7. Как понимать морфизм?

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

В связи с тем, что логика пронизывает любого рода деятельность и лежит в основе всех наук, то как фундаментальная и непрерывно развивающаяся наука она имеет много определений. Согласно одному из них, возникшему в недрах философской логики: «логика — это нормативная наука о формах и приемах интеллектуальной познавательной деятельности, осуществляемой с помощью языка» [Бочаров, Маркин, 2007]. “Когда мы называем язык инстинктивным самосознанием, инстинктивным мировоззрением и логикой, это означает, что язык является самосознанием, мировоззрением и логикой духа народа” (Г.Штейнталь). “Язык есть некая структура, по своей внутренней природе – форма мысли” (Э.Сепир). Мысль, в которой обобщаются отличительные свойства предмета, называется понятием.

По определению Н.Н. Непейводы: «Логика – наука, изучающая с формальной точки зрения понятия, методы их определения и преобразования, суждения о них и структуры доказательных рассуждений» [Непейвода, 1997].

Термину «понятие» в языке соответствует «слово». “Отношение понятия к слову сводится к следующему: слово есть средство образования понятия” (А.А. Потебня). Цитируется по [Налимов, 1979].

2.1 Слово Если вам иногда удаётся смотреть телевизор, тогда, возможно, вы видели фильм под названием «Терминатор». Там человек разговаривает с кибернетическим организмом на естественном языке. Человек не говорит ему:

«включи вторую извилину» или «подключи библиотеки из затылочной области», не начинает речь с открывающей фигурной скобки, “begin” или “void” и не заканчивает её через “end”, “return” или через закрывающую фигурную скобку.

Речь – это способность пользоваться языком слов, разделённых паузами.

– кодирование речи словами, разделёнными пробелами, позволяющее передавать её на расстояние и закреплять во времени.

«Как известно, слово является основным элементом языка. Слово обозначает вещи, слово выделяет признаки, действия, отношения. Слово объединяет объекты в известные системы, иначе говоря, кодирует наш опыт»

[Лурия, 1979, c.31]. Необходим язык, единственной конструкцией которого является слово.

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

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

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

В соответствии с принципом неокончательных решений, нужно выбирать тот язык, который обеспечивает наибольшую свободу выбора. Такой язык всегда имеет перспективу. Реально это означает, что язык должен иметь простое и компактное базовое ядро, которое можно расширять по мере необходимости. Принцип неокончательных решений предложен Д. Габором [Габор, 1972] и заключается в необходимости сохранения достаточной "свободы выбора" нескольких лучших решений на каждом шаге самоорганизации. Расширяемость должна позволять: на верхнем уровне – сколь угодно близкое приближение к естественному языку, в пределах тех ограничений, которые накладываются вычислительной системой, на нижнем уровне – максимально простое построение программного кода, обеспечивающее удобство выполнения команд процессора. Предельно упрощенной для транслятора является постфиксная форма записи, обеспечивающая максимальную простоту, используемых при компиляции правил. При построении компиляторов все выражения приходится переводить в постфиксную форму, применяя синтаксические распознаватели и семантические программы. Поэтому при изначальной записи в постфиксной форме, язык окажется удобным для создания проблемно-ориентированных языков программирования.

Уменьшить разрыв между задачей и процессом ее описания и решения возможно, если перейти к конструктивному программированию, снабдив программиста средствами самостоятельного ввода понятий, наглядно отображающими объекты и отношения исходной задачи, что значительно облегчит написание и ускорит отладку программ. Кроме того, замена методологии моделирования понятий задачи через универсальные, процессом непосредственного повышению надежности и удобочитаемости программ [Баранов С.Н., Ноздрунов Н.Р., 1988].

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

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

Резюмируем вышеизложенное требованиями к языку представления и программирования: это должен быть язык реального времени в смысле embedded computer real time systems, обеспечивающий полный доступ к техническим средствам, имеющий постфиксную форму записи и отличающийся надежностью, гибкостью, простотой, мобильностью, эффективностью и компактностью базового ядра.

Приведенным требованиям удовлетворяет язык 4th FORTH, являющийся стандартом Международного астрономического союза и используемый в США для решения широкого круга задач. Все компоненты языка, включая операционную систему, компилятор, интерпретаторы, текстовый редактор, виртуальную память, ассемблер и средства мультипрограммирования, могут следовать одному протоколу. Имея полный доступ к аппаратным средствам, язык может использовать средства ассемблера и функции операционной системы, что придает ему поразительную гибкость.

Из многочисленных высказываний специалистов о языке приведём лишь два. Майкл Хэм: 4th подобен Дао: это Путь, и осознается он, когда ему следуешь. Хрупкость его есть его сила; его простота есть его направление.

Д.С. Левин, А.И. Сенокосов: … это лучший язык программирования из тех, которые сейчас существуют. Человек, хотя бы раз прочувствовавший возможности Форта, сразу же с этим согласится и никогда в здравом уме и твердой памяти добровольно не вернется к другим языкам программирования.

В приложении 1 приведены сведения о применениях языка 4th Forth.

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

Схематически сказанное можно изобразить нижеприведённым рисунком.

Буквами A – E обозначены команды языка высокого уровня, определяемые на самом языке высокого уровня.

2.4 Дедуктивное построение программы Алфавит: ASCII – Американский стандартный код для обмена информацией - American Standard Code for Information Interchange, знаки которого называются символами (character).

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

Семантика:

Смысл может заключаться в исполнении какого-либо действия (состояние исполнения) или введении слова в словарь (состояние компиляции). Кроме того, по построению смысл имеет число. Следовательно, числа являются словами, определяющими своё собственное значение. В общем случае, слово, определяющее своё собственное значение, называется литералом. Числа – это всегда литералы. Отличительная особенность слова – исполнимость. Именно для этого оно и создаётся.

Синтаксис: Программа состоит из слов, разделённых пробелами:

1-е_СЛОВО 2-е_СЛОВО... N-e_СЛОВО При определении нового слова используется синтаксическая конструкция, которую предварительно обозначим знаком “|-“ и будем читать как ЕСЛИ... ТО...

1-е_СЛОВО 2-е_СЛОВО... M-e_СЛОВО |- НОВОЕ_СЛОВО, т.е. эта запись читается так: ЕСЛИ выполняется последовательность 1-е_СЛОВО НОВОЕ_СЛОВО, которое при своём исполнении вызывает указанную последовательность слов.

“Таким образом, наша система, основанная на знаниях, в качестве одного из компонентов должна включать память для хранения правил, которая содержит набор срабатывающих в определённых ситуациях правил, имеющих форму ЕСЛИ-ТО. Такие конструкции получили название продукционных правил” [К. Таунсенд, Д. Фохт, 1990, c.54-55.].

Исторически из практических соображений сложилось так, что многие слова, входящие в стандарт языка Forth, имеют минимальное количество символов. Например, вывод числа на экран производится словом. (dot точка), вывод числа без знака словом U. (u-dot -буква U [от слова – Unsigned] с точкой). Но их всегда можно переопределить.

Правило: при программировании не забывайте пробелы, отделяющие одно слово от другого.

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

Следовательно, семантическую дедуктивную систему.

2.5 Определение слов Определение – это логическая операция, назначение которой разнообразно. В философской логике достаточно подробно разработано понятие определения. Имеются и теории определения. Вначале нас будет интересовать синтаксическая сторона определения, как правила, «позволяющего производить взаимную замену одного выражения другим (Р.Карнап), соглашения об использовании языка (Х.Б. Карри) или правила перевода какого-то выражения с одного языка на другой (Л. Витгенштейн)»

[Корнел Попа, 1976, с.9].

2.5.1 Форма определения в математике Давая определение, следует заботиться о том, чтобы оно было во всех отношениях не только истинным, но и ясным.

Приведём пример определения в математике из книги «Математическая логика» Ю.Л. Ершова и Е.А. Палютина [Ершов, Палютин, 1987, c.25].

Определение. Секвенциями ИВ называются последовательности следующих четырех видов:

где Ф0, …, Фn, – формулы ИВ, n – натуральное число.

Разберём это определение. Вначале идёт слово Определение, набранное шрифтом, отличающимся от остального текста, затем собственно определение заканчивающееся абзацем, отделяющим его от последующего текста. Слово «Секвенция» от латинского “sequential”, что в переводе на русский язык означает «последовательность». «ИВ» - аббревиатура, ранее введённая как «Исчисление Высказываний». Также ранее введены символы Ф0, Фn,, которые в определении названы формулами. По умолчанию предполагается, что известны символы |-, n, точка, запятая, точка с запятой.

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

Аналогичное определение секвенции в книге Г. Такеути «Теория доказательств» [Такеути, 1978, с.15] излагается так, как приведено ниже.

Определение 1.8. Выражение вида, где и – произвольные конечные последовательности формул, называется секвенцией. При этом и называются соответственно антецедентом и сукцедентом этой секвенции, а каждая формула в последовательности или – секвенциальной формулой.

Далее идут пояснения о том, что означает секвенция интуитивно, что такое пустая секвенция и как в дальнейшем будут обозначаться секвенции.

2.5.2 Определение слова в машинных кодах Перейдём к определению слов в языке 4th Forth.

Прежде всего, необходимо выбрать среду программирования.

Предпочтение отдано интегрированной среде развития (Integrated Development Environment) IDE Win32Forth, выпущенной как Public Domain, из-за предоставляемого средой интерфейса.

Начнём с простейшего слова DUP (от duplicate), копирующего число в участок памяти, называемый стеком, для чего наберём в консоли Win32Forth:

где означает нажатие клавиши Enter, а SEE – видеть.

Увидим

DUP IS CODE

что слово DUP определяется через машинный код, записанный внизу в круглых скобках, и основу его составляет одна инструкция процессора – push (поместить в стек), применяемая к регистру ebx, в котором и находится вершина стека.

Работающая программа, определяющая слово DUP на ассемблере, показывается после набора в консоли слов

VIEW DUP

в виде

CODE DUP

где CODE - начало определения слова в машинных кодах;

c; - конец определения слова в машинных кодах;

next – текстовый интерпретатор для перехода к следующему слову.

Итак, чётко определяются начало и конец определения слова в машинных кодах. Теперь это слово применимо для работы на языке высокого уровня. В круглых скобках написан комментарий к определяемому слову: слева от стрелки то, чего требует слово для своего исполнения, справа от стрелки то, что выдаёт слово после выполнения. В данном примере комментарий показывает, что перед словом DUP должно быть написано конкретное число n и набор, к примеру, может выглядеть так Тогда на выходе будет n n, то есть 4 4.

После левого знака \ (back slash) идёт пояснение на естественном языке, говорящее о том, что дублируется значение на вершине стека данных.

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

2. 5.3 Определение через двоеточие Каждый язык принимает только те слова, которые ему понятны. Эти слова должны входить в словарь языка. Например, в словари всех развитых языков входят натуральные числа. Поэтому не возникает необходимости давать им отдельные определения: мы используем общепринятые знаки для их обозначений. Умножая два на два, мы уверены, что результат будет четыре, т.е.

в десятичной системе счисления Эта арифметика введена в язык программирования.

Теперь покажем справедливость слов Гёте (J.W.Goethe): “Дважды два это не четыре, а только дважды два, и то, что мы для краткости называем четыре.

Но четыре вообще не представляет собой ничего нового”.

Что мы сделали? В (2.2) слову 2 присвоили значение 7, тогда перемножение двух этих слов дало в результате 49 в (2.3).

Определение, данное в (2.2), не вербальное, а формальное. В нём начало определения отмечено двоеточием (colon), конец – точкой с запятой (semicolon). Эти слова, т.е. : (двоеточие) и ; (точка с запятой), в соответствии со стандартом ANS94 языка программирования Forth, входят в его ядро, их назначение: для двоеточия – начать определение; для точки с запятой – закончить определение. После сигнала о начале определения, т.е. двоеточия и следующего за ним пробела, набирается определяемое слово, заканчивающееся пробелом, после чего вводятся слова, определяющие последовательность действий, которое будет выполняться новым словом, и также разделённые пробелами, по схеме:

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

Если язык программирования принимает новое слово, т.е. включает его в словарь, выходит сигнал "ok".

Слово DUP, определённое в (2.1) в машинных кодах, можно определить через двоеточие следующим образом:

Пример:

3 Функция, или Введение в синтаксические конструкции 3.1 Понятие функции Говоря о некоторой функции, мы будем называть её функцией вещей или от вещей определённого рода, если все аргументы, к которым она применима, принадлежат к этому роду вещей.

Функция преобразует вход в выход, показывает связь между объектами и ставит в соответствие объекту на входе объект на выходе.

Рисунок 3.1 показывает, что применение к входу x функции f приводит к результату на выходе x f, которое обозначено через y. Функцию можно понимать, как правило, или операцию, применение которой к входным словамаргументам даёт соответствующие слова-значения на выходе.

3.2 Непосредственные вычисления Для вычислений используем следующие обозначения:

+ сложение; - вычитание; * умножение; / деление; MOD вычисление остатка;

/MOD вычисление остатка и частного.

Примеры. Ответы компьютера традиционно будем подчёркивать.

8 на 32 умножить, результат вывести на экран:

256 и 384 сложить, результат вывести на экран:

Из 640 128 вычесть, результат вывести на экран:

512 на 8 разделить, результат вывести на экран:

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

Считается, что такую запись впервые использовал польский математик Я. Лукашевич (Lukasiewicz). По сравнению с инфиксной записью, для постфиксной нотации требуется меньше места в памяти, кроме того, она также экономит и время компьютера.

Записи, приведённые в (3.1)-(3.4), можно заменить одним выражением:

Выполнив непрерывающуюся последовательность операций над операндами, мы получили тот же конечный результат, что и в (3.4). При такой записи промежуточные результаты не требуются. Эти режимы непосредственных вычислений (3.1)-(3.5) называются режимами стекового калькулятора. В интегрированной среде развития программ такого рода вычисления, как правило, проводятся в консоли.

Для записи функций в файл, нам потребуется правило записи в него.

Вопросы для самопроверки 2. Вычислите в уме 32 4 / 2 * -.

3.3 Арифметические функции Известно, что выражение «пять взять четыре раза» еще долго кажется детям более понятным, чем «пять умножить на четыре».

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

В (3.6)-(3.10):

слово : (colon - двоеточие) - начало определения функции;

слово ; (semicolon - точка с запятой) - окончание определения функции;

слова p, q, r, s - имена арифметических функций;

слово u - имя функции вывода на экран монитора.

После имён функций в круглых скобках записаны пояснения для стрелок.

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

В языке программирования пояснения называют комментариями.

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

В (3.10) переменная t перед стрелкой может пробегать значения от x до w.

После ввода функций (3.6)-(3.10) в программу проверим их выполнение:

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

Коммутативная диаграмма этих функций следующая:

Для проверки выполнения, необходимо добавить функцию вывода (3.10) и перед функциями (3.11)-(3.14) набрать числа, которыми в рассматриваемом примере являются: перед функцией (3.12) – слово “256”, а в остальных случаях - слово “8”.

Тождественную функцию определим так:

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

Для любых функций f ( a>b) и g ( b>c) выполнены равенства f1t = f и 1tg = g.

Вопросы для самопроверки.

1. Как записываются начало и конец определения функции?

2. Какова роль пробелов в языке программирования?

3. Что записывается в пояснениях слева и справа от стрелок?

4. Как записываются комментарии в языке программирования?

5. Сформулируйте закон тождества для композиции функций.

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

Начало текста обозначим словом точка-кавычка (dot-quote).”, окончание текста – кавычкой “ и наберём следующие функции:

Тогда РИЧАРД Ричард носит фамилию Томсон ok Этот пример построения в формальной логике, когда основное внимание обращается на форму в отвлечении от содержания, соответствует тому, что дан в книге А. Чёрча «Введение в математическую логику» [Чёрч, 1960, с. 15].

Просто записано это на языке программирования.

Истинность этого рассуждения подчиняется только форме, она не зависит от содержания, независимо от того истинны или ложны сами по себе исходные посылки и заключение. Слово.” (dot-quote - точка-кавычка), предназначенное для вывода текста на экран, поглощает весь текст до закрывающей кавычкиограничителя. Не забудьте, что все символы, не входящие в алфавит естественного языка, набираются при английской раскладке клавиатуры.

Теперь остановимся на примере, использованном для демонстрации метода резолюции в книге Ч. Чень, Р. Ли «Математическая логика и автоматическое доказательство теорем» [Чень, Ли, 1983, с. 95]:

"Посылка: Студенты суть граждане. Заключение: Голоса студентов суть голоса граждан". Запишем на языке программирования:

: СТУДЕНТЫ." Голоса студентов " ;

: ГРАЖДАНЕ." голоса граждан " ;

: ПОСЫЛКА СТУДЕНТЫ." суть " ГРАЖДАНЕ ;

Тогда ПОСЫЛКА Голоса студентов суть голоса граждан ok Тем самым показано, что заключение содержится в посылке.

Остановимся теперь на примере из применения исчисления предикатов к решению задач по книге Н. Нильсона «Искусственный интеллект» [Нильсон, 1973, с. 206]: "Если Майкл повсюду ходит за Джоном, а Джон находится в школе, то где Майкл?» Запишем на языке 4th:

: СЛЕДОВАНИЕ МАЙКЛ ДЖОН ;

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

Большие возможности при работе с текстом предоставляют векторные вычисления с использованием переменных и апострофов в определении слов [Броуди, 1990, с. 208-213]. Использование же бэктрекинга в языке полностью перекрывает возможности Пролога при работе с текстом [Гасаненко, 1993].

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

Вопросы для самопроверки 1. Запишите и выведите в виде текстовой функции начало песенки: В ЛЕСУ

РОДИЛАСЬ ЁЛОЧКА, В ЛЕСУ ОНА РОСЛА.

2. Запишите и выведите в виде текстовой функции начало припева гимна анархистов-махновцев: ЛЮБО, ЛЮБО, ЛЮБО, ЛЮБО БРАТЦЫ ЖИТЬ.

3. Постройте коммутативные диаграммы текстовых функций, приведённых 3.5 Квантор счётного цикла Квантор счётного цикла повторяет всё, что находится между словами DO … LOOP, т.е. выполняет цикл в соответствии с этими командами.

Например, если необходимо показать цифры, которыми нумеруются числа недели, то можно набрать:

В (3.15):

слово : (двоеточие) - начало определения;

слово NEDELYA - имя определяемого слова;

слово 8 - ограничение, предел, который не достигается при выполнении цикла;

слово 1 – индекс, определяющий первое число, при котором выполняется цикл;

слова DO (делать)... LOOP (цикл) – структура управления циклом;

слово I – текущее значение индекса, всего число значений - 7, ибо слово. (точка) – функция вывода числа на экран;

слово ; (точка с запятой) - конец определения.

Для пояснения структуры цикла, записав отдельно:

предел индекс DO I. LOOP, нарисуем её блок-схему Приращение Рисунок 3.3 - Блок-схема квантора счётного цикла В соответствии с блок-схемой первое значение индекса, пройдя через 1-й блок, сравнивается с пределом во 2-м блоке, при неравенстве по линии "Нет" переходит в 3-й блок для выполнения функции и, одновременно по обратной связи приращение в 4-м блоке добавляется в 1-м блоке к старому значению индекса, определяя текущее значение индекса. Последнее во 2-м блоке снова сравнивается с пределом, при неравенстве выполнение повторяется, при достижении равенства по стрелке "Да" выполнение цикла прекращается.

Последний индекс, равный пределу, для вычисления функции не используется.

Рассмотренная структура цикла читается как: выдать на экран все последовательные значения I, меняющиеся от 1 до 7.

Вопрос для самопроверки 1. Используйте циклы в текстовых функциях пункта 3.4.

4 Высказывание, или Введение в компьютерную логику А. Чёрч: “Предложение – это такое соединение слов, которое имеет самостоятельный смысл, т.е. выражает законченную мысль. Если мысль, выражаемая предложением, есть утверждение, то предложение называется повествовательным” [Чёрч,1960, с.29-30].

С. Клини: “Мы воспринимаем высказывания через выражающие их повествовательные предложения некоторого языка (предметного языка).

Высказывания суть смыслы этих предложений” [Клини, 1973, с.12].

Известны два метода построения исчисления высказываний, заложенные в силлогистике Аристотеля: аксиоматический метод и метод допущений. Методологическая структура аксиоматической системы проще методологической структуры систем, использующих допущения, хотя методы доказательств посредством допущений значительно проще методов доказательств в системах, построенных исключительно аксиоматическим методом [Слупецкий, Борковский, 1965, с.89]. Поэтому в аксиоматических системах содержательно используются методы построения доказательств посредством допущений.

Комлогия предлагает прямой метод построения исчисления высказываний на языке программирования (не путать с “прямым доказательством” в формальной логике).

4.1 Запись высказывания Высказывание может иметь вид последовательности слов и предложения языка программирования, включать в себя специальные символы, обозначающие операции, отношения.

Для представления двух чётко различающихся булевых значений, условно называемых «Истина» и «Ложь», используем ячейки памяти компьютера, в которые в двоичной системе счисления запишем для значения «Ложь» 0 (нуль), для значения «Истина» - 1 (единицу). Если ячейка 32разрядная, то столько нулей и столько же единиц необходимо записать, перейдя в двоичную систему счисления BINARY, а затем посмотреть, как это будет выглядеть в десятичной системе счисления DECIMAL.

BINARY 11111111111111111111111111111111 DECIMAL. -1 ok BINARY 00000000000000000000000000000000 DECIMAL. 0 ok Истина или ложь, определённая для какого-либо высказывания, называется истинностным значением этого высказывания. Набирая на компьютере, истину обозначают словом TRUE и тогда это в десятичной системе счисления –1 (минус единица), ложь словом FALSE или через 0.

Проверка:

Истинностные значения, в частности, широко используются в качестве признака, называемого флагом (flag). Флаг – это переменная, значение которой свидетельствует о том, что некоторый аппаратный или программный компонент находится в определённом состоянии или, что для него выполняется определённое условие. Мы ограничимся состояниями стека и используем обозначения: "ft", "ff" для обозначения слов «флаг истина» и «флаг ложь», а также “flags” для значений нескольких флагов.

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

Простые высказывания и соответственно символы, которые используются для их обозначения, называются атомами. Тогда P, Q, R атомы. Первое из этих высказываний, если вы читаете этот материал, истинное, третье ложно, второе ложно в десятичной системе счисления, но истинно в двоичной системе счисления. Истинностное значение второго высказывания в предложенной записи (4.2) не определено.

Работа с высказываниями на естественном языке в какой-либо предметной области требует словарей со словами этой предметной области.

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

4.2 Простейшие высказывания Из простых высказываний с помощью небольшого числа операций строятся так называемые сложные высказывания.

Из двух атомов P и Q можно построить новое высказывание, используя конструкцию P Q AND, которую называют конъюнкцией или логическим умножением высказываний P и Q. Результат применения функции AND (И) к атомам P и Q показывают в виде, так называемой, таблицы истинности:

Таблица 4.1- Таблица истинности конъюнкции

P Q P Q AND

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

конструкции FALSE AND, чтобы выход стал тоже ложным. Каждую строку таблицы 4.1 можно проверить. Например, вторую строку так а первую так Можно вычислить все истинностные значения логической операции в участке памяти, называемом стеком, содержимое которого выводится на экран словом.S (точка S), используя кванторы счётных циклов:

Тогда PQ&.S [4] -1 0 0 0 ok….

В выражении (4.4) I – индекс внутреннего цикла, J – индекс внешнего цикла, а в слове PQ& использован символ & (амперсанд), который в некоторых языках программирования используется для обозначения конъюнкции. Как мы уже знаем, ввод нового обозначения не вызывает Значение истинности высказывания P может быть изменено на противоположное значение использованием его отрицания: P NOT, когда P не выполняется. Таблица истинности для логической функции отрицания проста, ибо на входе имеется только один аргумент.

Таблица 4.2 - Таблица истинности отрицания Проверка на компьютере даёт:

В простых высказываниях (4.1)-(4.3), помеченных как атомы, логические функции не встречаются. Логические функции, называемые в математике связками, используются в составных высказываниях.

Используя конъюнкцию и отрицание, составим следующее высказывание:

что равносильно скобочной записи Построенное высказывание называется дизъюнкцией или логическим сложением, входящих в него высказываний. Вместо записи (4.5), используют сокращённую запись P Q OR, где OR (ИЛИ) есть логическая функция дизъюнкции.

Таблица истинности дизъюнкции, построенная на основании (4.5), имеет вид Таблица 4.3 - Таблица истинности дизъюнкции

P Q P Q OR

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

конструкции TRUE OR, чтобы выход стал тоже истинным. Каждую строку таблицы 4.3 можно проверить. Например, четвёртую строку так а третью так Используя кванторы счётных циклов, поместим в память истинностные значения дизъюнкции двух высказываний P, Q и выведем их на экран монитора PQ|.S [4] -1 -1 -1 0 ok….

Вертикальная черта “|” используется в некоторых языках программирования для обозначения дизъюнкции:

Используя дизъюнкцию и отрицание, построим следующее высказывание:

или в скобочной записи Построенное высказывание называется импликацией или односторонним условием, имеет обозначение -> и как результат применения этой функции для высказываний P, Q в постфиксной нотации записывается в виде P Q ->, что соответствует алгебраической записи P -> Q, а последнее отождествляют с выражением «если P, то Q», т.е. Q следует за P. Таблица истинности импликации, построенная на основании (4.7), имеет вид Таблица 4.4 - Таблица истинности импликации Если при истинном первом высказывании второе высказывание ложно, только тогда условие не выполняется и импликация двух высказываний становится ложной, ибо, если Q следует за P, то истинность P и ложность Q не могут быть истиной; в остальных случаях импликация двух высказываний - истина.

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

Используя кванторы счётных циклов, поместим в участок памяти, именуемый стеком, истинностные значения импликации двух высказываний Затем, PQ->.S [4] -1 -1 0 -1 ok….

Построим теперь следующее составное высказывание:

или в скобочной записи Построенное высказывание получает значение истины, если аргументы имеют противоположные истинностные значения и называется XOR (eXlusive OR- исключающее ИЛИ) или сложение по модулю два двух высказываний P,Q. Таблица истинности этих высказываний, полученная в соответствии с (4.9), имеет вид Таблица 4.5 - Таблица истинности исключающего ИЛИ

P Q P Q XOR

Применение функции XOR к двум высказываниям дает значение истины, если либо только первое, либо только второе высказывания имеют значения истины, но не оба одновременно. В некоторых языках программирования операция исключающего ИЛИ обозначается символом верхнего угла ^:

Любая строка таблицы истинности (4.5) может быть проверена. Например, вторая так:

Используя циклы, занесём истинностные значения в память:

и выведем их на экран монитора PQ^.... 0 –1 –1 0 ok Используя импликацию и конъюнкцию, построим следующее высказывание:

или в скобочной записи Оно называется двусторонним условием или эквивалентностью и отождествляется с выражением: “P тогда и только тогда, когда Q”. Для обозначения эквивалентности двух высказываний будем использовать цепочки вида P Q или в алгебраической записи P Q, которое трактуют как: “P – необходимое и достаточное условие для Q”.

Таблица истинности эквивалентности двух высказываний может быть построена по выражению 4.10 в следующем виде Таблица 4.6 - Таблица истинности эквивалентности Сравнение этой таблицы с операцией «исключающее ИЛИ», даёт возможность определить эквивалентность как отрицание XOR:

Как и ранее, каждую строку таблицы истинности эквивалентности можно проверить. Например, первую:

Вывод истинностных значений в цикле таков же, как и ранее:

4.3 Формулы 4.3.1 Синтаксис и семантика Атомы и логические функции дают возможность построения новых составных высказываний. Отдельные и составные высказывания называют правильно построенными формулами. Правильно построенная формула (ППФ) определяется так:

1. Атом - формула.

2. Если F – формула, то и её отрицание F NOT - формула.

3. Если F и G - формулы, то F G &, F G |, F G ->, F G, F G ^ - формулы.

4. Формула строится только вышеприведёнными правилами.

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

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

1-й пример. Пусть P и Q – два атома с истинностными значениями, соответственно 0 и -1. Тогда можно найти истинностные значения P NOT, P Q &, P Q |, P Q ->, P Q ^, P Q. Они соответственно:

-1, 0, -1, -1, -1, 0.

Значение истинности любой формулы зависит от структуры этой формулы и от значений истинности составляющих её высказываний.

Для краткости записи временно обозначим отрицание тильдой ~:

2-й пример. Рассмотрим формулу: F = P Q & S ~ R ->. Пусть атомы P, Q, R, S, входящие в формулу, имеют соответствующие истинностные значения 0, -1, 0, -1. Тогда:

и формула F оказалась истинной при назначенных истинностных значениях её атомов. Назначение атомам P, Q, R, S формулы F истинностных значений 0, -1, 0, -1 называется интерпретацией формулы F. Так как каждому из атомов P, Q, R, S можно приписать два значения, то формула F имеет интерпретаций. В общем случае, если некоторая формула состоит из n различных атомов, то у неё имеется 2n различных интерпретаций.

Существует формальное определение интерпретации правильно построенной формулы: пусть F формула высказываний, а A1, A2,..., An – её атомы. Тогда интерпретацией формулы F называется назначение каждому из её атомов A1, A2,..., An истинностного значения, т.е. в наших обозначениях либо -1, либо 0.

Будем говорить, что формула F истинна при интерпретации I, тогда и только тогда, когда F имеет значение –1 в этой интерпретации; если формула F получает значение 0 в интерпретации I, то формула F ложная при интерпретации I.

При записи бывает удобно представить интерпретацию списком, в который входят атомы и их отрицания, например запись {P, Q~, R, S~} будет означать, что атомам P и R приписаны значения «истина», т.е. –1, а Q и S приписаны значения «ложь», т.е. 0.

4.3.2 Тавтология и противоречие Рассмотрим формулы истинные при всех интерпретациях и формулы ложные при всех интерпретациях.

1-й пример. Рассмотрим формулу: F = P Q -> P & Q -> или в алгебраической записи F = ((P->Q)&P)->Q. У этой формулы два атома - P и Q.

Поэтому у формулы четыре интерпретации. Вычислим истинностные значения формулы F при всех этих четырёх интерпретациях:

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

2-й пример. Рассмотрим формулу: G = P Q ~ & P Q -> & или в алгебраической записи (P&Q~)&(P->Q). Построчный вывод на экран монитора истинностных значений формулы G следующий:

Занесём истинностные значения формулы G в память, используя кванторы счётных циклов:

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

Существуют определения для тавтологии и противоречия.

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

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

Из приведённых определений логично следует, что:

1. Если отрицание формулы невыполнимо, тогда и только тогда формула является тавтологией.

2. Если отрицание формулы является тавтологией, тогда и только тогда формула невыполнима.

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

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

5. Тавтологичная формула непротиворечива. Обратного сказать не можем.

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

3-й пример. Нетрудно проверить следующие выражения:

P P ~ & противоречие, поэтому необщезначимо;

Q Q ~ | тавтология, поэтому непротиворечива;

R R ~ -> необщезначима, но непротиворечива. Проверим последнее:

Если при интерпретации I формула F истинна, то говорят, что F выполнима в интерпретации I, или I удовлетворяет F. Если при интерпретации I формула F даёт ложь, то говорят, что F опровергается в интерпретации I или I опровергает F. Например, формула P Q ~ &, или в алгебраической записи (P & Q~), выполняется в интерпретации {P, Q~}, но опровергается в интерпретации {P, Q}.

В том случае, если интерпретация I удовлетворяет формулу F, то говорят также, что I является моделью формулы F.

4.3.3 Условные выражения Дюжина – это двенадцать однородных предметов. На языке программирования проверку на соответствие дюжине можно записать следующим образом:

Написав число перед определённым словом, набираем само слово следующим образом:

Здесь проверяется, равно ли число 12, если равно, выходит сообщение “Да”.

Слово “=” проверяет равенство значений двух чисел: того, что записано в выражении, и того, что вводится перед словом. Если условие, записанное перед IF, выполняется, то управление передаётся к тексту, непосредственно следующему за IF, если не выполняется, то управление выходит за пределы THEN. Конструкция управления выглядит так:

(условие) IF (выполнение) THEN (продолжение).

При проверке выполнения условия используется понятие «флаг».

Флаг – это логическая переменная, принимающая значение «истина», если условие выполняется, и значение «ложь», если условие не выполняется.

Значение флага направляется в память. Проверьте:

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

Введём теперь отрицание:

Используя отрицание, можно изменить условие IF на обратное условие, например:

Проверка:

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

Затем проверяем:

Знак вопроса перед стрелкой в комментарии означает, что на входе должен вводиться флаг.

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

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

P: Производительность труда низкая.

Q: Производство неконкурентоспособно.

R: Зарплата не выплачивается.

В рассматриваемом примере четыре утверждения:

1. P Q -> - Если производительность труда низкая, то производство неконкурентоспособно.

2. Q R -> - Если производство неконкурентоспособно, то зарплата не выплачивается.

3. P - Производительность труда низкая.

4. R - Зарплата не выплачивается.

Нужно показать, что если 1-е, 2-е, 3-е утверждения истинны, то истинно и 4-е утверждение. Запишем высказывания на языке программирования.

Q." Производство неконкурентоспособно. " ;

Выводим следствие:

СЛЕДСТВИЕ

Производительность труда низкая. Зарплата не выплачивается ok Таким образом, последовательности IF... THEN строят конъюнкции из предшествующих IF элементов.

Если высказывание R является логическим следствием утверждений P Q ->, Q R -> и P, то в логике это обозначается так: P Q ->, Q R ->, P |- R.

Логическому следствию даётся следующее определение:

Пусть вместе с формулами A1, A2,..., An дана и формула B. Формула B будет логическим следствием формул A1, A2,..., An тогда и только тогда, когда в каждой интерпретации I, в которой конъюнкция A1 A2 &...& An & истинна, истинна и формула B.

A1, A2,..., An называют аксиомами (постулатами или посылками) B.

Теорема 4.1. Пусть вместе с формулами A1, A2,..., An дана и формула B.

Тогда формула B является логическим следствием формул A1, A2,..., An, тогда и только тогда, когда конструкция A1 A2 &... & An & B -> тавтологична.

Доказательство можно провести, вспомнив, что тавтологичность означает истинность формулы при всех интерпретациях, как это и проведено в книге Чень Ч., Ли Р. Математическая логика и автоматическое доказательство теорем [Чень, Ли, 1983, с.26].

Теорема 4.2. Пусть вместе с формулами A1, A2,..., An дана и формула B.

Тогда формула B является логическим следствием формул A1, A2,..., An, тогда и только тогда, когда конструкция A1 A2 &... & An & B ~ -> противоречива.

Доказательство там же [Чень, Ли, 1983, с.26].

Если формула B является логическим следствием формул A1, A2,..., An, тогда конструкцию A1 A2 &... & An & B -> называют теоремой, а B – заключением теоремы. В общем случае, теорема – это утверждение, истинность которого установлена путём доказательства.

Дадим пример вывода логического следствия.

2-й пример. Рассмотрим следующие формулы:

Нужно показать, что формула B есть логическое следствие формул A1, A2. Для этого покажем тавтологичность формулы P Q -> P & Q ->.

Показательство:

: PQ->P&Q-> PQ->P&Q-> -1 -1 -1 -1 ok Нетрудно показать и противоречивость формулы P Q -> P & Q ~ &.

4.4 Правила вывода называемых заключением В.п., по множеству объектов, 4.4.1 Эквивалентные формулы Формулы A и B эквивалентны или формула B эквивалентна формуле A (обозначается A = B), тогда и только тогда, когда во всех интерпретациях формул A и B их истинностные значения совпадают.

Для преобразования формул необходим достаточный запас эквивалентных формул. Мы договорились: всегда истинную формулу обозначать через -1, всегда ложную через 0. Классифицируем несколько эквивалентных формул, обозначив их буквами A, B, C. Некоторые формулы называют законами. Эквивалентные формулы приведены в двух формах: слева в постфиксной форме, справа – в инфиксной форме, взятой в круглые скобки.

При построении эквивалентности "тогда и только тогда" мы использовали следующее преобразование:

Преобразование, использованное при построении импликации, называется законом контрапозиции:

Далее существуют (Z.3) Законы коммутативности:

(Z.4) Законы ассоциативности:

(Z.5) Законы дистрибутивности:

a) Дизъюнкции относительно конъюнкции b) Конъюнкции относительно дизъюнкции (Z.6) Свойства констант:

(Z.7) Закон исключённого третьего:

(Z.8) Закон противоречия:

(Z.9) Закон инволюции (возврата, двойного отрицания):

(Z.10) Законы де Моргана 4.4.2 Цепное правило Правила вывода используются для вывода истинных предложений из других истинных предложений. Если исходные предложения истинны, то считается, что использование правил вывода не даёт возможности вместе доказать как истинность, так и одновременно ложность какого-либо предложения. Если таковая возможность не исключается, то исходные предложения противоречивы и выводимое из них предложение всегда и истинно, и ложно, т.е. от дедуктивной системы пользы не просматривается.

Два классических правил вывода известны с древности. Действие одного из них: из двух заданных импликаций вывести новую импликацию. Это можно записать так: если A B -> истинно и B C -> истинно, то выводится A C ->, или вербально: если из A следует B, а из B следует C, то из A следует C. Это правило называют цепным, ибо осуществляется переход по цепи от A к B и от B к C.

Цепное правило в алгебраической записи выглядит так:

((A->B)&(B->C))->(A->C).

интерпретации дают истинностные значения. Для трёх логических переменных имеется восемь интерпретаций.

Выведем их для формулы:

F = A B -> B C -> & или в алгебраической записи F = (A->B)&(B->C):

LOOP LOOP LOOP ;

Следовательно, из восьми интерпретаций формулы F = AB->BC->& четыре являются её моделями. Возьмём их за основу при построении таблицы истинности:

Таблица 4.7 - Таблица истинности цепного правила Итак, существуют четыре интерпретации, при которых формула F = A B -> B C -> & истинна, во всех них формула A C -> также истинна, следовательно, по определению логического следствия формула A C -> является логическим следствием формул A B -> и B C ->.

Используем теперь теорему 4.1, для чего построим конструкцию цепного правила или в инфиксной форме и наберём

LOOP LOOP LOOP ;

Таким образом, показана истинность формулы Q при всех интерпретациях, т.е.

тавтология, что подтверждает истинность цепного правила.

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

((A~->B)&(B->C))->(A~->C), т.е. если A~ -> B истинно и B -> C истинно, то можно вывести A~ -> C. Таблица истинности для 2-й формы цепного правила будет выглядеть следующим образом:

Таблица 4.8 - Таблица истинности 2-й формы цепного правила Следовательно, A ~ C -> логическое следствие A ~ B -> и B C ->:

или в инфиксной форме:

Используя закон контрапозиции (Z.2), проведём обратное преобразование для каждой части выражений в (4.13) по отдельности:

или в инфиксной форме 2-я форма цепного правила в виде (4.14) носит название правила резолюции.

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

Цепное правило называют вторым законом гипотетического силлогизма.

4.4.4 Modus ponens В качестве единственного правила вывода, называемого modus ponens, или правилом отделения, мы принимаем процедуру перехода от двух формул вида A и A->B к одной формуле B, каковы бы ни были формулы A и B.

Второе издревле известное правило вывода носит название: modus ponens - сокращение посылки. Это правило можно записать так: если B истинно и B C -> истинно, то можно вывести C. Следовательно, из двух заданных предложений выводим третье предложение:

или в инфиксной записи Используя закон контрапозиции, преобразуем левую часть выражения (4.15) в эквивалентную форму:

или в инфиксной записи Сравнивая (4.15) и (4.16) с формами цепного правила (4.12)-(4.14), можно сказать следующее: правило modus ponens представляет собой цепное правило без A (точнее нуль, что означает ложь). Можно показать, что у правила modus ponens существует только одна модель для формулы когда истинными являются и B, и C.

Следовательно, изначально закладывается истинность того, что доказывается.

Для проверки истинности правила modus ponens построим конструкцию и проверим На правиле modus ponens основаны многие математические доказательства.

В приложении 2 даны программы проверок формул, общезначимых в немодальном пропозициональном исчислении по Р. Фейсу [Фейс, 1974].

Немного о предикатах 4. Предикат – функция, значениями которой являются высказывания об n-ках объектов, представляющих значения аргументов.

4.5.1 Понятие предиката Исчисление высказываний не позволяет проверить многие предложения, связанные с внутренней структурой естественных языков, ибо простые высказывания рассматриваются, как атомы, т.е. неделимые объекты, способные принимать лишь два истинностных значения. Логика предикатов призвана учитывать некоторые свойства и отношения объектов. Понятия «свойство» и «отношение» входят в общее понятие предиката. Предикат [lat.praedicatum] – логическое сказуемое с точки зрения грамматики.

Пример. Рассмотрим предложения: Студент учится; Анна студент;

следовательно - Анна учится. Первое предложение определяет, что студент имеет свойство учиться. Запишем это У предложения "Анна студент" первый член - имя конкретного студента, которое определим так:

Затем общая форма предложения:

Проверяем:

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

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

Например, когда в выражении "x студент", вместо x мы ставим имя конкретного студента, то это истинное высказывание, а если нечто другое, то это ложное высказывание.

Функция (x1,...,xn)P, содержащая n переменных, определенных на заданных областях, которая становится высказыванием, свойством или отношением при подстановке значений вместо этих переменных, называется n-местным предикатом. При n = 0 предикат называется высказыванием, при n = 1 - свойством, при n >= 2 -отношением. Тогда высказывание нульместный предикат, свойство - одноместный предикат, отношение – n-местный предикат.

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

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

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

"f", "f1", "f2" соответственно вместо слов «флаг», «первый флаг», «второй флаг», а также "ft", "ff" для обозначения слов «флаг истина» и «флаг ложь».

Таблица 4.9 – Таблица флагов логических функций высказываний OR ( f1 f2 -> f ) f: ft, если f1 или f2, или оба вместе истинны.

NOT ( f -> f ~ ) изменяет значение флага f на противоположное.

XOR ( f1 f2 -> f ) f: ft, если значения f1 и f2 противоположны.

-> (f1 f2 -> f ) f: ft, за исключением случая, Таблица 4.10 - Таблица флагов предикат-свойств Таблица 4.11 - Таблица флагов предикат-отношений Связи между свойствами и отношениями можно выразить следующими определениями:

Предикаты часто применяются в условных выражениях, определяемых конструкциями IF...THEN и IF...ELSE...THEN, когда условие формирует значение флага:

Эти конструкции применяются только внутри определений. Расширим пример (4.11) из пункта 4.3. Затем проверяем:

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

* Слово SWAP (обменять) будет пояснено позже на стр. 64.

4.5.3 Предикат-свойство высказывания является лишь его значение истинности и или л.

Примеры унарных (одноместных) предикатов приведены в таблице 4.10.

Рассмотрим пример. Пусть пропозициональная форма (форма предложения) – предикат, определённый в области целых чисел, будет таков: "x – нулю не равно", тогда, подставляя вместо x какое-либо целое число, получаем либо истинное, либо ложное высказывание. Такую форму высказывания "x – нулю не равно" логика предикатов и отождествляет с понятием свойства «не быть равным нулю», определённым в области целых чисел. Здесь свойство функция, область определения которой целые числа, а область значений – истина или ложь. Эту функцию, характеризующую не равные нулю целые числа, запишем как предикат (x)0. Табличная запись функции, называемая матрицей предиката, следующая:

Подставляя вместо x какое-либо целое число, не выходящее за пределы разрядной сетки компьютера, выводим истинностное значение предиката.

Проверка проста:

Можно ввести более развёрнутое определение : (x)0 0 IF." Истина " Аналогичную интерпретацию можно дать и остальным предикат-свойствам таблицы 4.10.

4.5.4 Предикат-отношение Я чувствую, что в этом отношении я ещё свеж и непорочен.

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

Примеры бинарных предикатов приведены в таблице 4.11. Проверим равенство двух чисел:

4 3 (x,y)РАВНО Ложь ok или 4 3 =. 0 ok В натуральных числах матрица предиката (x,y)РАВНО следующая:

т.е. на главной диагонали отношение истинно, в остальных местах ложно.

Операции сравнения двух значений, приведённые в таблице 4.11, называются реляционными операциями.

4.5.5 Применение логических функций к предикатам Применение логических функций к предикатам (x)P и (x)Q позволяет определить их отрицания (x)P ~, (x)Q ~; конъюнкцию (x)P (x)Q &;

дизъюнкцию (x)P (x)Q |; импликацию (x)P (x)Q ->; сложение по модулю два (x)P (x)Q ^; эквивалентность (x)P (x)Q. Примеры:

Целочисленные логики Эта «Логика» не похожа ни на одну из логик, созданных до сих пор.

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

5.1 Выбор отрицания 5.1.1 NOT Отсюда общеутвердительные и частноотрицательные Слово NOT можно проверить следующим образом:

SEE NOT

Тогда выйдет: : NOT 0= ;

Всё, что не равно нулю, в результате действия оператора даст нуль, т.е.

А теперь проверьте следующее:

DECIMAL 0 NOT. -1 ok Следовательно, любое ненулевое значение слово NOT воспринимает как истинное, и только нуль как ложь. Отчётливое свойство бинарности.

5.1.2 Шаблон инвертирования Для работы в двоичной системе счисления необходимо ввести слово BINARY. Теперь, попытка ввести цифру больше 1, будет отвергаться как не имеющая смысла в двоичной системе счисления.

Представим себе, что имеется двоичное число 10101010 и вы хотите изменить четвёртый справа разряд в "0", т.е. вы хотите превратить это число в 10100010. Используем для этого операцию логического умножения AND.

Операция AND сравнивает поразрядно два числа, и если в обоих из них эти разряды установлены в "1", то результат будет 1, иначе будет 0. Введите следующие предложения:

В обоих случаях вы увидите одинаковый результат: 10100010 ok Вторые числа называются разрядными (битовыми) масками. Разрядная маска это двоичное число, которое сравнивается с другим двоичным числом для изменения значений отдельных битов. Разрядные маски (бит-маски) часто используются для изменения битов в памяти.

Предположим теперь, что необходимо изменить значение бита, находящегося в каком-либо разряде, переведя его из 0 в 1. Логическая функция AND не сможет этого сделать, но можно использовать операцию логического сложения OR. Она также производит поразрядное сравнение двух двоичных чисел, но если хотя бы один из разрядов установлен в "1", то в результате тоже будет "1". Попробуем установить в "1" третий разряд в рассмотренном примере.

Для этого используем маску 00000100 или 10101100 и т.д.:

BINARY 10101010 00000100 OR U. 10101110 ok 10101010 10101100 OR U. 10101110 ok 10101010 10101110 OR U. 10101110 ok Более универсальной для создания маски является логическая функция исключающего ИЛИ – XOR, ибо если два разряда различны, то в бите результата устанавливается "1", если одинаковы, то - "0". Например:

BINARY 01010101 10101010 XOR U. 11111111 ok 01010101 01010101 XOR U. 0 ok Использование логической функции XOR с операндом, все биты которого равны единице, приводит к инвертированию битов второго операнда.

BINARY 11111111 01010101 XOR U. 10101010 ok Таким образом, выражение -1 XOR является двоичной маской или шаблоном инвертирования, ибо -1 U. 11111111111111111111111111111111 ok Это выражение и используем для определения отрицания:

5.2 Вложенные, перекрывающиеся и параллельные логики Далее, используются конструкции языка программирования для логических операций конъюнкции AND, дизъюнкции OR, сложения по модулю два XOR. Определим функции:

Напишем простейшую программу вывода на экран матрицы 20х целых чисел при входных данных, изменяющихся в диапазоне от –10 до 9.

:.XOR ( -> ) 10 -10 DO 10 -10 DO I J XOR LOOP LOOP где вместо XOR может быть записана любая другая логическая функция.

Аналогично записывается простая программа вывода чётных и нечётных чисел:

:.XORCN ( -> ) 11 -9 DO 10 -10 DO I J XOR 2 +LOOP Результаты обработки сведём в таблицы.

Таблица 5.1 – Таблица истинности для положительных и В таблице 5.1 0, т.е. целые неотрицательные числа;

Таблица 5.2 – Таблица истинности для чётных и нечётных чисел

Ч Ч Ч Ч Н Ч Н

Ч Н Ч Н Н Н Ч

Н Ч Ч Н Ч Н Ч

Н Н Н Н Н Ч Н

В таблице 5.2: Ч – чётные числа; Н – нечётные числа.

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

Конъюнкция. Если один из аргументов -1, то значение функции повторяет значение второго аргумента. Функция принимает значение -1 в единственном случае, когда оба аргумента имеют значение –1. Функция даёт в тех случаях: когда один из аргументов 0; если сумма двух аргументов –1; если сумма двух чётных чисел на входах –2; когда при чётном числе на одном из входов, на втором 1. Функция даёт 1 в тех случаях: когда сумма двух нечётных чисел на входах 0; когда при нечётном числе на одном из входов, на втором 1.

Часть сказанного продемонстрируем стрелочной нотацией:

и изобразим в виде структур вложенных и перекрывающихся конъюнкций.

Рисунок 5.1 - Структуры вложенных при n = 1, 2, 3, … конъюнкций, перекрывающихся в нуле: a) для целых чисел; b) начальный участок от нуля ;

c) по степеням числа Дизъюнкция. Если один из аргументов 0, то значение функции повторяет значение второго аргумента. Функция принимает значение 0 в единственном случае, когда оба аргумента имеют значение 0. Функция даёт -1 в случаях: когда один из аргументов –1; если сумма двух аргументов -1; когда сумма двух нечётных чисел на входе 0. Функция даёт –2 в случаях: когда сумма двух чётных чисел на входе –2; когда при чётном числе на одном из входов, на втором -2.

Часть сказанного демонстрируется стрелочной нотацией:

и изображается структурами вложенных и перекрывающихся дизъюнкций.

Рисунок 5.2 - Структуры вложенных при n = 1, 2, 3, … дизъюнкций, перекрывающихся в нуле: a) для целых чисел; b) начальный участок от нуля ;

c) по степеням числа Исключающее ИЛИ. Функция даёт ложь при равных операндах и истину, если сумма двух операндов -1. Если один из операндов 0, то функция повторяет значения второго операнда. Если один из операндов –1, то функция совпадает с функцией отрицания. Равные, но противоположные по знаку, значения только чётных или только нечётных чисел в одинаковых интервалах изменения входных величин, приводят к значению –2 на выходе. Равные, но противоположные по знаку, значения чётных и нечётных чисел в одинаковых интервалах изменения входных величин, приводят к значению -1 на выходе.

Стрелочная нотация для простейших случаев:

и структуры вложенных и перекрывающихся исключающих ИЛИ ниже Рисунок 5.3 - Структуры вложенных при n = 1, 2, 3, …исключающих ИЛИ, перекрывающихся в нуле: a) для целых чисел; b) начальный участок от нуля ;

c) по степеням числа 2, где X = 2n – 2n-1, Y = 2n-1 - 2n Импликация. Функция имеет единственный 0 для классического случая (-1,0), когда посылка истинная, а заключение ложное. Функция имеет значение -1, если посылка ложная, или заключение истинное, а также при равных операндах. Если посылка истинная или сумма двух операндов -1, то значение функции повторяет значение заключения. Если заключение ложное, то значение функции соответствует значению функции отрицания.

Стрелочная нотация для некоторых случаев:

( n, -(n+1) -(n+1) ) Импликация, при использовании только обобщённого фиксированного отрицания, предоставляет многообразие вложенных логик, примеры которых приводятся ниже.

Рисунок 5.4 - Общий участок импликации (для наглядности не все клетки заполнены) Рисунок 5.5 - Центральные логики импликации, симметричные по Далее в двух табличных строках приводятся логики импликации, симметричные только по выходам.

Рисунок 5.6 - Логики импликации, симметричные только по выходам Эквивалентность. Функция даёт истину при равных аргументах и ложь, если сумма двух операндов даёт -1. Если один из операндов –1, то значение функции повторяет значение второго операнда. Если один из операндов 0, то значение функции совпадает с функцией отрицания второго операнда. Равные, но противоположные по знаку значения только чётных или только нечётных чисел в одинаковых интервалах изменения входных величин, приводят к значению 1 на выходе. Равные, но противоположные по знаку значения чётных и нечётных чисел в одинаковых интервалах изменения входных величин приводят к значению 0 на выходе.

Стрелочная нотация для целых чисел:

( -(n+1), 0 -(n+1) ) Эквивалентность может быть представлена центральным участком и участками, в которых выделяются вложенные логики.

Рисунок 5.7 - Центральный участок эквивалентности Рисунок 5.8 - Вложенные логики эквивалентности: a) при нечётных входах;

b) при нечётных и чётных входах Проверка проведена в средах Win32Forth v.6.13.00 и Portable Forth v.17.

Является вопрос: как применить в программировании и (или) управлении вложенные, перекрывающиеся и параллельные логики? Напрашивается один из возможных вариантов для параллельных логик.

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

Рисунок 5.9 - Структура выделения свойств данных для параллельных логик 5.3 Троичная логика Для различения положительных и отрицательных чисел используется старший разряд, а для различения чётных и нечётных чисел – младший разряд числа. Вводя нуль и минус единицу, переходим к троичной логике. Далее приводятся таблицы истинности для отдельных операций.

Рисунок 5.10 - Троичная логика для: a) конъюнкции, b) дизъюнкции, Рисунок 5.11 - Троичная логика для: a) импликации, b) эквивалентности, Это как раз то, что называется циклической перестановкой.

Пример: 65 54 43 32 21 10 3 ROLL ok…….

Слово ROLL ведет отсчет с нулевого индекса, то есть с вершины стека.

Опираясь на это исходное слово, определим новые слова.

b) Переместить на вершину стека элемент n с индексом 2:

В соответствии со стековой нотацией, слово ROT (от ROTATE – вращать) помещает в вершину стека третий элемент, то есть производит вращение по кругу. Пример:

c) Переместить на вершину стека элемент n с индексом 1:

В соответствии со стековой нотацией, слово SWAP (обменять) осуществляет перестановку двух первых элементов стека.

Пример:

Обратное перемещение по кругу обеспечивается словом:

Пример:

В реальности слова SWAP, ROT и -ROT определяются через машинные коды.

Если перед каждым новым вводом последовательности чисел стек периодически очищается, то переместить на вершину стека первый введенный элемент можно конструкцией:

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

Здесь слово ?DO не исполняет тело цикла ни разу, если начальное и граничное значения оказались одинаковыми.

Вопросы для самопроверки 1. Что такое стек и что находится в его вершине?

2. Что такое глубина стека и слово, отображающее её?

3. Слово, отображающее содержимое стека на экран, и что оно показывает?

4. Какие слова предназначены для вывода чисел из стека?