The description of lists and sets of meta-language of normal forms of knowledge
Lists use for representation of various knowledge. As lists it comfortably to present formulas, functions, trees, columns, great numbers and many other difficult objects. Great number - one of the most essential structures of data, used both in mathematics, and in programming. The formalization of l...
Gespeichert in:
| Datum: | 2020 |
|---|---|
| 1. Verfasser: | |
| Format: | Artikel |
| Sprache: | Russian |
| Veröffentlicht: |
PROBLEMS IN PROGRAMMING
2020
|
| Schlagworte: | |
| Online Zugang: | https://pp.isofts.kiev.ua/index.php/ojs1/article/view/386 |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| Назва журналу: | Problems in programming |
| Завантажити файл: |  |
Institution
Problems in programming| id |
pp_isofts_kiev_ua-article-386 |
|---|---|
| record_format |
ojs |
| resource_txt_mv |
ppisoftskievua/03/59f34fd4f582274264894e6169e9f503.pdf |
| spelling |
pp_isofts_kiev_ua-article-3862020-12-02T14:52:38Z The description of lists and sets of meta-language of normal forms of knowledge Описание списков и множеств в метаязыке нормальных форм знаний Опис списків і множин в метамові нормальних форм знань Kurgaev, A.F. meta-language; set; list; predicate; recursion; definition UDC 004.424 метаязык; список; множество; предикат; рекурсия; определение УДК 004.8 метамова; список; множина; предикат; рекурсія; визначення УДК 004.424 Lists use for representation of various knowledge. As lists it comfortably to present formulas, functions, trees, columns, great numbers and many other difficult objects. Great number - one of the most essential structures of data, used both in mathematics, and in programming. The formalization of lists, list-based predicates and set-based predicates in the meta-language of normal forms of knowledge is presented, based on the known Prolog-formalizations of these concepts, which use a list-domain. Among the described list-based predicates are the following: adding an element to the list, removing an element, finding the last element of a list, finding adjacent elements in a list, concatenation of lists, reversing a list, palindrome, etc. Using the list-domain, the set-based predicates are described as follows: converting a list into a set, checking if an element is in a set, concatenation, intersection, difference, symmetrical difference, identity, complement of sets, relation of subset, proper subset. Problems in programming 2020; 1: 03-16 Предложена формализация списков, предикатов на списках и множествах в метаязыке нормальных форм знаний, базируясь на известных Пролог-формализациях этих понятий, использующих списковый домен. Среди предикатов на списках описаны: добавление элемента, удаление элемента, поиск последнего элемента, поиск соседних элементов, конкатенация списков, реверс и др. Используя списковый домен описаны предикаты на множествах: превращения списка в множество, принадлежности элемента множеству, объединения, пересечения, разности, симметрической разности, совпадения, дополнения множеств.Problems in programming 2020; 1: 03-16 Списки використовують для подання всіляких знань. У вигляді списків зручно представляти формули, функції, дерева, графи, множини й багато інших складних об'єктів. Множина – одна з найбільш важливих структур даних, використовуваних як у математиці, так і в програмуванні. Запропоновано формалізацію у метамові нормальних форм знань списків, предикатів на списках і множинах, базуючись на відомих Пролог-формалізаціях цих понять, що використовують списковий домен. Серед предикатів на списках описано: додавання елемента, видалення елемента, пошук останнього елемента, пошук сусідніх елементів, конкатенація списків, реверс, паліндром, видалення всіх входжень елемента і ін. Використовуючи списковий домен описано предикати на множинах: перетворення списку в множину, приналежність елемента множині, об'єднання, перетин, різниця, симетрична різниця, збіг, доповнення множин, відношення підмножини, власної підмножини.Problems in programming 2020; 1: 03-16 PROBLEMS IN PROGRAMMING ПРОБЛЕМЫ ПРОГРАММИРОВАНИЯ ПРОБЛЕМИ ПРОГРАМУВАННЯ 2020-02-28 Article Article application/pdf https://pp.isofts.kiev.ua/index.php/ojs1/article/view/386 10.15407/pp2020.01.003 PROBLEMS IN PROGRAMMING; No 1 (2020); 03-16 ПРОБЛЕМЫ ПРОГРАММИРОВАНИЯ; No 1 (2020); 03-16 ПРОБЛЕМИ ПРОГРАМУВАННЯ; No 1 (2020); 03-16 1727-4907 10.15407/pp2020.01 ru https://pp.isofts.kiev.ua/index.php/ojs1/article/view/386/389 Copyright (c) 2020 PROBLEMS IN PROGRAMMING |
| institution |
Problems in programming |
| baseUrl_str |
https://pp.isofts.kiev.ua/index.php/ojs1/oai |
| datestamp_date |
2020-12-02T14:52:38Z |
| collection |
OJS |
| language |
Russian |
| topic |
meta-language set list predicate recursion definition UDC 004.424 |
| spellingShingle |
meta-language set list predicate recursion definition UDC 004.424 Kurgaev, A.F. The description of lists and sets of meta-language of normal forms of knowledge |
| topic_facet |
meta-language set list predicate recursion definition UDC 004.424 метаязык список множество предикат рекурсия определение УДК 004.8 метамова список множина предикат рекурсія визначення УДК 004.424 |
| format |
Article |
| author |
Kurgaev, A.F. |
| author_facet |
Kurgaev, A.F. |
| author_sort |
Kurgaev, A.F. |
| title |
The description of lists and sets of meta-language of normal forms of knowledge |
| title_short |
The description of lists and sets of meta-language of normal forms of knowledge |
| title_full |
The description of lists and sets of meta-language of normal forms of knowledge |
| title_fullStr |
The description of lists and sets of meta-language of normal forms of knowledge |
| title_full_unstemmed |
The description of lists and sets of meta-language of normal forms of knowledge |
| title_sort |
description of lists and sets of meta-language of normal forms of knowledge |
| title_alt |
Описание списков и множеств в метаязыке нормальных форм знаний Опис списків і множин в метамові нормальних форм знань |
| description |
Lists use for representation of various knowledge. As lists it comfortably to present formulas, functions, trees, columns, great numbers and many other difficult objects. Great number - one of the most essential structures of data, used both in mathematics, and in programming. The formalization of lists, list-based predicates and set-based predicates in the meta-language of normal forms of knowledge is presented, based on the known Prolog-formalizations of these concepts, which use a list-domain. Among the described list-based predicates are the following: adding an element to the list, removing an element, finding the last element of a list, finding adjacent elements in a list, concatenation of lists, reversing a list, palindrome, etc. Using the list-domain, the set-based predicates are described as follows: converting a list into a set, checking if an element is in a set, concatenation, intersection, difference, symmetrical difference, identity, complement of sets, relation of subset, proper subset. Problems in programming 2020; 1: 03-16 |
| publisher |
PROBLEMS IN PROGRAMMING |
| publishDate |
2020 |
| url |
https://pp.isofts.kiev.ua/index.php/ojs1/article/view/386 |
| work_keys_str_mv |
AT kurgaevaf thedescriptionoflistsandsetsofmetalanguageofnormalformsofknowledge AT kurgaevaf opisaniespiskovimnožestvvmetaâzykenormalʹnyhformznanij AT kurgaevaf opisspiskívímnožinvmetamovínormalʹnihformznanʹ AT kurgaevaf descriptionoflistsandsetsofmetalanguageofnormalformsofknowledge |
| first_indexed |
2025-07-17T10:00:42Z |
| last_indexed |
2025-07-17T10:00:42Z |
| _version_ |
1850410573538263040 |
| fulltext |
Теоретичні та методологічні основи програмування
© А.Ф. Кургаев, 2020
ISSN 1727-4907. Проблеми програмування. 2020. № 1 3
УДК 004.8 https://doi.org/10.15407/pp2020.01.003
А.Ф. Кургаев
ОПИСАНИЕ СПИСКОВ И МНОЖЕСТВ
В МЕТАЯЗЫКЕ НОРМАЛЬНЫХ ФОРМ ЗНАНИЙ
Предложена формализация списков, предикатов на списках и множествах в метаязыке нормальных
форм знаний, базируясь на известных Пролог-формализациях этих понятий, использующих списковый
домен. Среди предикатов на списках описаны: добавление элемента, удаление элемента, поиск послед-
него элемента, поиск соседних элементов, конкатенация списков, реверс и др. Используя списковый
домен описаны предикаты на множествах: превращения списка в множество, принадлежности элемента
множеству, объединения, пересечения, разности, симметрической разности, совпадения, дополнения
множеств.
Ключевые слова: метаязык, список, множество, предикат, рекурсия, определение.
Введение
Список – один из самых простых и
полезных типов структур составных
объектов логического программирования,
позволяющий во многих случаях улуч-
шить «читабельность» программ. Запись
в виде списка свободна по форме и одно-
временно достаточно точна и понятна
[1–3].
Списки можно использовать для
представления всевозможных знаний.
Также они позволяют представить практи-
чески любые неоднородные и/или иерар-
хические структуры данных, возможные в
символьных вычислениях, поддерживаю-
щие функциональный стиль программиро-
вания. В виде списков удобно представ-
лять формулы, функции, деревья, графы,
множества и многие другие сложные объ-
екты [4–6].
Множество – одна из наиболее
важных структур данных, используемых
как в математике, так и в программирова-
нии. Это набор элементов, подобный спис-
ку, отличающийся от него лишь фактом
принадлежности элемента множеству [3].
В метаязыке нормальных форм зна-
ний (НФЗ) [7, 8], в отличие от ЛИСПа и
Пролога, нет такой встроенной структуры
данных, как список, эффективность кото-
рой обоснована не только теоретически, но
и обширной практикой использования
этих языков при создании систем искус-
ственного интеллекта. Тем более в мета-
языке НФЗ нет такой встроенной структу-
ры данных, как множество. Поэтому, для
практического использования метаязыка
НФЗ важно реализовать понятия списка,
множества и предикаты на списках и мно-
жествах, опираясь на стандартные домены
метаязыка НФЗ.
В качестве базовой структуры ис-
пользуем область данных из [7, 8]:
домен D представлен двумя
независимыми массивами – входным INP
и выходным OUT, с которыми связаны
переменные m и n, принимающие значения
текущих координат соответствующих
массивов;
две библиотеки одноименных
предикатов – библиотеку анализа над дан-
ными из INP и библиотеку порождения
над данными из OUT;
набор системных процедур,
управляющих этими элементами домена
D:
o RB – истинный предикат пе-
реключения библиотек;
o RIO – истинный предикат пе-
реключения массивов INP и OUT;
o UIO – истинный предикат
объединения / разделения массивов INP и
OUT.
Во всех последующих формальных
описаниях предикатов на списках и мно-
жествах использована нотация метаязыка
НФЗ [7, 8]:
1. description = determination
( determination ) ;
https://doi.org/10.15407/pp2020.01.003
Теоретичні та методологічні основи програмування
4
2. determination = negativ
nameConcept definition bodyDeterm
endDeterm;
3. negativ = inversion / true;
4. nameConcept = identifier / integer
/ chainSigns;
5. identifier = letter
(letter/decimalDigit );
6. integer = decimalDigit
(decimalDigit );
7. chainSigns = ^metaSign sign
(^metaSign sign );
8. bodyDeterm = structure /
terminal;
9. terminal = space ( space );
10. structure = singleDefinit
(separator singleDefinit );
11. singleDefinit = negativ primary
mode ( concatenate negativ primary mode);
12. primary = iterationSeq /
nameConcept / line;
13. iterationSeq = startIterationSymb
bodyDeterm endIterationSymb;
14. mode = analysis / traceAnalysis /
generation / true;
15. line = quotationMark
nameConcept quotationMark;
где definition – разделитель двух частей
определения, изображается символом '=';
separator – отношение альтернативного
выбора изображается символом '/';
concatenate – отношение конкатенации
изображается символом space ' ';
startIterationSymb, endIterationSymb – пара
скобок '(' и ')', обрамляющих итерируемый
элемент;
inversion – отношение отрицания изобра-
жается символом '^';
endDeterm – конец определения изобража-
ется символом ';';
quotationMark – текстовая кавычка, изоб-
ражается символом ''';
analysis – режим анализа изображается
символом ‘?’;
traceАnalysis – режим анализа со следом
изображается символом '#';
generation – режим порождения изобража-
ется символом '!';
letter = 'A' / 'B' / 'C' /…/ 'Z' / 'a' / 'b' / 'c' /... /
'z';
decimalDigit = '0'/'1'/'2'/'3'/'4'/'5'/'6'/'7'/'8'/'9';
sign = '-' / '&' / '%' / '$' / '@' / '~' / ':' / '<' / '>' /
… / ',' / '.' / '_';
metaSign = '(' / ')' / space / '/' / '=' / '?' / '#' / '!' /
';' / '''/ '”' ;
1. Представление задачи
В терминах метаязыка НФЗ любая
задача формулируется как доказательство
категорического суждения P(x), предикат
P которого задан именованной структурой,
а субъект (возможно, многоместный аргу-
мент x) задан последовательностью эле-
ментов, ограниченной круглыми скобками:
subject = "( )" / "(" element (","element ) ")";
Структуру термина element примем
подобной в Прологе и в нотации метаязы-
ка НФЗ [7, 8] опишем так:
element = term / list;
list = '[' list_content ']';
list_content = element (',' element) / head
comma tail / variable / true;
head = term (',' term);
comma = ',' / true;
tail = list;
term = number / variable / atom / structure;
structure = atom '(' term (',' term) ')';
variable = letter1 (letter / letter1 / number);
letter1 = A / B / C / ... / Z;
letter = a / b / c / ... / z;
number = numeral (numeral);
numeral = 0/1/2/3/4/5/6/7/8/9;
atom = letter (letter / letter1 / numeral);
E1= element;
E2= element;
E3= element;
Список – это рекурсивная структура
данных, поэтому нужны и рекурсивные
алгоритмы для его обработки. Главный
способ обработки списка – это поэлемент-
ный просмотр и обработка списка до его
исчерпания. Эти алгоритмы обычно зада-
ются двумя утверждениями: одно опреде-
ляет, что делать с пустым списком, второе
– что делать с обычным списком.
При описании любой задачи необ-
ходимо, прежде всего, определиться с ар-
гументами предиката, принять некоторую
структуру области данных, описать про-
Теоретичні та методологічні основи програмування
5
цесс анализа конкретного значения аргу-
ментов, и далее, – процесс вывода. Среди
базовых предикатов на списках: формиро-
вание, объединение списков; поиск эле-
мента в списке; вставка элемента в список
и удаление из списка и др. [9].
2. Предикаты на списках
2.1. Печать списков. Печать эле-
ментов списка в Прологе задается двумя
утверждениями:
wrіte_a_lіst([ ]).
wrіte_a_lіst([Н|Т]):- wrіte(H), nl!,
wrіte_a_lіst(Т).
/* nl - переход на новую строку */
Первое из них утверждает факт ис-
тинности для пустого списка, второе –
инициирует печать головы непустого
списка и рекурсивный вызов печати хвоста
списка. В метаязыке НФЗ этот предикат
определяется так:
wrіte_a_lіst='(' '[' L# ']' ')' viv_wrіte_a_lіst;
viv_wrіte_a_lіst = ^genL ^Х / ^stepL?
^wrіte_H nl! viv_wrіte_a_lіst;
^genL = RIO L ']'! RIO;
^stepL = Х comma L# ;
^wrіte_H = X nl!;
X = term;
L = term (',' term) / true;
Здесь, в первом утверждении опи-
сан анализ структуры аргумента предиката
wrіte_a_lіst, в процессе которого с пере-
менной L связывается исходное значение
списка, и далее, вызывается предикат
viv_wrіte_a_lіst, первая альтернатива кото-
рого утверждает, что пустой список печа-
тать не надо, а вторая альтернатива утвер-
ждает поэлементную печать головы списка
и рекурсивный вызов предиката
viv_wrіte_a_lіst на сокращенном списке.
2.2. Добавление элемента в спи-
сок. У предиката add(X,L,L1]) три аргу-
мента: добавляемый элемент X, начальный
список L и результирующий – L1. Проще
всего добавить элемент в список – вста-
вить его в самое начало, как голову нового
списка L1. В Прологе это записывают в
виде факта:
add(X,L,[X|L]).
Все варианты вывода предиката
add(X,L,L1) (добавление: известного эле-
мента X к пустому или непустому списку
L с получением неизвестного списка L1;
неизвестного элемента X к известному
списку L с получением известного списка
L1; неизвестного элемента X к неизвест-
ному списку L с получением известного
списка L1; известного элемента X к из-
вестному списку L с получением известно-
го списка L1) в метаязыке определим в
форме пяти альтернативных определений
термина add:
add = '(' X# ',' '[' ']' ','? '[' A# ']' ')' ^wrіteХS /
'(' X# ',' '[' Т# ']' ','? '[' A# ']' ')' ^wrіteAdd /
'(' A# ',' '[' L1# ']' ','? '[' L2# ']' ')' ^genL2
сontrolAdd ^wrіteХ /
'(' A# ',' '[' B# ']' ','? '[' L2# ']' ')' ^genL2
bindingХ_L1 ^wrіteVV /
'(' Х# ',' '[' L1# ']' ',' '['? L2# ']' ')' ^genL2
analysХ_L1;
^wrіteХS = A '=' '[' X ']' nl!;
^wrіteAdd = A '=' '[' X ',' Т ']' ';' nl!;
^genL2 = RIO L2 ']'! RIO;
сontrolAdd = Х# analysL1 ^',';
analysL1 = RB L1! RB / ^RB;
bindingХ_L1 = Х comma L1# ^',';
^wrіteX = A '=' X ';' nl!;
^wrіteVV = A '=' X ',' B '=' L1 ';' nl!;
analysХ_L1 = RB Х comma L1! RB / ^RB;
А = variable;
B = variable;
Т = term (',' term);
L1 = term (',' term) / true;
L2 = term (',' term) / true;
Первая альтернатива завершается
порождением одноэлементного списка,
вторая альтернатива – порождением ново-
го списка, составленного из известного
элемента с присоединением к нему извест-
ного списка. Третья альтернатива после
успешного вычитания первого списка из
второго завершается порождением остав-
шейся головы второго списка. Четвертая
альтернатива после успешного разделения
второго списка на его голову и хвост за-
вершается порождением найденных эле-
мента и первого списка. Пятая альтернати-
ва состоит в проверке на эквивалентность
Теоретичні та методологічні основи програмування
6
второго списка с конкатенацией известно-
го элемента и первого списка.
2.3. Удаление элемента. Предикат
away(X,L,L1) удаления элемента опериру-
ет тремя аргументами: L1 – это список L,
из которого изъят элемент X. В Прологе
записывается двумя утверждениями, пер-
вое из которых – простой факт, заверша-
ющий вычисление, а второй – рекурсивное
правило:
away(X, [X|T],T).
away(X, [Y|T], [Y|T1]):- away(X,T,T1).
Все четыре варианта (удаление из-
вестного элемента X из известного списка
L с получением неизвестного списка L1;
выяснение, действительно ли известный
список L1 получен удалением известного
элемента Х из известного списка L; выяс-
нение неизвестного списка L, из которого
удален известный элемент X с получением
известного списка L1; выяснение неиз-
вестного элемента X, удаленного из из-
вестного списка L с получением известно-
го списка L1) вывода предиката
away(X,L,L1) в метаязыке определим в
форме соответствующих четырех альтер-
натив.
away = away1 / away2 / away3 / away4;
away1='(' X# ',' '['? Т# ']' ','? A L# ')'
viv_away1 ^wrіteL;
viv_away1 = ^genТ analysX ','? Т#
^form_result / ^current_result viv_away1;
away2='(' X# ',' '['? Т# ']' ',' '['? L1 L# ']' ')'
viv_away1 ^genL analysL1;
away3='(' X# ','? A# ',' '['? L1# ']' ')' ^genXL1?
L# ^wrіteL;
away4='(' A# ',' '['? Т# ']' ',' '['? L# ']' ')'
viv_away2;
viv_away2 = ^genT ^headTail1 ^genL
searchMatches viv_away2 / ^wrіteX;
searchMatches = analysX / Y comma
searchMatches;
^headTail1 = X ',' T#;
^genXL1 = RIO X ',' L1! RIO;
^form_result = ^genL variantsL? L#;
variantsL = ^T? ^genT? / ^concatL_Т;
^concatL_Т = RIO L ',' Т RIO!;
^current_result = Y ',' Т# ^genL currentL? L#;
currentL = ^T? ^genY / ^concatL_Y;
^concatL_Y = RIO L ',' Y RIO!;
^genT = RIO Т ']'! RIO;
^genY = RIO Y ']'! RIO;
^wrіteL = A '=' '[' L ']' nl!;
analysХ = RB Х! RB / ^RB;
Y = term;
2.4. Принадлежность элемента
списка. У предиката member(X,L) принад-
лежности элемента Х списку L два аргу-
мента: L – некоторый список и Х – объект
того же типа, что и элементы списка L. Его
определение основывается на следующем:
X – или голова списка L, или X принадле-
жит его хвосту. В Прологе это записывают
в виде двух утверждений, первое из них –
факт, завершающий вычисление, второй –
рекурсивное правило. Если же список
пуст, то предикат ложен: у пустого списка
нет элементов:
member(X, [X| _ ]).
member(X, [ _ | T ]):- member(X,T).
В метаязыке предикат member(X,L)
можно определить рекурсией: если X сов-
падает с головой списка, то, независимо от
значения его хвоста, получим результиру-
ющее значение истинности «истина»; ина-
че, делается очередной шаг исследования
следующего элемента списка L после уда-
ления головы текущего списка.
member = '(' X# ',' '[' Т# ']' ')' viv_member /
'(' А# ',' '['? X# ^wrіteХ (',' X# ^wrіteХ) ']'
')';
viv_member = ^genT analysX /
^step2 viv_member;
^step2 = Y comma? Т#.
Этот предикат можно использовать
так: во-первых, конечно, для проверки,
есть ли в списке конкретное значение, во-
вторых, – получить элементы заданного
списка.
2.5. Конкатенация списков. У
предиката conc(L1,L2,L3) конкатенации
списков три аргумента; первые два L1 и L2
– объединяемые списки, а третий – список
L3 результат конкатенации первых двух.
За основу определения этого термина бе-
рут рекурсию по первому списку, а за ба-
зис – факт, утверждающий, что присоеди-
Теоретичні та методологічні основи програмування
7
нение произвольного списка к пустому
списку дает тот самый произвольный спи-
сок.
conc([ ], L, L).
conc([H|T], L, [H|T1]) :- conc(T,L,T1).
Этот предикат можно применять
для решения разных задач: для получения
списка, являющегося конкатенацией двух
заданных; для проверки, является ли тре-
тий список конкатенацией двух первых;
для разбивки третьего списка на подспис-
ки; для поиска одного из первых списков
по заданным двум другим и др. Для этих
вариантов использования предикат конка-
тенации conc(L1,L2,L3) определим в мета-
языке так:
conc=conc_1/conc_2/conc_3/conc_4/conc_5;
conc_1 = '(' '[' ']' ',' '[' ']' ',' analysA1 ')' /
'(' '[' L1# ']' ',' '[' ']' ',' analysA2 ')' /
'(' '[' ']' ',' '['? L2# ']' ',' analysA3 ')' /
'(' '['? L1# ']' ',' '['? L2# ']' ',' analysA4 ')';
analysA1 = A# ^wrіteEmpty / '[' ']';
^wrіteEmpty = A '=' '[' ']' nl!;
analysA2 = A# ^wrіteL1 / analysL1 ^',';
^wrіteL1 = A '=' '[' L1 ']' nl!;
analysA3 = A# ^wrіteL2 / analysL2 ^',';
^wrіteL2 = A '=' '[' L2 ']' nl!;
analysL2 = RB L2! RB / ^RB;
analysA4=A# ^wrіteL1_L2 / analysL1_L2
^',';
^wrіteL1_L2 = A '=' '[' L1 ',' L2 ']' nl!;
analysL1_L2 = RB L1 ',' L2! RB / ^RB;
conc_2 = '('? A# ',' '['? L2# ']' ',' '['? L3# ']' ')'
^genL3 analysCon6;
^genL3 = RIO L3 ']'! RIO;
analysCon6 = analysL2 ^',' ^wrіteEmpty /
^headTail3 ^genХ ^takeL1 ^genL3
analysC;
^headTail3 = X ',' L3#;
analysC = analysL1_L2 ^',' ^wrіteL1 /
^headTail3 ^genL1X ^takeL1 ^genL3
analysC;
^genL1X = RIO L1 ',' X ']'! RIO;
conc_3 = '(' '['? L1# ']' ','? A# ',' '['? L3# ']' ')'
^genL3 analysL1 wrіteConc5;
wrіteConc5=^',' ^wrіteEmpty / ',' L2#
^wrіteL2;
conc_4 = '('? A L1# ','? B# ',' '[' L3# ']' ')'
^genL3 ^takeL2 ^wrіtePair ^headTail2
below;
below = ^genХ ^takeL1 ^wrіtePair (^genL2
^headTail2 ^genL1X ^takeL1 ^wrіtePair);
^takeL2= L2#;
^headTail2 = X comma L2#;
^takeL1 = L1#;
^wrіtePair = A '=' '[' L1 ']' ',' B '=' '[' L2 ']' ';'
nl!;
conc_5 = '('? A L1# ',' '['? Y ',' B# ']' ',' '['
zeroPair nextPair;
zeroPair = Т3# ']' ')' ^genT3 ^listL2?
^wrіtePair / ^takeХL2 ^genХ;
nextPair = ^takeL1 ^genL2 ^listL2 ^wrіtePair
/
^takeХL2 ^genL1X nextPair;
^listL2= analysY comma? L2#;
analysY = RB Y! RB / ^RB;
^takeXL2 = X comma L2#;
^genT3 = RIO T3 ']'! RIO;
^genХ = RIO Х ']'! RIO;
L3 = term (',' term) / true;
L4 = term (',' term) / true;
T1 = term (',' term);
T2 = term (',' term);
T3 = term (',' term);
T4 = term (',' term).
Первая альтернатива conc_1 опре-
деляет варианты формирования результа-
та, если первые два списка составлены из
констант или один из них или оба являют-
ся пустыми, а третий список задан кон-
стантами или именован переменной. Вто-
рая альтернатива conc_2 определяет вари-
ант поиска первого списка, если второй и
третий списки составлены из констант.
Третья альтернатива conc_3 определяет
вариант поиска второго списка, если пер-
вый и третий списки составлены из кон-
стант. Четвертая альтернатива conc_4
определяет вариант поиска первого и вто-
рого списков, если третий список состав-
лен из констант. Пятая альтернатива
conc_5 определяет вариант поиска первого
A и второго B списков, находящихся соот-
ветственно левее и правее заданного эле-
мента Y третьего списка '[' T3 ']', состав-
ленного из констант.
2.6. Последний элемент списка. В
Прологе предикат last(L,X) определяется
как последний элемент одноэлементного
списка являясь этим элементом, а послед-
Теоретичні та методологічні основи програмування
8
ний элемент обычного списка – это по-
следний элемент его хвоста:
last ([X],X).
last ([_|L],X):- last (L,X).
В метаязыке этот предикат можно
определить, используя итерацию:
last = '(' '[' (Y ',' )? X# ']' ','? A# ')' ^wrіteХ.
Здесь итерация (Y ',') выбирает
первые n-1 элементов списка L , последний
элемент которого связывает переменную
Х#, чье значение далее составляет резуль-
тат решения.
2.7. Два соседних элемента спис-
ка. У этого предиката neighbors(X,Y,L) три
параметра: первые два X, Y – элементы,
третий L – список элементов такого же ти-
па. Для случая, когда порядок размещения
элементов X,Y в списке L важен, в Проло-
ге этот предикат определяют с использо-
ванием предиката конкатенации:
neighbors(X,Y,L):- conc(_,[X,Y|_],L).
Все пять вариантов (выяснение,
действительно ли известные два элемента
X, Y соседствуют в известном списке L;
выяснение, какой неизвестный элемент X
является соседним слева от известного
элемента Y в известном списке L; выясне-
ние, какой элемент Y является соседним
справа от известного элемента X в извест-
ном списке L; выяснение, какие пары эле-
ментов X, Y соседствуют в известном
списке L; сконструировать новый список
из двух известных элементов) вывода пре-
диката neighbors(X,Y,L) в метаязыке опре-
делим в форме соответствующих альтер-
натив.
В метаязыке предикат
neighbors(X,Y,L) можно определить так:
neighbors = neighbors1 / neighbors2 /
neighbors3 / neighbors4 / neighbors5;
neighbors1 = '(' X# ',' Y# ',' '[' L# ']' ')'
viv_neighbors1;
viv_neighbors1 = ^genL analysXY / ^stepL
viv_neighbors1;
neighbors2='(' X# ','? Y# ','? A# ')'
^wrіteXYS;
neighbors3 = '(' X# ','? A# ',' '['? L# ']' ')'
viv_neighbors3;
viv_neighbors3 = ^genL analysX? Y#
^wrіteY / ^stepL viv_neighbors3; ;
neighbors4='(' A# ','? Y# ',' '['? L# ']' ')'
viv_neighbors4;
viv_neighbors4 = ^genL? X# analysY
^wrіteX / ^stepL viv_neighbors4;
neighbors5='(' A# ','? B# ',' '['? L# ']' ')'
(^genL?
Х comma Y# ^wrіteXY ^genL ^stepL);
analysXY = RB X ',' Y! RB / ^RB;
^wrіteXYS = A '=' '[' X ',' Y ']' nl!;
^wrіteY = A '=' Y ';' nl!;
^wrіteXY = A '=' X ',' B '=' Y ';' nl!.
2.8. Реверс списка. У этого преди-
ката reverse(L1, L2) два параметра: первый
– исходный список L1, второй – обращен-
ный список L2. За базис определения этого
термина принимают факт, утверждающий,
что реверс пустого списка дает пустой
список. Шаг рекурсии состоит в конкате-
нации обращенного хвоста списка с пер-
вым элементом исходного списка:
reverse([ ],[ ]).
reverse([X|T],Z):– reverse(T,S),
conc(S,[X],Z).
В метаязыке предикат reverse(L1,
L2) можно определить так:
reverse = '(' '[' ']' ',' A# ')' ^wrіteEmpty /
'(' '[' L2# ']' ',' A# ')' viv_reverse ^wrіteL1 /
'(' '[' L2# ']' ',' '['? L3# ']' ')' v_reverse
^genL1 analysL3;
viv_reverse = ^genL2 ^headTail2 ^genX
^takeL1 (^genL2 ^headTail2 ^genL1X
^takeL1);
analysL3 = RB L3! RB / ^RB.
2.9. Палиндром. Палиндромом
называют список, совпадающий со своим
обращением. В Прологе предикат
palindrom(L) определяют через предикат
reverse (L,L) с двумя одинаковыми аргу-
ментами:
palindrom(L):- reverse (L,L).
Подобное метаязыковое определе-
ние состоит из двух последовательных
преобразований: обращение заданного
Теоретичні та методологічні основи програмування
9
списка и проверка, совпадает ли результат
с начальным списком:
palindrom = '(' '[' L2# ']' ')' viv_reverse
^genL1 analysL2.
2.10. Удаление из списка всех
вхождений заданного значения. Этот
предикат delete_all(X,[L],[L1]) имеет три
параметра: первый Х – удаляемый эле-
мент, второй L – начальный список, а тре-
тий L1 – результат удаления из начального
списка L всех вхождений заданного эле-
мента Х.
Определение на Прологе включает
три утверждения: первое является базовым
фактом – пустой список не уменьшается;
второе утверждает, что после удаления за-
данного элемента из головы начального
списка L результирующий список является
хвостом списка L без вхождений заданного
элемента Х; третье утверждает, что ре-
зультирующий список является конкате-
нацией последовательности элементов без
удаляемого и результата удаления задан-
ного элемента из хвоста начального спис-
ка.
delete_all(_,[],[]).
delete_all(X,[X|L],L1):- delete_all (X,L,L1).
delete_all (X,[Y|L],[Y|L1]):- X<>Y,
delete_all (X,L,L1).
Метаязыковое определение для не-
известного результирующего списка (за-
данного именем А переменной) включает
две рекурсивные альтернативы: удаление
головы текущего списка L2 в случае ее
тождественности заданному элементу;
иначе присоединить голову текущего
списка к текущему составу результирую-
щего списка L3.
delete_all = '(' Y# ',' '[' L2# ']' ',' '[' A L3# ']' ')'
viv_del_all;
viv_del_all = ^genL2 ^listL2 viv_del_all /
^takeXL2 ^upbuildingL3 ^takeL3 viv_del_all
/ ^wrіteL3;
^genL3X = RIO L3 ',' X ']'! RIO;
^upbuildingL3 = ^genL3 ^nullX ^genL3X /
^genХ;
^nullX = X;
^takeL3= L3#;
^wrіteL3 = A '=' '[' L3 ']' nl!.
Если нужно изъять не все вхожде-
ния определенного значения в список, а
только первое, то в Прологе используют
следующее определение:
delete_one(_,[],[]).
delete_one(X,[X|L],L):-!.
delete_one(X,[Y|L],[Y|L1]):-
delete_one(X,L,L1).
Метаязыковое определение этой
семантики получает вид:
delete_one = '(' Y# ',' '[' L2# ']' ',' '[' A L3# ']'
')' viv_del_one;
viv_del_one = ^genL2 ^listL2 ^wrіteL3_L2 /
^takeXL2 ^upbuildingL3
^takeL3
viv_del_one/^wrіteL3;
^wrіteL3_L2 = A '=' '[' L3 ',' L2 ']' nl!.
3. Понятие множества
В метаязыке НФЗ, также как в Про-
логе и ЛИСПе нет такой встроенной
структуры данных, как множество. По-
этому, придется реализовывать это поня-
тие, используя имеющиеся стандартные
домены. В качестве базового примем
списковый домен, приняв:
Определение 1. Множество – спи-
сок без элементов повтора.
Фактически, нет никакой реализа-
ции понятия множество, которое бы точно
отвечало этому математическому объекту.
Принятое определение – лишь приближе-
ние к "истинному" объекту множество.
Рассмотрим предикаты, реализую-
щие основные теоретико-множественные
отношения.
3.1. Предикат превращения спис-
ка в множество. Эту функцию выполняет
предикат, удаляющий из списка все по-
вторные вхождения элементов. Аргумен-
тами предиката unik(L1,L2) являются два
списка: произвольный начальный – L1 и
результирующий – L2 без повторяемых
элементов. Его семантика простая: если
элемент Х головы списка L1 входит в
хвост этого списка L1 (проверяется преди-
катом member), то он не записывается в ре-
зультирующий список L2, иначе этот эле-
мент Х списка L1 вставляется в результи-
рующий список L2 в качестве его головы.
Теоретичні та методологічні основи програмування
10
Пролог описание этого предиката
имеет вид.
unik([ ],[ ]).
unik([H|T], L):– member(H,T), unik(T,L).
unik([H|T], [H|L]):– unik(T,L).
Подобное метаязыковое определе-
ние включает две альтернативы: первая
фиксирует тот факт, что пустой список
остается пустым безусловно; вторая аль-
тернатива определяет процесс вывода ре-
зультирующего списка для общего случая
в форме итерации двух вложенных альтер-
натив. Первая из них определяет наличие
повторений в текущем исследовании спис-
ка, а вторая – процесс пошагового накоп-
ления результирующего списка с исполь-
зованием термина ^upbuildingL1.
unik = '(' '[' ']' ',' '[' ']' ')' / '(' '[' L# ']' ','? A L1#
')' viv_unik ^wrіteL1;
viv_unik=(^genL ^headTail2 member1
^genL ^stepL/ ^genL ^stepL ^upbuildingL1
^takeL1);
member1 = ^genL2 analysX / ^stepL2
member1;
^upbuildingL1 = ^genL1 ^nullX ^genXL1 /
^genХ;
^genL1 = RIO L1 ']'! RIO;
^stepL2 = Y ','? L2# ']';
Далее рассмотрим метаязыковую
реализацию основных теоретико-множе-
ственных отношений.
3.2. Принадлежность элемента
множеству. В качестве реализации преди-
ката принадлежности элемента x множе-
ству A (xA) можно использовать преди-
кат member(X,L) принадлежности элемен-
та Х списку L, где: Х – объект того же ти-
па, что и элементы списка L.
3.3. Объединение двух множеств.
Объединением двух множеств является
множество, чьи элементы принадлежат
или первому, или второму множеству.
Формальное определение объединения
множеств A и B:
AB ={x | xA xB}
на рис. 1 обозначено штриховкой.
A B
AÈB
Рис. 1. Объединение множеств A и B
У предиката union(L1,L2,L3) три
параметра: первые два L1, L2 – объединя-
емые множества, третий L3 – результат
объединения двух первых множеств. При
этом важно, чтобы ни одно значение не
входило в итоговое множество повторно.
Пролог описание этого предиката
имеет вид.
union([ ],S2,S2).
union([H|T],S2,S):– member(H,S2), !,
union(T,S2,S).
union([H|T],S2,[H|S]):– union(T,S2,S).
В метаязыке предикат
union(L1,L2,L3) определим для случаев,
когда являются пустыми оба первых мно-
жества или один из них, или же оба пер-
вых множества составлены из констант, а
третье множество является, соответствен-
но, пустым, задано константами или име-
новано переменной.
union = '(' '[' ']' ',' '[' ']' ',' analysA1 ')' /
'(' '[' L1# ']' ',' '[' ']' ','? A# ')' ^wrіteL1 /
'(' '[' ']' ',' '['? L1# ']' ','? A# ')' ^wrіteL1 /
'(' '['? L# ']' ',' '[' ']' ',' '['? L1# ']' ')'
equivalentLL1 / '(' '[' ']' ',' '['? L# ']' ',' '['?
L1# ']' ')' equivalentLL1 / '(' '['? L# ']' ','
'['? L1# ']' ',' A# ')' viv_union_2 ^wrіteL_L1 /
'(' '['? L# ']' ',' '['? L1# ']' ',' '['? L4# ']' ')'
viv_union_3 / '(' '['? L1# ']' ','? А# ',' '['?
L2# ']' ')' viv_minus_L2L1 ^wrіteL /
'('? А# ',' '['? L1# ']' ',' '['? L2# ']' ')'
viv_minus_L2L1 ^wrіteL / '('? A L1# ','? B#
',' '[' L3# ']' ')' ^genL3 ^takeL2 ^unionAnswer;
^unionAnswer = ^wrіtePair ^headTail2
^hypothes1 ^takeL1 ^wrіtePair below;
below = (^genL2 ^headTail2 ^hypothes2
^takeL1 ^wrіtePair);
equivalentLL1 = ^genL (^headTail2 ^genL1
^takeL3 member2 ^genL2) nullX
^genL1 (^headTail2 ^genL ^takeL3
Теоретичні та методологічні основи програмування
11
member2 ^genL2) nullX;
member2 = ^genL3 analysX / ^stepL3
member2;
viv_ union_2 = ^genL (^headTail2 ^genL1
^takeL31 member3 ^genL2) nullX;
member3 = (^genL3 analysX ^takeL3 /
^stepL3 ^genYL1 ^takeL1);
viv_ union_3 = viv_ union_2 ^genLL1? L#
^genL4? L1# equivalentLL1;
^wrіteL_L1 = A '=' '[' L ',' L1 ']' nl!;
^takeL31 = L3 L1#;
^stepL3 = Y ',' L3#;
^genYL1 = RIO Y ',' L1! RIO;
^genLL1 = RIO L ',' L1 ']'! RIO;
^genL4 = RIO L4 ']'! RIO.
Интерпретация термина analysA1
вывода результата для пустых объединяе-
мых множеств состоит в порождении пу-
стого множества, как значения переменной
А, или порождении значения истинности
истина, если результирующее множество
задано формой пустого множества.
Вторая и третья альтернативы за-
вершаются печатью wrіteL1 значения из-
вестного множества в качестве значения
результирующего множества.
Четвертая и пятая альтернативы за-
вершаются значением истинности истина
термина viv_union_1, если эквивалентны
результирующее и не пустое заданное
множество.
Шестая альтернатива завершается
печатью wrіteL_L1 значения объединенно-
го множества после удаления из множе-
ства L1 элементов множества L в процессе
интерпретации термина viv_union_2.
Седьмая альтернатива в процессе
вывода термина viv_union_3 состоит вна-
чале в синтезе объединения множеств L и
L1 (используя предикат viv_union_2), да-
лее переназначение переменных и, в за-
вершение (используя предикат
equivalentLL1), вывод эквивалентности
синтезированного множества заданному
значению результирующего множества.
Восьмая и девятая альтернативы
вычисляют и печатают неизвестное мно-
жество, используя термин viv_minus_L2L1
вычитания над известными (результирую-
щим и одним из компонентных) множе-
ствами.
Десятая альтернатива состоит в по-
рождении перераспределения заданного
значения результирующего множества на
два составляющих множества. Семантика
этого процесса совпадает с семантикой
термина conc_4 порождения перераспре-
деления заданного значения результиру-
ющего списка на два подсписка.
3.4. Пересечение двух множеств.
Пересечение двух множеств – это множе-
ство из элементов, принадлежащих и пер-
вому, и второму множествам. Формальное
определение пересечения множеств A и B:
A∩B ={x|xA & xB}
на рис. 2 обозначено штриховкой.
У предиката, реализующего эту
операцию, три параметра: первые два L1,
L2 – исходные множества, третье множе-
ство L3 – результат пересечения двух пер-
вых.
A B
A∩B
Рис. 2. Пересечение множеств A и B
В итоговое множество входят те
элементы, которые есть и в первом, и во
втором множестве одновременно. Пролог
описание этого предиката имеет вид.
intersection([],_,[]).
intersection([H|T1],S2,[H|T]):–
member(H,S2),!,
intersection(T1,S2,T).
intersection([_|T],S2,S):–
intersection(T,S2,S).
Базис рекурсии: пересечение пусто-
го множества с любым множеством будет
пустым множеством.
Шаг рекурсии включает два случая:
если голова первого множества является
элементом второго множества, она стано-
вится головой результирующего множе-
ства, чей хвост образуется как пересечение
хвоста первого множества со вторым мно-
жеством; иначе, результирующее множе-
Теоретичні та методологічні основи програмування
12
ство образуется пересечением хвоста пер-
вого множества со вторым множеством.
В метаязыке предикат
intersection(L1,L2,L3) определим для слу-
чаев, когда пустыми являются оба первых
множества или одно из них, или же оба
первых множества составлены из кон-
стант, а третье множество является, соот-
ветственно, пустым, задано константами
или именовано переменной.
intersection = intersectionEmpty ',' analysA1
')' / '(' '['? L1# ']' ',' '['? L2# ']' ','? A L# ')'
viv_intersect_1 ^wrіteL / '(' '['? L1# ']' ','
'['? L2# ']' ',' '['? L4# ']' ')' viv_intersect_2;
intersectionEmpty = '(' '[' ']' ',' '[' ']' /
'(' '[' L1 ']' ',' '[' ']' / '(' '[' ']' ',' '[' L1 ']';
viv_intersect_1 = (^genL2 ^headTail2 ^genL1
^takeL3 member4) nullX;
member4 = ^genL3 analysX ^genXL? L# /
^stepL3 member4;
viv_intersect_2 = viv_intersect_1 ^genL4?
L1# equivalentLL1;
^genХL = RIO Х ',' L! RIO.
Интерпретация термина analysA1
вывода результата при наличии пустых
множеств состоит в порождении пустого
множества, как значения переменной А,
или порождении значения истинности ис-
тина, если результирующее множество за-
дано формой пустого множества.
Вторая альтернатива завершается
печатью wrіteL множества, являющегося
пересечением заданных множеств.
Третья альтернатива описывает по-
следовательность действий: вначале, син-
тез пересечения двух заданных множеств,
далее переназначение переменных и, в
завершение, вывод эквивалентности син-
тезированного множества заданному зна-
чению результирующего множества.
3.5. Разность двух множеств. Раз-
ность двух множеств – это множество, со-
ставленное из элементов первого множе-
ства, не принадлежащих второму. На рис.
3 штриховкой обозначена формальная за-
пись двух вариантов разности множеств A
и B:
A\B={x|xA & хB},
В\А={x|xВ & хА}.
A B
A\B
B
B\A
A
Рис. 3. Разность множеств A и B
У предиката minus(L1,L2,L3), реа-
лизующего разность, три аргумента: пер-
вый L1 – уменьшаемое множество, второй
L2 – вычитаемое множество, третий L3 –
результат вычитания второго множества из
первого. Третье множество содержит эле-
менты первого множества без элементов
второго. Пролог-описание этого предиката
имеет вид.
minus([],_,[]).
minus([H|T],S2,S):– member(H,S2),!,
minus(T,S2,S).
minus([H|T],S2,[H|S]):– minus(T,S2,S).
Базис рекурсии: вычитание произ-
вольного множества из пустого множества
ничего, кроме пустого множества, дать не
может. Шаг рекурсии: если голова первого
множества входит во второе множество, то
разность множеств образуется вычитанием
второго множества из хвоста первого; ина-
че, разность множеств является конкате-
нацией головы первого множества и ре-
зультата вычитания второго множества из
хвоста первого множества.
В метаязыке предикат
minus(L1,L2,L3) определим для случаев,
когда: пустыми являются оба первых мно-
жества или только уменьшаемое; пустым
является вычитаемое множество, а резуль-
тирующее неизвестно; пустым является
вычитаемое множество, а уменьшаемое и
результирующее множества заданы; зада-
ны уменьшаемое и вычитаемое множества,
а результирующее неизвестно; все три
множества заданы или же заданы вычита-
емое и результирующее множества, а
уменьшаемое неизвестно.
minus ='(' '[' ']' ',' '['? L1# ']' ',' analysA1 ')' /
'(' '[' L1# ']' ',' '[' ']' ','? A# ')' ^wrіteL1 /
'(' '[' L# ']' ',' '[' ']' ','? L1# ')'
Теоретичні та методологічні основи програмування
13
equivalentLL1 /
'(' '['? L2# ']' ',' '['? L1# ']' ',' A L # ')'
viv_minus_L2L1 ^wrіteL /
'(' '['? L2# ']' ',' '['? L1# ']' ',' '['? L4# ']' ')'
viv_minus /
'(' '['? А# ']' ',' '['? L# ']' ',' '['? L1# ']' ')'
^wrіteL_L1 /
'(' '['? L2# ']' ',' A L # ',' '['? L1# ']' ')'
viv_minus_L2L1 ^wrіteL;
viv_minus_L2L1 = (^genL2 ^headTail2
stepMinus);
stepMinus = ^genL1 ^takeL3 ^member5
^genXL? L# / true;
member5 = ^genL3 analysX/^stepL3
member5;
viv_minus = viv_minus_L2L1 ^genL4? L1#
equivalentLL1.
Интерпретация термина analysA1
вывода результата при наличии пустых
множеств состоит в порождении пустого
множества, как значения переменной А,
или порождении значения истинности ис-
тина, если результирующее множество за-
дано формой пустого множества.
Вторая альтернатива завершается
печатью wrіteL уменьшаемого множества,
как значения результирующего множества.
Третья альтернатива описывает
условие эквивалентности уменьшаемого и
результирующего множеств при пустом
вычитаемом множестве.
Четвертая альтернатива описывает
последовательность действий по формиро-
ванию и печати разности заданных мно-
жеств: уменьшаемого и вычитаемого.
Пятая альтернатива описывает вы-
числение разности заданных множеств,
далее переназначение переменных и, в за-
вершение, вывод эквивалентности синте-
зированного множества заданному значе-
нию результирующего множества.
Шестая альтернатива завершается
печатью wrіteL_L1 конкатенации вычита-
емого и результирующего множеств.
Седьмая альтернатива описывает
последовательность действий по формиро-
ванию и печати разности заданных мно-
жеств: уменьшаемого и результирующего.
3.6. Отношение подмножества.
Одно множество содержится в другом,
если каждый элемент первого множества
принадлежит второму множеству. Фор-
мальное определение отношения под-
множества (AKO – a kind of ) множеств
A и B:
ABx(xAxB).
На рис. 4 обозначено штриховкой.
У предиката subset(L1,L2), реали-
зующего это отношение, два параметра: L1
– множество, являющееся подмножеством
другого L2 множества.
B
A
Рис. 4. Множество А является
подмножеством В
Базис рекурсии: представлен фак-
том, утверждающим, что пустое множе-
ство является подмножеством любого
множества.
Шаг рекурсии: первое множество
является подмножеством второго, если
первый элемент первого множества при-
надлежит второму множеству, а его хвост
является подмножеством второго множе-
ства.
Пролог описание этого предиката
имеет вид.
subset([],_).
subset([H|T],S):– member(H,S), subset(T,S).
В метаязыке предикат subset(L1,L2)
определим для трех случаев, когда: пу-
стым является первое L1 множество, а
второе L2 – любым; оба множества L1, L2
– произвольны; первое L1 множество за-
дано переменной, а второе – константное.
subset = '(' '[' ']' ',' '[' L1 ']' ')' / '(' '[' L2# ']' ',' '['
L1# ']' ')' viv_Subset / '(' A L1# ','?
'[' L# ']' ')' ^wrіteL1 ^genL ^headTail2
^hypothes1 ^takeL1 ^wrіteL1 viv_Subset1;
viv_Subset = (^genL2 ^headTail2 stepSubset)
nullX;
stepSubset = ^genL1 ^takeL3 ^member5;
Теоретичні та методологічні основи програмування
14
viv_Subset1 = (^genL2 ^headTail2
^hypothes2 ^takeL1 ^wrіteL1).
Первая альтернатива определения
термина subset фиксирует тот факт, что
пустое множество является подмноже-
ством любого множества.
Вторая альтернатива состоит в по-
очередной проверке элементов первого
множества L2 со всеми элементами второ-
го множества L1.
Третья альтернатива описывает
процесс последовательного порождения
всех (начиная с пустого) подмножеств за-
данного множества L2.
3.7. Совпадение двух множеств.
Два множества A и B называются равны-
ми, если одновременно выполнено AB и
BA, т. е. множество A содержится в
множестве B и множество B в множестве
A. Иначе говоря, два множества равны,
если все элементы первого множества со-
держатся во втором множестве, и наобо-
рот. Пролог-описание предиката, описы-
вающего отношение эквиваленции двух
множеств, имеет вид.
equal(A,B):– subset(A,B), subset(B,A).
В метаязыке предикат equal(L,L1)
определяется последовательностью итера-
ций: первая проверяет вхождение всех
элементов первого множества L во второе
множество L1, а вторая итерация проверя-
ет вхождение всех элементов второго
множества L1 в первое множество L.
equal = '(' '['? L# ']' ',' '['? L1# ']' ')' subsetLL1
subsetL1L;
subsetLL1= ^genL (^headTail2 ^genL1
^takeL3 member2 ^genL2) nullX;
subsetL1L = ^genL1 (^headTail2 ^genL
^takeL3 member2 ^genL2) nullX.
3.8. Отношение собственного
подмножества. Если множество B содер-
жит множество A и другие элементы, кро-
ме элементов множества А, то А – соб-
ственное подмножество множества В:
AB (рис. 4) на Прологе имеет вид.
prop_subset(A,B):– subset(A,B),
not(equal(A,B)).
Подобным же образом этот преди-
кат prop_subset(L,L1) определяется и в ме-
таязыке:
prop_subset = '(' '['? L# ']' ',' '['? L1# ']' ')'
subsetLL1 ^subsetL1L.
3.9. Симметрическая разность. В
отличие от обычной разности, симметри-
ческая разность не зависит от порядка ее
аргументов. Симметрической разностью
двух множеств называется множество, чьи
элементы либо принадлежат первому и не
принадлежат второму множеству, либо
принадлежат второму и не принадлежат
первому множеству. Формальное опреде-
ление симметрической разности множеств
A и B:
AΔB={x|(xA & xB) (xB & xA)}.
На рис. 5 обозначено штриховкой.
A B
A∆B
Рис. 5. Симметрическая разность
множеств А и В
Симметрическую разность можно
выразить через уже реализованные опера-
ции:
AΔB=(A\B)(B\A).
Эти соотношения на Прологе полу-
чат вид.
sim_minus(A,B,SM):– minus(A,B,A_B),
minus(B,A,B_A),
union(A_B,B_A,SM).
В метаязыке предикат
sim_minus(L1,L2,L3) также можно выра-
зить через уже определенные предикаты
minus(L1,L2,L3) и union(L1,L2,L3) в сле-
дующей форме.
sim_minus = '(' Е1 ',' E2 ',' E3# ')'
Теоретичні та методологічні основи програмування
15
^genE1E2AB minus takeAB
^genE2E1BA minus takeBA
^genABBASM union;
^genE1E2AB = '(' Е1 ',' E2 ',' 'AB' ')'!;
takeAB = 'AB' '=' '['? A_B#;
^genE2E1BA = '(' Е2 ',' E1 ',' 'BA' ')'!;
takeBA = 'BA' '=' '['? B_A#;
^genABBASM = '(' A_B ',' B_A ',' 'SM' ')'!.
В этом выражении термины
^genE1E2AB, ^genE2E1BA и ^genABBASM
формируют многоместные аргументы со-
ответствующих предикатов minus и union,
а takeAB и takeBA – принимают вычис-
ленные значения переменных.
3.10. Дополнение. Дополнением
DА множества A является подмножество
элементов некоторого определенного уни-
версума U, не принадлежащих A. Фор-
мальное определение отношения
supp(A,DА) дополнения:
DА = U\A ={x|xU & хА}.
На рис. 6 обозначено штриховкой.
A
Рис. 6. Отношение дополнения
множества A
Множество DА вычислимо лишь
тогда, когда определены множества U и A.
Для этого случая семантика предиката
supp(U,A,DА) совпадает с семантикой
предиката minus(U,A,DА), что на Прологе
представляется в форме.
supp(U,A,DА):– minus(U,A,DА).
Предикат supp(L1,L2,L3) можно
выразить и в метаязыке через уже опреде-
ленный предикат minus(L1,L2,L3) в сле-
дующей форме.
supp = '(' Е1 ',' E2 ',' E3# ')' ^genE1E2Е3
minus;
^genE1E2Е3 = '(' Е1 ',' E2 ',' E3 ')'!.
Здесь Е1 – универсальное множе-
ство U, Е2 и Е3 – взаимно дополнительные
множества А и DА.
Выводы
Базируясь на известных описаниях
на Прологе, использующих списковый до-
мен, впервые разработана в метаязыке
НФЗ новая практически пригодная форма-
лизация списков, предикатов на списках и
множествах.
Представляется, что составленная
метаязыковая формализация практически
пригодна не только в качестве новой реа-
лизации задач оперирования списками,
множествами, но и в качестве специфика-
ции для реализации этих задач в составе
других систем.
Литература
1. Братко, Иван. Алгоритмы искусственного
интеллекта на языке PROLOG. 3-е издание.
Пер. с англ. М.: Издательский дом "Виль-
ямс", 2004. 640 с.
2. Адаменко А.Н., Кучуков А.М. Логическое
программирование и Visual Prolog. СПб.:
БХВ-Петербург, 2003. 992 с.
3. Клоксин У., Меллиш К. Программирова-
ние на языке Пролог. М.: Мир, 1987. 334 с.
4. Abelson, Harold. Structure and interpretation
of computer programs. Harold Abelson and
Gerald Jay Sussman, with Julie Sussman. 2nd
ed. The MIT Press Cambridge, Massachusetts
London, England © 1996 by The
Massachusetts. 576 р.
5. Haskell 98. Language and Libraries. The
Revised Report. Editor by Simon Peyton
Jones. Cambridge Academ, 2003. 277 p.
6. Seibel, Peter. Practical Common Lisp.
Apress, 2005. 501 р. DOI 10.1007/978-1-
4302-0017-8.
7. Кургаев А.Ф., Григорьев С.Н. Нормальные
формы знаний. Доп. НАН України. 2015.
№ 11. С. 36–43.
8. Кургаев А.Ф., Григорьев С.Н. Метаязык
нормальных форм знаний. Кибернетика и
системный анализ. 2016. Том 52. № 6.
С. 11–20.
9. Кургаев А.Ф. Формализация списков в ме-
таязыке нормальных форм знаний. Доп.
НАН України. 2017. № 10. С. 18–27. doi:
https://doi.org/10.15407/dopovidi2017.10.018
Теоретичні та методологічні основи програмування
16
References
1. Bratko, Ivan. Prolog Programming for
Artificial Intelligence / Third Edition. –
Addison-Wesley, 2012. – 696 p.
2. Adamenko A.N., Kuchukov A.M. Logical
Programming and Visual Prolog. - St.
Petersburg: BHV-Petersburg, 2003. - 992 p.
(in Russian).
3. Clocksin, William., Mellish, Christopher S.
Programming in Prolog: Using the ISO
Standard 5th Edition. – Berlin, Heidelberg:
Springer-Verlag, 2003. – 300 p. DOI
10.1007/978-3-642-55481-0
4. Abelson, Harold. Structure and interpretation
of computer programs / Harold Abelson and
Gerald Jay Sussman, with Julie Sussman. –
2nd ed. / The MIT Press Cambridge,
Massachusetts London, England © 1996 by
The Massachusetts. – 576 р.
5. Haskell 98. Language and Libraries. The
Revised Report / Editor by Simon Peyton
Jones. – Cambridge Academ, 2003. – 277 p.
6. Seibel, Peter. Practical Common Lisp. –
Apress, 2005. – 501 р. DOI 10.1007/978-1-
4302-0017-8
7. Kurgaev, A. The normal forms of knowledge
/ A.Kurgaev, S.Grygoryev. – Dopov. NAN
Ukraine, 2015, № 11. – Р. 36-43 (in Russian).
8. Kurgaev, A. Metalanguage of Normal Forms
of Knowledge / A.Kurgaev, S.Grygoryev. –
Cybernetics and Systems Analysis. –
November 2016, 52(6), 839-848. DOI
10.1007/s10559-016-9885-3
9. Kurgaev, A. The Formalization of Lists in the
Meta-Language of Normal Forms of
Knowledge / Dopov. NAN Ukraine. – 2017. –
№10. – Р. 18 – 27. (in Russian). doi:
https://doi.org/10.15407/dopovidi2017.10.018
Получено 27.01.2020
Об авторе:
Кургаев Александр Филиппович,
доктор технических наук,
профессор, ведущий научный сотрудник.
Количество научных публикаций в
украинских изданиях – более 240.
Количество научных публикаций в
зарубежных индексированных
изданиях – 24.
Индекс Scopus: 2,
h-индекс (Google Scholar): 6
http://orcid.org/0000-0001-5348-2734.
Место работы автора:
Институт кибернетики имени
В.М. Глушкова НАН Украины,
03187, Киев-187,
проспект Академика Глушкова, 40.
Тел.: 8 050 881 62 18.
E-mail: afkurgaev@ukr.net
mailto:afkurgaev@ukr.net
|