Разработка формальной системы (стр. 1 из 2)
Министерство образования Российской Федерации
Рязанская государственная радиотехническая академия
Кафедра ВПМ
Разработка формальной системы
по дисциплине “Математическая логика”
Проверил: Каширин И. Ю.
Рязань 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=
.Определение 2. Весом вогнутостей пазла А называется величина Vвг(А), равная количеству сторон при ai = -1, i=
.Определение 3. Модулем пазла А называется величина М(А), определяемая следующим уравнением:
М(А)=
,где qi и bi :
; 
где 
Отношение меньше (больше).
Определение 4. Пазл А меньше (больше) пазла В по количеству выпуклостей (по количеству вогнутостей) если вес выпуклостей (вогнутостей) А меньше (больше) веса выпуклостей (вогнутостей) пазла В, т.е.
А <” B (A >” B), если Vвп(A) < Vвп(B) (Vвп(A) > Vвп(B))
[А <’ B (A >’ 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<’B по количеству выпуклостей;
VМвг(A) =1; Vвг(В)=1; Vвг(A) = Vвг(B), значит A=”B по количеству вогнутостей;
М(А)=1200; М(В)=221; М(А) ≠ М(В), значит A ≠ B.
4. Свойства отношений.
Отношение больше (меньше)1.
1) Отношение антирефлексивно.
Доказательство. Отношение А <” A (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вг(C) => 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 =
где i =
Операция наложения справедлива для любых пазлов.
Операция имеет вид:
С = А + В.
Примеры.
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> называется алгебраической системой, где А – множество однотипных элементов, называемое носителем алгебры или базовым множеством, Ω – множество операций с областью определения и областью значений в множестве А, R – множество отношений на элементах множества А.
Множество А представляет собой множество всех пазлов, представленных в виде картежей, описанных выше.
Сигнатура алгебры Ω = { + , * , -1() , 0 , 1 }.
R = {<, <’, <”, >, >’, >”, =, =’, =”}
Согласно определению операций, мы получим пазл в виде картежа, описанного выше, значит мы получим элемент базового множества, что говорит о замкнутости операций.
7. Свойства операций.
Свойство единицы:
А + А-1 = А-1 +А = 1 – сильная единица:
Аi * 0 = 0 * Ai = A, i=
- слабая единица;Операция наложения.
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 – соответствуют картежам, описанным выше.