Студопедия
Новини освіти і науки:
Контакти
 


Тлумачний словник






Пригадуємо форму умовиводу

Теорема про логічний наслідок

.........

За означенням, умовивід називають правильним тоді і тільки тоді, коли . Позначимо і будемо перевіряти правильність умовиводу тотожністю . Зведемо формули А та В до Д К Н Ф.

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

Теорема. Для того щоб умовивід був правильним, необхідно і досить, щоб елементарні суми висновку були присутні в добутку посилок.

Необхідність. () ().

Будемо доводити обернене до протилежного твердження ()().

Доведення.

()

.

Достатність. ()().

Доведення.

().

 



Интернет реклама УБС

28. Одержання наслідків за посилками

 



Интернет реклама УБС

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

Для того, щоб з даних посилок одержати всі можливі логічні наслідки, потрібно звести кон’юнкцію посилок до ДКНФ і виписати елементарні суми по одній, потім всі можливі логічні добутки по 2, 3 і т.д.

 



Интернет реклама УБС

Приклад.

?

Зводимо кон’юнкцію посилок до ДКНФ. .

Виписуємо елементарні суми та їх логічні добутки.

 



Интернет реклама УБС

1) =

2) =

3) =

4) ====

5) ===

6)===

7) =

 



Интернет реклама УБС

29. Одержання посилок за логічним наслідком

 



Интернет реклама УБС

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

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

Приклад.

Зводимо логічний наслідок до Д К Н Ф. =. Відсутні елементарні суми . Одержуємо:

=

=

=

Одержали такі правильні умовиводи

 



Интернет реклама УБС

 

 



Интернет реклама УБС

30. Поняття про релейно - контактні схеми

 



Интернет реклама УБС

Опрацювати самостійно. [ 4 ], ст. 55.

 



Интернет реклама УБС

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

 



Интернет реклама УБС

31. Означення числення висловлень

 



Интернет реклама УБС

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

Означають числення висловлень так.

1. Символами числення висловлень є:

1) Великі латинські букви і ці ж букви з індексами: A, B, C, …, X, Y, Z, A1, B1,…. Ці символи називають змінними висловленнями.

2) Логічні зв’язки: ¯ , , , . Це відповідно логічні операції заперечення, кон’юнкція, диз’юнкція, імплікація.

3) Дужки (, ), відкриваюча та закриваюча.

Інших символів числення висловлень не має.

2. Означення формули.

1) Змінні висловлення є формули.

2) Якщо та формули, то формулами є:

,,,. При записі формул можна користуватись правилом старшинства логічних операцій.

3. Аксіоми числення висловлень. ( Початкові істинні формули).

11.

12.

21.

22.

23.

31.

32.

33.

41.

42.

43.

4. Правила виведення. Домовимось істинність формули позначати знаком ┝ .

1) Правило підстановки. ┝ , де та - довільні буква та формула.

2) Правило висновку. (┝ )(┝ ).

 



Интернет реклама УБС

32. Виведення формул у численні висловлень

 



Интернет реклама УБС

Почнемо з прикладів. Довільну істинну формулу позначимо буквою

Довести ┝

1) , аксіома 11

2) , заміна на

3) , істинна формула

4) , висновок з 2,3

5) , заміна на

 



Интернет реклама УБС

Довести ┝

1) , аксіома 12

2) , заміна на

3) , аксіома 11

4) , висновок з 2,3

5) , заміна на

6) , висновок з 3,5

 



Интернет реклама УБС

Як видно з прикладів, для формального доведення використовують пронумеровані рядки. В кожному рядку записують тільки істинну формулу і обов’язково обґрунтовують її істинність. Пояснення можуть бути такі: аксіома, висновок, заміна, раніше доведено, істинна формула. В останньому рядку записують доведену формулу.

 



Интернет реклама УБС

33. Несуперечливість числення висловлень

 



Интернет реклама УБС

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

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

1) Аксіоми числення висловлень є тотожно істинними формулами в алгебрі висловлень. Це встановлюється прямою перевіркою (таблиці, тотожні перетворення). ( ДС )

2) Правила виведення справедливі в алгебрі висловлень.

а) Правило підстановки. ┝ , де та - довільні буква та формула. В алгебрі висловлень , бо елементарне висловлення приймає два значення , складне висловлення не більше.

б) Правило висновку. (┝ )(┝ ). В алгебрі висловлень

( )() випливає з означення імплікації.

3) Всі істинні формули числення висловлень є тотожно істинними в алгебрі висловлень.

Випливає з перших двох тверджень.

Теорема. Числення висловлень несуперечливе.

Доведемо цю теорему методом від супротивного. Припустимо, що ┝і ┝. З третього допоміжного твердження одержуємо ┝і далі ┝. Одержали протиріччя, що і доводить теорему.

 



Интернет реклама УБС

VI. Логіка предикатів

34. Поняття про предикати

 



Интернет реклама УБС

