Referat.me

Название: Числення висловлень

Вид работы: реферат

Рубрика: Математика

Размер файла: 46.7 Kb

Скачать файл: referat.me-215331.docx

Краткое описание работы: Реферат на тему: Числення висловлень Числення висловлень ) згідно з поданою у розділі 1 схемою означається таким чином. Алфавіт числення висловлень складається з елементарних і змінних висловлень (пропозиційних змінних): a,b,c,d,...,x,y,z (можливо з індексами), знаків логічних операцій ,,, і круглих дужок ( та ).

Числення висловлень

Реферат на тему:

Числення висловлень

Числення висловлень (ЧВ ) згідно з поданою у розділі 1 схемою означається таким чином.

1. Алфавіт числення висловлень складається з елементарних і змінних висловлень (пропозиційних змінних): a ,b ,c ,d ,...,x ,y ,z (можливо з індексами), знаків логічних операцій Ú,Ù,Ø,® і круглих дужок ( та ).

2. Поняття формули означається аналогічно алгебрі висловлень.

а) всі пропозиційні змінні та елементарні висловлення є формулами;

б) якщо A і B - формули, то вирази (слова) (A ÙB ), (A ÚB ), (ØA ), (A ®B ) також є формулами;

в) інших формул, ніж побудовані за правилами а) і б) немає.

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

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

3. Аксіомами числення висловлень будуть такі формули:

A 1. a ®(b ®a )

A 2. (a ®b )®((a ®(b ®c ))®(a ®c ))

