Математика в Internet

ОСНОВИ ДИСКРЕТНОГО АНАЛІЗУ.
Автори: Н.Д.Федоренко,В.В.Демченко

     3.17. КОНСТРУКТИВНИЙ МЕТОД ДОВЕДЕННЯ В ЛОГІЦІ ВИСЛОВЛЮВАНЬ

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

Мінімальне покриття - це покриття з найменшим числом термів.

Трансверсальне покриття включає всі можливі терми. Як правило, саме трансверсальні покриття дають повну картину можливих наслідків із сформованих причин.

Розглянемо дію конструктивного методу на слідуючому прикладі.

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

"Так, сказав він, - але "білу дірку я все таки відкрив".

Розв'язання. Розглянемо висловлювання:

={десь щось вибуло};

={десь щось прибуло};

={"чорна дірка" існує};

={"біла дірка" існує};

={нічого побачити не можна}.

Запишемо легенду клаузою:

.

. {якщо в одному місці щось вибуло, то в іншому прибуло }

. {якщо існує "чорна дірка", то в неї все провалюється, тобто в її околі щось вибуває}

. {якщо існує "біла дірка", то з неї в простір щось прибуває}

. {якщо існує "чорна дірка", то її не можливо побачити} або {астроном нічого не побачив}

. {якщо існує "чорна дірка", то десь у просторі повинно щось з'явитися}

.

Складемо таблицю істинності. (Таблиця 23)

З таблиці видно, що одиниці узагальненої причини Р не покриваються одиницями наслідку D, тобто - хибний висновок.

Істинним є наслідок - одиниці істинного наслідку повністю покривають одиниці узагальненої причини, тобто істинною є "якщо існує "чорна дірка", то десь у просторі обов'язково щось з'явиться". Складемо по таблиці доскональну диз'юнктивну нормальну форму (ДДНФ).



Спростивши ДДНФ отримаємо МДФ (мінімальну диз'юнктивну форму).



Трансверсальні покриття (існує три):

.

Мінімальне покриття:.

Таблиця 23.



Закінчення табл.23.




ЗМІСТ