Главная

Популярная публикация

Научная публикация

Случайная публикация

Обратная связь

ТОР 5 статей:

Методические подходы к анализу финансового состояния предприятия

Проблема периодизации русской литературы ХХ века. Краткая характеристика второй половины ХХ века

Ценовые и неценовые факторы

Характеристика шлифовальных кругов и ее маркировка

Служебные части речи. Предлог. Союз. Частицы

КАТЕГОРИИ:






Звести формулу до ДНФ;




2) співставити отриману ДНФ з ознаками ДДНФ;

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

За допомогою ДДНФ розв'язують задачу огляду всіх гіпотез даної формули.

Наприклад, приведемо до ДДНФ таку формулу:

(А É В) Ù (`B É A)

Спочатку приведемо її до ДНФ, тобто позбавимося імплікації відповідно до «закону виключення імплікації»А É В º`А Ú В:


(`A Ú B) Ù (`B Ú A)

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

(`A Ú B) Ù (B Ú A)

Застосуємо до нього «закон дистрибутивності кон’юнкції по відношенню до диз’юнкції»А Ù (В Ú С) º (А Ù В) Ú (А Ù С):

(`A Ù B) Ú (`A Ù A) Ú (B Ù B) Ú (A Ù B)

Отримана формула є ДНФ вихідної формули.

Якщо співставити її з ознаками ДДНФ, то стає очевидним, що під формула А Ù`А скорочується, оскільки відповідно до ознак жоден диз'юнкт не може мати змінної одночасно із її запереченням.

Підформула В Ù В також скорочується відповідно до ознак ДДНФ, оскільки жоден диз’юнкт не повинен мати двох однакових змінних і після її скорочення залишається В (вироджена диз’юнкція):

(`A Ù B) Ú B Ú (А Ù В)

Ще однією ознакою ДДНФ є те, що у кожному її диз’юнкті наявні усі змінні, які є у вихідній формулі. Тобто, відповідно до цієї ознаки у другому диз’юнкті В не вистачає змінної А. Тому необхідно приписати за допомогою кон’юнкції до диз’юнкта В диз’юнкцію А Ú`А:

(`A Ù B) Ú [B Ù (A Ú `A)] Ú (А Ù В)

Після чого застосовуємо у квадратних дужках «закон дистрибутивності кон’юнкції по відношенню до диз’юнкції»А Ù (В Ú С) º (А Ù В) Ú (А Ù С) і отримуємо формулу:

(`A Ù B) Ú (В Ù А) Ú (В Ù`А) Ú (А Ù В)

Отриману формулу знову співставляємо із ознаками ДДНФ і скорочуємо схожі формули, оскільки у ДДНФ неможе бути двох однакових диз’юнктів:

(`A Ù B) Ú (В Ù А) Ú (В Ù`А) Ú (А Ù В)

І в резутаті отримуємо таку формулу:

(`A Ù B) Ú (В Ù А)

Із цієї формули ДДНФ очевидно, що вихідна формула має 3 гіпотези:

1. (`A Ù B)

2. (В Ù А)

3. (`A Ù B) Ú (В Ù`А)

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

Перевіримо це на нашому прикладі:

(`A Ù B) É [(A É B) Ù (`B É A)]

Для перевірки цього факту зведемо дану формулу до КНФ:

(`A Ù B) Ú [(`A Ú B) Ù (`B Ú A)]

`A Ú`B Ú [(`A Ú B) Ù (B Ú A)]

(А Ú`В Ú`А Ú В) Ù (А Ú`В Ú В Ú А)

Кожен кон'юнкт отриманої КНФ має змінну і її заперечення, а це означає, що ` АÙ B дійсно є гіпотезою для вихідної формули.

Скороченою диз'юнктивною нормальною формою (СДНФ) даної формули називається така її ДНФ, яка задовольняє такі умови:

1) у жодному диз'юнкті немає двох однакових кон'юнктів;

2) якщо є два однакових диз'юнкти, то один з них скорочується;

3) жоден диз'юнкт не містить змінної і її заперечення.