A 3. (a Ùba

A 4. (a Ùbb

A 5. (a ®b )®((a ®c )®(a ®(b Ùc )))

A 6. a ®(a Úb )

A 7. b ®(a Úb )

A 8. (a ®c )®((b ®c )®((a Úbc ))

A 9. (a ®Øb )®(b ®Øa )

A 10. ØØa ®a

4. Правилами виведення є:

1) правило підстановки . Якщо A - вивідна формула, яка містить літеру p (позначимо цей факт A (p )), то вивідною є і формула A (B ), що здобувається з A заміною всіх входжень літери p на довільну формулу B ; записується

A (p )

A (B )

2) правило висновку (modus ponens ). Якщо A і A ®B - вивідні формули, то вивідною є й формула B ; записується

A , A ® B

B

У поданому описі числення висловлень аксіоми є формулами числення (відповідними до означення формули); формули, що використовують у правилах виведення (A , A ®B тощо), є метаформулами , або так званими схемами формул .

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

Наприклад, для схеми формул A ®B , якщо замінити A на p , а B - на p Ùq , то з даної схеми отримаємо формулу числення p ®(p Ùq ); якщо ж метазмінну A замінити на p ®q , а B - на (p Ùqp , то дістанемо формулу (p ®q )®((p Ùqp ) тощо.

Використання схем формул можна поширити і на всі аксіоми. Наприклад, якщо в системі аксіом пропозиційні змінні a ,b ,c замінити метазмінними A ,B ,C , то отримаємо десять схем аксіом, що задають десять нескінченних множин аксіом. Таким чином приходимо до іншого способу побудови числення висловлень: з нескінченною множиною аксіом (що задається скінченним числом схем аксіом), але без правила підстановки, оскільки воно неявно міститься у поясненні (інтерпретації ) схем аксіом.

Перший спосіб є більш послідовно конструктивним: всі його засоби явно зафіксовані і скінченні; при введенні числення в ЕОМ (наприклад, для автоматизації доведень теорем та побудови виведень для заданих формул) він виглядає природнішим.

З іншого боку, другий спосіб більш відповідає математичній традиції тлумачення (інтерпретації) формул: наприклад, алгебраїчна тотожність (a +b )2 =a 2 +2ab +b 2 або відомі логарифмічні чи тригонометричні тотожності тлумачаться саме як схеми тотожностей, а не конкретні тотожності, справедливі лише для конкретних літер. Правило підстановки при цьому мається на увазі і присутнє неявно. Втім, досить очевидно, що перехід від одного способу побудови числення до іншого є нескладним.

Аксіоми числення висловлень разом з правилами виведення повністю визначають поняття довідної (вивідної) формули у ЧВ, або теореми ЧВ.

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

Розглянемо приклади виведення теорем ЧВ.

Приклад 5.2. Доведемо, що формула a ®a є теоремою ЧВ.

1) Підставляючи в аксіому A 2 змінну a замість змінної c і b ®a замість b , матимемо вивідну формулу

(a ®(b ®a ))®((a ®((b ®aa ))®(a ®a ))

2) Підформула a ®(b ®a ) є аксіомою A 1. Тоді з вивідних формул

a ®(b ®a ) і (a ®(b ®a ))®((a ®((b ®aa ))®(a ®a ))

за правилом висновку виводимо формулу

(a ®((b ®aa ))®(a ®a )).

3) Замінимо в аксіомі A 1 b на (b ®a ):

a ®((b ®aa ).

4) Знову, застосовуючи правило висновку до двох останніх формул, матимемо, що формула a ®a є вивідною.

Для зручності приймемо таку форму запису виведення формул у ЧВ:

а) послідовність формул виведення писатимемо в стовпчик, нумеруючи їх у порядку слідування F 1, F 2,....

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

Правило підстановки записуватимемо у вигляді A = A (B ), а правило висновку - у вигляді MP(A , A ®B ) = B .

Тоді останнє виведення набере вигляду:

F 1: A 2 = (a ®(b ®a ))®((a ®((b ®aa ))®(a ®a ))

F 2: MP(A 1,F 1) = ((a ®((b ®aa ))®(a ®a ))

F 3: A 1 = (a ®((b ®aa ))

F 4: MP(F 3,F 2) = (a ®a )

Отже, ми довели таку метатеорему числення висловлень: |- (a ®a ).

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

Наведемо приклади виведення деяких формул зі заданих множин формул.

Приклад 5.3. 1). a |- (b ®a )

F 1: a

F 2: MP(F 1,A 1) = b ®a

2). a ,b ,a ®(b ®c ) |-c

F 1: a

F 2: b

F 3: a ®(b ®c )

F 4: MP(F 1,F 3) = b ®c

F 5: MP(F 2,F 4) = c

3). a ,b |- (a Ùb )

F 1: A 5 = ((a ®a )®((a ®b )®(a ®(a Ùb ))))

F 2: (a ®a ) (див.приклад 5.2)

F 3: MP(F 2,F 1) = ((a ®b )®(a ®(a Ùb )))

F 4: b

F 5: A 1 = (b ®(a ®b ))

F 6: MP(F 4,F 5) = a ®b

F 7: MP(F 6,F 3) = (a ®(a Ùb ))

F 8: a

F 9: MP(F 8,F 7) = (a Ùb )

Безпосередньо з означення поняття вивідності випливають такі очевидні твердження для довільної множини формул Г.

Лема 1. Якщо |-B , то Г |-B .

Лема 2. Якщо A 1 ,A 2 ,...,An |-B , то A 1 ,A 2 ,...,An ,Г |-B .

Лема 3. Якщо Г |-A і A |-B , то Г |-B (транзитивність відношення вивідності).

Будь-яку доведену у численні вивідність вигляду Г |- A , де Г - множина формул, A - довільна формула, можна розглядати як правило виведення , яке можна додати до заданої множини правил.

Наприклад, доведену у прикладі 3(1) вивідність a |-b ®a разом з правилом підстановки можна розглядати як правило , що може бути інтерпретовано так: «якщо формула A є вивідною, то вивідною є і формула B ®A , де B - довільна формула». Це правило надалі можна використовувати для побудови нових виведень. Такі правила називатимемо похідними правилами . За допомогою додаткових похідних правил дістаємо можливість скоротити виведення формул, не виконуючи повного виведення. Маючи скорочене виведення, завжди можна побудувати повне виведення, замінюючи кожну формулу, яка є результатом застосування похідного правила виведення, на повне її виведення. Такою формулою є, наприклад, формула F 2 у прикладі 3(3). Iнакше кажучи, похідні правила - це будівельні блоки при побудові виведень формул ЧВ, кожен з яких замінює кілька кроків звичайного виведення.

Могутнім засобом одержання ряду важливих і корисних похідних правил виведення є так звана метатеорема дедукції (МТД ); зокрема, сама МТД може розглядатись як таке похідне правило.

Теорема 3 (метатеорема дедукції ). Якщо Г,A |- B , то Г |- A ®B , де Г - множина формул (можливо, порожня), A і B - формули.

Доведення . Зауважимо, що доведення метатеорем на відміну від теорем числення проводиться змістовно як звичайне математичне доведення.

Будемо виходити з того, що задані аксіоми є схемами аксіом, тобто не будемо користуватись правилом підстановки.

Нехай Г,A |- B . Тоді існує виведення B 1 ,B 2 ,...,Bn з Г,A таке, що Bn =B . Доведемо за індукцією, що для будь-якого k £n Г |- A ®Bk .

Розглянемо спочатку випадок k =1, тобто формулу B 1 . B 1 , як перша формула виведення, повинна або бути аксіомою, або міститися в Г, або співпадати з A .

Зі схеми аксіоми A 1 випливає, що B 1 ®(A ®B 1 ) є аксіомою. Якщо B 1 - аксіома або міститься в Г, то за правилом висновку A ®B 1 є вивідною з Г. Якщо ж B 1 =A , то з прикладу 2 маємо, що A ®A , тобто A ®B 1 є вивідною формулою. Отже, у будь-якому випадку отримаємо Г |- A ®B 1 .

Відтак, припустімо, що Г |- A ®Bі для довільного i <k і розглянемо формулу Bk . Можливі чотири ситуації:

а) Bk - аксіома;

