Численні висловів

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

Передбачається, що читач знайомий з основними концепціями булевої алгебри Але для використання як посилань повторимо деяких законів булевої алгебри, які нам будуть потрібні надалі

■ Розподільні закони

f AND ( g OR h ) ≡  ( f AND g ) OR ( f AND h ) f OR ( g AND h ) ≡  ( f OR g ) AND ( f OR h )

■ Закони де Моргана

NOT ( f AND g ) ≡  ( NOT f ) OR ( NOT g )

NOT ( f OR g ) ≡  ( NOT f ) AND ( NOT g )

Тут f, g і h – довільні логічні вирази

Тепер звернемося до логіки як такої Логіку можна розглядати як формальний метод проведення міркувань Оскільки метод проведення міркувань формалізований, він може використовуватися для вирішення формальних завдань, таких як перевірка допустимості фактичного параметра шляхом дослідження лише структури цього фактичного параметра у вигляді стандартної послідовності кроків (наприклад, в якій не приділяється жодної уваги змістом самих цих кроків) Зокрема, оскільки це – формальний метод, він може бути автоматизований (іншими словами, запрограмований) і тому його виконання можна покласти на деякий механізм

Обчислення висловлювань і числення предикатів-це, взагалі кажучи, два особливих напрямки логіки (фактично перше є підмножиною останнього)

Термін числення, в свою чергу, являє собою просто загальний термін, який відноситься до будь-якій системі символічних обчислень в даних розглянутих випадках обчислення являє собою визначення истинностного значення (TRUE або FALSE) деяких формул або виразів

Терми

Почнемо цей розділ з припущення, що є деяка колекція обєктів, званих константами, стосовно до яких ми можемо висловлювати твердження різного роду У термінах баз даних ці константи представляють собою значення з відповідних доменів, а твердженнями можуть бути, наприклад, логічні вирази, такі як 3> 2 . Визначимотерм як твердження, яке включає такі константи2 і відповідає наведеним нижче вимогам:

а) або не включає ніяких логічних операторів (див наступний підрозділ), чи бо укладено в круглі дужки

б) в результаті обчислення недвозначно приймає значення або TRUE, або

FALSE

Наприклад, всі наступні твердження є термами: Постачальник S1 знаходиться в Лондоні, Постачальник S2 знаходиться в Лондоні і Постачальник S1 поставляє деталь Р1 (При зазвичай використовуваних нами значеннях даних вони приймають значення, відповідно, TRUE, FALSE і TRUE) На відміну від цього, такі твердження не є термами, оскільки вони не приймають недвозначно значення TRUE або FALSE: Постачальник S1 поставляє деталь р (Де р – змінна) і Постачальник S5 буде поставляти деталь Р1 колись у майбутньому.

Формули

Потім визначимо поняття формули Формули числення висловів і, взагалі кажучи, числення предикатів використовуються в системах баз даних (крім усього іншого) при формулюванні запитів і будуються за правилами, показаним нижче

&ltformula&gt

::=   &ltterm&gt

| NOT  &ltterm&gt

I &ltterra&gt AND  &ltformula&gt

I &ltfcerm&gt  OR  &ltformula&gt

| &ltterm&gt

&ltformula&gt

&ltterm&gt

::=    &ltatomic  formula&gt

| (  &ltformula&gt  )

Формули обчислюються відповідно до істиннісними значеннями складових їх термів, із застосуванням звичайних таблиць істинності для логічних операторів (AND, OR і тд) З цього випливають наведені нижче висновки

2 Точніше, містить імена таких констант або, іншими словами, літерали В основній частині літератури відмінність між цими поняттями практично не враховується

1 Показана в визначенні структури формули &ltformula&gt атомарна формула

&ltatomic formula&gt — це логічне вираз, який не містить логічні ських операторів і не укладено в круглі дужки

2 Символ ⇒ являє собою логічний оператор, відомий під назвою

логічної імплікації Вираз f ⇒ g визначено як логічно еквіва

лентний висловом (NOT f) OR g

