Разработка формальної системы

року міністерство освіти Російської Федерации.

Рязанська державна радіотехнічна академия.

Кафедра ВПМ.

Розробка формальної системы.

Пояснювальна записка до курсовому проекту.

з дисципліни «Математична логика».

Перевірив: Каширин І. Ю.

Рязань 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), т. е.

В якості відносин візьмемо бінарні відносини менше () і рівність (=) елементів по:

. кількості опуклостей (>'; «; Vвп (B)).

[А ' B), якщо Vвг (A) < Vвг (B) (Vвг (A) > Vвг (B)) ]. Ставлення більше є зворотним до відношенню менше, тобто. якщо 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 Vвг (A)). 2) Ставлення антисимметрично. Доказ. Якщо, А «B) то Vвг (A) < Vвг (B) (Vвг (A) > Vвг (B)) => умова Vвг (A) > Vвг (B) (Vвг (A) < Vвг (B)) не так, звідси не так, що, А >» B (A B = A. 3) Ставлення транзитивно. Доказ. Нехай, А = У, У = З, тоді М (A) = М (B), М (B) = М© => М (A) = М© => A = З. Ставлення рівності є ставленням эквивалентности.

5. Операції на безлічі об'єктів предметної області. Їх семантика. Будемо розглядати дві бінарні операції: накладення (+) і склеювання (*); унарная операція: інверсія (()-1) і нульарные: операції слабкої (0) і сильної (1) единицы.

Операция слабка одиниця — 0. Ця операція — константа 0 представляє - собою картеж виду (0,0,0,0) Операція сильна одиниця — 1. Ця операція — константа 1i — є одне із картежей:

. (1, 0, -1, 0), при і =1;

. (0, 1, 0, -1), при і =2;

. (-1, 0, 1, 0), при і =3;

. (0, -1, 0, 1), при і =4; де і визначає бік з елементом «опуклість». Операція накладення. Ця операція накладає один пазл в інший, у результаті виходить новий пазл. Новий пазл утворюється з такого правилу: Правило бічних граней: якби накладываемой боці 1го пазлу перебуває опуклість, а й у 2го пазлу на відповідної боці - увігнутість, то результатом буде порожня сторона якби сторони обох пазлів перебувають опуклість (чи увігнутість), то результаті вийде сторона опукла (вогнутостью) якщо сторона однієї з пазлів є пустопорожньою, то результуюча сторона матиме хоча б елемент, як і сторона другого пазлу вищесказане можна відобразити формулами:

З = A + B: c’i = ai + bi ci = [pic] де і = [pic] Операція накладення справедлива для будь-яких пазлів. Операція має вид:

З = А + У. Приклади. 1) А = (0, 0, -1, 1),.

У = (-1, 1, -1, -1).

A + B = З = (-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 + З) ((A + B) + З. Властивості стосовно операції склеювання: 4) Операція не дистрибутивна зліва, т. до. A + (B * З)? (A + B) * (A + З) 5) Операція не дистрибутивна справа, т. до. (A * B) + З? (A + З) * (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) відповідає відношенню менше за кількістю опуклостей алгебраїчній системи; виконується, якщо, А «У.. Предикат R' (A, B) відповідає відношенню рівності за кількістю опуклостей алгебраїчній системи; виконується, якщо, А =' У.. Предикат R» (A, B) відповідає відношенню рівності за кількістю вогнутостей алгебраїчній системи; виконується, якщо, А =" У.. Предикат R (A, B) відповідає відношенню рівності алгебраїчній системи; виконується, якщо, А = У. Функціональні символи:. f+ відповідає операції накладення.. f2+ (A, B) (A + B.. F* відповідає операції склеювання.. f2* (Ai, Bj) (Ai * Bj, i, j=[pic], |і - 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=[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 (З)) (((A (B) ((A (З)) г)((A ((B) ((B (A), B ((A (B); INSERT INTO `ref` (`id_predmet`, `name_predmet`, `id_ref`, `name_ref`, `text_ref`) VALUES (A (((B ((A); д)(A ((A (A)) (((A (A) ((A (A)), (A ((A (A)); INSERT INTO `ref` (`id_predmet`, `name_predmet`, `id_ref`, `name_ref`, `text_ref`) VALUES (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 (З, то? A (З A? B, З? D, B, D? E, то A, B? E? A ((B (З), то? B ((A (З)? A ((B (З), то A + B (З? A + B (З, то? A ((B (З)? — символ «выводимости «.

10. Блок-схема програми, що демонструє ставлення, і основні операції алгебраїчній системи. Приклад виконання програми. Нижче приведено блок-схема програми, що містить функції і складні процедури, які реалізують основні операції, і відносини алгебраїчній системи, і приклад роботи програми, у якій користувачем задаються 2 пазлу — Проте й У і обчислюється З = A + B, D = A * З, відбувається порівняння Проте й В.

[pic].

———————————- [1] Усі докази наведено для відносини больше (меньше) за кількістю вогнутостей; для відносини больше (меньше) за кількістю опуклостей доказ аналогічне. [2] Для рівності за кількістю вогнутостей і опуклостей застосовується аналогічне доказательство.

———————————- [pic].

[pic].

[pic].

[pic].