WWW.REFERATCENTRAL.ORG.UA - Я ТУТ НАВЧАЮСЬ

... відкритий, безкоштовний архів рефератів, курсових, дипломних робіт

ГоловнаЛогіка → Елементи логіки - Реферат

Елементи логіки - Реферат

(A B) A B - закони Де Моргана
(7) A A - закон подвійного заперечення
(8) A 0 0, A 1 A, A 0 A, A 1 1 - закони поглинання
(9) A A 1 - закон виключеного третього
(10) A A 0 - закон суперечності
(11) A B B A - закон контрапозиції
Корисно також пам'ятати ще два закони:
(12) A B A B
(13) A B (A B) (B A).
На законах грунтуються так звані рівносильні перетворення формул, коли формула або її підформула заміняється на рівносильну їй. В результаті одержується формула, рівносильна початковій. Такі перетворення бувають потрібні для спрощення формул. Наприклад, формула A ( A B) має рівносильні формули A ( A B), A (A B), (A A) B, A B, що одержуються послідовним застосуванням законів (12), (7), (2), (4).
3. Нормальні форми висловлень
Розглянемо два різновиди формул, що мають певні структурні особливості. Саме структура цих формул зумовлює їх використання у таких важливих галузях застосування математичної логіки, як автоматизація доведення тверджень і логічне програмування.
Закони (2) стверджують асоціативність зв'язок кон'юнкції. Звідси формула вигляду ((…((A1 A2) A3) …) An) має еквівалентний запис A1 A2 A3 … An. Формула в такому записі називається кон'юнкцією формул A1, A2, A3, …, An.
Означення. Елементарною кон'юнкцією називається кон'юнкція формул, кожна з яких є або пропозиційною змінною, або запереченням такої. Наприклад, A1 A2 A3.
Означення. Диз'юнктивною нормальною формою (скорочено ДНФ) називається диз'юнкція елементарних кон'юнкцій. Наприклад, формула A B B C D. Зауважимо, що її структуру краще видно в записі A B B C D або в записі .
Будь-яка формула може бути перетворена до ДНФ. Ми не будемо доводити це твердження, а лише опишемо потрібні рівносильні перетворення. Застосуванням законів (13) і (12) можна позбутися зв'язок і , тобто перетворити формулу до рівносильної, у якій є лише зв'язки , і . Далі, якщо у формулі є заперечення диз'юнкцій чи кон'юнкцій, то вони "спускаються" до пропозиційних змінних застосуванням законів Де Моргана (6). Далі, якщо у формулі є множники-диз'юнкції, то їх можна позбутися застосуванням першого з законів дистрибутивності (3). В результаті всі множники у кон'юнкціях формули є елементарними, і вона являє собою ДНФ. Застосування законів (1), (2), (4), (5), (7)-(10) може скоротити цей процес.
Приклад. Розглянемо перетворення (A B) (C B). Після знаків у дужках указано номери законів, застосованих при черговому перетворенні:
(A B) (B C) (13, 12)
( ( A B) ( C B)) ( ( C B) ( A B)) (6, 7, 2)
(A B C B) ( B C A B) (3)
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. Якщо за деяких значень
Loading...

 
 

Цікаве