Логіка > Елементи логіки
º A×ØB×ØB×CÚA×ØB×ØAÚA×ØB×BÚØC×ØB×CÚØC×ØAÚØC×BÚ ÚB×ØB×CÚB×ØAÚB×B º(1, 4, 9, 8) º A×ØB×CÚØA×ØCÚB×ØCÚB×ØAÚB º(5) º A×ØB×CÚØA×ØCÚB За законами (2) зв'язки диз'юнкції також асоціативні, звідки формули ((…((A1ÚA2)Ú A3)Ú …)ÚAn) і A1ÚA2ÚA3Ú…ÚAn також є еквівалентними. Остання з них називається диз'юнкцією формул A1, A2, A3, …, An. Означення. Елементарною диз'юнкцією називається диз'юнкція формул, кожна з яких є або пропозиційною змінною, або запереченням такої. Наприклад, A1ÚØA2ÚA3. Означення. Кон'юнктивною нормальною формою (скорочено КНФ) називається кон'юнкція елементарних диз'юнкцій. Наприклад, формула (AÚB)Ù(ØBÚCÚØD), яку можна подати також у вигляді  . Будь-яка формула перетворюється до рівносильної їй КНФ з використанням тих самих законів, тільки замість першого з законів дистрибутивності (3) вживається другий: AÚ(BÙC) º (AÚB)Ù(AÚC). Приклад. Розглянемо перетворення формули (A®B)«(C®B) після одержання формули (A×ØBÚØCÚB)×(ØB×CÚØAÚB): (A×ØBÚØCÚB)×(ØB×CÚØAÚB) º(3) º (A×ØBÚØC)(A×ØBÚB)×(ØB×CÚØA)×(ØB×CÚB) º(3) º (AÚØC)×(ØBÚØC)×(AÚB)×(ØBÚB)×(ØBÚØA)×(CÚØA)× ×(ØBÚB)×(CÚB) º(9) º (AÚØC)×(ØBÚØC)×(AÚB)×(ØBÚØA)×(CÚØA)×(CÚB) 4. Тавтології, суперечності та логічні висновки Означення. Формула називається тотожньо істинною, або тавтологією, якщо має значення 1 при всіх можливих значеннях пропозиційних змінних. Наприклад, AÚØA чи (A®B)Ú(B®A). Неважко також переконатися, що заміною знаків º на зв'язку « у законах (1)-(13), наведених у п.1.1, одержуються саме тавтології. Тавтології характерні тим, що коли всі входження тієї самої літери замінити на будь-яке, але одне й те саме висловлення, то нове висловлення буде істинним. Наприклад, підставимо у тавтологію ((AÚB)ÙØB)®A замість літери A висловлення "світить сонце", а замість літери B – "світять зорі". Одержане висловлення "Якщо світить сонце або світять зорі, і не світять зорі, то світить сонце" є істинним. Підкреслимо, що сама по собі структура цього висловлення вже забезпечує його істинність. Неважко переконатися, що якщо тавтологіями є деяка формула X і формула X®Y, то Y також є тавтологією. Означення. Формула називається тотожньо хибною, або суперечністю, якщо має значення 0 при всіх можливих значеннях пропозиційних змінних. Одним із характерних прикладів суперечності є висловлення AÙØA. Ця суперечність використовується у доведенні тверджень вигляду A®B методом "від супротивного". Припускають істинність заперечення Ø(A®B), тобто істинність AÙØB. З істинності ØB виводять ØA, одержуючи суперечність AÙØA. Вона свідчить про хибність AÙØB, тобто істинність A®B. Зауважимо, що для доведення істинності A®B достатньо з ØB вивести ØA, тобто довести істинність протилежного твердження ØB®ØA. Адже за законом контрапозиції (11) A®B º ØB®ØA Очевидно, що заперечення будь-якої тавтології є суперечністю, і навпаки. На відміну від тавтологій, підстановка висловлень у суперечності породжує хибні висловлення. Тепер розглянемо поняття логічного висновку. У математиці, як і у звичайному житті, доводиться з'ясовувати, чи випливає деяке твердження з одного або кількох інших, тобто чи є це твердження їх логічним висновком. Приклад. Припустимо, що купівельна спроможність грошей падає, якщо зростають податки, і що люди незадоволені, коли падає купівельна спроможність грошей. Припустимо також, що податки зростають. Звідси можна дійти висновку, що люди незадоволені. Для цього позначимо висловлення літерами: A – "податки зростають", B – "купівельна спроможність грошей падає", C – "люди незадоволені". Припущення прикладу висловимо формулою: (A®B)Ù(B®C)ÙA. Доведемо, за істинності такої умови істинним буде висловлення C. Перетворимо (A®B)Ù(B®C)ÙA до ДНФ: (A®B)Ù(B®C)ÙA º (ØAÚB)Ù(ØBÚC)ÙA º AÙ(ØAÚB)Ù(ØBÚC) º º (AÙØA)Ù(AÙB)Ù(ØBÚC) º (AÙB)Ù(ØBÚC) º º (AÙBÙØB)Ú(AÙBÙC) º AÙBÙC. Отже, маємо, що істинною є формула AÙBÙC. Але вона істинна лише тоді, коли кожний співмножник істинний. Звідси висловлення C є істинним. Таким чином, з істинності формул (A®B), (B®C) і A випливає істинність C. У такому випадку C називається логічним висновком цих формул. Означення. Формула Y називається логічним висновком формул X1, X2, …, Xn, якщо з істинності X1ÙX2Ù…ÙXn випливає істинність формули Y. Формули X1, X2, …, Xn називаються засновками Y. Перевірити, чи є одна формула логічним висновком інших, можна за допомогою порівняння таблиць істинності цієї формули та кон'юнкції інших. Але можна діяти зовсім іншим способом на основі двох наступних тверджень. Теорема 1. Формула Y є логічним висновком формул X1, X2, …, Xn тоді й тільки тоді, коли формула (X1ÙX2Ù…ÙXn)®Y є тавтологією. Доведення. 1 (Необхідність). Припустимо, що формула Y є логічним висновком формул X1, X2, …, Xn. Якщо за деяких значень літер у формулах X1, X2, …, Xn хоча б одна з них хибна, то за означенням імплікації (X1ÙX2Ù…ÙXn)®Y істинна. Якщо ж за деяких значень літер у формулах X1, X2, …, Xn всі вони істинні, X1ÙX2Ù…ÙXn також істинна. Але формула Y є логічним висновком формул X1, X2, …, Xn, тому вона також істинна. Тоді істинна і формула (X1ÙX2Ù…ÙXn)®Y. Отже, за будь-яких значень літер (X1ÙX2Ù…ÙXn)®Y істинна, тобто є тавтологією. 2 (Достатність). Припустимо, що (X1ÙX2Ù…ÙXn)®Y є тавтологією. Тоді якщо за якихось значень літер у формулах X1, X2, …, Xn всі вони істинні, то Y також істинна, тобто є їх логічним висновком. Теорема 2. Формула Y є логічним висновком формул X1, X2, …, Xn тоді й тільки тоді, коли формула (X1ÙX2Ù…ÙXnÙØY) є суперечністю. Доведення. За теоремою 1, формула Y є логічним висновком формул X1, X2, …, Xn тоді й тільки тоді, коли формула (X1ÙX2Ù…ÙXn)®Y є тавтологією. Звідси Y є логічним висновком формул X1, X2, …, Xn тоді й тільки тоді, коли заперечення Ø((X1ÙX2Ù…ÙXn)®Y)є суперечністю. Але Ø((X1ÙX2Ù…ÙXn)®Y) º Ø(Ø(X1ÙX2Ù…ÙXn)ÚY) º º Ø(Ø(X1ÙX2Ù…ÙXn))ÙØY º X1ÙX2Ù…ÙXnÙØY. Таким чином, твердження теореми істинне. Розглянемо приклад застосування наведених теорем. Доведемо, що формула B є логічним висновком формул A®B і A. Перетворимо формулу (A®B)ÙAÙØB: (A®B)ÙAÙØB º (ØAÚB)ÙAÙØB º (ØAÙAÙØB)Ú(BÙAÙØB) º 0Ú0 º 0. Отже, формула (A®B)ÙAÙØB суперечлива, і за теоремою 2 формула B є логічним висновком формул A®B і A. Той факт, що формула B є логічним висновком формул A®B і A, відіграє в математиці дуже важливу роль. Він дозволяє з уже відомих істинних тверджень A®B і A одержати нове істинне твердження B. Зауважимо, що такий спосіб одержання, або виведення нових тверджень у математичній логіці є одним із основних. Таке виведення задається спеціальним правилом виведення, яке має вигляд  і назву modus ponens (правило відокремлення). Воно дозволяє одержати висновок B твердження A®B як окреме висловлення, тобто відокремити його вид засновку A. У математичній логіці існують і інші правила виведення, але тут ми їх не розглядаємо. Підіб'ємо невеличкий неформальний підсумок. Ми познайомилися з двома принципово різними способами одержання нових висловлень. Перший полягає в тому, що ми будуємо складні висловлення з простіших за допомогою логічних зв'язок, а також "перебудовуємо" їх, виконуючи рівносильні перетворення на основі законів. Описані способи побудови та перетворення висловлень складають основу алгебри висловлень.
Назва: Елементи логіки
Дата публікації: 2005-03-01 (2770 прочитано) |
.gif){kind=spacer}
