Название конкурса: Конкурс по информатике «Языки программирования»
Участник: Мельников Николай Анатольевич
Результат (баллов): 9 из 15
Затрачено времени: 6:09
Дата участия: 31.01.2022
Идентификатор результата: A502 332322
Вопрос № 1. Компьютерная программа – это файл, созданный компьютером.
Выберите неверное утверждение:
Вопрос № 2. 2
Современные компьютеры используют в основном систему счисления с основанием …
Вопрос № 3. Основные элементы, из которых строится программа
Лексика языка программирования описывает …
Вопрос № 4. Смысл правильных конструкций языка программирования
Синтаксис языка программирования описывает …
Вопрос № 5. 2 поколения
Языки ассемблера относятся к языкам …
Вопрос № 6. 3 поколение
К какому поколению относятся языки логического программирования?
Вопрос № 7. Текст программы на языке высокого уровня интерпретируется специальной программой.
Выберите неверное утверждение:
Вопрос № 8. Скомпилированная программа выполняется быстрее, чем интерпретируемая
В чём основное преимущество компиляции?
Вопрос № 9. Интерпретатором
Для перевода программы с языка программирования высокого уровня в машинные коды используется специальная программа, называемая …
Вопрос № 10. Логическое программирование
Эта парадигма программирования противопоставляется императивному подходу. В программе описывается предметная область и что нужно найти.
Вопрос № 11. Декларативного программирования
Программа состоит из инструкций, которые выполняются последовательно. Это характерно для …
Вопрос № 12. Prolog
Выберите из перечисленных язык логического программирования:
Вопрос № 13. SQL
Выберите из перечисленных язык декларативного программирования:
Вопрос № 14. Компиляция
Какой тип исполнения преимущественно характерен для языка программирования Pascal?
Вопрос № 15. Интерпретация
Какой тип исполнения преимущественно характерен для языка программирования Python?
Для получения наградных материалов необходимо проверить корректность введенных данных участника и оплатить оргвзнос.
Директивное программирование — один из наиболее естественных для человека подходов к написанию программ. Ведь программа в этом случае состоит из операторов присваивания и предложений, управляющих последовательностью их выполнения. При написании подобной программы необходимо найти такую цепочку команд, которая приведет в конце концов к вычислению (и, возможно, печати) одной или нескольких искомых величин
Императи́вное программи́рование — это парадигма программирования (стиль написания исходного кода компьютерной программы), для которого характерно следующее:
в исходном коде программы записываются инструкции (команды);
инструкции должны выполняться последовательно;
при выполнении инструкции данные, полученные при выполнении предыдущих инструкций, могут читаться из памяти;
данные, полученные при выполнении инструкции, могут записываться в память.
Императивная программа похожа на приказы (англ. imperative — приказ, повелительное наклонение), выражаемые повелительным наклонением в естественных языках, то есть представляют собой последовательность команд, которые должен выполнить компьютер.
При императивном подходе к составлению кода (в отличие от функционального подхода, относящегося к декларативной парадигме) широко используется присваивание. Наличие операторов присваивания увеличивает сложность модели вычислений и делает императивные программы подверженными специфическим ошибкам, не встречающимся при функциональном подходе [1].
Основные черты императивных языков:
использование именованых переменных;
использование оператора присваивания;
использование составных выражений;
использование подпрограмм;
и др.
Текущая версия страницы пока не проверялась опытными участниками и может значительно отличаться от версии, проверенной 29 апреля 2017 года; проверки требуют 3 правки.
В императивном программировании порядок выполнения (порядок исполнения, порядок вычислений) — это способ упорядочения инструкций программы в процессе её выполнения.
Инструкции, входящие в программу, могут исполняться как последовательно, одна за другой, так и одновременно; как однократно, так и многократно; последовательность исполнения инструкций может совпадать с последовательностью их расположения в записи программы или не совпадать, а также зависеть как от текущего состояния вычислителя, исполняющего программу, так и от внешних событий, образовывая, таким образом, разнообразные порядки выполнения инструкций.
Организация желаемого порядка выполнения может быть осуществлена с помощью различных механизмов, таких как специализированные инструкции вычислителю или управляющие конструкции высокоуровневых языков программирования или встроенные в вычислитель механизмы для прерывания, сохранения и восстановления состояния, модификация и генерация инструкций программы и других.
Поток управления[править | править код]
В императивном программировании предполагается, что процесс выполнения программы заключается в выполнении её инструкций вычислителем. В момент выполнения инструкции говорят, что она управляет вычислителем, переход к выполнению следующей называется передача управления или просто переход. Последовательность передач управления в процессе выполнения программы формирует её поток управления (также поток выполнения).
Способность вычислителя выбирать инструкции для выполнения в зависимости от своего состояния, а также возможность одновременного выполнения нескольких инструкций порождают существование разветвлённых (которые могут быть выполнены при определённых условиях) и параллельных (выполняющихся одновременно) связанных и взаимодействующих между собой потоков управления в одной программе.
Совокупность потоков программы, образующих разнообразные порядки, может быть изображена в виде ориентированного графа, где узлы соответствуют инструкциям программы, а ребра — переходам между ними.
Виды порядков выполнения[править | править код]
Порядок выполнения инструкций отражает структуру алгоритма, реализуемого программой. Каждой базовой алгоритмической конструкции соответствует свой порядок выполнения, как правило, с таким же названием.
Простейшим порядком выполнения является последовательный или естественный порядок, когда инструкции выполняются последовательно, одна за другой, в порядке их появления в записи программы. Естественный порядок образуется при реализации алгоритмической конструкции «следование».
Отклонение от естественного для применяемого способа записи порядка называется переход. В этом случае после окончания выполнения текущей инструкции вычислитель переходит не к следующей в записи, а к некоторой другой, определённым образом заданной инструкции. При безусловном переходе инструкция перехода выбирается без учета состояния вычислителя, при условном переходе — в зависимости от состояния вычислителя, путём проверки условия.
Условный переход позволяет организовывать ветвление потока управления, образуя ветвящийся порядок, при котором исполнению подлежит только одна из двух или более внутренних фрагментов-ветвей программы. Ветвящийся порядок реализует алгоритмическую конструкцию «ветвление».
Переход к ранее выполненной инструкции позволяет организовать многократное исполнение набора инструкций, образуя циклический порядок их выполнения (цикл) и реализуя алгоритмическую конструкцию «цикл».
Другой способ организовать повторное выполнение набора инструкций в программе состоит в выделении предназначенных к повтору инструкций в обособленную часть программы, называемую подпрограмма, с возможностью многократной передачи управления (называемой вызов) в подпрограмму и последующим возвратом в место вызова.
Вычислитель может иметь возможность прервать выполнение программы и передать управление определённой инструкции в зависимости от своего состояния или сигналов внешних устройств, образуя прерывание. После его обработки выполнение программы может быть продолжено с места прерывания.
Передача управления заранее подготовленному набору инструкций для определённой, как правило необычной или ошибочной (исключительной), ситуации без возможности возврата в место возникновения образует обработку исключений.
См. также[править | править код]
- Алгоритм
- Граф потока управления
- Ветвление (программирование)
- Цикл (программирование)
- Control-flow integrity
Примечания[править | править код]
Базовые понятия Программа состоит из последовательности инструкций, оформленных в строгом соответствии с правилами, составляющими синтаксис данного языка. При создании программ могут быть допущены синтаксические или логические ошибки. Синтаксические ошибки – это нарушение правил написания программы. Логические ошибки разделяются на ошибки алгоритма и семантические ошибки. Ошибка алгоритма – это несоответствие построенного алгоритма ходу получения результата поставленной задачи. Семантическая ошибка – неправильное понимание смысла (семантики) операторов выбранного языка программирования.
Алфавит языка Си: – прописные и строчные буквы латинского алфавита и знак подчеркивания (код 95); – арабские цифры от 0 до 9; – специальные символы, смысл и правила использования которых будем рассматривать по тексту; – разделительные символы: пробел, символы табуляции, новой страницы и новой строки. Каждому из множества значений, определяемых одним байтом, в таблице кодов ставится в соответствие символ. Символы с кодами от 0 до 127 (первая половина таблицы) одинаковы для всех компьютеров, коды 128 – 255 (вторая половина) могут отличаться и обычно используются для национального алфавита, коды 176 – 223 символы псевдографики, а коды 240 – 255 – специальные знаки (можно посмотреть в приложении 1 [1, 2]).
Лексемы Из символов алфавита формируются лексемы (элементарные конструкции) языка – минимальные значимые единицы текста в программе: – идентификаторы (имена объектов); – ключевые (зарезервированные) слова; – знаки операций; – константы; – разделители (скобки, точка, запятая, точка с запятой, пробельные символы). Границы лексем определяются другими лексемами, такими как разделители или знаки операций, а также комментариями.
Идентификатор (ID) – это имя программного объекта (константы, переменной, метки, типа, функции и т. д. ). В идентификаторе могут использоваться латинские буквы, цифры и знак подчеркивания; первый символ ID – не цифра; пробелы и другие специальные символы внутри ID не допускаются. В Си прописные и строчные буквы – различные символы. Идентификаторы Name, NAME, name – различные объекты. Ключевые (зарезервированные) слова не могут быть использованы в качестве идентификаторов.
При именовании объектов следует придерживаться общепринятых соглашений: – имена переменных и функций обычно пишутся строчными (малыми) буквами; – имена типов пишутся с большой буквы; – имена констант – большими буквами; – идентификатор должен нести смысл, поясняющий назначение объекта в программе, например, birth_date – день рождения, sum – сумма; – если ID состоит из нескольких слов, как, например, birth_date, то принято либо разделять слова символом подчеркивания, либо писать каждое следующее слово с большой буквы – Birth. Date.
Комментарии Базовый элемент языка программирования – комментарий – не является лексемой. Внутри комментария можно использовать любые допустимые на данном компьютере символы, т. к. компилятор их игнорирует. В Си комментарии ограничиваются парами символов /* и */, а в С++ введен вариант комментария, который начинается символами // и заканчивается символом перехода на новую строку.
Общая структура программы на языке Си 1. Директивы препроцессора 2. Определение типов пользователя (typedef) 3. Описание прототипов функций 4. Определение глобальных переменных 5. Функции
Простейшая программа Рассмотрим кратко основные части структуры программ. Перед компиляцией программа обрабатывается препроцессором, который работает под управлением директив. Препроцессорные директивы начинаются символом #, за которым следует ее наименование, указывающее выполняемое действие. Препроцессор выполняет предварительную обработку программы, в основном это подключение (include) так называемых заголовочных файлов (обычных текстов) с объявлением стандартных библиотечных функций, использующихся в этой программе. Общий формат: #include < Имя_файла. h > где h – расширение заголовочных файлов.
Если имя файла заключено в угловые скобки (< >), то поиск данного файла производится в стандартной папке, если в двойные кавычки (” ”), то в текущей папке. К наиболее часто используемым библиотекам относятся: stdio. h – содержит стандартные функции ввода вывода данных; conio. h – функции для работы с консолью (клавиатура, дисплей); math. h – математические функции; iostream. h – ввод вывод в потоке;
Второе основное назначение препроцессора – обработка макро определений. Макроподстановка определить (define) имеет общий вид: #define ID строка Например: #define PI 3. 1415927 – в ходе препроцессорной обработки программы идентификатор PI везде будет заменяться значением 3. 1415927.
Пример простейшей программы: #include <stdio. h> void main(void) // Заголовок функции { // Начало функции printf (“ Высшая оценка знаний – 10 ! ”); } // Конец функции Отличительный признак функции – скобки ( ) после ее имени, в которых заключается список параметров. Если параметров нет, указывают атрибут void (пустой, отсутствующий). Перед функцией указывается тип возвращаемого результата, если результата нет – void. В фигурных скобках записывается текст (код) функции, т. е. набор выполняемых ею инструкций, каждая из которых оканчивается символом «; » . В нашем примере только функция printf – вывод указанной фразы на экран.
В предыдущем примере для вывода использована стандартная функция printf, описанная в файле stdio. h. Используя потоковый вывод, этот пример можно записать следующим образом: #include <iostream. h> void main () { cout << “ 10 is the best mark ! ” << endl; } Если параметров нет, атрибут void можно не писать. cout (class output) – вывод данных в потоке с помощью операции побитового сдвига <<; endl (end line) – перевод курсора на новую строку.
Типы данных Данные в языке Си разделяются на две категории: простые (скалярные) и сложные (составные) типы данных. Тип данных определяет: – внутреннее представление в памяти; – диапазон допустимых значений; – набор допустимых операций. Базовые типы данных: символьный – char (character), целый – int (integer), вещественный обычной точности – float, вещественный удвоенной точности – double.
Данные целого типа могут быть короткими – short, длинными – long, со знаком – signed и беззнаковыми – unsigned. Атрибут unsigned может использоваться для типа char. Атрибут long может использоваться для типа double. Тип void указывает его отсутствие. Сложные типы данных: массивы, структуры – struct, объединения – union, перечисления – enum.
Диапазон и объем памяти данных Тип Объем памяти (байт) char 1 int 4 – 32768 … 32767 short (int) 2 – 32768 … 32767 long (int) 4 – 2147483648 … 2147483647 unsigned int 4 0 … 65535 unsigned long 4 0 … 4294967295 float 4 3, 14*10– 38 … 3, 14*1038 double 8 1, 7 *10– 308 … 1, 7 *10308 Диапазон значений – 128 … 127
Декларация объектов Все объекты программы (кроме самоопре деленных констант) необходимо декларировать, т. е. объявить компилятору об их присутствии. Общий формат объявления: Атрибуты Список-Объектов; Элементы Списка разделяются запятыми, а Атрибуты – разделителями (хотя бы одним пробелом), например: long int i, j, k;
Атрибуты могут быть следующими: Класс памяти – определяет способ размещения в памяти (статическая, динамическая), область видимости и время жизни (по умолчанию – auto), данные атрибуты будут рассмотрены позже; Тип – базовый тип, или созданный ранее тип Пользователя (по умолчанию – тип int). Класс памяти и тип – атрибуты необязательные и при отсутствии одного из них (но не обеих одновременно) устанавливаются по умолчанию. Примеры декларации простых объектов: char ss; int i, j, k; double a, b, x;
Данные целого типа (integer) Тип int – целое число, обычно соответствующее естественному размеру целых чисел. Квалификаторы short и long указывают на различные размеры и определяют объем памяти, выделяемый под них, например: short x; long x; unsigned x = 8; – декларация с инициализацией числом 8; атрибут int в этих случаях может быть опущен.
Для определения константных значений можно использовать атрибут const, указывающий запрет изменения введенной величины в программе, например const N = 20; или const double PI = 3. 1415926; Атрибуты signed и unsigned показывают, как интерпре тируется старший бит – как знак или как часть числа: int Знак unsigned Значение числа 31 30 29 . . . 2 1 0 Значение числа 31 30. . . 2 1 0 – Номера бит
Данные символьного типа (char) Любой символ в памяти занимает соответствует конкретному коду. один байт и Для персональных компьютеров (ПК) наиболее распространена ASCII (American Standard Code for Information Interchenge) таблица кодов (см. Приложение 1). Данные типа char рассматриваются компилятором как целые, поэтому можно использовать величины со знаком signed char (по умолчанию) – символы с кодами от – 128 до +127 и unsigned char – беззнаковые символы с кодами от 0 до 255. Примеры: char res, simv 1, simv 2; char sim = ‘s’; – декларация символьной переменной с инициализацией символом s.
Данные вещественного типа (float, double) Характеристика данных: Тип float Мантисса Порядок (4 байта) 7 цифр после запятой 38 15 308 19 4932 double (8 байт) long double (10 байт) Переменная типа double формально соответствует типу long float. Внутреннее представление этих данных состоит из мантиссы и порядка, т. е. < Мантисса > * 10 < Порядок >
КОНСТАНТЫ Константами называют величины, которые не изменяют значений во время выполнения программы. Константа – это неадресуемая величина и, хотя она хранится в памяти, определить ее адрес невозможно! Константы нельзя использовать в левой части операции присваивания. В языке Си константами являются: – самоопределенные константы; – имена (идентификаторы) массивов и функций; – элементы перечислений.
Целочисленные константы Десятичные константы – это набор цифр 0. . . 9, первая из которых не 0 (со знаком или без него). Для длинных целых констант указывается признак L(l) – 273 L (273 l). Константа, которая слишком длинна для типа int, рассматривается как long. Восьмеричные константы – это набор цифр от 0 до 7, первая из которых 0, например: 020 = 16 – десятичное. Шестнадцатеричные константы – набор цифр от 0 до 9 и букв от A до F (a. . . f), начинающаяся символами 0 Х (0 х), например: 0 X 1 F (0 х1 f) = 31 – десятичное. Восьмеричные и шестнадцатеричные константы также могут быть long, например, 020 L или 0 X 20 L. Примеры целочисленных констант: 1992 777 1000 L – десятичные; 0777 00033 01 L – восьмеричные; 0 x 123 0 X 00 ff 0 xb 8000 L – шестнадцатеричные.
Константы вещественного типа Данные константы размещаются в памяти по формату double и могут иметь две формы: 1) с фиксированной точкой: n. m (n, m – целая и дробная части числа); 2) с плавающей точкой (экспоненциальная форма) представляется в виде мантиссы и порядка: n. m. E p где n. m – мантисса (n, m – целая и дробная части числа), Е (или е) – знак экспоненты, р – порядок. Например, 1, 25 10– 8 можно записать 1. 25 E– 8 или 0. 125 E– 7 Примеры: 1. 0 – 3. 125 100 Е– 10 – 0. 12537 е+5 Пробелы внутри чисел не допускаются. Для разделения целой и дробной части используется точка. Дробную или целую часть можно опустить, но не обе сразу, например, 1. (или 1. 0). 5 (или 0. 5)
Символьные константы Символьная константа – это символ, заключенный в одинарные кавычки (апострофы), например: ‘а’. Так же используются специальные управляющие симво лы (escape последовательности), например (первый символ обратный слеш): n – новая строка; t – горизонтальная табуляция; – нулевой символ. При присваивании символьной переменной они должны быть заключены в апострофы. Текстовые символы непосредственно вводятся с клави атуры, а специальные и управляющие – представляются в исходном тексте парами символов, например: – обратный слеш; ‘ – апостроф; » – кавычки. Примеры символьных констант: ‘А’ ‘9’ ‘$’ ‘n’
Строковые константы Строковая константа – символы, заключенные в кавычки (”). Кавычки не являются частью строки, а служат только для ее ограничения. Строка в языке Си представляет собой массив символов. Внутреннее представление константы «1234 ABC»: ‘1’ ‘2’ ‘3’ ‘4’ ‘A’ ‘B’ ‘C’ » В конец строковой константы компилятор автоматически добавляет нулевой символ », называемый нуль-терминатор, который на печать не выводится и является признаком окончания строки. Примеры строковых констант: «Summa» «n t Result = n» » » EXIT » » Длинную строковую константу можно разбить на несколько с помощью обратного слеша (). Например: «Вы учитесь в Белорусском государственном университете информатики и радиоэлектроники» Компилятор воспримет такую запись, как единое целое.
Операции, выражения Выражения используются для вычисления значений определенного типа и состоят из операндов, операций и скобок. Операнд может быть, в свою очередь, выражением (константой или переменной). Операции выполнить. задают действия, которые необходимо В языке Си используются четыре первичных операции: – операция доступа к полям структур и объединений при помощи идентификаторов «. » (точка); – операция доступа к полям структур и объединений при помощи указателей «->» (стрелка); – операция индексации «[ ]» при обращении к элементам массива; – операция «( )» при обращении к функции.
Операции делятся на унарные, бинарные и тернарные – по количеству участвующих операндов, и выполняются в соответствии с приоритетами. Для изменения порядка выполнения операций используются круглые скобки. Унарные операции имеют больший приоритет над бинарными. Большинство операций выполняются слева направо. Унарные операции, операции присваивания и условная операция (? : ) выполняются справа налево. Арифметические операции Бинарные арифметические операции: + (сложение); – (вычитание); / (деление, для int операндов – с отбрасыванием остатка); * (умножение); % (остаток от деления целочисленных операндов со знаком первого операнда – деление «по модулю» ).
Операндами традиционных арифметических опера ций (+, –, *, /) могут быть любые объекты, имеющие допустимые типы (константы, переменные, функции, элементы массивов, арифметические выражения). Унарные операции +, – (знак) определены только для числовых операндов, при этом «+» носит только информационный характер, «–» меняет знак операнда на противоположный (не адресная операция). Порядок выполнения операций: 1) выражения в круглых скобках; 2) вычисление функций (стандартные функции и функции пользователя); 3) операции * , / , %; 4) операции – , +.
При записи сложных выражений нужно использовать общепринятые математические правила: Т. е. использовать круглые скобки. Единственной исключительной ситуацией при выполнении арифметических операций является деление на ноль, другие ситуации (переполнение, исчезновение порядка или потеря значимости) компилятором игнорируются.
Операция присваивания Общий формат: Операнд_1 = Операнд_2 ; Операндом_1 (L–значение – Left-Value) может быть только адресное выражение, т. е. именованная, либо косвенно адресуемая указателем переменная. Операндом_2 (R–значение – Right-Value) может быть константа, переменная и любое выражение, составленное в соответствии с синтаксисом языка Си. Операция выполняется справа налево. Тип результата определяется типом левого операнда. Приведите примеры «хитрых» ситуаций!
Присваивание значения в языке Cи рассматривается как выражение, имеющее значение левого операнда после присваивания. Поэтому присваивание может включать несколько операций, изменяя значения нескольких операндов, например: i = j = k = 0; k = 0, j = k, i = j; x = i + (y = 3) – (z = 0); y = 3, z = 0, x = i + y – z; Примеры недопустимых выражений: – присваивание константе: 2 = x + y; – присваивание функции: getch() = i; – присваивание результату операции: (i + 1) = 2 + y;
Сокращенные формы операции присваивания В языке Си используются два вида сокращенной записи операции присваивания: 1) вместо записи v = v # e; где # – любая арифметическая операция; рекомендуется использовать запись v #= e; Например, s = s + 2; s += 2; знаки операций записываются без пробелов; 2) вместо записи x = x # 1; где # – символы, обозначающие операцию инкремента (+1), либо декремента (– 1), рекомендуется использовать запись: префиксную ##x; ++х; х; x##; х++; х ; или постфиксную
Операции инкремента (++) и декремента ( ) – унарные. Если эти операции используются отдельно, то различий между постфиксной и префиксной формами нет. Если же они используются в выражении, то 1) в префиксной форме (##x) сначала значение x изменится на 1, а затем x будет использовано в выражении; 2) в постфиксной форме (x##) сначала значение x используется в выражении, а затем изменяется на 1. Например, int x, a = 2, b = 5; 1) x = ++a * b; a = 3, b = 4, x = 12; 2) x = a++ * b ; x = 10, a = 3, b = 4;
Преобразование типов Если операнды арифметических операций имеют один тип, то результат операции будет иметь такой же тип. Если в операциях участвуют операнды различных типов, то они преобразуются к «большему» типу (в смысле объема памяти), т. е. неявные преобразования идут от «меньших» объектов к «большим» : – значения char и short преобразуются в int; – если один операнд double, то и другой преобразуется в double; – если один операнд long, то и другой преобразуется в long. Внимание! Результат операции 1 / 3 значение НОЛЬ, т. к. и 1 и 3 имеют тип int !!! Чтобы избежать такого рода ошибок необходимо явно изменить тип хотя бы одного операнда, т. е. записывать, например: 1. / 3, т. к. 1. вещественная константа !!!
Типы char и int могут свободно смешиваться в арифметических выражениях. Переменные char автоматически преобразуются в int. При присваивании значение правой части преобразуется к типу левой, который и является типом результата. Поэтому необходимо быть внимательным, т. к. при некорректной записи могут возникнуть неконтролируемые ошибки. При преобразовании int в char старший байт просто отбрасывается. Если double x; int i;
Операция явного приведения типа Формат операции: (Тип) Выражение; ее результат – значение Выражения, преобразованное к заданному Типу. Рекомендуется использовать эту исключительных случаях, например: операцию double x; int n = 6, k = 4, m = 3; x = (n + k) / m; x = 3; x = (double)(n + k) / m; x = 3. 333333. в
Стандартные библиотечные файлы В любой программе кроме инструкций используются стандартные функции, входящие в библиотеку языка Си, которые облегчают создание программ. В стандартных библиотечных файлах описаны прототипы функций, макросы, глобальные константы. Это заголовочные файлы с расширением *. h, которые хранятся в папке include и подключаются на этапе предпроцессорной обработки. Математические функции языка Си декларированы в файле math. h (некоторые в stdlib. h). В файле math. h описаны макроконстанты, такие как, например , это M_PI (и другие). У большинства математических функций аргументы и возвращаемый результат имеют тип double. Аргументы тригонометрических функций должны быть заданы в радианах (2π радиан = 3600).
Математическая функция |x| ex xy ln(x) lg 10(x) sin(x) cos(x) tg(x) arcsin(x) arccos(x) arctg(x / y) sh(x)=0. 5 (ex–e x) ch(x)=0. 5 (ex+e x) tgh(x) Остаток от деления x на y Наименьшее целое >=x Наибольшее целое <=x Имя функции sqrt(x) fabs(x) exp(x) pow(x, y) log(x) log 10(x) sin(x) cos(x) tan(x) asin(x) acos(x) atan 2(x, y) sinh(x) cosh(x) tanh(x) fmod(x, y) ceil(x) floor(x)
Из библиотеки conio. h при создании КОНСОЛЬНЫХ приложений мы будем пользоваться только функцией getch( ); Которая выполняет ожидание нажатия любой клавиши; ее результат – код нажатой клавиши.
Потоковый ввод-вывод Для ввода вывода в языке С++ используются два класса: cin (класс ввода), cout (класс вывода). Для их работы необходимо подключить файл iostream. h. Стандартный поток вывода cout по умолчанию связан со стандартным устройством вывода stdout (дисплей монитора), а ввода cin – со стандартным устройством ввода stdin (клавиатура). Вывод на экран (помещение в поток <<): cout << Имя-Объекта-Вывода; Ввод с клавиатуры (извлечение из потока >>): cin >> Имя-Переменной;
Пример: #include < iostream. h > void main () { int i, j, k; cout << “ Input i, j ”; cin >> i >> j ; k=i+j; cout << “ Sum i + j = “ << k << endl; /* end line – переход на новую строку и очистка буферов ввода-вывода */ }
Функции вывода данных на дисплей Стандартные функции ввода/вывода описаны в файле stdio. h. Для вывода на экран чаще всего используются: printf и puts. Формат функции форматного вывода на экран: printf ( Управляющая Строка , Список Вывода ); В Управляющей записывают: Строке, заключенной в кавычки, − Поясняющий текст (комментарии); − Список модификаторов форматов, определяющих способ вывода объектов (признак – символ %); − Специальные управляющие символы.
В Списке Вывода указываются выводимые объекты: пере менные, константы, выражения (вычисляемые перед выводом). Количество и порядок форматов должен совпадать с количеством и порядком следования печатаемых объектов. Так как функция printf выполняет вывод данных в соответствии с указанными форматами, формат может использоваться для преобразования типов выводимых объектов.
Если признака модификации (%) нет, то вся информация выводится как комментарии. Основные модификаторы формата: %d – десятичное целое число (int); %c – один символ (char); %s – строка символов; %f – вещественное типа float; %ld – длинное целое (long int); %lf – вещественное типа double (long float).
Управляют выводом специальные последовательности символов: n – новая строка; t – горизонтальная табуляция; b – шаг назад; r – возврат каретки; v – вертикальная табуляция; – обратная косая; ‘ – апостроф; » – кавычки; – нулевой символ (пусто).
В модификаторах формата функции printf после символа % можно указывать ширину поля вывода, например, %5 d – для int, %8. 4 lf – для double (4 цифры после запятой для поля, шириной 8 символов). Если указанных позиций для вывода целой части числа не хватает, то происходит автоматическое расширение. Можно использовать функцию printf для нахождения кода ASCII некоторого символа: printf (» %c – %d n», ‘a’); Функция puts (Имя-Строки); выводит на экран строку, автоматически добавляя к ней символ перехода на начало новой строки (n). Аналогом такой функции будет: printf (“%s n”, Имя-Строки);
Функции ввода информации Форматированный ввод с клавиатуры: scanf (Управляющая Строка , Список Ввода); в Управляющей строке указываются только модификаторы форматов, количество и порядок которых должны совпадать с количеством и порядком вводимых объектов, тип преобразуется в соответствии с модификаторами. Список Ввода – адреса переменных (через запятую), т. е. для ввода перед именем переменной указывается символ & – операция «взять адрес» . Если вводим значение строковой переменной, то символ & не используем, т. к. строка – это массив символов, а имя массива – это адрес его первого элемента. Например: int kypc; // Курс double grant; // Стипендия char name[20]; // Фамилия printf (» Input kypc, grant, name n «); scanf («%d%lf%s», &kypc, &grant, name);
Вводить данные с клавиатуры можно как в строку, разделяя данные хотя бы одним пробелом, так и в столбец, нажимая после каждого значения клавишу Enter. В функции scanf используется тот же набор основных модификаторов форматов, что и printf. Внимание! Функцией scanf по формату %s строка вводится только до первого пробела. Для ввода фраз, состоящих из слов, разделенных пробелами, используется функция: gets (Имя-Строковой-Переменной); Символы вводятся при помощи функции getch(). Простой ее вызов организует задержку выполнения программы до нажатия любой клавиши.
Пример использования функции getch: char s; s = getch(); cout << “Character = » << s << endl; cout << “Code = » << (int) s << endl; переменная s – символ нажатой клавиши, а (int)s – код этого символа. При запуске программы автоматически открываются стандартные потоки ввода – stdin (по умолчанию связан с клавиатурой) и вывода – stdout (экран монитора). Внимание! Ввод данных функциями gets, getch выпол няется с использованием потока stdin. Если указанная фу нкция не выполняет своих действий (проскакивает), перед ее использованием необходимо очистить поток (буфер) ввода с помощью функции (stdlib. h) fflush (stdin);
Введение
Программирование
у большинства людей ассоциируется с
понятием алгоритма, последовательности
действий по достижению результата.
Однако это относится к традиционному,
императивному программированию. Наряду
с ним существует другой подход к
разработке программ, называемый
декларативным программированием, при
котором понятие алгоритма отступает
на задний план. В декларативном
программировании от программиста
требуется описывать не последовательность
действий для нахождения результата, а
Свойства требуемого результата.
Считается, что такой подход больше
соответствует человеческому мышлению.
Декларативное
программирование на протяжении нескольких
десятков лет привлекало людей различных
категорий, имеющих отношение к разработке
программного обеспечения. Это определялось
следующими присущими декларативным
языкам особенностями:
• выразительностью
(программы на декларативных языках
оказываются короче императивных
программ, выполняющих аналогичные
действия);
• ориентированностью
на присущий человеку образ мышления
(декларативные программы представляют
набор предложений, описывающих конкретные
свойства требуемого решения);
• параллелизмом
(декларативное программирование дает
предпосылки к реализации на параллельных
ЭВМ).
При этом под
декларативным программированием
понимается программирование на языках
функционального или логического
программирования.
Реализуется
декларативное программирование
средствами двух основных стилей,
определяемых как функциональное и
логическое программирование, каждый
из которых в определенной степени
соответствует основным положениям
декларативного программирования.
Функциональное и
логическое программирование на протяжении
десятилетий использовались для решения
задач искусственного интеллекта,
принимались в качестве базовых архитектур
при разработке ЭВМ пятого поколения. В
настоящее время функциональное и
логическое программирование базируются
на строгой математической основе, имеют
широкий набор программных инструментов,
используемых для решения широкого круга
задач, связанных в основном с проблемами
искусственного интеллекта и символьными
вычислениями.
Декларативное
программирование, которое можно назвать
«подходом с позиций человека», в отличие
от императивного подхода к разработке
программ, который можно назвать «подходом
с позиций компьютера», имеет значение
и с точки зрения новаций, привнесенных
в программирование. Достаточно сказать,
что только с функциональным языком
программирования Лисп связаны многие
нововведения, ставшие впоследствии
привычными: многооконный графический
интерфейс и полноэкранные редакторы,
символические отладчики и инспекторы
данных, диалоговые системы программирования.
Самое главное новшество, которое сейчас
вводится во все большее число систем
программирования, начиная с Java,
– автоматическое управление памятью
и «уборка мусора». То же самое можно
сказать и о многих других функциональных
языках программирования ML,
Miranda,
Haskell.
Функциональное и
логическое программирование являются
стилями программирования «сверхвысокого»
уровня по отношению к языкам программирования
высокого уровня.
Функциональное и
логическое программирование ориентированы
на решение задач, которые можно отнести
к проблеме искусственного интеллекта.
Задачи искусственного интеллекта
относятся к трудноформализуемым задачам,
которые можно описать в терминах «что
надо получить», но, зачастую, довольно
сложно определить в терминах «как
получить результат».
Императивная и
декларативная парадигмы программирования
Существуют две
парадигмы программирования: императивная
и декларативная. Основной (традиционной)
парадигмой программирования является
императивное (процедурное) программирование.
В рамках императивной парадигмы
рассматривается класс языков
программирования, в которых программа
явно указывает способ получения
результата, не определяя ожидаемых
свойств результата. Процедура получения
результата имеет вид последовательности
операций. Отсюда следуют характерные
черты императивной
программы:
• указание логики
управления в программе;
• определение
порядка выполнения операций;
• наличие операторов
присваивания, выполняющих разрушающее
присваивание.
Императивная
парадигма основана на «фон-неймановской»
вычислительной модели, основными
параметрами которой являются:
• программа состоит
из набора команд, которые выполняются
последовательно;
• поименованные
области памяти (концепция переменных
как областей памяти, к которым можно
обращаться по имени).
Концепция памяти
как хранилища значений, содержимое
которого может обновляться операторами
программы, является фундаментальной в
императивном программировании.
Реализация программы
сводится к последовательному выполнению
операторов с целью преобразования
исходного состояния памяти, то есть
значений исходных данных, в заключительное,
то есть в результаты. Таким образом, с
точки зрения программиста имеются
программа и память, причем первая
последовательно обновляет содержимое
последней.
Императивные
языки
программирования характеризуются
следующими особенностями:
• необходимостью
явного управления памятью, в частности
описанием переменных;
• малой пригодностью
для символьных вычислений;
• отсутствием
строгой математической основы;
• высокой
эффективностью реализации на традиционных
ЭВМ.
Одним из важнейших
классификационных признаков процедурного
языка является его уровень. Уровень
языка программирования определяется
семантической (смысловой) емкостью его
конструкций и степенью его ориентации
на программиста. Язык программирования
частично ликвидирует разрыв между
методами решения различного рода задач
человеком и вычислительной машиной.
Чем более язык ориентирован на человека,
тем выше его уровень. К императивным
языкам программирования относятся
ассемблеры и хорошо распространенные
языки программирования высокого уровня,
например такие, как Фортран, Паскаль,
Си.
Принципиально
иную вычислительную модель предполагает
декларативная
парадигма
программирования. При использовании
декларативного языка в программе в
явном виде указывается, какими свойствами
должен обладать результат, но не
определяется порядок его получения. В
идеальном случае декларативная программа
будет состоять из предложений, описывающих
необходимый результат. Характерно, что
в этом случае порядок предложений,
определяющих конкретные свойства
результата, не имеет значения. В
декларативной парадигме отсутствует
концепция переменной, как поименованной
области памяти, и явное управление.
Декларативные языки не привязаны жестко
к традиционной фон-неймановской модели
вычислений. В большинстве случаев
алгоритм достижения необходимого
результата может иметь высокую степень
параллелизма.
Декларативная
парадигма программирования реализуется
с помощью одного из двух стилей
программирования: функционального или
логического программирования.
Функциональное
и логическое программирование – стили
декларативного программирования
В настоящее время
декларативная парадигма программирования
реализуется с помощью одного из следующих
стилей программирования: функционального
и логического программирования.
Основной конструкцией
в функциональных
языках служит
символьное выражение (S-выражение).
К S-выражениям
относятся скалярные константы,
структурированные объекты, функции,
тела функций и вызовы функций.
Функция трактуется
как однозначное отображение из области
определения функции в область значений
функции, что полностью соответствует
математическому определению функции.
Функциональный
язык программирования включает следующие
элементы:
• классы констант,
которыми могут манипулировать функции;
• набор базовых
(определенных в данной системе) функций,
называемых примитивами;
• правила построения
новых функций на основе примитивов;
• правила
формирования выражений па основе вызовов
функций.
Программа
представляет собой совокупность описаний
функций и выражений, которые необходимо
вычислить. Заданное в программе выражение
вычисляется посредством редукции, то
есть серии упрощений по следующим
правилам:
• вызовы
функций-примитивов заменяются
соответствующими значениями;
• вызовы определенных
программистом функций заменяются их
телами, в которых параметры замещены
аргументами.
В функциональном
программировании не используется
концепция памяти как хранилища значений
переменных, характерная для фон-неймановской
вычислительной архитектуры. Операторы
присваивания отсутствуют, вследствие
чего переменные обозначают не области
памяти, а объекты программы, что полностью
соответствует понятию переменной в
математике. В функциональном
программировании нет существенных
различий между константами и функциями,
то есть между данными и программами. В
результате этого функция может быть
значением вызова другой функции, а также
элементом структурированного объекта.
Число аргументов при вызове функции не
обязательно должно совпадать с числом
параметров, указанных при ее описании.
Таким образом, функциональные языки
можно определить как языки сверхвысокого
уровня по отношению к языкам высокого
уровня.
Логическое
программирование
базируется на понятии отношения
(реляция). Поэтому существует другое
название логического программирования
– реляционное программирование.
Программа представляет собой совокупность
определений отношений между объектами
и цели.
Процесс выполнения
логической программы трактуется как
процесс доказательства общезначимости
логической формулы, построенной из
программы по правилам, установленным
семантикой используемого языка. Результат
вычисления является побочным продуктом
этого процесса.
В логическом
программировании нужно только
специфицировать факты, описывающие
задачу, а не определять последовательность
шагов, которые требуется выполнить. Это
свидетельствует о декларативном
характере языков логического
программирования, которые характеризуются:
• высоким уровнем;
• строгой ориентацией
на символьные вычисления;
• возможностью
инверсных вычислений, то есть переменные
в процедурах не делятся на входные и
выходные.
Следует отметить,
что логическое программирование в
принципе неэффективно с вычислительной
точки зрения. Программы на языке
логического программирования имеют
небольшое быстродействие, так как
вычисления осуществляются методом проб
и ошибок, поиском с возвратами к предыдущим
шагам. Несмотря на это, логическое
программирование привлекательно именно
с точки зрения приближения к декларативной
парадигме программирования. Наибольший
эффект логическое программирование
дает при решении неформальных задач,
задач, алгоритм решения которых неизвестен
или получение алгоритма сопряжено с
большими трудностями. В этом случае
описание задачи в терминах того, что
надо получить, приводит к цели с
наименьшими затратами.
Наибольшее
количество описанных выше задач относится
к сфере проблем искусственного интеллекта.
Системы
искусственного интеллекта – основная
область приложения функционального и
логического программирования
Под термином
системы искусственного интеллекта
(СИИ) понимаются кибернетические системы,
моделирующие некоторые стороны
интеллектуальной деятельности человека
– логическое, аналитическое мышление.
Задачей-максимум в области СИИ можно
считать понимание принципов и механизмов
интеллектуальной деятельности человека.
Однако в идеале вряд ли такая задача
достижима когда-либо вообще. Практически
работы в области СИИ проводились по
отдельным задачам, каждая из которых
предполагала имитирование отдельной,
строго ограниченной области интеллектуальной
деятельности. Ниже следует перечень
основных из этих задач:
• проблемы
естественного языка (ЕЯ-проблемы),
основная цель – общение с ЭВМ на
естественном для человека языке;
• экспертные
системы – системы обработки данных,
основанные на знаниях и экспертных
оценках в некоторой области;
• распознавание
образов – автоматическое наблюдение
и идентификация (классификация) объектов;
Основные пути для
решения этих задач – эвристическое
программирование и с помощью
нейрокомпьютерных систем. Эвристическое
программирование предполагает описание
логической спецификации задачи. При
решении задачи с помощью нейрокомпьютерных
систем моделируется система, функционирующая
на основе имитации некоторых известных
свойств организации нервной деятельности
высших животных. В этом случае не
требуется описания логики задачи,
достаточно набора примеров, на решение
которых настраивается нейронная сеть.
Программы на
декларативных языках гораздо ближе к
логической спецификации (ЛС), чем на
любом императивном языке. В большинстве
случаев – это просто записывание
логической спецификации задачи в
терминах конкретного языка программирования.
Для большинства программных систем
искусственного интеллекта характерно
то, что они имеют дело со сложными
проблемами, которые недостаточно хорошо
понимаемы. Для многих проблем искусственного
интеллекта не существует четко заданных
алгоритмических решений, но они могут
быть исследованы с помощью механизмов
символических рассуждений.
Разработка
естественно-языковых интерфейсов и
машинный перевод. В настоящее время
используется более сложная модель,
включающая анализ и синтез
естественно-языковых сообщений. Модель
состоит из нескольких блоков:
морфологический анализ – анализ слов
в тексте; синтаксический анализ – анализ
предложений, грамматики и связей между
словами; семантический анализ – анализ
смысла каждого предложения на основе
некоторой предметно-ориентированной
базы знаний; прагматический анализ —
анализ смысла предложений в окружающем
контексте на основе собственной базы
знаний. Синтез включает аналогичные
этапы, но несколько в другом порядке.
Сферы применимости
функционального и логического
программирования
Учитывая положения,
изложенные в предыдущих параграфах
можно определить признаки функциональных
задач, которые целесообразно решать с
использованием средств функционального
или логического программирования.
Поскольку четких и однозначных
рекомендаций по выбору стиля
программирования в общем случае
рассмотрения функциональной задачи
нет, можно привести определенный набор
эвристических правил, позволяющих
определиться при выборе подходов к
решению конкретной задачи. Языки
функционального и логического
программирования следует применять в
следующих случаях:
• алгоритм решения
задачи неизвестен или его разработка
сопряжена со значительными трудозатратами;
• задача не критична
по затратам ресурсов вычислительной
системы, но требует больших затрат
времени программиста.
Функциональное и
логическое программирование предоставляют
в распоряжение программиста средства
высокоуровневой разработки программного
обеспечения, применяемые для решения
специфичных задач в основном из области
искусственного интеллекта и символьных
вычислений. Функциональное и логическое
программирование нецелесообразно
применять при решении задач численных
вычислений, так как большинство этих
задач имеют достаточно хорошо разработанный
алгоритм и критичны по затратам
вычислительных ресурсов (оперативной
памяти и времени счета).
Выводы
Императивная
парадигма ориентируется на спецификацию
путей получения решения, а декларативная
– на спецификацию искомого решения.
В функциональном
программировании искомое решение
описывают с помощью функций, в логическом
программировании – с помощью логических
отношений.
Функциональное и
логическое программирование предназначены
для искусственного интеллекта и
символьных вычислений.
Логическая
программа
– это множество аксиом и правил, задающих
отношения между объектами. Вычислением
логической программы является вывод
следствий из программы. Программа задает
множество следствий, которое и представляет
собой значение программы. Искусство
логического программирования состоит
в построении
ясных и изящных программ с требуемым
значением.
Основные
конструкции логического программирования
–
термы и утверждения
– заимствованы
из логики. Имеются три
основных вида утверждений: факты, правила
и вопросы.
Имеется единственная структура
данных: логический терм.
Факты
Простейшим
видом утверждения является факт.
Факты используются для констатации
того, что выполнено некоторое отношение
между объектами. Например:
отец(авраам,
исаак).
Этот
факт утверждает, что Авраам является
отцом Исаака или, что выполнено отношение
отец между индивидами, названными авраам
и исаак. Другое название для отношения
– предикат.
Имена индивидов называются атомами.
Аналогично факт плюс(2,3,5)
означает, что имеет место отношение «2
плюс
3
равно 5» Известно отношение плюс
может быть задано с помощью множества
фактов определяющих таблицу сложения.
Вот начальный фрагмент таблицы:
плюс(0,0,0), плюс(0,1,1), плюс(0,2,2), плюс(0,3,3).
плюс(1,0,1), плюс(1,1,2), плюс(1,2,3), плюс(1,3,4).
отец(фарра,
авраам). мужчина(фарра).
отец(фара,нахор). мужчина(авраам).
отец(фарра,аран). мужчина(нахор).
отец(авраам,исаак). мужчина(аран).
отец(аран,лот) мужчина(исаак).
отец(аран,милка). мужчина(лот).
отец(аран,иска).
женщина(сара).
мать(сара,исаак). женщина(милка).
женщина(иска).
Программа
1.1.
База данных библейской семьи.
Конечное
множество фактов образует программу.
Это простейший вид логической программы.
Множество фактов, с другой стороны,
составляет описание ситуации. Такой
подход лежит в основе программирования
баз данных, рассматриваемого в следующей
главе. Пример базы данных семейных
отношений в Библии приведен в программе
1.1.
Предикаты отец, мать, мужчина и женщина
выражают очевидные отношения.
Вопросы
Второй
формой утверждения в логической программе
является вопрос.
Вопрос – это средство извлечения
информации из логической программы. С
помощью вопроса выясняется, выполнено
ли некоторое отношение между объектами.
Например, с помощью вопроса отец
(авраам,исаак)?
выясняется, верно ли, что выполнено
отношение отец
между объектами авраам
и
исаак?
Исходя из фактов программы
1.1,
ответ на этот вопрос – да.
Синтаксически
вопросы и факты выглядят одинаково,
однако их можно различить по контексту.
В тех случаях, когда возможна
неоднозначность, конец факта будет
обозначаться точкой, а конец вопроса
–
вопросительным знаком. Объект без точки
и вопросительного знака мы называем
целью. факт Р.
утверждает, что цель Р
является истинной. В вопросе Р?
спрашивается, является ли истинной цель
Р.
Простой
вопрос
состоит из одной цели.
Что
касается программы, то поиск ответа на
вопрос состоит в том, чтобы определить,
является ли вопрос логическим следствием
программы. Логические следствия выводятся
путем применения правил. Простейшее
правило вывода совпадение:
из Р выводимо Р. Вопрос является логическим
следствием тождественного с ним факта.
Если
используется программа, содержащая
факты, подобно программе
1.1,
то процедура поиска ответа на простой
вопрос выполняется непосредственно. В
программе ищется факт, предполагаемый
в вопросе. Если факт, тождественный
вопросу, найден, то ответ – да.
Ответ
нет
дается в том случае, когда факт,
тождественный вопросу, не найден,
поскольку данный факт не является
логическим следствием программы. Такой
ответ не подвергает сомнению истинность
вопроса, он просто показывает, что нам
не удалось доказать истинность вопроса
с помощью программы. На оба вопроса –
женщина
(авраам)?
и плюс(1,0,2)?
программа
1.1
ответит нет.
Логические
переменные, подстановки и примеры
Логические
переменные служат для обозначения
неопределенных объектов и соответственно
этому используются. Рассмотрим их
применение в вопросах. Предположим, мы
хотим выяснить, чьим отцом был авраам.
Для этого можно задавать вопросы: отец
(авраам, лот)?,
отец
(авраам, милка)?...,
отец (авраам, исаак)?,...
до тех пор, пока не будет получен ответ
да. С помощью переменной реализуется
более удобный способ поиска ответа.
Вопрос формулируется в виде отец
(авраам,
X)?.
Ответом
на вопрос является Х
=
исаак.
Переменные
в данном случае служит для представления
совокупности вопросов. Как
будет объяснено в дальнейшем, с помощью
вопроса, содержащего переменную,
выясняется, имеется ли такое значение
переменной, при котором вопрос будет
логическим следствием программы.
Использование
переменных в логических программах
отличается от использования переменных
в традиционных языках программирования.
В логических программах переменная
обозначает неопределенный, но единственный
объект, а не некоторую область памяти.
Введя
переменные, мы можем определить
единственную структуру данных в
логических программах – термы.
Определение термов индуктивно. Константы
и переменные являются термами. Кроме
того, термами являются составные термы,
или структуры. Составной
терм
содержит функтор
(называемый главным функтором терма) и
последовательность из одного или более
аргументов, являющихся термами. Функтор
задается своим именем, которое суть
атом, и своей арностью,
или числом аргументов. Синтаксически
составные термы имеют вид f(t
,t
,…t
),где
f
– имя n-арного
функтора, а t
– аргументы. Примеры составных термов:
s(0),
горячий (молоко), имя (джон, доу), list(a,
list
(b,
nil)),
foo(X)
и tree(tree(nil,3,nil),
5,R).
Вопросы,
цели и вообще термы, в которые не входят
переменные, называются основными.
Термы, содержащие переменные, называются
неосновными.
Так, foo
(a,b)
– основной терм, a
bar(X)
–
нет.
• Определение.
Подстановкой
называется конечное (возможно, пустое)
множество пар вида
X
=
t
где
X
–
переменная и t
– терм;
X
X
,
при i
j
и
X
не входит в t
при любыхi
и j.
•
Примером
подстановки, состоящей из одной пары,
может служить
{X =
исаак}.
Подстановки могут применяться к термам.
Результат применения подстановки
к терму А, обозначается А,
есть терм, полученный заменой каждого
вхождения переменной Х в А на t
для каждой пары вида Х
=
t
из
.
Результат
применения
{X =
исаак}
к терму отец
(авраам,
X)
есть терм отец(авраам,
исаак).
• Определение:
А называется примером
В, если найдется такая подстановка
,
что
А
=
B.
•
По
определению цель отец
(авраам, исаак)
является примером терма отец
(авраам,
X).
Аналогично
мать(
сара, исаак)
– пример терма мать
(X,
Y)
при подстановке
{X
=
сара, Y=
исаак}.
Экзистенциальные
вопросы
В
логических терминах переменные в
вопросах связаны квантором существования
это означает на интуитивном уровне, что
вопрос отец(авраам,
X)?
следует читать: «Существует ли такое
X,
что авраам
является отцом X».
В общем случае вопрос Р(Т
T
,…,T
)?,
содержащий переменные Х
,X
,
…,X
.
означает следующее: «Существуют ли
такие X
,Х
,…,X
,
что p(T
,T
,…,T
)».
Для удобства квантор существования
обычно не пишется.
Введем
еще одно правило вывода – обобщение:
при любой подстановке
экзистенциальный вопрос Р логически
следует из примера Р.
Из факта отец(авраам,
исаак)
следует существование такого
X,
что истинно отец(авраам,
X),
а именно Х
=
исаак.
Процедура
поиска ответа на экзистенциальный
неосновной вопрос при использовании
программы, состоящей из фактов, сводится
к поиску факта, являющегося примером
вопроса. Ответом, или решением
,
будет такой пример. Ответ нет
дается, если подходящего факта нет в
программе.
Поиск
ответа на неосновной вопрос представляет
собой вычисление, выходом которого
является пример вопроса. Иногда мы
изображаем этот пример с помощью
подстановки, применение которой к
вопросу и дает решение.
Экзистенциальный
вопрос в общем случае может иметь
несколько решений. Из программы
1.1
ясно, что Аран – отец троих детей.
Следовательно, вопрос отец(аран,
X)?
имеет решения {Х=лот},
{X=милка},
{X=иска}.
Другим вопросом, обладающим множеством
решений, является плюс(X,Y,4)?,
в котором ищутся числа, дающие в сумме
4.
Решениями, например, будут
{X =
0, У
=
4} и
{X =
1, Y=
3}.
Обратите внимание, что различным
переменным X
и Y
могут соответствовать различные объекты.
Интересным
вариантом последнего вопроса является
(плюс
X,
X,
4)?,
в котором требуется, чтобы два числа,
дающие в сумме
4,
совпадали. Имеется единственный ответ
– {X
= 2}.
Универсальные
факты
Переменные
также полезны и в фактах. Предположим,
что все библейские персонажи любят
гранаты. Вместо того чтобы включать
соответствующий факт для каждого
индивида:
любит(авраам,
гранаты).
любит(сара,
гранаты).
все
это можно выразить универсальным фактом
любит(X,
гранаты).
В данном случае переменные
позволяют выразить совокупность многих
фактов.
Факт умножить(0,
X,
0)
объединяет все факты, утверждающие, что
0,
умноженный на любое число, дает
0.
Переменные
в фактах неявно связаны квантором
общности; это на интуитивном уровне
означает, что факт любит(X,
гранаты)
утверждает, что для всех Х справедливо:
X
любит гранаты. В общем случае факт
p(T
,T
,…,T
).
следует понимать так. что при любых
значениях переменных X
,…,X
,
где
X
–переменные,
входящие в факт p(T
,T
,…,T
).
выполнено. Естественно, из факта с
квантором общности можно вывести любой
пример факта. Например, из любых(X,
гранаты)
следует любит(авраам,
гранаты).
Это
– третье правило вывода, называемое
конкретизацией,
из утверждения Р
с квантором общности выводится пример
Р
при любой подстановке
.
Как
и в случае вопроса, можно добиться, чтобы
два неопределенных объекта, обозначенных
переменными, совпадали – для этого
нужно использовать имя одной и той же
переменной. Факт плюс(0,
X,
X)
означает, что
0
является левой единицей по сложению.
Это следует понимать так, что при всех
значениях
X, 0
плюс X
равно
X. Аналогичное
использование переменных возникает
при переводе фразы «каждый любит себя»
в факт любит(X,
X).
Поиск
ответа на основной вопрос при использовании
факта с квантором общности происходит
непосредственно. Ищется факт, для
которого вопрос является примером.
Например, ответом на вопрос плюс(0,
2, 2)
на основе факта плюс(0,
X,
X)
будет
да.
Поиск ответа на неосновной вопрос при
использовании неосновных фактов требует
нового понятия: общий пример двух термов.
Определение.
С называется общим
примером
термов А и В. если С есть пример А и С
есть пример B.
Иными словами, если найдутся такие
подстановки
и
,
что С
=A
синтаксически совпадает с В
.
Например,
цели плюс(0,
3, Y)
и плюс(0,
X,
X)
имеют общий пример плюс(0,
3, 3).
Применения подстановки {Y
=
3}
к плюс(0,
3, Y)
и подстановки
{X = 3}
к плюс(0,
X,
X)
приводят к плюс(0,
3, 3).
В
общем случае при поиске ответа на вопрос
с использованием факта ищется общий
пример вопроса и факта. Если общий пример
существует, то он и будет, ответом. В
противном случае ответ – нет.
Ответ
на экзистенциальный вопрос на основе
универсального факта с использованием
общего примера требует двух логических
выводов. Факт выводится из примера с
помощью правила конкретизации, а пример
выводится из вопроса с помощью правила
обобщения.
Конъюнктивные
вопросы и общие переменные
Важным
обобщением обсуждавшихся до сих пор
вопросов являются конъюктивные
вопросы
.
Конъюнктивные вопросы
–
это конъюнкция целей, поставленная в
виде вопроса, например:отец(фара,
X),
отец(X,
Y)
или в общем виде: Q
…Q
.
Простые вопросы – это частный случай
конъюнктивных вопросов с единственной
целью. Логически вопрос состоит в
выводимости конъюнкции из программы.
Мы всюду используем
«,»
для обозначения логического «и». Не
следует путать запятую, отделяющую
аргументы цели, с запятой, отделяющей
цели и обозначающей конъюнкцию.
В
простейшем конъюнктивном вопросе все
цели простые, например, отец
(авраам, исаак), мужчина(лот)?
Ясно, что ответ на этот вопрос, исходя
из программы
1.1, – да,
так как обе цели являются фактами
программы. Вообще на вопрос Q
…Q
?
в
котором каждое Q
,
– основная цель, ответом, исходя из
программы P
будет да,
если каждое Q
выводится из P.
Таким образом, конъюнкция основных
вопросов не очень интересна.
Конъюнктивные
вопросы представляют интерес в тех
случаях, когда имеются одна или более
общие
переменные,
т.е. переменные, входящие в две различные
цели вопроса. Примером служит вопрос
отец
(аран, X),
мужчина(X)?
О6ластью
переменной в конъюнктивном вопросе
является вся конъюнкция. Таким образом,
вопрос p(X),q(X)?
означает: «Существует ли такое
X,
что
p(X)
и q(X)
одновременно?»
Как и в простых вопросах, переменные в
конъюнктивных вопросах неявно связаны
квантором существования.
Общие
переменные используются для ограничения
простых вопросов путем сужения области
значения переменных. Мы уже рассматривали
пример с вопросом плюс(X,
X,
4)?,
в котором поиск чисел, дающих в сумме
4,
был ограничен тем, что числа должны быть
равными. Рассмотрим вопрос отец(аран,
X),
мужчина(X)?
В этом случае решения вопроса
отец(аран,
X)?
ограничены детьми мужского пола.
Программа 1.l
показывает, что существует единственное
решение {X
=
лот}. С другой стороны, данный вопрос
можно рассматривать как ограничение
решений вопроса мужчина(X)?
множеством индивидов, отцом которых
является Аран.
Несколько
иное использование общих переменных
демонстрируется в вопросе отец(фарра,
X),
мужчина(X,
Y)?.
С одной стороны, вопрос ограничивает
сыновей Фарры теми, кто сам является
отцом. С другой стороны, ищутся индивиды,
чьи отцы были сыновьями Фарры. Имеется
несколько решений, например:
{X = авраам,
Y
=
исаак} и {X
=
аран,
Y=
лот}.
Конъюнктивный
вопрос логически следует из программы
Р, если все цели
–
следствия Р, причем общим переменным в
разных целях сопоставлено одно и то же
значение. Достаточное условие выводимости
состоит в существовании основного
примера вопроса, являющегося следствием
P.
Из такого примера вопрос может быть
получен с помощью обобщения.
Процедура
поиска решения конъюнктивного вопроса
A
,A
,…,A
с помощью программы Р состоит в нахождении
такой подстановки
,
что
A
и …A
будут основными примерами фактов из Р.
То, что одна и та же подстановка применяется
ко всем целям, обеспечивает единое
соответствие переменным в вопросе.
Рассмотрим, например, вопрос
отец(аран,X)?мужчина(X)?
при использовании программы
1.1.
Применение подстановки {X
=
лот}
к вопросу дает основной пример
отец(аран,лот),мужчина(лот),
который является следствием программы.
Правила
Интересные
конъюнктивные вопросы сами по себе
определяют отношения. Вопрос
отец(аран,X),мужчина(X)?
выражает свойство быть сыном Арана.
Вопрос отец(фарра,X),отец(X,Y)?
относится к внукам Фарры. Так мы приходим
к третьему и самому важному виду
утверждения в логическом программировании
– к правилу, позволяющему определять
новые отношения в терминах существующих
отношений.
Правила
–
это утверждения вида
A
B
,B
,…B
где
n≥
0.
A
называется заголовком
правила, а последовательность B
– телом
правила.
Как A,
так и B
;
должны быть целями. Правила, факты и
вопросы называются также хорновыми
предложениями
или просто
предложениями.
Заметим, что факт – это частный случай
правила при n=0.
Факты называются также единичными
предложениями.
Кроме того, имеется специальное название
для правил, тело которых состоит из
одной цели, т.е. для случая n
= 1.
Такие предложения называются
итерационными
предложениями.
В правилах, как и в фактах, переменные
связаны кванторами общности, область
действия кванторов – все правило.
Правило,
выражающее свойство быть сыном:
сын(X,Y)отец(Y,X),мужчина(X)
Аналогично
можно определить свойство быть дочерью:
дочь(Х,Y)
отец(Y,Х),женщина(Х).
Правило
для отношения быть дедушкой:
дедушка(Х,Z)
отец(Х,Y),отец(Y,Z).
Возможны
два способа интерпретации правил. При
первом правила используются для
построения новых и сложных вопросов в
терминах простых вопросов. Вопрос
сын(X,аран)?
в программе, содержащей приведенное
выше правило для отношения сын,
переводится в соответствии с этим
правилом в вопрос отец(аран,X),мужчина(X)?
и решается как и раньше. Новый вопрос,
включающий отношение сын,
строится из простых вопросов, содержащих
отношения отец
и
мужчина.
Такая интерпретация правил сводится к
процедурному истолкованию правил.
Процедурное истолкование правила для
отношения дедушка
состоит в следующем: «Для ответа на
вопрос, является
ли
X
дедушкой Y
ответьте на конъюнктивный вопрос,
является .ли X
отцом
Z
и Z
отцом
Y».
Второй
способ основан на интерпретации правил
как логических аксиом. Обратная стрелка
используется для обозначения логического
следования. Правило для отношения сын
понимается так: «X
– сын Y
если Y –
отец X
и Х – мужчина». Здесь правила используются
для построения новых или сложных
отношений на основе других, более простых
отношений. Предикат сын
определяются через предикаты отец
и
мужчина.
Соответствующее понимание правила
известно как декларативное понимание.
Декларативное понимание правила для
отношения дедушка состоит в следующем:
«Для всех X,
Y
и
Z,
если
X – отец Z
и
Z
– отец Y,
то Х – дедушка Y».
Хотя
формально все переменные в предложении
связаны квантором общности, мы будем
иногда говорить о переменных, входящих
лишь в тело, а не в заголовок предложения,
как если бы они были связаны в теле
квантором существования. Например,
правило для отношения дедушка
можно понимать так: «Для всех X
и Y,
Х – дедушка Y,
если найдется такое
Z,
что Х – отец
Z
и
Z – отец
Y».
Мы не приводим обоснования подобной
словесной трансформации и рассматриваем
ее как некоторое удобство чтения.
Для
введения правил в наше рассмотрение
логического вывода потребуется закон
modus
ponens.
Modus
ponens
утверждает, что из В и A
В следует
A.
Определение.
Обобщенный закон modus
ponens
утверждает, что из правила
R=(A
B
,B
,…B
)
и фактов
B
B
…
B
выводится
A’
при условии, что
A
B
,B
,…,B
является
примером R.
Правила
совпадения и конкретизации являются
частными случаями обобщенного закона
modus
popens.
Теперь
все готово для полного определения
понятия логической программы и
соответствующего понятия логического
следствия.
Определение.
Логическая программа – это конечное
множество правил.
Определение.
Цель G
с кванторами существования является
логическим следствием программы Р, если
в Р найдется такое предложение с основным
примером A
B
,B
,…B
,
n0,
B
,…,B
– логические следствия Р и A
– пример G.
Заметим,
что цель С логически следует из программы
Р тогда и только тогда, когда G
может быть выведена из Y
с помощью конечного числа применений
обобщенного правила modus
ponens.
Рассмотрим
вопрос сын(S,аран)?
относительно программы
1.1,
расширенной правилом для отношения
сын.
Применение подстановки {X
=
лот,
Y
=
аран}
к данному правилу приводит к примеру
сын(лот,аран)отец(аран,лот),
мужчина(лот).
Обе цели в теле правила являются фактами
программы
1.1.
Таким образом, из обобщенного modus
ponens
следует ответ S
=
лот.
Процедура
поиска ответа на вопрос отражает
определение логического следования.
Угадываются основной пример цели и
основной пример правила, далее рекурсивно
ищется ответ на конъюнктивный вопрос,
соответствующий телу этого правила.
Доказательство цели A
в программе Р сводится к выбору правила
A
B
,B
,…B
в P
и указанию такой подстановки
,
что
A = A
и B
–
основные цели при 1il.
Далее рекурсивно доказывается каждая
цель B
.
В такой процедуре могут возникать сколь
угодно длинные цепочки доказательств.
В общем случае угадать нужный основной
пример и выбрать должное правило сложно.
Правило,
сформулированное для описания отношения
сын, корректно, но не является полным
описанием соответствующего понятия.
Мы не сможем, например, заключить, что
Исаак был сыном Сары. Не было указано,
что ребенок является сыном, как отца,
так и матери. Можно добавить новое
правило, описывающее данное понятие, а
именно:
сын(Х,Y)
мать (Y,X),мужчина
(X).
Аналогично
определение отношения внук
требует четырех правил, включающих оба
случая – отец и мать:
внук
(X,
Y)
отец (Y,
Z),отец
(Z,
X).
внук(Х,
Y)
отец(Y,
Z),мать(Z,
X).
внук(Х,
Y)
мать(Y,Z),отец(Z,
X).
внук(Х,
Y)
мать(Y,
Z),
мать(Z,
Х).
Имеется
лучший, более компактный способ задания
этих правил. Нам нужно задать отношение
родитель,
подходящее для отца и для матери. Частично
искусство логического программирования
и состоит в определении промежуточных
предикатов, дающих полную и изящную
аксиоматизацию некоторого отношения.
Правило, описывающее отношение родитель,
строится непосредственно, исходя из
того, что родитель является или отцом,
или матерью. Логические программы могут
включать альтернативные определения
или, более формально, – дизъюнкцию,
применяя альтернативные правила, как
в случае отношения родитель:
родитель(Х,
Y)
отец(Х, Y).
родитель(Х,
Y)
мать(Х, Y).
Правила
для отношений сын
и внук
теперь запишутся так:
сын(Х,
Y)
родитель (Y,
X),
мужчина
(X).
внук(X,
Y)
родитель(Y,
Z),родитель(Z,
X)
Совокупность
правил с одним и тем же предикатом в
заголовке, такая, как пара правил для
родителей, называется процедурой.
Позже мы увидим, что при операционной
интерпретации этих правил в Прологе
подобные наборы правил действительно
аналогичны процедурам или подпрограммам
в традиционном программировании.
Простой
абстрактный интерпретатор
Операционная
процедура поиска ответа на вопрос была
неформально описана в предыдущих
разделах. Углубляясь в детали, рассмотрим
абстрактный интерпретатор логических
программ. Поскольку обобщенное правило
modus
ponens
ограничено применением к основным
целям, интерпретатор отвечает лишь на
основные вопросы.
Абстрактный
интерпретатор выполняет вычисления с
ответами да/нет. Он получает программу
Р и основной вопрос Q
и дает ответ да,
если
Q
выводимо из Р, и ответ нет
в противном случае. Кроме того, если
цель невыводима, интерпретатор может
вообще не завершить работу. В этом случае
не выдается никакого ответа. Рис.
1.1
демонстрирует работу интерпретатора.
Вход:
Основной вопрос
Q
и программа P
Результат:
да,
если найден вывод
Q
из программы P,
Алгоритм: нет
в противном случае.
Положить
резольвенту равной
Q,
пока
резольвента A
,…A
не пуста начало
выбрать
цель
A
,
1
i
n
и
такой основной пример предложения A
B
,B
,…B
,k0
в P
что A
=
A
;
(если
такого предложения нет, то выйти из
цикла); положить резольвенту равной
A
,…A
,B
,…B
,A
,…,A
конец
если
резольвента пуста, то результат – да,
иначе результат – нет.
Рис.
1.1.
Абстрактный интерпретатор логических
программ.
На
любой стадии вычислений существует
текущая цель, называемая резольвентой.
Протоколом
интерпретатора называется последовательность
резольвент, которые строятся в процессе
вычисления, вместе с указанием сделанного
выбора. Рассмотрим вопрос сын(лот,аран)?
при использовании программы
1.2,
являющейся подмножеством фактов
программы
1.1,
которое дополнено правилами, определяющими
отношения сын
и дочь.
На рис.
1.2
приводится протокол поиска ответа.
Протокол
в неявном виде содержит вывод основного
вопроса в программе. Удобнее изображать
вывод в виде дерева вывода. Введем
необходимые понятия.
Вход:
сын (лот, аран)? и программа 1.2
Резольвента
не пуста
Выбор:
сын (лот, аран) (единственный выбор)
Выбор:
сын (лот, аран)
отец (аран, лот), мужчина (лот).
Новая
резольвента: отец (аран, лот), мужчина
(лот)?
Резольвента
не пуста
Выбор:
отец (аран, лот)
Выбор:
отец (аран, лот).
Резольвента
не пуста
Выбор:
мужчина (лот)
Выбор:
мужчина (лот).
Новая
резольвента пуста
Результат:
да
Рис.1.2.
Протокол интерпретатора
отец(аврам,
исаак). мужчина(исаак).
отец(аран,
лот) мужчина(лот)
отец(аран,
милка). женщина(милка).
отец(аран,
иска). женщина(иска).
сын(Х,Y)
отец(Y,Х),
мужчина(Х).
дочь(Х,Y)
отец(Y,Х),
женщина(Х).
Программа
1.2.
Отношения в библейской семье.
Определение:
Основная
редукция
цели G
с помощью программы Р состоит в замене
цели
G
телом того примера правила из Р, чей
заголовок совпадает с данной целью.
Редукция
является главным вычислительным шагом
в логическом программировании. Она
соответствует применению обобщенного
правила modus
ponens,
а также одной итерации цикла «пока» в
абстрактном интерпретаторе. Замененная
при редукции цель называется снятой,
появившиеся цели называются производными.
Применим
данные понятия к анализу протокола на
рис.
1.2.
В протоколе имеются три редукции. Первая
редукция снимает цель сын
(лот,аран)
и строит две производные цели – отец
(аран.лот)
и мужчина
(лот).
Следующая редукция применяется к цели
отец(аран.лот)
и не дает производных целей. Третья
редукция также не дает производных
целей при снятии цели
мужчина (лот).
Дерево
вывода
состоит из вершин и ребер и изображает
цели, снимаемые в процессе вычисления.
Корень дерева вывода в случае простого
вопроса совпадает с этим вопросом.
Вершины дерева соответствуют целям,
снимаемым в процессе вычисления.
Направленное ребро, ведущее из одной
вершины в другую, соответствует переходу
от снимаемой цели к производной. Деревом
вывода для конъюнктивного вопроса
является просто совокупность деревьев
вывода для отдельных целей в конъюнкции.
Рис.
1.3
изображает дерево вывода для протокола,
приведенного на рис.
1.2.
Рис.
1.3.
Простое дерево вывода.
В
интерпретаторе имеются два неопределенных
выбора: выбор цели из резольвенты для
снятия и выбор предложения (и подходящего
основного примера) для редукции. Эти
два выбора имеют различную природу.
Выбор
цели для снятия произволен. В любой
имеющейся резольвенте все цели должны
быть сняты. Можно показать, что порядок
снятия при построении доказательства
не имеет значения. Иными словами, если
существует доказательство цели, то оно
является доказательством независимо
от того, в каком порядке применяются
редукции. В терминах дерева вывода это
означает, что порядок ветвей несущественен.
Наоборот,
выбор предложения и подходящего основного
примера является решающим. В общем
случае существует несколько вариантов
предложений и бесконечно много основных
примеров. Выбор производится
недетерминировано. Понятие
недетерминированного выбора применяется
весьма плодотворно в определении многих
моделей вычислений, например, в конечных
автоматах и машинах Тьюринга.
Недетерминированный выбор состоит в
неопределенном выборе из некоторого
числа альтернатив, который предположительно
производится методом «предвидения»;
если только некоторые из альтернатив
приводят к успешному вычислению (в нашем
случае – к нахождению доказательства),
то одна из них и будет выбрана. Формально
понятие определяется следующим образом:
вычисление, содержащее недетерминированный
выбор по определению заканчивается
успешно, если существует последовательность
недетерминированных выборов, приводящая
к успеху. Конечно, ни одна из реальных
машин не может непосредственно реализовать
это определение.
Интерпретатор,
представленный на рис.
1.1,
может быть расширен так, чтобы он давал
ответы и на неосновные экзистенциальные
вопросы. Для этого следует ввести
дополнительный шаг: угадывание основного
примера вопроса. Этот шаг подобен тому,
на котором интерпретатор угадывает
основные примеры правил. Угадать
правильный основной пример в общем
случае непросто, так как это означало
бы знание результата вычисления до его
выполнения.
Чтобы
избавиться от ограничений, налагаемых
основными примерами, и бремени угадывания,
потребуются новые понятия.
Деревья
вывода позволяют использовать важную
меру сложности – число вершин в дереве.
Она показывает, сколько шагов редукции
выполнялось при вычислении.
Значение
логической программы
Откуда
известно, что логическая программа
вычисляет то, что мы хотим? Корректна
она или некорректна? Для ответа на
подобные вопросы мы должны определить,
что же является значением логической
программы. Дав такое определение, можно
будет проверять, совпадает ли значение
программы с предположительным значением.
• Определение:
Значением
логической
программы Р, обозначаемым М(Р), называется
множество выводимых из Р основных
единичных целей.
•
Из
этого определения следует, что значением
логической программы, построенной
просто из основных фактов, такой, как
программа
1.1,
является сама программа. Другими словами,
для простых программ программа «значит
ровно то, что написано». Рассмотрим
программу
1.1,
расширенную двумя правилами определения
отношения родитель.
Что будет ее значением? Оно содержит
кроме фактов об отцах и матерях, явно
указанных в программе, также все факты
вида родитель
(X,
Y)
Для каждой пары Х и Y,
такой, что факт oтец(X,Y)
или мать(Х,Y)
присутствуют в программе. Этот пример
показывает, что значение программы в
явном виде содержит все то, что программа
утверждает неявно.
Если
предположить, что подразумеваемое
значение программы также задано в виде
множества основных единичных целей, то
можно спросить, как соотносятся
действительное и подразумеваемое
значения программы. Мы
можем
проверить, все ли утверждения программы
корректны или вычисляет ли программа
все, что нам требуется.
Неформально мы
называем программу корректной
относительно некоторого заданного
значения М,
если значение М
(Р) программы
Р
является подмножеством М.
Иными словами, корректная программа не
вычисляет того, что не требуется.
Программа полна относительно М,
если М
есть подмножество М(Р),
т.е. полная программа вычисляет все, что
задано. Следовательно, программа Р
корректна и полна относительно заданного
значения М, если М
= М(Р).
В тех случаях,
когда из имен предикатов или констант
интуитивно ясно, что является их
значением, будем считать в данной книге,
что подразумеваемое значение определяется
в программе смыслом имен.
Например, если в
программе для отношения сын
содержится только первая аксиома,
которая ссылается на отношение отец,
то программа неполна относительно
интуитивно понимаемого значения
отношения сын,
так как цель сын(исаак,сара)
невыводима.
Если к программе добавить правило
сын(Х, Y)
мать(Х, Y),
мужчина (Y).
то получим программу,
некорректную относительно подразумеваемого
значения ввиду выводимости утверждения
сын (сара,
исаак).
Будем называть
основную цель истинной
относительно подразумеваемого значения,
если цель входит в данное значение, и
ложной
в противном случае. В тех случаях, когда
подразумеваемое значение определяется
именами предикатов и констант, содержащихся
в программе, цели, входящие в такие
значения, будем называть просто истинными.
Резюме
Основная структура
в логических программах – это терм.
Терм
есть константа, переменная или составной
терм. Константы обозначают конкретные
объекты, такие, как целые числа и атомы,
в то время как переменная обозначает
единственный, но неопределенный объект.
Символом атома может служить любая
последовательность букв, которая берется
в кавычки, если ее можно спутать с другими
символами (такими, как переменные или
целые числа). Символы переменных
отличаются начальной прописной буквой.
Составной терм
строится из функтора (называемого
главным функтором терма) и последовательности
из одного или более термов, называемых
аргументами.
Функтор
задается
своим именем, т.е. некоторым атомом, и
арностью,
или числом аргументов. Константы
рассматриваются как 0-арные функторы.
Синтаксически составной терм записывается
как f(t
,t
,…t
),где
f
– имя n-арного
функтора, а t
– аргументы..
Для n-арного
функтора
f
используется запись f/n.
Функторы с одинаковыми именами, но
различными арностями различны. Терм
является основным
, если в
нем не содержится переменных; в противном
случае терм неосновной.
Цели –
это атомы или составные, в общем случае
неосновные термы.
Подстановка –
это конечное (возможно, пустое) множество
пар вида Х
= t,
где X
– переменная, t
– терм,
причем переменные в левых частях пар
различны. Для любой подстановки
= {X
=
t
,X
=t
,…,X
=t
}
и терма S
терм S
обозначает результат одновременной
замены каждого вхождения в
S
переменной
X
на t
,1<i<n.
Терм
S
называется примером
терма
S.
Логическая
программа – конечное
число предложений. Предложением,
или правилом,
является замкнутое квантором общности
утверждение вида
A
B
,B
,…B
,
k0,
где
A
и
B
– цели.
Декларативное понимание такого
утверждения
– «А
следует из конъюнкции целей
B
;»,
процедурная интерпретация – «для ответа
на вопрос А
ответь на конъюнктивный вопрос B
,B
,…B
».
А называется
заголовком
предложения, последовательность B
– телом
предложения. При k
=
0 предложение
называется фактом
или единичным
предложением
и имеет запись A.,
декларативное понимание – «A
истинно», процедурная интерпретация
– «цель А
выполнена». При
k
=
1 предложение
называется итерационным.
Вопросом
называется конъюнкция вида
A
,…,A
?n>0.
где A
– цели.
Считается, что переменные в вопросе
связаны квантором существования.
Вычисление
логической
программы Р
строит пример заданного вопроса,
логически выводимый из Р.
Цель G
выводима из
Р,
если существует такой пример А
цели G,
что A
B
,…B
,
n
0, – основной пример предложения в Р
и каждое В
,
выводимо из Р.
Выводимость цели из тождественного
факта рассматривается как особый случай.
С помощью логической
выводимости индуктивно определяется
значение
программы Р.
Множество основных примеров фактов из
Р
принадлежит значению Р.
Основная
цель
G
входит в значение, если существует такой
основной пример G
B
,…B
правила из Р,
что B
,…B
входят в значение Р.
Таким образом, значение состоит из тех
основных примеров, которые выводятся
из программы.
Подразумеваемое
значение М программы Р
также задается в виде множества основных
единичных целей. Программа Р
корректна
относительно
подразумеваемого значения М,
если М(Р)
образует подмножество М.
Программа Р
полна
относительно
М, если М
– подмножество
М(Р).
Ясно,
что программа корректна и полна
относительно ее подразумеваемого
значения (наиболее желательный случай),
когда М
= М(Р).
Основная цель
называется истинной
относительно подразумеваемого значения,
если она принадлежит этому значению. В
противном случае цель называется ложной.