б) Bk міститься у Г;

в) Bk = A ;

г) Bk є вивідною з деяких попередніх формул Bj та Bl за правилом висновку; у цьому випадку формула Bl повинна мати вигляд Bj ®Bk .

У випадках а), б), в) доведення твердження Г |- A ®Bk здійснюється аналогічно доведенню для B 1 (випадки а) і б) - за допомогою схеми аксіоми A 1; випадок в) - за допомогою результату прикладу 5.2).

У випадку г) за індуктивним припущенням маємо Г |- A ®Bj і Г |- A ®Bl , де Bl - це Bj ®Bk , тобто Г |- A ®(Bj ®Bk ).

Підставимо у схему аксіоми A 2 A замість a , Bj замість b і Bk замість c . Дістанемо (A ®Bj ) ® ((A ®(Bj ®Bk )) ® (A ®Bk )).

Застосовуючи до останньої вивідної формули двічі правило висновку, отримаємо Г |- A ®Bk . Залишилось покласти k =n .

Розглянемо декілька застосувань метатеореми дедукції.

1. Дуже поширеним методом математичних доведень є метод доведення від супротивного : припускаємо, що A є вірним (істинним твердженням), і доводимо, що, по-перше, з A виводиться B , а по-друге, що з A виводиться ØB , що неможливо; отже, A невірно, тобто вірно ØA .

У термінах числення висловлень цей метод формулюється так:

«якщо Г, A |- B і Г,A |- ØB , то Г |- ØA ».

Доведемо справедливість цього правила у численні висловлень.

Справді, за теоремою дедукції, якщо

Г, A |- B і Г, A |- ØB , то Г |- A ®B і Г |- A ®ØB

F 1: A ®B

F 2: A ®ØB

F 3: A 9 = (A ®ØB )®(B ®ØA )

F 4: MP(F 2,F 3)=B ®ØA

F 5: A 2 = (A ®B )®((A ®(B ®C ))®(A ®C ))

F 6: MP(F 1,F 5) = (A ®(B ®C ))®(A ®C )

F 7: F 6 = ((A ®B )®(B ®ØA ))®((A ®B )®ØA ))

F 8: A 1 = (B ®ØA )®((A ®B )®(B ®ØA ))

F 9: MP(F 4,F 8) = (A ®B )®(B ®ØA )

F 10: MP(F 9,F 7) = (A ®B )®ØA

F 11: MP(F 1,F 10) = ØA

Доведене твердження (метатеорему) часто називають правилом введення заперечення і записують у вигляді

Г, A | - B ; Г, A | - Ø B

Г |- ØA

Крім того, неважко переконатись у справедливості для числення висловлень такого твердження або метатеореми, яку можна вважати оберненою до метатеореми дедукції (ОМТД): «якщо Г |- A ®B , то Г, A |- B »

Послідовно маємо

F 1: A

F 2: A ®B

F 3: MP(F 1,F 2) = B

2. Доведемо тепер закон виключення третього : |- A ÚØA .

F 1: A 6 = A ®(A ÚØA )

F 2: (a ®a ) = (Ø(A ÚØA ))®(Ø(A ÚØA )) (див.приклад 2)

З формул F 1 і F 2 маємо (за ОМТД)

F 3: Ø(A ÚØA ),A |- A ÚØA

F 4: Ø(A ÚØA ), A |- Ø(A ÚØA )

За доведеним правилом введення заперечення у формула з F 3 і F 4 отримаємо:

F 5: Ø(A ÚØA ) |- ØA .

Аналогічно використовуємо аксіому A 7, в якій замість b підставляємо ØA .

A 7 = ØA ®(A ÚØA )

Ø(A ÚØA ), ØA |- A ÚØA

