• Гідрологія і Гідрометрія
• Господарське право
• Економіка будівництва
• Економіка природокористування
• Економічна теорія
• Земельне право
• Історія України
• Кримінально виконавче право
• Медична радіологія
• Методи аналізу
• Міжнародне приватне право
• Міжнародний маркетинг
• Основи екології
• Предмет Політологія
• Соціальне страхування
• Технічні засоби організації дорожнього руху
• Товарознавство продовольчих товарів

Предикати

1 2 3 4

ПЛАН

Discussion

Most theories of translation assume that the translator works consciously, analytically, alertly; the model presented in this chapter assumes that the translator only rarely works consciously, for the most part letting subliminal or habitual processes do the work. Speculate on the nature and origin of this difference of opinion. Are the traditional theories idealizations of the theorist's own conscious processes? Is this chapter an idealization of some real-world translators' bad habits? Exercises

1. Базові поняття

2. Основні закони правильного мислення

3. Класифікація міркувань

4. Дедуктивні міркування

4.1 Основні ідеї

4.2 Складні судження

4.3 Безпосередні умовиводи

5. Прості силогізми

6. Індуктивні міркування

7. Висновки за аналогією

8. Нечітка логіка

9. Предикати

10. Формальні теорії

11. Процедура резолюції

12. Формальні граматики

13. Теорія алгоритмів

14. Теорія імовірності й умовна ймовірність Байеса

1. Базові поняття

Під логікою в самому загальному змісті розуміється наука про закони мислення. Логіка вивчає побудову мір­кувань, що гарантують одержання правильних виведень із істинних посилок.

Математичний стиль мислення, за А.Я. Хінчином, визначається наступними особливостями:

1. Тверда схема міркування;

2. Лаконізм, свідоме прагнення знаходити найкоротший шлях до мети;

3. Чітка розбивка ходу міркувань на випадки й підвипадки;

4. Скрупульозна чіткість формулювань і символіки.

Математична (символічна) логіка будується на основі загальнолюдської й розробляє вирахування (насампе­ред висловлень і предикатів), що дозволяють застосувати математичні методи до аналізу форм і законів доказово­го міркування.

Інтерес до логіки зріс із появою ЕОМ – у зв'язку зі спробами навчити машину робити логічні висновки. Тому роботи в області інформатики й ШІ не можуть не опиратися на логіку.

Розглянемо основні ідеї, які лежать в основі логічних міркувань. Насамперед, відзначимо найважливіші прин­ципи діалектичної логіки:

1. Аналіз самого об'єкта, а не нашого подання про нього;

2. Розгляд конкретного об'єкта в конкретних умовах;

3. Аналіз тих і тільки тих його властивостей і зв'язків, які істотні в цих умовах;

4. Розгляд об'єкта (процесу) у його розвитку.

У логіці виділяють наступні форми мислення, поняття, висловлення й міркування.

Поняття про предмет представляє можливий варіант відповіді на питання «Що це?». З поняттям зв’язуються найбільш істотні (необхідні й достатні в сукупності) ознаки предмета. Поняття виражається словом.

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

Інтенсіонал поняття - це його визначення через більш загальне (родове поняття) із вказівкою видових відмінностей. Інтенсіонал поняття – це визначення його через співвіднесення з поняттям вищого рівня абстракції з вказівкою специфічних властивостей.

Інший спосіб визначає поняття через співвіднесення з поняттями нижчого рівня абстракції або перелік фактів, які відносяться до об'єкта, що визначається. Це є визначення через дані, або екстенсіонал поняття. Екстенсіональне визначення дається через поняття більш низького рівня ієрархії або факти (визначення через дані).

Приклад. Поняття “персональний комп'ютер”. Його інтенсіонал: “Персональний комп'ютер це дружня ЕОМ, яку можна поставити на стіл і купити менш ніж за $1000”. Екстенсіонал цього поняття: “Персональний комп'ютер це Мас, IВМ РС, Sincler...”.