Розглянемо приклади висловлень 1>3, 2>3, 3>3, 4>3 і т. д. Виділимо в цих висловленнях предмети 1, 2, 3, 4 і т. д. і властивість „>3” цих предметів. Для позначення предметів використаємо змінну „х”. Одержуємо предикат х>3. Для предиката обов’язково треба вказати множину для значень х. Можна вказати хN, а можна і х = {1,2,3,4,5}. Говорять, що предикат х>3 одномісний, а х> y та x+ y = z, ( x,y,zN), відповідно двомісний і трохмісний предикати. Ці предикати можна позначити відповідно P1(x), P1(x,y), P1(x,y,z).

Індекси вказують на те, що йде мова про конкретний предикат. При підставленні в конкретний предикат замість предметних змінних x,y,z їх конкретних значень з множини визначення предикатів одержуємо висловлення, які істинні або хибні. Наприклад P1(2)=0, P1(7,6)=1, P1(2,3,5)=1, що означає 2>3 - хибно, 7>6 - істинно, 2+ 3 = 5 – істинно.

Означення. Предикатом (предикатною функцією) від змінних називають функцію що набуває двох значень 0 або 1 при будь-яких конкретних значеннях її аргументів.

Говорять, що n – місний предикат визначений на множині М. Для предикатів виконуються логічні операції ¯ , Ù, Ú, ", 1, ( заперечення, кон’юнкція, диз’юнкція, імплікація, еквівалентність ). Формули логіки предикатів будують за тими же правилами, що і формули алгебри висловлень. Наприклад:

, ,.

 



Интернет реклама УБС

35 Означення кванторів

 



Интернет реклама УБС

(х) – квантор загальності. (х)Р(х) – читають: „для всіх х виконується Р(х)”, „для всіх х істинне Р(х)”.

(х) – квантор існування. (х) – читають: „існує х, що виконується Р(х)”, „існує х, що істинно Р(х)”

Нехай Р*(х), хМ – конкретний предикат.

 



Интернет реклама УБС

Означення квантора загальності.

 



Интернет реклама УБС

 



Интернет реклама УБС

Означення квантора існування.

 



Интернет реклама УБС

 



Интернет реклама УБС

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

 



Интернет реклама УБС

36. Зв’язок між кванторами і логічними операціями

 



Интернет реклама УБС

Нехай конкретний предикат визначений на множині . Доведемо, що

Доведення: і і ……

….і

Висновок: Квантору загальності відповідає операція кон’юкція для випадку скінченної множини визначення предикатів.

Доведемо, що

Доведення: і і ……

….і

Висновок: Квантору існування відповідає операція диз’юкція для випадку скінченної множини визначення предикатів.

 



Интернет реклама УБС

37. Інтерпретація формул логіки предикатів

 



Интернет реклама УБС

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

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

Тепер виконуємо синтез:

і і . Одержали, що висловлення істинне.

38. Рівносильні формули логіки предикатів

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

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

Приклад: Довести що . , .

Виконаємо інтерпретацію. , , де та конкретні предикати на довільній множині .

Доведення:

.

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

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

 



Интернет реклама УБС

39. Нерівносильні формули логіки предикатів

 



Интернет реклама УБС

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

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

Приклад: Довести нерівносильність формул.

, .

Будуємо інтерпретацію формул та . Замінимо конкретним предикатом (- ) для .

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

 



Интернет реклама УБС

.
. .
.  
. .
  . .

 

Одержали: .

40. Тотожно істинні формули логіки предикатів

 



Интернет реклама УБС

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

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

Приклад. . Довести .

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

. З означення імплікації випливає, що , а з цього що .

 



Интернет реклама УБС

41. Формули логіки предикатів, що не є тотожно істинними

 



Интернет реклама УБС

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

Приклад. . Довести .

Будуємо інтерпретацію формули . Замінимо конкретним предикатом , а конкретним предикатом для .

,

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

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

 



Интернет реклама УБС

 

 

Одержали

 



Интернет реклама УБС


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

  1. IІI. Формулювання мети і завдань уроку. Мотивація учбової діяльності
  2. ReM – модифікований критерій Рейнольда, який визначається за формулою
  3. Абсолютні й відносні посилання у формулах
  4. АДАПТОВАНА ДО РИНКУ СИСТЕМА ФОРМУВАННЯ (НАБОРУ) ОКРЕМИХ КАТЕГОРІЙ ПЕРСОНАЛУ. ВІДБІР ТА НАЙМАННЯ НА РОБОТУ ПРАЦІВНИКІВ ФІРМИ
  5. Алгоритм формування комплексу маркетингових комунікацій
  6. Алгоритм формування потенціалу Ф2
  7. Алгоритм формування статутного фонду банку
  8. Альтернативні джерела формування підприємницького капіталу
  9. Аналіз ефективності формування та використання банківських ресурсів
  10. АНАЛІЗ ОБОРОТНИХ АКТИВІВ ЗА ДЖЕРЕЛАМИ ЇХ ФОРМУВАННЯ
  11. Аналіз процесу формування маркетингових комунікацій
  12. Аналіз руху та ефективності формування грошових потоків




<== попередня сторінка | наступна сторінка ==>
Логіка розв’язування рівнянь | Правила Де Моргана

Не знайшли потрібну інформацію? Скористайтесь пошуком google:


 

© studopedia.com.ua При використанні або копіюванні матеріалів пряме посилання на сайт обов'язкове.


Генерація сторінки за: 0.01 сек.