Ø(A ÚØA ), ØA |- Ø(A ÚØA )

Отримуємо

F 6: Ø(A ÚØA ) |- ØØA .

За правилом введення заперечення з F 5 і F 6 дістанемо:

F 7: |- ØØ (A ÚØA )

F 8: A 10 = ØØ(A ÚØA )®(A ÚØA )

F 9: MP(F 7,F 8) = A ÚØA , тобто |- A ÚØA .

Iснують й інші числення висловлень , тобто числення з іншими системами аксіом і правилами виведення.

Наприклад, розглянемо числення висловлень ЧВ1, яке використовує тільки логічні операції Ø і ® і має таку систему аксіом:

S 1. a ®(b ®a )

S 2. (a ®(b ®c ))®((a ®b )®(a ®c ))

S 3. (Øa ®Øb )®((Øa ®ba )

Правилами виведення в новому численні є ті самі правила, що і в старому, тобто правило підстановки і правило висновку.

Якщо в системі аксіом першого числення замінити підформули (a Úb ) на (Øa ®b ), а підформули (a Ùb ) - на Ø(a ®Øb ), то справедливою є така теорема.

Теорема 4. Обидва наведені числення висловлень ЧВ і ЧВ1 є рівносильними в тому смислі, що множини формул вивідних у кожному з цих числень (множини теорем цих числень) співпадають між собою.

Доведення теореми полягає в тому, що доводиться вивідність усіх аксіом першого числення з аксіом другого, і навпаки (з урахуванням зауважень відносно Ú і Ù).

Яке з двох числень краще? Однозначної відповіді на це питання немає. Друге числення є більш компактним і наочним; відповідно більш компактними є доведення різних його властивостей. У той же час, у багатшому першому численні виведення різноманітних формул є, взагалі кажучи, коротшими.

Можливі й інші числення, що рівносильні двом наведеним.

Похожие работы

  • Математична логіка

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

  • Частинні похідні і диференціали вищих порядків

    Пошукова робота на тему: Частинні похідні і диференціали вищих порядків. Частинні похідні вищих порядків Теорема про рівність змішаних похідних Диференціали вищих порядків

  • Використання модульної арифметики. Обчислення з многочленами. Методи множення. Складність обчисл

    Використання модульної арифметики. Обчислення з многочленами. Методи множення. Складність обчислень Ефективний шлях багаторазового зведення за модулем – використання методу Монтгомері, який було запропоновано в 1985 році. Цей метод особливо ефективний при апаратній реалізації алгоритмів. Дуже зручно відмовитися від операцій множення і ділення та замінити їх операціями додавання.

  • Алгебра висловлень

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

  • Сучасна логіка 2

    РЕФЕРАТ на тему: „СУЧАСНА ЛОГІКА” Термін “логіка” сьогодні загалом застосовується у трьох головних значеннях. По-перше, ним позначають будь-яку необхідну закономірність у взаємозв’язку об’єктивних явищ – “логіка фактів”, “логіка історичного розвитку” тощо. По-друге, словом “логіка” позначають закономірності у зв’язках і у розвитку думок – “логіка міркування”, “логіка мислення”.

  • Комбінаторика

    Розділ . Елементи теорії множин §1.1. Поняття множини Поняття множини є одним з фундаментальних у математиці. Воно належить до понять яким не можна дати строге означення, тобто до так званих первісних, які не можна визначити через простіші поняття. Інтуєтивно множину розуміють як сукупність (сімейство, набір, зібрання, клас) деяких, обєктів об’єднаних за певною ознакою чи властивістю.

  • Інтегральне числення

    Вивчення елементарних функцій, інтеграли від яких не є елементарними функціями, тобто вони не обчислюються в скінченному вигляді або не 6еруться. Наближені методи обчислення визначених інтегралів. Дослідження невласних інтегралів та ознаки їх збіжності.

  • Алгоритмічні проблеми

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

  • Розв'язання рівнянь методом оберненої матриці та методом Гауса

    Запис системи рівнянь та їх розв'язання за допомогою методів оберненої матриці та Гауса. Поняття вектора-стовпця з невідомих та вільних членів. Пошук оберненої матриці до даної. Послідовне виключення невідомих за допомогою елементарних перетворень.

  • Теореми Ролля Лагранжа Коші Правило Лопіталя Формула Тейлора для функції однієї та двох змін

    Пошукова робота на тему: Теореми Ролля, Лагранжа, Коші. Правило Лопіталя. Формула Тейлора для функції однієї та двох змінних. План Основні теореми диференціального числення