Основними типами визначення понять є:

1. Порівняння – установлення подібності або розходження в поняттях;

2. Аналіз – розчленовування цілого на складові частини;

3. Синтез – створення цілого з деякого числа складових частин (ознак, властивостей, відношень);

4. Абстрагування – виділення в якому-небудь понятті певних ознак при відволіканні від інших;

5. Узагальнення – об'єднання різних об'єктів в однорідні групи на підставі загальних ознак,

6. Індукція – перерахування приватних прикладів і правило породження (як у мовах програмування).

Визначення повинне бути чітким, розмірним і не повинне містити логічного кола, тобто прямого або непря­мого посилання на себе ж. Приклади порушення перерахованих вимог:

1. Лев - цар звірів (це взагалі не визначення, а метафора).

2. Бочка - посудина для зберігання рідин. Це визначення в одному змісті широке (рідини можуть зберіга­тися не тільки в бочку), в іншому - вузьке (у бочці можуть зберігатися й сипучі речовини).

3. Кількість - визначення предмета з його кількісної сторони (логічне коло).

Усяке поняття має зміст – комплекс ознак предмета в даному понятті, і об'єм – сукупністю об'єктів, що вхо­дять у дане поняття. За об'ємом поняття діляться на порожні (реально не існуючі), одиничні й загальні (зокрема, універсальні, тобто що охоплюють всі предмети даного виду). З погляду змісту поняття діляться на позитивні й негативні (присутні чи ні певні ознаки в понятті), безвідносні й відносні, порівнянні й непорівнянні. У логічному відношенні один з одним перебувають тільки порівнянні поняття (у їхньому змісті присутні загальні ознаки). Вони бувають сумісними (об'єми понять мають співпадаючу частину) і несумісними. Виділяють три види відношень сумі­сності: рівнозначність, перетинання, підпорядкування об'ємів. Існують і три види відношень несумісності: супідря­дність, протилежність, протиріччя.

На рис.1 показані можливі відношення між порівнянними поняттями.

Рис. 1. Відношення порівнянних понять

Зв'язок між об'ємом і змістом понять виражається законом зворотного відношення: якщо два поняття порів­нянні в логічному змісті й зміст першого з них більше, ніж другого, то об'єм першого менше об'єму другого. Із цим законом зв'язане узагальнення (перехід від поняття з меншим об'ємом і більшим змістом до поняття з більшим об'ємом і меншим змістом) і обмеження (протилежний перехід).

Однією з основних логічних операцій над об'ємом і змістом понять є ділення поняття. При її виконанні розрі­зняють ділене поняття, підстава ділення (ознаки), члени ділення (множина понять, видових стосовно вихідного). Ділення повинне бути повним, за єдиною підставою, без перекриттів, безперервним (кожний крок ділення пови­нен проводитися на одному ієрархічному рівні). Приватним випадком ділення є дихотомічне (на два класи із супе­речливими ознаками). Практичне застосування операції ділення понять пов'язане із класифікацією — приведенням знань про предметну область у систему. Підстава ділення повинне відповідати цілі класифікації. Класифікація зав­жди має деревоподібну структуру.

Поняття є вихідним матеріалом для побудови висловлень (суджень). Із граматичної точки зору висловлення - просте речення. У висловленнях утримується інформація про предмети, явища, процеси тощо. Висловлення мо­жуть бути істинними або хибними.

Елементарне висловлення складається із суб'єкта S (логічний підмет – те, про що мова йде у висловленні), предиката Р (логічний присудок – те, що затверджується або заперечується у висловленні про суб'єкт), і квантора («всі», «деякі»).

Логічний зв'язок між суб'єктом і предикатом висловлення виражається зв'язуванням «є» або «не є» (у мно­жині «є» заміняється на «суть»), хоча в самому реченні це зв'язування може лише матися на увазі. Відповідність або невідповідність цього зв'язку реальності робить судження істинним або хибним.