Для того, щоб привести формулу до СДНФ необхідно виконати такі дії:

1) привести вихідну формулу до ДНФ;

2) співставити отриману ДНФ із ознаками СДНФ;

3) послідовно застосувати до отриманого виразу «закони виявлення» і «закони поглинання».

За допомогою СДНФ знаходять всі прості гіпотези довільної формули.

Наприклад, візьмемо формулу:

((A Ù B) Ú C) É C

Знайдемо всі її прості гіпотези, тобто приведемо її до СДНФ.

((A Ù B) Ú C) Ú C

((A Ù B) Ù`C) Ú C

((`A Ú`B) Ù`C) Ú C

(`А Ù`С) Ú (`В Ù`С) Ú С

Формула у останньому рядку є ДНФ вихідної формули. Співставляємо її з ознаками СДНФ. А потім приводимо її до СДНФ. Для цього спочатку застосовуємо «закон виявлення» Ù В) Ú (`А Ù С) º (А Ù В) Ú (`А Ù С) Ú (В Ù С) і отримуємо вираз :

(`А Ù`С) Ú (`В Ù`С) Ú С Ú`А Ú`В

Далі застосовуємо «закон поглинання»(А Ù В) Ú А º А:

(`А Ù`С) Ú (`В Ù`С) Ú С Ú`А Ú`В

Після застосування «закону поглинання» ми отримали таку формулу:

С Ú`А Ú`В

Тобто, вихідна формула має чотири прості гіпотези:

С;

А;

В;

4. С Ú`А Ú`В.

ТЕМА: ЧИСЛЕННЯ ЛОГІКИ ВИСЛОВЛЮВАНЬ

 

Лекція № 6. Аксіоматичне числення логіки висловлювань (2 год.)

Загальна характеристика числення логіки висловлювань. Мова числення логіки висловлювань. Аксіоматичне числення логіки висловлювань. Мова аксіоматичного числення логіки висловлювань. Синтаксис системи S2: правила утворення та правила перетворення.

Алфавіт та дефініція формули у аксіоматичному численні. Характеристика правил перетворення: дефініція аксіоми, дефініція теореми, список аксіом Давида Гільберта, правила доведення із аксіом: правило відділення ("модус поненс") та правило підстановки, дефініція доведення, дефініція доказової формули.

Алгоритм доведення теореми із аксіом.

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

Семінарське заняття № 6 (2 год.)

1. Визначення числення логіки висловлювань. Структура числення логіки висловлювань.

2. Характеристика синтаксису аксіоматичного числення логіки висловлювань:

а) правила утворення;

б) правила перетворення.

3. Побудова доведення у системі S2 із аксіом.

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

Контрольні запитання та вправи

1. У чому полягає різниця між афавітом системи S1 та S2?

2. Чим характеризується формула у системі S2?

3. Що включають у себе правила перетворення мови аксіоматичного числення логіки висловлювань?

4. Що означає поняття «теорема» в аксіоматичному численні логіки висловлювань?

5. Як визначається поняття «аксіома» в системі S2 ?

6. Як формулюється правило відділення в аксіоматичному численні логіки висловлювань?

7. Сформулюйте дефініцію доведення в системі S2 .

8. Як будується доведення із аксіом в аксіоматичному численні логіки висловлювань?

9. Хто запропонував набір аксіом для доведення теорем у S2?

10. Як будується доведення із гіпотез в аксіоматичному численні логіки висловлювань?

11. Доведіть, що наведені формули є теоремами в аксіоматичному численні логіки висловлювань (з аксіомами):

• q É q;

• (p É q) É ((p Ú q) É q)

12. Побудуйте доведення із гіпотез:

