Аксіоматична побудова обчислення висловлювань.

КАТЕГОРІЇ:

Автомобілі Астрономія Біологія Географія Будинок і сад Інші мови інше Інформатика Історія Культура література логіка Математика Медицина металургія механіка Освіта Охорона праці Педагогіка політика право Психологія релігія риторика Соціологія Спорт Будівництво технологія туризм фізика Філософія фінанси хімія Креслення Екологія Економіка електроніка

1. VII В залежності від порядку обчислення податку на прибуток
2. Адміністративно-територіальний побудова Російської Федерації
3. Б1-В2 Побудова орнаменту в смузі
4. В 2. Нормативний капітал банку, його сутність, значення, методика обчислення.
5. В 2. Показники достатності нормативного капіталу і методика їх обчислення.
6. В 2. Економіч. характер. рес. (Пасивів) банку, їх классиф., Методика обчислення.
7. Питання 2. Акцизи на алкогольну і тютюнову продукцію: особливості обчислення та сплати. Зміни, які вступили в силу в 2013-2014гг.
8. Питання 3. Акциз: сутність акцизів, платники, об'єкт оподаткування, механізм обчислення і сплати, перспективи розвитку.
9. Питання 3. Податок на доходи фізичних осіб в Російській Федерації: основи побудови, механізм обчислення і сплати, порядок стягнення і повернення податку.

Розглянутий вище підхід до обчислення висловлювань (шляхом їх подання у вигляді пропозіціонних форм, проведення еквівалентних перетворень цих форм з метою їх спрощення, побудови таблиць істинності і встановлення факту тотожною істинності висловлювання) базувався на інтуїтивних, змістовних поняттях і отримав назву «теорії моделей», коли ставив різні можливі значення пропозіціонних букв (істина або брехня) у всіляких комбінаціях ми отримували «моделі», «реалізації», «втілення» того, що можуть висловлювати ті чи інші висловлювання.

Зараз ми розглянемо інший підхід до побудови логіки та обчислення висловлювань; а саме, аксіоматичний підхід або метод формальних теорій. Цей підхід ще називають теорією доказів, і він пов'язаний з питанням про те, чи не можна описати логічні докази і висновки так, як це робиться в геометрії. Введемо ряд визначень.

Формальна (аксіоматична) теорія Т вважається певної, якщо виконуються наступні умови:

1. Визнач кінцеве або рахункове безліч символів теорії Т (безліч, елементи якого можна поставити у взаємно однозначну відповідність числах натурального ряду 1, 2, 3, ... називається рахунковим). Кінцеві послідовності символів теорії Т називаються виразами цієї теорії Т;

2. Є ефективно розпізнавати підмножина виразів теорії Т, зване формулами цієї теорії;

3. Виділено деяку підмножину формул, які називаються аксіомами теорії Т;

4. Є кінцеве безліч правил виведення P1, ..., Pn. Для кожного правила Pi існує деяке позитивне значення j, таке, що для кожного підмножини містить j формул і деяку форму А, ефективно вирішується питання про застосування правила Pi до цього подмножеству формул і формулою А. Якщо правило застосовується, то А називається наслідком даних формул по правилом Pi.

Під словом «ефективно» мається на увазі те, що існує деяка зумовлена послідовність дій (тобто алгоритм, процедура), що дозволяє за кінцеве число кроків відповісти на необхідний питання позитивно або негативно.

Висновком в теорії Т називається будь-яка кінцева послідовність А1, ..., Аn формул така, що для будь-якого i формула Аi є або аксіома теорії Т, або безпосередній наслідок будь-яких попередніх формул по одному з правил виведення.

Формула А теорії Т називається теоремою цієї теорії, якщо існує висновок в Т, в якому останній формулою є А. Такий висновок називається доказом (висновком) формули А.

Слід зазначити, що поняття теореми не обов'язково ефективно, тобто може і не існувати ефективної процедури, що дозволяє визначити по цій формулі, чи існує її висновок в теорії Т. Теорія, для якої такий алгоритм існує називається вирішуваною, в іншому випадку - нерозв'язною.

Формула А є наслідком безлічі формул Г в теорії Т тоді і тільки тоді, коли існує така кінцева послідовність формул А1, ..., Аn, що Аn є А і для кожного i Ai є або аксіома, або елемент Г, або безпосередній наслідок деяких попередніх формул по одному з правил виведення. Така послідовність називається висновком А з Г. Члени безлічі формул Г називаються гіпотезами або посилками виводу. Затвердження типу «А є наслідок Г» позначають Г├А (можна читати «Г дає А»). Для вказівки того, що А є наслідок Г саме в теорії Т користуються позначенням Г├тА. Для кінцевого безлічі Г = {В1, ..., Вn},

(Де Вi∈Г елементи безлічі Г) замість {В1, ..., Вn} ├тА зазвичай пишуть В1, ..., Вn├тА.

Якщо Г порожня множина ∅ (тобто множина не містить жодного елемента), то Г├А тоді і тільки тоді, коли А є теоремою (тобто аксіомою або формулою

виведеної з аксіоми). Замість ∅├А пишуть ├А (тобто А теорема). Очевидними є такі властивості поняття виводимості:

1. Якщо Г⊆ Δ (тобто «Г підмножина Δ», «Г включається в Δ») і Г├А, то Δ├А. Тобто якщо А виводиться з Г, то воно виводиться буде якщо до Г додати нові посилки.

2. Г├А тоді і тільки тоді, коли в Г існує кінцеве підмножина Δ, для якого Δ├А. Достатність умови випливає з попереднього властивості. Необхідність випливає з того, що кожен висновок А з Г використовує лише кінцеве число посилок з Г.

3. Якщо Δ├А і Г├В для будь-якого В з безлічі Δ, то Г├А, тобто якщо А виводиться з Δ і кожна формула з Δ виведена з Г, то А виводиться з Г.

Дата додавання: 2015-04-18; переглядів: 30; Порушення авторських прав