Примітка Для позначення цього оператора в главі 8 і в інших попередніх розділах використовувалася конструкція IF . THEN .. END IF .

3 З метою скорочення кількості круглих дужок, необхідних для регламентації бажаного порядку обчислення, застосовуються звичайні правила пріоритету для

логічних операторів (NOT, потім AND, потім OR, потім ⇒)

4&nbsp Висловлювання являє собою просто формулу &ltformula&gt, складену згідно з наведеним вище визначенням (термін формула використовується для того, щоб в цьому і наступному розділах застосовувалася единообразная терми нологія)

Правила виведення

Тепер перейдемо до опису правил виводу для обчислення висловлювань Кількість подібних правил дуже велике Кожне з них являє собою затвердження в наступній формі

╞ f   ⇒ g

Тут f і g – формули, а символ ╞ може розглядатися як що позначає завжди справедливо те, що; зверніть увагу на те, що деякий подібний символ потрібно для того, щоб ми могли формувати метаутвержденія (тобто твердження про твердженнях) Нижче наведені деякі приклади правил логічного висновку

1&nbsp&nbsp&nbsp ╞ ( f  AND  g   )    ⇒   f

2&nbsp&nbsp&nbsp ╞ f  ⇒   (   f   OR  g   )

3&nbsp&nbsp&nbsp ╞ ( (   f    ⇒  g   )   AND   ( g  ⇒ h )                                        )  ⇒   (   f  ⇒   )

4&nbsp&nbsp&nbsp ╞ ( f   AND   (   f    ⇒  g   )    )     ⇒  g

Примітка Останнє правило є особливо важливим Воно називається правилом modus ponens (або правилом відділення) Неформально це правило говорить, що якщо висловлювання f є істинним і з f слід д, то д також має бути істинним Наприклад, припустимо, що наведені нижче формулиа) і б) обидві є істинними

а) У мене немає грошей

б) Якщо у мене грошей, то я повинен заробляти на життя миттям посуду З цього можна зробити висновок, що справжньою є також формула в) . в) Я повинен заробляти на життя миттям посуду

Продовжимо опис правил логічного висновку

5&nbsp&nbsp&nbsp ╞  (   f  ⇒   (   g ⇒ h   )    )    ⇒   (    (f  AND g   )    ⇒ h   )

6&nbsp&nbsp&nbsp ╞  (    (   f   OR  g   )   AND   (   NOT  g   OR  h   )    )   ⇒   (   f   OR  h   )

Примітка Останнє з цих правил також відноситься до числа особливо важливих Воно називається правилом резолюції Додаткова інформація про нього наведена в наступному підрозділі, Докази, а також у розділі 244

Докази

Тепер у нас є необхідний логічний апарат для проведення формальних доказів (у контексті числення висловів) Проблема докази являє собою проблему визначення того, є Чи деяка конкретна формула g (Висновок) логічним наслідком з деякого заданого безлічі формул fl, f2,

. , fn (Предпосилок3), що можна представити у символічному вигляді, як показано нижче

fl,   f2,     ,   fn g

Це символічне позначення можна прочитати так: Формула g може бути отримана шляхом дедуктивного логічного висновку (Або, простіше кажучи, може бути логічно виведена) з формул fl, f2, , Fn . Зверніть увагу на використання ще одного металінгвістіческая символу, ├. Основний метод проведення такого доказу відомий під назвою прямого логічного висновку Прямий логічний висновок полягає в тому, що правила логічного висновку неодноразово застосовуються до передумов, до формул, дедуктивно виведеним з цих передумов, до формул, дедуктивно виведеним з цих формул і тд, до тих пір, поки не буде дедуктивно виведено висновок Іншими словами, процес логічного висновку, образно висловлюючись, розгортається в прямому напрямку у вигляді суцільної ланцюжка від передумов до увязнення Але є також кілька описаних нижче варіантів цього основного підходу

1&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp Прийняття передумови Якщо g має форму р ⇒ q, прийняти р в якості додат

нительной передумови і показати, що q може бути дедуктивно виведена з за

даних передумов і р

