|
Реферат: Разработка программы на языке LISP для построения кривых Серпинского i-го порядка (Математика)
МИНИСТЕРСТВО ВЫСШЕГО И СРЕДНЕГО СПЕЦИАЛЬНОГО ОБРАЗОВАНИЯ РФ
МОСКОВСКИЙ ИНСТИТУТ РАДИОТЕХНИКИ, ЭЛЕКТРОНИКИ И АВТОМАТИКИ
Курсовой проект
Тема:
«Разработка программы на языке LISP
для построения кривых Серпинского i-го порядка»
|Факультет: |ВАВТ |
|Дисциплина: |ФПО |
|Студент: | |
|Группа: | |
|Специальность: |2202 |
|Преподаватель: |Яшин Л.З. |
МОСКВА
Май 1998
Оглавление
Задание 3
Формализация задачи 4
Схема алгоритма 6
Текст программы 8
Руководство пользователя 11
Тест программы 12
Литература 14
Задание
Оригинальный узор на рисунке 1 состоит из суперпозиции четырех кривых.
Эти кривые соответствуют некоторому регулярному образу. Алгоритм для
построения этих кривых на экране монитора или на графопостроителе под
управлением вычислительной машины описан в [1].
Задача проекта – реализовать этот алгоритм в виде программы на
функциональном языке программирования Lisp.
[pic]
Рисунок 1
Формализация задачи
Анализируя рисунок 1, можно обнаружить, что он получен путем наложения
друг на друга нескольких кривых. Первые две из них показаны на рисунке 2.
Кривая Si называется кривой Серпинского i-го порядка. Необходимо выяснить,
какова рекурсивная схема этих кривых.
[pic]
Рисунок 2
Главная особенность кривой Серпинского состоит в том, что она замкнута
и в ней нет пересечений. Это означает, что основная рекурсивная схема
должна давать разомкнутую кривую линию, четыре части которой соединяются
линиями, не принадлежащими самому рекурсивному образу. И действительно, эти
замыкающие линии представляют собой отрезки прямых в четырех внешних углах,
на рисунке 2 они выделены жирными линиями. Можно считать, что они
принадлежат к непустой начальной кривой S – квадрату, «стоящему» на одном
углу. Теперь достаточно легко составить рекурсивную схему.
Четыре составляющих образа, для наглядности, обозначим через A, B, C,
D, а процедуры, рисующие соединительные прямые, будем обозначать стрелками,
указывающими соответствующем направлении. Надо отметить, что четыре
рекурсивных образа по существу идентичны, но лишь повертываются на 90(.
Основной образ кривых Серпинского задается схемой:
S: A ( B ( C ( D (
а рекурсивные составляющие (горизонтальные и вертикальные отрезки –
двойной длины):
A: A ( B ( D ( A
B: B ( C ( A ( B
C: C ( D ( B ( C
D: D ( A ( C ( D
Предположим, что для построения части прямой в нашем распоряжении есть
процедура Line, передвигающая перо в заданном направлении на заданное
расстояние, причем направление задается целочисленным параметром i, как
[pic] градусов. Если единичную прямую обозначить через h, то с помощью
рекурсивных обращений к аналогично составленным процедурам для B и D и к
самой A довольно просто написать процедуру, соответствующую схеме А.
( defun A ( k )
( cond ( ( > k 0 )
( A ( - k 1 ) ) ( Line 1 h )
( B ( - k 1 ) ) ( Line 0 ( * 2 h ) )
( D ( - k 1 ) ) ( Line 7 h )
( A ( - k 1 ) ))))
Эта процедура инициируется главной программой по одному разу для
каждой кривой Серпинского, образующих приведенный рисунок. Употребление
явного параметра для уровня гарантирует окончание работы, так как глубина
рекурсии не может быть больше k. Главная программа строится по образцу S.
Ее задача - установить начальную точку кривой, т.е. исходные координаты
пера (Px и Py) и единичную длину приращения h. Квадрат, где рисуется
кривая, помещается в середине экрана, заданной ширины и высоты.
Графическое изображение полученного алгоритма представлено в следующем
разделе (Рисунок 3).
По сравнению с таким рекурсивным построением эквивалентные программы,
где избегали употребления рекурсии, выглядят крайне сложными и запутанными.
Схема алгоритма
[pic]
Рисунок 3 Схема алгоритма главной процедуры
[pic]
Рисунок 4 Схема алгоритма процедуры A[1]
Текст программы
;; SIERPINS.LSP для XLISP версии 2.1
;; ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
;; Программа построения кривых Серпинского i-го порядка.
;;
;; ЗАПУСК: > (SierpinskiCurve 4)
;;
;; Замечание: Переменная *VMode* управляет установкой видео режима,
;; и по умолчанию установлена в значение 18.
;; Эта установка соответствует режиму 640x480 Color,
;; и работает на большинстве систем. В случае проблемы
;; с установкой этого режима необходимо выбрать
;; значение этой переменной в соответствии с документацией
;; на оборудование.
;;
( defvar *VMode* 18 ) ;Видео режим по умолчанию
( defvar *MaxX* 640 ) ;Максимальная ширина экрана по умолчанию
( defvar *MaxY* 480 ) ;Максимальная высота экрана по умолчанию
( defvar *SquareSize* 256 ) ;Размер области для построения
;;
;; Функция инициализирует графический режим, устанавливает переменные
;; *MaxX* *MaxY* *SquareSize* в соответствии с выбранным режимом
;;
(
defun InitGraph()
(
case *VMode*
( 4 ;320x200 Color
( mode 4 )
( setq *MaxX* 320 *MaxY* 200 *SquareSize* 128 ) )
( 16 ;640x350 Color
( mode 16 )
( setq *MaxX* 640 *MaxY* 350 *SquareSize* 128 ) )
( 18 ;640x480 Color
( mode 18 ) )
( 106 ;800x600 Color
( mode 106 106 800 600 )
( setq *MaxX* 800 *MaxY* 600 *SquareSize* 512 ) )
( t ( error Unsupported graphics mode: *VMode* ) )
)
)
;;
;; Функция реализует задержку на заданное время
;;
(
defun pause ( time )
( let ( ( fintime ( + ( * time internal-time-units-per-second )
( get-internal-run-time ) ) ) )
( loop ( when ( > ( get-internal-run-time) fintime )
( return-from pause ) ) ) )
)
;;
;; Функция целочисленного деления
;;
(
defun div ( a b ) ( round ( / a b ) )
)
;;
;; Функция рисования прямой:
;; Параметры: - направление рисования (0-7)
;; - длинна прямой
;;
(
defun Line( Direction Size )
( setq x Px y Py )
(
case Direction
( 0 ( setq x ( + x Size) ) )
( 1 ( setq x ( + x Size ) y ( - y Size ) ) )
( 2 ( setq y ( - y Size) ) )
( 3 ( setq x ( - x Size ) y ( - y Size ) ) )
( 4 ( setq x ( - x Size) ) )
( 5 ( setq x ( - x Size ) y ( + y Size ) ) )
( 6 ( setq y ( + y Size) ) )
( 7 ( setq x ( + x Size ) y ( + y Size ) ) )
)
( move Px Py x y )
( setq Px x Py y )
)
;;
;; Функции A, B, C, D - рекурсивные функции рисования
;;
(
defun A ( k )
( cond ( ( > k 0 )
( A ( - k 1 ) ) ( Line 1 h )
( B ( - k 1 ) ) ( Line 0 ( * 2 h ) )
( D ( - k 1 ) ) ( Line 7 h )
( A ( - k 1 ) )
) )
)
(
defun B ( k )
( cond ( ( > k 0 )
( B ( - k 1 ) ) ( Line 3 h )
( C ( - k 1 ) ) ( Line 2 ( * 2 h ) )
( A ( - k 1 ) ) ( Line 1 h )
( B ( - k 1 ) )
) )
)
(
defun C ( k )
( cond ( ( > k 0 )
( C ( - k 1 ) ) ( Line 5 h )
( D ( - k 1 ) ) ( Line 4 ( * 2 h ) )
( B ( - k 1 ) ) ( Line 3 h )
( C ( - k 1 ) )
) )
)
(
defun D ( k )
( cond ( ( > k 0 )
( D ( - k 1 ) ) ( Line 7 h )
( A ( - k 1 ) ) ( Line 6 ( * 2 h ) )
( C ( - k 1 ) ) ( Line 5 h )
( D ( - k 1 ) )
) )
)
;;
;; Главная процедура
;; Параметры: - количество итераций
;;
(
defun SierpinskiCurve ( Count )
( InitGraph ) ;Установка графического режима
( setq h ( div *SquareSize* 4 ) ) ;Вычисление длины линии
( setq x0 ( div *MaxX* 2 ) ) ;Вычисление начальной точки
( setq y0 ( + ( div *MaxY* 2 ) h ) ) ;для рисования
( ;Основной цикл
do (( i 1 )) ;Инициализация счетчика
(( eql i ( + Count 1 ) ) 'Done ) ;Условие завершения
( setq x0 ( - x0 h ) ) ;Вычисление координат начальной
( setq h ( div h 2 ) ) ;точки для рисования и
( setq y0 ( + y0 h ) ) ;единичной длины линии
( setq Px x0 Py y0 ) ;Установка пера
( color i ) ;Установка цвета для рисования
( A i ) ( Line 1 h ) ;Рисование
( B i ) ( Line 3 h )
( C i ) ( Line 5 h )
( D i ) ( Line 7 h )
( pause 1.0 ) ;Задержка
( setq i ( + i 1 )) ;Инкримент счетчика
) ;Конец основного цикла
)
( print Try (SierpinskiCurve 4) ) ;Подсказка
Руководство пользователя
Требования к системе:
V x86 персональный компьютер (386 минимум; 486, Pentium, или
Pentium Pro рекомендуется)
V Microsoft DOS 3.30 или выше
V Microsoft Windows 3.1, Microsoft Windows for Workgroups,
Microsoft Windows 95, Microsoft Windows NT 3.51 или 4.0
V 512 Kb RAM
V 5 Kb свободного пространства на жестком диске
V Установленный интерпретатор XLisp версии 2.1 или выше
Для запуска программы необходимо:
o Включить компьютер
o Загрузить интерпретатор XLisp c параметром «Sierpins.lsp»:
C:XLISPXLISP.EXE SIERPINS.LSP[2](
o В ответ на приглашение XLisp ввести: (SierpinskiCurve 4)(
Тест программы
Тест проводился на рабочей станции со следующей конфигурацией:
o Pentium 166
o 32 Mb RAM
o SyncMaster 17Glsi
o S3 Trio64V+
o Windows 95
Интерпретатор XLisp был запущен в окне MS-DOS.
Программа тестировалась при значениях параметра Count от 1 до 4. В
результате тестов были получены следующие изображения на экране
монитора[3]:
[pic]
Рисунок 5
[pic]
Рисунок 6
[pic]
Рисунок 7
[pic]
Рисунок 8
Литература
o “Алгоритм + структура данных = программа”, H.Вирт
o “XLisp-Plus 2.1 Programmers Manual”, David Michael Betz
-----------------------
[1] Схемы алгоритмов процедур B, C и D аналогичны A, и поэтому, в их
изображении нет необходимости.
[2] Данный пример предполагает, что XLisp установлен в каталоге C:XLISP и
его запуск производится в режиме MS-DOS.
[3] В программе был установлен графический видео режим с разрешением
640x480 256 Color
Реферат на тему: Разработка формальной системы
Министерство образования Российской Федерации
Рязанская государственная радиотехническая академия
Кафедра ВПМ
Разработка формальной системы
Пояснительная записка к курсовому проекту
по дисциплине “Математическая логика”
Проверил: Каширин И. Ю.
Рязань 2003г.
Содержание
1. Предметная область.
2. Основные объекты предметной области и отношения на множестве этих
объектов.
3. Семантика отношений. Примеры.
4. Свойства отношений.
5. Операции на множестве объектов предметной области. Их семантика.
Примеры.
6. Разработка алгебраической системы.
7. Свойства операций.
8. Тип и класс полученной алгебраической системы.
9. Формальная логическая система с аксиоматикой свойств операций. Примеры
логического вывода.
10. Программа, демонстрирующая отношения и основные операции алгебраической
системы. Пример выполнения программы.
1. Предметная область.
В качестве предметной области будем рассматривать пазл.
2. Основные объекты предметной области и отношения на множестве этих
объектов. Примеры.
Основным объектом предметной области является картеж следующего вида:
(а1, а2, а3, а4),
где а1 – верхняя сторона пазла;
. а2 - правая сторона пазла;
. а3 - нижняя сторона пазла;
. а4 - левая сторона пазла;
Значения а1, а2, а3, а4 определяются следующим образом (в зависимости от
элемента на этой стороне):
. ai = -1 если на стороне вогнутость
. ai = 1 если на стороне выпуклость
. ai = 0 если на стороне нет ни выпуклость ни вогнутости (пустая
сторона)
Запись А2 означает, что используется 2я сторона пазла А, т.е. А2 = а2.
Пример 1.
(-1, 0, 1, 1), т.е.
В качестве отношений возьмем бинарные отношения меньше () и
равенство (=) элементов по:
. количеству выпуклостей (>’; ”; <”; =”)
. по общему числу (=)
3. Семантика отношений.
Введем понятие веса и модуля пазла:
Определение 1. Весом выпуклостей пазла А называется величина Vвп(А), равная
количеству сторон при ai = 1, i=[pic].
Определение 2. Весом вогнутостей пазла А называется величина Vвг(А), равная
количеству сторон при ai = -1, i=[pic].
Определение 3. Модулем пазла А называется величина М(А), определяемая
следующим уравнением:
М(А)=[pic],
где qi и bi :
[pic]; [pic] где [pic]
Отношение меньше (больше).
Определение 4. Пазл А меньше (больше) пазла В по количеству выпуклостей (по
количеству вогнутостей) если вес выпуклостей (вогнутостей) А меньше
(больше) веса выпуклостей (вогнутостей) пазла В, т.е.
А <” B (A >” B), если Vвп(A) < Vвп(B) (Vвп(A) > Vвп(B))
[А ’ B), если Vвг(A) < Vвг(B) (Vвг(A) > Vвг(B)) ].
Отношение больше является обратным к отношению меньше, т.е. если A > B, то
B < A и наоборот, если A < B, то B > A.
Отношение равенство.
Определение 5. Пазл А равен пазлу В по количеству выпуклостей
(вогнутостей), если вес выпуклостей (вогнутости) пазла А равен весу
выпуклостей (вогнутости) пазла В, т. е.
. А =’ В по количеству вогнутостей, если Vвг(А)=Vвг(В)
. А =” В по количеству выпуклостей, если Vвп(А)=Vвп(В)
Определение 6. Пазл А равен пазлу В, если равны модули пазлов, т.е A=B,
если. М(А)=М(В).
Пример.
А = (-1, 1, 0, 0),
В = (0, 1, 1, -1);
. Vвп(A) =1; Vвп(В)=2; Vвп(A) < Vвп(B), значит A” A) не выполняется ни для какого
пазла А, т. к.
Vвг (A) = Vвг (A) и не может быть, что Vвг(A) < Vвг(A) (Vвг(A) > Vвг(A)).
2) Отношение антисимметрично.
Доказательство. Если А <” B (A >” B) то Vвг(A) < Vвг(B) (Vвг(A) > Vвг(B))
=> условие Vвг(A) > Vвг(B) (Vвг(A) < Vвг(B)) неверно, отсюда неверно, что А
>” B (A <” B).
3) Отношение транзитивно.
Доказательство. Пусть A <” B, B <” C, тогда Vвг(A) < Vвг(B), Vвг(B) Vвг(A) < Vвг(C), т. о. А <” C (Аналогично для отношения больше).
Отношение равенство[2].
1) Отношение рефлексивно.
Доказательство. Для любого пазла А М(A) = М(A) => А = А.
2) Отношение симметрично.
Доказательство. Пусть А = B, тогда М(A) = М(B) => М(B) = М(A) => B = A.
3) Отношение транзитивно.
Доказательство. Пусть А = В, В = С, тогда М(A) = М(B), М(B) = М(C) => М(A)
= М(C) => A = C.
Отношение равенства является отношением эквивалентности.
5. Операции на множестве объектов предметной области. Их семантика.
Будем рассматривать две бинарные операции: наложение (+) и склеивание (*);
унарная операция: инверсия (()-1) и нульарные: операции слабой (0) и
сильной (1) единицы.
Операция слабая единица - 0.
Данная операция - константа 0 представляет - собой картеж вида
(0,0,0,0)
Операция сильная единица - 1.
Данная операция - константа 1i - представляет собой один из картежей:
. (1, 0, -1, 0), при i =1;
. (0, 1, 0, -1) , при i =2;
. (-1, 0, 1, 0) , при i =3;
. (0, -1, 0, 1) , при i =4;
где i определяет сторону с элементом «выпуклость».
Операция наложения.
Данная операция накладывает один пазл на другой, в результате чего
получается новый пазл. Новый пазл образуется по следующему правилу:
Правило боковых граней:
если на накладываемой стороне 1го пазла находится выпуклость, а у 2го пазла
на соответствующей стороне - вогнутость, то результатом будет пустая
сторона
если на сторонах обоих пазлов находятся выпуклость (или вогнутость), то в
результате получится сторона с выпуклостью (вогнутостью)
если сторона одного из пазлов является пустой, то результирующая сторона
будет иметь тот же элемент, что и сторона второго пазла
вышесказанное можно отобразить формулами:
C = A + B:
c’i = ai + bi
ci = [pic]
где i = [pic]
Операция наложения справедлива для любых пазлов.
Операция имеет вид:
С = А + В.
Примеры.
1) А = (0, 0, -1, 1),
В = (-1, 1, -1, -1).
A + B = C = (-1, 1, -1, 0), т.е.
Операция склеивания.
Данная операция склеивает два пазла для получения нового.
Операция выполняется не для всех пазлов, а только для тех, которые
удовлетворяют условиям операции:
. склеиваемые стороны на должны бать пустыми и должны иметь
противоположные элементы (т.е., например, 1й пазл – вогнутость (
2й пазл - выпуклость);
. разность между номерами склеиваемых сторон должна быть по модулю
равна 2 (т.е., например, 1й пазл – 2 ( 2й пазл – 4: |2 - 4| = 2 );
Новый пазл получается следующим образом:
. звездочкой (*) указываются номера склеиваемых сторон;
. элементы сторон, противоположных склеиваемым сторонам, не
изменяются;
. элементы двух других сторон образуются по правилу боковых сторон ;
Операция имеет вид: С = А1 * В3 = (а1*, а2, а3, а4) * (b1, b2, b3*, b4)
Пример.
А = (0, 1, -1, 0),
В = (-1, 1, 0, -1).
А2*В4 = (0, 1*, -1, 0) * (-1, 1, 0, -1*) = (-1, 1, -1,0), т.е.
Операция инверсия.
Данная операция инвертирует пазл, т. е. заменяет выпуклости вогнутостями и
наоборот, в результате чего получается новый пазл. Операция имеет вид: С =
А-1.
Пример.
А = (0, 1, -1, 0)
А-1 = С = (0, -1, 1, 0), т. е.
6. Алгебраическая система.
Определение 7. Система трех множеств ? = называется
алгебраической системой, где А – множество однотипных элементов, называемое
носителем алгебры или базовым множеством, ? – множество операций с областью
определения и областью значений в множестве А, R – множество отношений на
элементах множества А.
Множество А представляет собой множество всех пазлов, представленных в виде
картежей, описанных выше.
Сигнатура алгебры ? = { + , * , -1() , 0 , 1 }.
R = {’, >”, =, =’, =”}
Согласно определению операций, мы получим пазл в виде картежа, описанного
выше, значит мы получим элемент базового множества, что говорит о
замкнутости операций.
7. Свойства операций.
Свойство единицы:
А + А-1 = А-1 +А = 1 – сильная единица:
Аi * 0 = 0 * Ai = A, i=[pic] - слабая единица;
Операция наложения.
1) Операция идемпотентна, поскольку для данной операции справедливо
утверждение
A + A = A;
2) Операция коммутативна, поскольку для данной операции справедливо
утверждение
A + B = B + A;
3) Операция не ассоциативна, поскольку для нее справедливо утверждение
A + (B + C) ( (A + B) + C.
Свойства по отношению к операции склеивание:
4) Операция не дистрибутивна слева, т. к. A + (B * C) ? (A + B) * (A + C)
5) Операция не дистрибутивна справа, т. к. (A * B) + C ? (A + C) * (B + C)
Операция склеивание.
Поскольку условие операции не выполняться для всех пазлов, то операция
склеивания:
1) не идемпотентна
2) не коммутативна
3) не ассоциативна
и по отношению к операции наложения:
4) не дистрибутивна слева
5) не дистрибутивна справа
8. Тип и класс полученной алгебраической системы.
Типом алгебраической системы является следующее множество
{ 0(0), 1(0), -1(1), +(2), *(2)}
Алгебра, содержащая бинарную операцию, есть группоид. Алгебра, содержащая
бинарную операцию и единицу, называется группоидом с единицей. Алгебра (А,
+(2), 1(0)) является моноидом.
Алгебра (А, *(2), 1(0)) является группоидом с единицей.
9. Формальная логическая система с аксиоматикой свойств операций.
Построим формальную логическую систему на основе имеющейся алгебраической
системы.
Предметные константы:
Константы 1 и 0 – соответствуют картежам, описанным выше.
Множество переменных:
{A1, A2,…,А81 } – множество картежей, обозначенных латинскими буквами. Вид
картежа описан ранее.
Предикатные символы:
. Предикат W’ (A, B) соответствует отношению меньше по количеству
выпуклостей алгебраической системы; выполняется, если А ’ В.
. Предикат S” (A, B) соответствует отношению больше по количеству
вогнутостей алгебраической системы; выполняется, если А >” В.
. Предикат R’ (A, B) соответствует отношению равенства по количеству
выпуклостей алгебраической системы; выполняется, если А =’ В.
. Предикат R” (A, B) соответствует отношению равенства по количеству
вогнутостей алгебраической системы; выполняется, если А =” В.
. Предикат R (A, B) соответствует отношению равенства алгебраической
системы; выполняется, если А = В.
Функциональные символы:
. f+ соответствует операции наложения.
. f2+ (A, B) ( A + B.
. F* соответствует операции склеивания.
. f2* (Ai, Bj) ( Ai * Bj, i,j=[pic], |i – j| = 2.
. f-1 соответствует операции инверсия.
. f-1 (A) ( (A)-1.
Синтаксис термов:
Терм - всякая предметная константа, предметная переменная либо
функциональная форма.
Предикатная форма – предикатная константа, соединяющаяся с подходящим
числом терм:
P(t1, .., tm);
P( ).
Если fn – функциональный символ, t1, t2, …, tn – термы, то fn (t1, t2, …,
tn) также терм.
Понятие формулы в логике определим следующим образом:
. всякая предикатная форма есть формула;
. если А – формула, то А-1 тоже формула;
. если А и В - формулы, то А + В, А * В также формулы;
. если А - формула и хА - переменная, то (xА и (xA - формулы;
. других формул нет.
Для данной формальной логической системы справедливы следующие аксиомы:
1. E (f+(A, 0), A),
2. E ( f+(A, A), A),
3. ((i | i=[pic]) E (f*(Ai, f-1(Ai)),1i),
4. E (f+(A, B), f+(B, A)),
5. ((A | f-1(Ai) = 1i , i=[pic]) E (f*(Ai, 1i),Ai)
Формула общезначима (является тавтологией), если она истинна в любой
интерпретации.
Формула невыполнима (противоречива, тождественно ложна), если она при
всех интерпретациях является ложной.
Множество теорем определим как множество общезначимых формул.
Приведем примеры логического вывода:
1)Пусть А, В, С- любые формулы, тогда выводами являются следующие
последовательности:
а)A ( (B ( A);
б)A ( (B ( A), A ( (B ( A);
в)A ( (A ( A), (A ( (B ( C)) ( ((A ( B) ( (A ( C))
г)((A ((B) ( (B ( A), B ( (A ( B),(A ( ((B ( (A);
д)(A ( (A ( A)) ( ((A ( A) ( (A ( A)), (A ( (A ( A)),(A ( A) ( (A ( A):
[pic].
2)Выведем: ? A(u) ( (uA(u), где A(u) – любая предикатная формула.
Формула(u(A(u) ( (A(u), согласно аксиоме (xF(x) ( F(y), выводима. Формула
(p ( (q) ( (q ( (p) – тавтология и следовательно выводима. Из этого
следует, что предикатная формула (A ( (B) ( (B ( (A), где А, В- любые
формулы, выводима в исчислении предикатов. Тогда выводима и формула [pic].
Отсюда по правилу заключения ?A(u)(((u(A(u), то есть ?A(u) ( (uA(u).
Также можно использовать и следующие правила вывода:
? A ( B, ? B ( C, то ? A ( C
A? B, C ? D, B, D ? E, то A, B ? E
? A ( (B ( C), то? B ( (A ( C)
? A( (B ( C), то A + B ( C
? A + B ( C, то? A ( (B ( C)
? - символ « выводимости »
10. Блок-схема программы, демонстрирующей отношение и основные операции
алгебраической системы. Пример выполнения программы.
Ниже приведена блок-схема программы, содержащая функции и процедуры,
которые реализуют основные операции и отношения алгебраической системы, и
пример работы программы, в которой пользователем задаются 2 пазла – А и В
и вычисляется С = A + B, D = A * C, происходит сравнение А и В.
[pic]
-----------------------
[1] Все доказательства приведены для отношения больше(меньше) по количеству
вогнутостей; для отношения больше(меньше) по количеству выпуклостей
доказательство аналогичное.
[2] Для равенства по количеству вогнутостей и выпуклостей применяется
аналогичное доказательство.
-----------------------
[pic]
[pic]
[pic]
[pic]
| |
