Аналітичне та формальний доказ теореми в ІВ
1. Аналітичне пряме і формальне доказ істинності висновку (теореми)
істинність вонг алгоритм програма
В основі прямого доказу істинності теореми Q лежить перша версія теореми дедукції, яка говорить:
формула Q (теорема, пропозиція) істинна тоді і тільки тоді, коли формула
P1 P2 ... Pn В® Q
общезначима (тобто тотожно істинна)
де P1, P2, ..., Pn - формули посилок
Q - формула теореми
На основі цієї теореми доведемо істинність наступної формули за допомогою законів логіки висловлювань:
[() () () ()]
[() () () ()] =
= () () () () =
=
= () () D =
= () D =
CD =
=
= істина
Уявімо формальний доказ теореми по Вонг
[() () () ()]
Наведемо до КНФ
() () () ().
2. Аналітичне та формальний доказ істинності висновку (теореми) від протилежного
В основі доведення теореми від протилежного лежить друга версія (слідство) теореми дедукції, яка говорить:
формула Q (теорема, припущення) істинна тоді і тільки тоді, коли формула
P1 Г™ P2 Г™ ... Г™ Pn Г™
суперечлива. Дійсно, якщо Q - істинна, то формула заперечення Q (тобто) помилкова, отже, з властивості кон'юнкції випливає, що формула суперечлива. p> Таким чином, для доведення теореми від протилежного, раде здійснювати пошук протиріччя у формулі.
Алгоритм пошуку протиріччя побудований на методі пропозіціональной резолюції, в основі якого лежить принцип силогізму.
Сутність, принципу силогізму полягає в тому, що з двох пропозицій виду (A Гљ B) і (Г№A Гљ C) слід третій істинне речення (B Гљ C) або
[(A Гљ B) Г™ (Г№A Гљ C)] В® (B Гљ C)
тобто ця формула є загальнозначущої (тавтологією).
() () () () ==
= [() () () ()] () =
= () () () () =
= () () () =
= B () C () =
= BDC =
BDC B = брехня
Ми одержали протиріччя, отже, теорема доведена.
Уявімо формальний доказ теореми методом резолюції:
() () () ()
Наведемо до КНФ
() () () ()
Замінивши Г™ коми, отримаємо безліч ППФ (диз'юнктів)
(), (), (), (),
Граф - дерево докази від протилежного.
Ми одержали протиріччя, отже, теорема доведена.
3. Змістовний словесний алгоритм і граф - схема алгоритму докази по Вонг (до...
