Логические основы систем специального назначения с элементами системного анализа

1.

«Национальный исследовательский ядерный университет «МИФИ»
ИНСТИТУТ ИНТЕЛЛЕКТУАЛЬНЫХ КИБЕРНЕТИЧЕСКИХ СИСТЕМ
КАФЕДРА «КОМПЬЮТЕРНЫЕ СИСТЕМЫ И ТЕХНОЛОГИИ»
Курсовая работа по дисциплине:
«Логические основы систем специального назначения
с элементами системного анализа»
Руководитель:
д.т.н., профессор НИЯУ МИФИ
Кулик С.Д.
Москва, 2022

2.

Содержание
1.
Введение
2.
Синтаксис и семантика Пролог-программ
3.
Расширение функционала языка на примере списков
4.
Метод резолюций
5.
Задача установления соответствия
6.
Решение числового ребуса
7.
Заключение
8.
Список использованных источников
2

3.

1. Введение
• 1956 г. — первый язык символьной обработки списков ИПЛ1 и программа “Логик-
теоретик” для автоматического доказательства теорем.
• 1957 г. — программа для игры в шахматы NSS, работающая на основе эвристики и
описания целей.
• 1960 г. — программа GPS – универсальный решатель задач.
• 1963 г. — LISP (List Processing).
• 1965 г. — работа Дж. А. Робинсона, посвященная методу автоматического поиска
доказательств в исчислении предикатов первого порядка.
• 1966 г. — язык рекурсивных функций Рефал.
• 1971 г. — язык программирования со встроенной процедурой логического вывода
PROLOG
3

4.

1. Введение
• РЕФАЛ (Рекурсивных функций алгоритмический) — один из
старейших функциональных языков программирования,
ориентированный на символьные вычисления: обработку
символьных строк (например, алгебраические выкладки); перевод
с одного языка (искусственного или естественного) на другой;
решение проблем, связанных с искусственным интеллектом.
Соединяет в себе математическую простоту с практической
направленностью на написание больших и сложных программ.
• Появился в 1966 г.
• Автор
Турчин Валентин Фёдорович
https://ru.wikipedia.org/wiki/%D0%A0%D0%95%D0%A4%D0%90%D0%9B
http://pespmc1.vub.ac.be/TURCHIN.html
4

5.

1. Введение
Кафедра №22 Кибернетика НИЯУ МИФИ
1970-1980 гг.
• В эти годы встала проблема создания инструментария для
«вычислительных решений». Это ассоциировалось с проблемой
создания трансляторов с языков программирования. Для
кафедры была открыта совершенно новая область теоретических
исследований в виде теории формальных грамматик, так и
практическую область создания трансляторов.
• На кафедре была создана методика разработки трансляторов с
использованием языка РЕФАЛ и разработано несколько
трансляторов, среди которых следует отметить транслятор с языка
Simula — прообраза современных объектно-ориентированных
языков
5

6.

1. Введение
• Пролог (англ. Prolog, от Programing in Logic) — это язык
программирования, предназначенный для обработки символьной
нечисловой информации.
• Основная парадигма — логическое программирование.
• Сегодня существует довольно много реализаций Пролога.
Наиболее известные из них следующие:
SWI Prolog, BinProlog, AMZI-Prolog, Arity Prolog, CProlog, Micro
Prolog, МПролог, Prolog-2, Quintus Prolog, SICTUS Prolog, Silogic
Knowledge Workbench, Strawberry Prolog, UNSW Prolog.
6

7.

2. Синтаксис и семантика Пролог-программ
Описание фактов:
терм
старше
(коля, маша).
имя отношения
(функтор)
аргументы
старше(коля, дима).
старше(маша, саша).
7

8.

2. Синтаксис и семантика Пролог-программ
Запросы:
?- старше(коля, маша).
true.
?- старше(саша, маша).
false.
Использование переменных:
?- старше(коля, X).
X = маша ;
X = дима.
8

9.

2. Синтаксис и семантика Пролог-программ
Описание правил:
младше(X, Y) :- старше(Y, X).
?- младше(маша, коля).
true.
9

10.

2. Синтаксис и семантика Пролог-программ
Ошибка рекурсии:
старше(X, Z) :- старше(X, Y), старше(Y, Z).
?- старше(саша, коля).
ERROR: Stack limit exceeded
Решение проблемы:
старше(коля, маша, факт).
старше(X, Z, правило) :- старше(X, Y, факт), старше(Y, Z, _).
?- старше(саша, коля, правило).
false.
10

11.

2. Синтаксис и семантика Пролог-программ
Объекты языка Пролог:
• Примеры атомов: анна, nil, <-->, ‘Том‘.
• Числа бывают вещественными и целыми. Используются редко.
• Переменные начинаются либо с прописной буквы, либо с символа
подчеркивания.
• Структуры состоят из нескольких компонент,
которые могут состоять из констант,
переменных или структур. Пример:
дата(1, октября, 2022).
11

12.

3. Расширение функционала языка на примере списков
Список — структура данных, представляющая собой последовательность
некоторого числа элементов.
[футбол, лыжи, теннис].
Голова
Хвост
Структуры в языке Пролог представляются в виде двоичных деревьев.
Если в качестве функтора, соединяющего Голову и Хвост взять точку, то
данный список может быть представлен так:
.(футбол, .(лыжи, .(теннис, []))).
Для разделения списка на Голову и Хвост используется оператор “|”:
[Голова | Хвост].
12

13.

3. Расширение функционала языка на примере списков
Операция конкатенации должна возвращать список, являющийся
объединением поданных на вход списков. Отношение:
конкатенация(L1, L2, L).
L1, L2 — изначальные списки, L — результирующий список.
Правило состоит из двух случаев:
конкатенация([], L, L).
конкатенация([X | L1], L2, [X | L3]) :- конкатенация(L1, L2, L3).
Проверка:
?- конкатенация([1,2,3], [2,3,4], L).
L = [1, 2, 3, 2, 3, 4].
13

14.

3. Расширение функционала языка на примере списков
Отношение подсписок проверяет, является ли список S подсписком L:
подсписок(S, L) :- конкатенация(L1, L2, L), конкатенация(S, L3, L2).
Проверка:
?- подсписок([1,2], [0,1,2,3]).
true .
14

15.

3. Расширение функционала языка на примере списков
Отношение добавления расширяет список L данным элементом X:
добавить(X, L, [X | L]).
Проверка:
?- добавить(1, [2,3], L).
L = [1, 2, 3].
15

16.

4. Метод резолюций
В основе системы программирования на языке Пролог лежит мощный решатель.
С помощью решателя находятся решения задач сформулированных на языке Пролог.
В основе этого решателя лежит специальный метод РЕЗОЛЮЦИЙ.
16

17.

4. Метод резолюций
Термины.
Атомная формула — это выражение p(t1,...,tn), где p — n-местный предикатный
символ, а t1,...,tn — термы.
Литерал — атомная формула или отрицание атомной формулы.
Дизъюнкт — это дизъюнкция конечного числа литералов.
Если дизъюнкт не содержит литералов, его называют пустым дизъюнктом #.
17

18.

4. Метод резолюций
Формулировка правила резолюций.
С1, С2 — предложения в исчислении высказываний.
P — контрарный литерал.
С1 = P ∨ C’1
С2 = ¬P ∨ C’2