• q Ù p, q É (p É r) |-`r

 

РЕКОМЕНДОВАНА ЛІТЕРАТУРА:

[ 1: с.41-45; 2: с.113-121; 4: с. 343-350; 15: с. 184-193; 18: с. 47-64; 29: с. 72-87, 104-122; 44: с. 14-15; 121;165; 714; 52: с. 48-53, 101-108, 112-113, 142-143, 148-157.]

ЗАВДАННЯ ДЛЯ САМОСТІЙНОЇ РОБОТИ

(4 год.)

Конспект статей із словника

Філософський енциклопедичний словник. - К, 2002. - "Аксіома"; - "Гіпотеза";

- "Доведення"; - "Числення висловлювань".

-"Числення ";

Методичні вказівки

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

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

Дефініція формули у системі S2 така сама, як і у системі S1. Різниця лише у тому, що фомула у системі S2 характеризується не таблицями істинності, а ситуацією виводу. Тобто, тотожно-істинні формули (або тавтології) розподіляються на теореми і аксіоми.

 

Правила перетворення системи S2 складаються із таких компонентів:

1) Дефініція аксіоми.

2) Дефініція теореми.

3) Список аксіом.

4) Правила доведення, які включають:

а) правило відділення, або правило “modus ponens” (МР);

б) правило підстановки (п/п).

5) Дефініція доведення.

6) Дефініція доведеної формули.

Список аксіом у системі S2 повинен бути достатнім для доведення теорем у цій же системі. Як зразок візьмемо набір аксіом запропонований німецьким вченим Давидом Гільбертом:

1. А É (В É А)

2. (А É (В É С) É ((А É В) É (А ÉС))

3. (А Ù В) É А

4. (А Ù В) É В

5. А É (В É (А Ù В))

6. А É (А Ú В)

7. В É (А Ú В)

8. (А É С) É ((В É С) É ((АÚ В) É С))

9. (А É В) É ((А É В) É`А)

10. (А É В) É (`В É`А)

Якщо застосувати до наведеного набору аксіом правила доведення, то можна вивести будь-яку теорему в системі S2 .

Правила виводу:

1. правило відділення або “ modus ponens” (МР) записується так:

А

А É В

В

2. правило підстановки (п/п) має вигляд:

А (x1, x2,... xn)

А¢ (x1¢, x2¢,... xn¢)

Дефініція доведення (виводу):Доведенням називається послідовність формул А1,... Аn де кожна із формул є або аксіомою, або доказаною раніше формулою, або отримана за правилами доведення; остання формула послідовності Аn є виразом, який потрібно було довести.

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

Якщо формула доказова, то записують так: |- А.

Якщо формула не доказова, то: -| А.

Для того щоб побудувати доведення формули F, необхідно здійснити такі дії:

1) виписати одну із аксіом;

2) послідовно застосувати правило підстановки (п/п) і правило відділення (МР)

3) доведення є закінченим, якщо останнім виразом у послідовності формул буде формула F.

Розглянемо структуру доведення на прикладі доказу теореми:

|- р É р.

Доведення.

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

аксіома 1:А É (В É А). Замість символів метамови (А і В) підставляємо пропозиційні змінні об’єкт-мови і отримуємо таку формулу:

1. р É (q É p) - Ах.1

Оскільки у формулі, яку необхідно довести немає пропозиційної змінної q, нам необхідно застосувати правило підстановки і замість q підставимо p É p:

2. p É ((p É p) É p) - q/p É p за п/п до 1