2&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp Зворотний логічний висновок Замість спроби довести, що р ⇒ q, довести про тівоположность твердження, NOT q ⇒ NOT p

3&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp Приведення до абсурду Замість того, щоб доводити безпосередньо, що р ⇒ q,

прийняти припущення, що р і NOT q одночасно є істинними, і ви

вести з цього протиріччя

4&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp Резолюція У цьому методі використовується правило логічного висновку на основі ре золюціі (правило 6 з наведеного вище списку)

Розглянемо метод резолюції більш докладно, оскільки він має широке застосування (зокрема, він узагальнюється також на випадок обчислення предикатів, як буде показано в розділі 244)

Насамперед, слід зазначити, що правило резолюції по суті являють собою таке правило, яке дозволяє виключати подформули Наприклад, якщо дано

наступні дві формули: f OR g і NOT g OR h, то можна виключити g і NOT g, щоб вивести наведену нижче спрощену формулу:

3Вформальнойлогикевместотерминапередумовапріменяетсятакжетермінпосилка,абогіпотеза

f   OR  h

Зокрема, якщо дано, що f OR g і NOT g (тобто можна прийняти, що h має значення TRUE), ТО МОЖНА вивести f

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

А ⇒ (В ⇒ С), NOT D OR А, В ├ D ⇒ З

Тут А, в, с і D – формули Почнемо з того, що приймемо заперечення увязнення в якості додаткової передумови, а потім запишемо кожну передумову на окремому рядку наступним чином:

А ⇒ (В ⇒ С)

NOT  D  OR A

У

NOT (D ⇒ С)

Ці чотири рядки неявно зєднані один з одним операторами AND.

Тепер перетворимо кожну окрему рядок у конюнктівную нормальну форму, тобто в форму, що складається з однієї або декількох формул, зєднаних один з одним операторами AND, притому що кожна окрема формула містить (можливо) оператори NOT і OR, але не оператори AND (CM главу 18) Безумовно, другий і третій рядки вже перебувають у цій формі Для того щоб перетворити в неї інші два рядки, спочатку видалимо всі входження оператора ⇒ (Використовуючи визначення цього оператора в

термінах NOT і OR), потім у міру необхідності застосуємо розподільні закони

і закони де Моргана (див початок цього розділу) Крім того, можна видалити зайві круглі дужки і пари суміжних операторів NOT (які скасовують один одного) Чотири наведені вище рядки приймають наступний вид

NOT AOR NOT В OR З

NOT DOR A

У

D ANDNOT З

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

NOT A OR NOT В OR З

NOT D OR A

У

D NOT З

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

Для цього візьмемо перші два рядки, що містять, відповідно, NOT А і А, і застосуємо до них правило резолюції, що призводить до отримання наступного результату

NOT D OR NOT В OR

С В D NOT З

Примітка У загальному випадку може також знадобитися зберегти дві початкові рядки, але в даному конкретному прикладі вони нам більше не знадобляться

Тепер знову застосуємо це правило і для цього знову виберемо перші два рядки

(При цьому відбувається резолюція формул NOT в і в) отриманий результат показаний нижче

NOT D OR З

D

NOT З

Знову виберемо перші два рядки (NOT D і D) і отримаємо наступний результат

з

NOT З

Знову ж, застосуємо це правило (з і NOT с) остаточний результат являє собою порожній безліч висловлювань (яке зазвичай відображається таким чином: []) такий результат відповідно із загальноприйнятим угодою розглядається як протиріччя Таким чином, бажаний результат доведений шляхом приведення до абсурду

Джерело: Дейт К Дж, Введення в системи баз даних, 8-е видання: Пер з англ – М: Видавничий дім «Вільямс», 2005 – 1328 с: Ил – Парал тит англ

Схожі статті:


Сподобалася стаття? Ви можете залишити відгук або підписатися на RSS , щоб автоматично отримувати інформацію про нові статтях.

Коментарів поки що немає.

Ваш отзыв

Поділ на параграфи відбувається автоматично, адреса електронної пошти ніколи не буде опублікований, допустимий HTML: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>

*

*