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

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

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

.........

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

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

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

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

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

Доведення.

()

.

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

Доведення.

().

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

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

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

Приклад.

?

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

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

1) =

2) =

3) =

4) ====

5) ===

6)===

7) =

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

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

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

Приклад.

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

=

=

=

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

1₁.

1₂.

2₁.

2₂.

2_3.

3₁.

3₂.

3₃.

4₁.

4₂.

4₃.

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

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

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

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

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

Довести ┝

1) , аксіома 1₁

2) , заміна на

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

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

5) , заміна на

Довести ┝

1) , аксіома 1₂

2) , заміна на

3) , аксіома 1₁

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), відповідно двомісний і трохмісний предикати. Ці предикати можна позначити відповідно P₁(x), P₁(x,y), P₁(x,y,z).

Індекси вказують на те, що йде мова про конкретний предикат. При підставленні в конкретний предикат замість предметних змінних x,y,z їх конкретних значень з множини визначення предикатів одержуємо висловлення, які істинні або хибні. Наприклад P₁(2)=0, P₁(7,6)=1, P₁(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. Аналіз руху та ефективності формування грошових потоків

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