Далі застосуємо аксіому 2: (А É (В É С) É ((А É В) É (А É С)) антецедент, якої нагадує формулу 2 рядка. Здійснюємо підстановку пропозиційних змінних об’єкт-мови замість символів метамови отримуємо формулу:

3. (р É (q É r)) É ((p É q) É (p É r)) - Ax. 2

Очевидно, що вихідна фомула немає у своєму складі пропозиційних змінних q і r, отже необхідно знову застосувати правило підстановки, тобто замість q підставити q/p É p, а замість r підставити р:

4. (p É ((p É p) É p)) É ((p É (p É p)) É (p É p) - q/p É p, r/p за п/п до 3

Якщо порівняти 2 і 4 рядки нашого доведення, то можна помітити, що антецедент формули 4 рядка (виділений) і формула 2 рядка співпадають. Отже, це дає нам право застосувати правило відділення (МР):

5. (p É (p É p)) É (р É р) -за МР, до 2, 4

Консеквент (виділений)отриманої формули відповідає формулі, яку необхідно довести. Тобто, далі необхідно обрати таку аксіому, яка допоможе застосувати правило відділення, щоб отримати формулу p É p. Такою аксіомою

є аксіома 1: А É (В É А):

6. p É (q É p) - Ax 1

Застосуємо правило підстановки і замість q підставимо р:

7. p É (p É р) - q/p за п/п до 6

І врешті-решт використовуємо правило відділення (МР) і отримуємо формулу, яку потрібно було довести:

8. |- р É р -за МР до 7, 5

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

Те, що формула В доказується із гіпотез А1, …, Аn записується так:

А1, …, Аn |- B.

Наприклад, побудуємо доведення формули r із гіпотез p Ù q, p É (q É r).

p Ù q, p É (q É r) |- r

Спочатку виписуємо перше припущення:

1. p Ù q - припущення 1

Потім із списку аксіом обираємо необхідну нам аксіому. У нашому випадку застосуємо аксіому 3: (А Ù В) É А, оскільки антецедент цієї аксіоми нагадує формулу першого припущення. Замінюємо символи метамови на пропозиційні змінні об’єкт-мови:

2. (p Ù q) É p - аксіома 3

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

3. p - МР до 1 і 2

Далі виписуємо друге припущення:

4. p É (q É r) - припущення 2

Формула 3 рядка і антецедент формули 4 рядка співпадають; отже, до них можна застосувати правило відділення (МР):

5. q É r - МР до 3 і 4

Із списку аксіом обираємо аксіому 4: (А Ù В) É В за принципом, щоб можна було застосувати МР до 1 і 6 рядків:

6. (p Ù q) É q - аксіома 4

Якщо співставити формулу 1 рядка і антецедент формули 6 рядка, то очевидно, що до них необхідно застосувати правило відділення:

7. q - МР до 1 і 6

І нарешті, застосовуємо правило відділення до 5 і 7 рядків:

8. r - МР до 5 і 7.

Отже, виходячи із цього доведення можна стверджувати, що із припущень p Ù q, p É (q É r) можна вивести r.

 

Лекція № 7-8. Метатеорема про дедукцію.

Металогічні принципи у S2.

(4 год).

Поняття "теорема" і "метатеорема".

Метатеорема про дедукцію (теорема Ербрана) та її особливості.

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

 

Семінарське заняття № 7 (2 год.)

1. Метатеорема про дедукцію.

2. Металогічні принципи аксіоматичного числення логіки висловлювань:

а) принцип розв'язання;

б) принцип несуперечливості;

в) принцип повноти;

г) принцип незалежності.

Контрольні запитання

1. Які фундаментальні властивості числень вам відомі?

2. Як формулюється мета теорема про дедукцію?

3. Які ви знаєте металогічні принципи?

4. Що означає «принцип розв’язання?

5. Скільки метатеорем описують «принцип розв’язання»?

6. Відносно яких компонентів доведення формулюється «принцип несуперечності»?

7. Які властивості формалізованих мов характеризує «принцип повноти»?

8. Що означає функціональна повнота мови?

9. Що означає дедуктивна повнота мови?

10. В якому сенсі в логіці вживається термін «незалежність»?

 

РЕКОМЕНДОВАНА ЛІТЕРАТУРА:

[ 2: с. 116-121; 4: с. 350-359; 15: с. 184-193; 18: с. 47-64; 29: с. 72-87, 104-122; 44: с. 15,416-417.]

ЗАВДАННЯ ДЛЯ САМОСТІЙНОЇ РОБОТИ

(4 год.)

Конспект статей із словника

Філософський енциклопедичний словник. — К, 2002. - -"Аксіоматичний метод ";

- "Незалежність аксіом".

 

Методичні вказівки

Ознайомлення з цією темою дозволяє студенту з’ясувати, що необхідно розрізняти теорміни “теорема ” і “ метатеорема ”.

Теоремаминазиваються доказувані формули числення, тоді як метатеореми – це доказувані змістовні твердження про властивості числення.