Приклади висловлень:

1. Всі дельфіни - теплокровні.

2. Жоден кит не є рибою.

3. Туркменія - республіка.

За структурою висловлення діляться на прості (вони мають логічну форму "S є Р" або "S не є Р") і складні (граматично виражаються складними реченнями).

Прості висловлення бувають:

1. Атрибутивні (у них виражається приналежність або не приналежність якоїсь властивості об'єкту або класу
об'єктів). В атрибутивні висловлення часто включають кванторні зв'язування;

2. Про відношення між декількома об'єктами;

3. Про існування або не існування якого-небудь об'єкта або явища.

За якістю прості висловлення діляться на стверджувальні й негативні. З кількісної точки зору висловлення діляться на одиничні, приватні й загальні. У приватних судженнях слово «деякі» не виключає варіанта «всі». Перелічимо основні типи висловлень і їхнього позначення:

1. А - загальностверджувальні ("Усякий S є Р");

2. Е - загальнонегативні ("Усякий S не є Р");

3. І - частковостверджувальні ("Деякий S є Р");

4. О - частковонегативні ("Деякий S не є Р").

2. Основні закони правильного мислення

Найбільш важливими є логічні закони:

1. Тотожності.

2. Несуперечності.

3. Протиріччя.

4. Виключеного третього (у класичній логіці).

5. Достатньої підстави.

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

Закон несуперечності: два судження, в одному з яких щось стверджується, а в другому те саме, в той же час і в тому ж відношенні заперечується, не можуть бути одночасно істинними.

За законом протиріччя два суперечних один одному висловлення не можуть бути одночасно істинними: при­наймні одне з них хибне. Його формульнйй вид: А Ù Ø А º 0 (ми будемо позначати логічні константи "істина" і "не­правда" нулем і одиницею відповідно).

Закон виключеного третього: із двох суперечних суджень одне неодмінно є істинним, друге - хибним, а третього і бути не може. Якщо закон несуперечності діє і між суперечними, і між протилежними судженнями, то закон виключеного третього діє лише між суперечними судженнями - загальностверджувальним і частковозаперечним, загалmнозаперечним і частковостверджувальним, одиничним стверджувальним і одиничним заперечним.

Закон достатньої підстави вимагає, щоб жодне твердження не визнавалося справедливим без достатньої під­стави (яку підставу вважати достатньою – це питання особливе). Даний закон має змістовний характер.

3. Класифікація міркувань

Найпростішим видом міркувань є одержання з одного або декількох висловлень нового висловлення. З ви­словлень А₁, А₂,..., А_n слідує висловлення В, якщо В істино завжди, коли істині Аі, А₂,..., А_п. Вихідні висловлення називаються посилками, а нове висловлення В – висновком (наслідком). Можливість виведення висновку з поси­лок забезпечується логічним зв'язком між ними. Перевірити правильність виведення з посилок можна логічними засобами – без звертання до безпосереднього досвіду.

Істині з погляду логіки виведення формуються застосуванням правил логічного проходження (правил виве­дення). Звичайно вони записуються у вигляді А₁, А₂,..., А_{n ®} В або у вигляді дробу:

А₁, А₂,..., А_n

В

Логічне виведення — це в загальному випадку багатоетапний процес переходу від посилок до висновків і далі від отриманих висновків як нових посилок — до нових висновків. Залежно від наявності проміжних кроків мір­кування діляться на безпосередні та опосередковані. З іншого погляду вони класифікуються на:

1. Дедуктивні (від загального до приватного);

2. Індуктивні (від часткового до загального);

3. За аналогією (від приватного до приватного).

Дедуктивні міркування володіють найбільшою (строгою) доказовістю, а міркування за аналогією – наймен­шою.

4. Дедуктивні міркування

4.1. Основні ідеї

При дедуктивних міркуваннях уважається. що

1. Вихідні посилки міркування є істинними;

2. Істині посилки при правильному їхньому застосуванні породжують тільки істині наслідки.

У логіці особливу роль грають логічні форми, істинність яких справедлива внаслідок їхньої структури. їх на­зивають тавтологіями, або загальнозначущими формами.

Правила виведення при дедуктивних міркуваннях, по суті, описують тавтології.

Розглядаються два види формальних логічних конструкцій: терми — аналоги імен іменників і формули — аналоги речень.

Формули зі змінними, які обертаються у висловлення при підстановці замість змінних яких-небудь значень, називають висловлювальними формами.

У сучасній математичній логіці реченню, що виражає властивості предмета х, зіставляється логічна функція Р(х) однієї змінної, що називається одномісним предикатом. Значення предиката — "істина" або "неправда". Від­ношення між п суб'єктами задається n-місцевим предикатом Р(х₁,х₂,...,х_n). Порядок аргументів предиката у всіх випадках повинен дотримуватися той самий.

4.2. Складні судження

Слова "НЕ", "І", "АБО", "ЯКЩО... ТО", "ТОДІ Й ТІЛЬКИ ТОДІ", "ІСНУЄ", "ВСІ" і деякі інші називають логічними зв'язуваннями (операторами) і позначають логічні операції, за допомогою яких з виражень, що позначають деякі поняття, будуються більш складні. Логічні зв'язування співвідносяться з логічними операціями:

Особливо важливе значення має зв'язування "імплікація", оскільки саме вона використається при записі продукцій.

Складні висловлення залежно від зв'язування підрозділяються на:

1. Сполучні (зв'язування І);

2. Розділові (зв'язування АБО), застосовується у двох варіантах:

а) нестрога диз'юнкція "АБО А, АБО В, АБО ОБИДВА";

б) струга диз'юнкція - "АБО А, АБО В" (виключне АБО - допускається тільки одна з альтернатив);

3. Умовні (зв'язування "ЯКЩО ... ТО" - імплікація);

4. Судження еквівалентності (зв'язування 'ТОДІ Й ТІЛЬКИ ТОДІ");

5. Змішані висловлення (використовують різні зв'язування).

Логічні зв'язування "ДЛЯ ВСЯКОГО", "ІСНУЄ" називаються кванторами. Вони відносяться до змінних в речен­ні (ці змінні вважаються зв'язаними) і позначаються V і 3 відповідно. Квантори дозволяють формувати загальні й приватні судження.

4.3. Безпосередні умовиводи

Використання умовиводів вимагає обліку розподіленості термінів S і Р. Термін уважається розподіленим, як­що його об'єм цілком входить в об'єм іншого терміна або цілком з нього виключається. Суб'єкт розподілений у за­гальних й не розподілений у приватних судженнях; предикат - розподілений у негативних й не розподілений у стверджувальних судженнях. Одиничний об'єкт розподілений завжди.

Обіг — це зміна ролей суб'єкта й предиката. Обіг не міняє кількісну характеристику понять. Якщо предикат вихідного судження не розподілений, то він не може бути розподілений і у висновку, де стає суб'єктом. Тому його об'єм повинен бути обмежений.

Таким чином, можливі обіги А ® І (з обмеженням), Е ® Е , І ® І.

Всі S суть РЖодне S не є Р

Деякі Р суть S Жодне Р не є S

Не обертаються судження частковонегативні та ті, що мають мнимі предикати. У випадку перетворення якість судження змінюється на протилежне, а предикат заміняється на суперечний йому термін.

Всі S суть РДеякі S не суть P

Жоден S не є –P Деякі S суть не –P

Протиставлення предикату утворюється послідовним застосуванням перетворення й обертання посилки:

Всі S суть Р

Всі не - Р не суть S

Відношення між порівнянними висловленнями наочно демонструє "логічний квадрат" (рис. 2).

Рис. 2. Логічний квадрат

У вершинах квадрата зазначені типи простих суджень. Боки й діагоналі квадрата виражають різні логічні відношення між висловленнями:

1. Підпорядкування за істинністю: з істинності загального висловлення типу А або Е логічно слідує істинність висловлення І (відповідно О);

2. Підпорядкування за хибністю: з хибності приватного твердження І або О логічно слідує хибність вислов­лення А (відповідно Е);

3. Протиріччя: якщо одне із суджень у парі А і О, І і Е істинно, то інше хибне;

4. Протилежність (контрарність) між висловленнями А і Е – вони можуть бути одночасно хибними, але не можуть бути одночасно істинними;

5. Субконтрарність між висловленнями І і О: вони можуть бути одночасно істинними, але не можуть бути одночасно хибними.

5. Прості силогізми

Серед опосередкованих висновків найбільш важливі силогізми – умовиводи, у яких із двох категоричних суджень, зв'язаних загальним (середнім) терміном, виходить третє судження – виведення. Меншим терміном силогізму називають суб'єкт ви­сновку, більшим - його предикат. Кожний із цих (крайніх) членів входить і в одну з посилок, відповідно іменованих меншою й більшою. Середній термін входить в обидві посилки й відсутній у висновку.

При побудові силогізмів керуються відомими з античних часів правилами, що ведуть від істинних посилок до істинних висновків:

1. У силогізмі повинні бути тільки три терміни (часта помилка - "учетверення термінів", коли один із трьох термінів неявно використовується у двох змістах).

2. Середній термін повинен бути розподілений принаймні в одній з посилок.

3. Термін, не розподілений у посилці, не може бути розподілений у висновку

4. Хоча б одна з посилок повинна бути загальним судженням.

5. Хоча б одна з посилок повинна бути стверджувальним судженням.

6. Якщо одна з посилок негативна, то висновок повинен бути негативним.

7. Якщо одна з посилок приватна, то висновок також повинен бути приватним.

Розрізняють чотири фігури силогізму:

Для різних фігур силогізмів існують свої додаткові правила:

1. У першій фігурі більша посилка повинна бути загальною, а менша - стверджувальною. Ця фігура найбільш
типова для дедуктивного умовиводу.

2. У другій більша посилка повинна бути загальна, а одна з посилок і висновок - негативними.

3. У третій менша посилка повинна бути стверджувальною, а висновок - приватним.

4. Четверта фігура до загальностверджувальних висновків не приводить.

Найбільш часті порушення цих правил:

1. Висновок по першій фігурі з меншою негативною посилкою;

2. Висновок по другій фігурі із двома стверджувальними посилками.

З урахуванням зазначених правил із загального числа 4³ = 64 комбінацій типів посилок і висновку (А, Е, І, О) лише 19 виявляються припустимими.

6. Індуктивні умовиводи

Індуктивні умовиводи – це міркування, у яких рух думки йде від часткових випадків до загальної закономірності (Україна – країна Європейського континенту. Білорусь - країна Європейського континенту. Обидві країни – європейські);

Серед принципово іншого виду умовиводів - індуктивних - виділяють такі:

1. повна індукція – заключення належить тільки до тих випадків, які розглянуті у посилках. Наприклад: Прямокутні трикутники мають площу, що дорівнює половині добутку (множенню) основи на висоту. Тупокутні трикутники мають площу, яка дорівнює половині добутку основи на висоту. Гостровугільні трикутники мають площу, яка дорівнює половині добутку основи на висоту. Значить всі трикутники мають площу, яка дорівнює половині добутку основи на висоту.

2. неповна індукція – заключення належить не лише до випадків, які розглянуті у посилках, але і до всіх випадків того ж роду.

Правдоподібні індуктивні міркування проводяться з обліком не тільки повторюваності ознак в об'єктів деяко­го класу, але і їхнього взаємозв'язку й причинної залежності між даними ознаками й властивостями розглянутих об'єктів. Формулюються вони у вигляді принципів єдиного розходження, єдиної подібності, єдиного залишку й ана­логії.

Єдине розходження.Якщо при незмінних інших умовах після введення якого-небудь фактору з'являється (або після видалення його зникає) деякий ефект, то зазначений фактор і становить причину ефекту.

Єдина подібність.Якщо всі обставини, крім одного, можуть бути відсутніми, не знищуючи цим ефекту, то це одна обставина є причиною ефекту.

Єдиний залишок.Якщо відняти з якого-небудь явища ту частину його, що відповідно до колишніх дослі­джень виявляється наслідком присутніх у явищі відомих причин, то залишок явища є наслідок інших причин (при­клад - зроблене Левер'є відкриття Нептуна за відхиленням Урана від розрахункової орбіти).

Застосовуються також нечіткі виведення, коли істинність посилок установлена з деяким ступенем упевнено­сті й висновок виведений з певним ступенем вірогідності (ймовірності). Математичне обґрунтування нечітких ви­ведень будується на теорії нечітких множин Л. Заді.

7. Висновки за аналогією

Аналогією називається такий умовивід, в якому від схожості предметів в одних ознаках робиться висновок про схожість цих предметів і в інших ознаках.

Умовивід за аналогією відбувається так: якщо порівнюючи два предмета, встановлюють, що предмет А має ознаки abcd, а предмет В має ознаки abc, то роблять здогалний висновок про те, що предмет В має і ознаку d.

Схематично структуру умовиводу за аналогією можна записати так:

А має ознаки abcd

В має ознаки abcd

Отже, В має ознаку d

Приклад аналогії:

Із всіх плоских фігур рівної площі найменший периметр має коло

Із всіх тіл рівного об'єму найменшу поверхню має куля

Аналогія лежить в основі моделювання – методу вивчення об'єктів і процесів за їхніми моделями. Нестрога аналогія приводить лише до ймовірних висновків. Відомі наступні способи збільшення ймовірності правильного висновку:

1. Використання причинних зв'язків,

2. Збільшення числа ознак,

3. Облік ступеня подібності ознак,

4. Збільшення різнорідності ознак,

5. Зважування подібності й розходження з урахуванням важливості ознак.

8. Нечітка логіка

Не завжди можна описати подію за допомогою точно певних правил. Наприклад, можна сказати, що в лю­дини легке нездужання, якщо в нього температура більше 37°, але менше 38°, а при більшій температурі захво­рювання може виявитися серйозним. Люди не завжди можуть відповісти на питання точно. Чи можна довідатися, яка в людини температура, якщо він говорить, що злегка занедужав? Швидше за все, ні. Такі слова, як високий, гарячий і легкий, являють собою лінгвістичні змінні, які не можна визначити одним значенням. Використання цих понять при формулюванні правил називається нечіткою логікою.

Лінгвістичні змінні використовуються в базі знань для виконання логічних виведень. Для їхнього аналізу за­стосовуються формули теорії ймовірностей. При цьому в оцінці значень змінних присутні такі поняття, як малень­кий, середній, великий. Варто пам'ятати, що значення ймовірностей, що беруть участь в обчисленнях, визначаю­ться відповідно до конкретної ситуації й працюють тільки в її рамках.

Предикатом Р(хі,...,х_п) називається логічна функція n змінних – не обов'язково логічних. Точніше предикатом Р(х1,...,хn) називається функція, змінні якої набувають значень із деякої множини М, а сама вона набуває двох значень: 1 (істинне) і 0 (хибне), тобто Р(х1,...,хn): Мn → {1, 0}. Наприклад, преди­кат T(x²+y²<R²) перевіряє знаходження точки з координатами (х,у) усередині окружності радіуса R із центром на початку координат, а предикат U("cum" є "cucumber") – входження першого символьного рядка в інший.

У вирахування предикатів входять квантори. Квантор — загальна назва для логічних операцій, що обмежують область істинності якого-небудь предиката. Найчастіше обмежуються квантором загальності V (позначення:, читається: «для всіх.», «для будь-якого.» або «будь-який.») і квантором існування E (позначення:, читається: «існує.» або «знайдеться.»).

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

При інтерпретації предикатів можливі три основних ситуації:

1. формула здійсненна, тобто існує набір констант, що робить предикат істинним: x²+y²<R²

2. формула здійсненна для будь-яких наборів (загальнозначуща): cos(x+y) = cos(x)cos(y)-sin(x)sin(y)

3. формула нездійсненна (суперечлива): n=n+1.

10. Формальні теорії

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

В алфавіт мови системи входять предметні константи, предметні змінні, предикатні константи, предикатні змінні, логічні зв'язування й квантори, допоміжні символи (дужки, коми тощо).

Множина слів мови складається із правильно побудованих формул (ППФ). Це аксіоми, що задаються насам­перед при побудові теорії. Правила виведення дозволяють одержувати з аксіом нові ППФ – теореми. Множина аксіом називається незалежною, якщо ні одну з них не можна, вивести із сукупності інших. Часто для спрощення доказу теорем у систему аксіом включають і залежні.

Безпосередня виводимість F з Fi,F₂,...,F_n записується у вигляді ------------- . Над рисою записуються передбачувані істинними посилки, під рисою – висновок). Факт виводимості позначається Fi,F₂,...,F_n \- F. Мітка d служить для посилань на правило.

У формальних системах логічного типу в множину аксіом завжди входять логічні, використання яких поряд зі специфічними для даної теорії правилами виведення дозволяє формалізувати процес доказу.

Логічне вирахування будемо називати несуперечливим, якщо в ньому не виведені одночасно F і F . У супе­речливих вирахуваннях виведена будь-яка формула. Остання обставину можна використати для доказу несуперечності вирахування: досить показати існування в ньому невиведеної формули.

11. Процедура резолюції

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

У сучасних системах автоматизації логічного виведення широко використається метод резолюцій. У проце­дурі резолюцій замість заданої формули F, передбачуваної тотожно істинною, розглядають її заперечення -iF і на­магаються довести його суперечливість. Це власне кажучи "доказ від противного". У його основі лежить операція виключення з різних пропозицій висловлень-резольвент, якщо ці висловлення в одних пропозиціях заперечують­ся, а в інших - ні. Необхідна суперечливість встановлюється як одночасна справедливість двох взаємовиключних висловлень. Якщо процес виведення резольвент обірветься, не привівши до протиріччя, то вихідна теорема невір­на. Достоїнством методу резолюцій є можливість виявлення протиріччя набагато раніше, ніж буде виконаний пов­ний перебір можливостей. Розроблено багато евристичних поліпшень спрямованості й тим самим - швидкодії ме­тоду.

Спочатку запишемо відомі істинні факти у вигляді логічного добутку диз'юнктивних форм:

1. BvA

2. CvB

3. С

Допустимо, що ми хочемо довести А. Щоб це зробити, доповнимо заданий набір запереченням А:

1. BvA

2. CvB

3. C

4. A

Виключимо тепер знову введене речення і його заперечення в іншому реченні. Цей процес називається ре­золюцією (може бути, тому, що резолюції найчастіше негативні??). Наприклад, ми можемо виключити А й А в

першому, залишивши в них без зміни сукупність інших висловлень (таку сукупність називають резольвентою). У результаті залишаються

1. В

2. CvB

3. С

Тепер виключимо В в першому реченні й В ­– у другому:

1. С

2. С

Крім обох залишившихся речень, одержуємо порожнє речення, що означає істинність А. Правила виведення представляються як В D Е -> А (хорновські диз'юнкти).

Вибір пари речень, що зіставляються при виборі чергової резольвенти, реалізується в ієрархічно організова­ному просторі станів - дереві І/АБО на основі стратегії "углиб, починаючи ліворуч". Задана мета Р зіставляється з першим реченням, що має Р у якості висновку. Потім доводиться перший компонент відповідного диз'юнкта, і т.д.

12. Формальні граматики

Виникнення метаматематики (у зв'язку з роботами по обґрунтуванню математики) і її розвиток, структурні дослідження в лінгвістиці й особливо роботи з машинного перекладу (зокрема, з алгоритмічних мов на машинний) привели до створення науки про осмислені знакові системи.

Формальна мова— це множина формальних ланцюжків символів алфавіту, породжуваних граматикою мови.

Остання визначається як четвірка об'єктів G=<T,U,A,P>, у якій Т - множина термінальних (алфавітних) сим­волів; U - множина нетермінальних символів, що утворять ієрархічну систему похідних понять мови; А - найбільш загальне поняття, називане аксіомою (у випадку алгоритмічних мов - програма в цілому); Р - сукупність правил виведення.

Як приклад такого правила приведемо (у нотації Бекуса) визначення ідентифікатора для мови програмуван­ня:

<ідентифікатор>::=<літера> | <ідентифікаторхлітера> | <ідентифікаторхцифра>

(послідовність літер і цифр, що починається з літери).

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

Практичні застосування теорії формальних граматик (ТФГ) зв'язані переважно з аналізом вхідного ланцюжка символів – точніше, зі зборкою з неї понять, що класифікують. Зокрема, досить плідним виявилося застосування ТФГ для систем штучного інтелекту, що вирішують задачі технічної діагностики й аналізу телеметричної інформа­ції. Складність цих задач залежить від класу граматики, що визначається типом правил, що породжують (зокрема, залежністю їх від контексту для ланцюжків символів). Найпростіші граматик відповідають кінцевим автоматам. Ме­тоди ТФГ застосовуються й при розробці людино-машинного інтерфейсу в СШІ.

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

13. Теорія алгоритмів

Алгоритмом прийнято називати будь-яку кінцеву систему правил перетворення інформації над кінцевим ал­фавітом. Літери алфавіту являють собою первинний тип елементарних даних, слова, що із них складаються, мо­жуть розглядатися як одномірні масиви. З літер і слів формуються нові (структуровані) типи даних. Над такими даними визначаються специфічні операції. За допомогою операцій будуються формули мови - вирази. Оператори мови роблять перетворення даних і можуть містити посилання на оператор, виконуваний наступним. Програма з формальної точки зору являє собою кінцеву впорядковану послідовність операторів.

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

Основні вимоги до алгоритмів:

1. Алгоритм має справу з даними - вихідними, проміжними й вихідними, записаними в деякому алфавіті, і за­
стосовується до різних наборів даних.

2. Алгоритм складається з окремих елементарних кроків, спосіб виконання яких системі відомий.

3. Послідовність кроків детермінована.

4. Алгоритм закінчується після кінцевої кількості кроків.

Алгоритмічні мови – лише засоби для запису алгоритмів. Для фактичного виконання останніх потрібно де­яка інтерпретуюча система.

Відомо кілька десятків універсальних алгоритмічних моделей, які в остаточному підсумку виявилися еквіва­лентними. Частіше інших використовуються

1. Рекурсивні функції,

2. Машини Т'юрінга,

3. Продукційна система Поста,

4. Нормальні алгоритми Маркова.

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

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

14. Теорія імовірності й умовна ймовірність Байеса

Теорія ймовірностей вивчає випадкові події. Дуже часто людина, сама того не зауважуючи, висловлює при­пущення або робить виведення, користуючись термінологією теорії ймовірностей. Наприклад, "Я на 80 відсотків упевнений, що все в порядку".

кількість експеріментів, ісходом яких є якась подія

загальна кількість експеріментів

Імовірність можна визначити в такий спосіб:

Припустимо, що експеримент полягає у дворазовому киданні монети. Можливі різні ісходи цих експеримен­тів.

Читайте також:

1. МОДУЛЬ 2: «Висловлення. Предикати. Теореми.».
2. МОДУЛЬ 2: «Висловлення. Предикати. Теореми.».
3. Предикати

Переглядів: 1092