До таких фундаментальних властивостей числень відносяться: вивідність, розв’язуваність, несуперечливість, повнота, незалежність. Кожна із цих властивостей описується метатеоремами: про дедукцію, про несуперечливість, про розв’язуваність, про повноту, про незалежність.

Студентам необхідно знати, що теорема про дедукцію формулюється так:

“Якщо А1, …, Аn-1, Аn |- B, то А1, …, Аn-1 |- Аn É B ”. Тобто, якщо із формул А1, …, Аn-1 і Аn виводиться В, то із формул А1, …, Аn-1 виводиться імплікація Аn É B. Іншими словами: Якщо дано доведення В із А1, …, Аn-1, Аn, то можна побудувати заключення Аn É B на підставі цього доведення ”.

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

а) із довільних формул А1, …, Аn вивідна кожна із цих формул:

А1, …, Аn |- Аі де n ³ i ³ 1;

б) із довільних формул А1, …, Аn вивідна кожна формула, яка вивідна в S2:

А1, …, Аn |- R (R – вивідна формула S2);

в) якщо із довільних формул А1, …, Аn вивідна формула виду МР, то із них вивідний консеквент цього модусу.

Ці особливості вивідності (дедукції) на підставі метатеореми про дедукцію є очевидними на основі таких семантичних міркувань:

1. Особливість (а) виражає властивість рефлексивності слідування: “Із засновку випливає він сам”: А |= А, так як |= А É А.

2. Особливість (б) виражає властивість істинних (вивідних) формул. “Кожна істинна формула розглядається як консеквент L - É (логічно істинної імплікації) з довільним антецедентом”.

3. Особливість (в) фіксується так “ Якщо із А1, …, Аn |-В¢ і із

А1, …, Аn |- В¢ É В², то |= В¢ É В², але це можливо, коли |= В² ”

Властивості роз’язання, несуперечливості, повноти і незалежності називають металогічними принципами. І аналізуються вони через доведення відповідних метатеорем.

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

Принцип розв’язання характеризується доведенням відповідних метатеорем. Їх всього чотири:

МТ1 - |- А É |= А (формулюється: «якщо А – доказане, то тотожно-істинне А»)

МТ2 - ù |= А É ù |- А (формулюється: «якщо А не тотожно-істинне, то і не доказане А»)

МТ3 - |= А É |- А (формулюється: «якщо А тотожно-істинне, то доказане А»)

МТ4 - ù |- А É ù |= А (формулюється: «якщо А не доказане, то не тотожно-істинне А»).

Теорію називають суперечливою, якщо всі її формули є теоремами. Інакше її називають несуперечливою.

Принцип несуперечливості формулюється відносно:

• теорем,

• правил висновку,

• елементів алфавіту.

Дефініція несуперечливості відносно теорем:

Логічна система несуперечлива, якщо, не всі правильно побудовані формули є теоремами. Це положення доводиться МТ5..

Наслідком МТ5 є семантичне формулювання несуперечливості:

«Якщо хоча б одна правильно побудована формула недоказувана, то жодна теорема не є логічним протиріччям».

Дефініція несуперечливості відносно правил висновку:

В синтаксичному смислі система S2 несуперечлива відносно правил висновку, якщо в ній неможливо довести А і довести ù А».

Доведення цього положення здійснюється двома метатеоремами:

МТ6 (пряма): |- А Éù|-ù А ( формулюється так: «Якщо вивідне А, то невірно, що вивідне ù А);

МТ7 – (обернена): |- ù А É ù |- А (формулюється так: «Якщо в S2 вивідне ùА, то невірно, що вивідне А»).

Дефініція несуперечливості відносно елементів алфавіту (пропозиційних змінних):

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

б) у семантичному розумінні: - жодна окремо взята пропозиційна змінна не є тавтологією.

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

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

По-перше, виразні можливості засобів мови;

По-друге, виразні можливості дедуктивних засобів мови.

У зв’язку з цим розрізняють:

а) функціональну повноту мови;






Не нашли, что искали? Воспользуйтесь поиском:

vikidalka.ru - 2015-2024 год. Все права принадлежат их авторам! Нарушение авторских прав | Нарушение персональных данных