Практика по дедуктивному выводу

Метод дедуктивного вывода

Выводом формулы Ф из множества формул A,B,C… называется такая последовательность формул, что любая формула из этой последовательности есть либо аксиома (включая исходные высказывания), либо выводима из множества предшествующих ей формул. В этом случае формулу Ф называют заключением, а последовательность формул, получаемых в ходе вывода, - схемой дедуктивного вывода.

Формальная запись вывода:

A, B, C… |- Ф

или

Связь между отношением логического вывода (в схеме дедуктивного вывода) и импликацией (в схеме закона алгебры высказываний):

|- A&B&C…®Ф

Именно это соотношение позволяет применить правила введения и удаления логических связок вместо самих аксиом в логическом выводе.

Вывод заключения всегда логически следует из множества посылок и аксиом и опирается на два основных правила:

1. Modus ponens – m.p. - (прямое доказательство): если A и (A®B) - выводимые формулы, то B также выводимая формула, т.е.

2. Modus tollens - m.t. - (доказательство от противного): если ØB и (A®B) - выводимые формулы, то ØA также выводимая формула, т.е.

Оба правила являются отражением части таблицы истинности для импликации, поскольку, по определению дедуктивного вывода, все посылки в нем имеют значение истины:

№ п/п	А	ØА	В	ØВ	А®В
	Л	И	Л	И	И
	И	Л	И	Л	И

Здесь строка 2 соответствует правилу m.p., а строка 1 - правилу m.t. Таким образом вновь проявляется связь импликации (т.е. алгебры) и дедуктивного вывода (т.е. исчисления).

1. Дано сложное высказывание: «Всякое общественно опасное деяние наказуемо. Преступление есть общественно опасное деяние. Дача взятки – преступление. Следовательно, дача взятки наказуема».

Правилен ли вывод?

Решение:

1. Выделим из высказывания ПП:

• А:= «Существуют общественно опасные деяния»

• В:= «Есть наказуемость»

• С:= «Имеются преступления»

• D:= «Имеет место дача взятки»

2. Запишем формулы-посылки и формулы-заключения:

• Ф₁ = А®В - Всякое общественно опасное деяние наказуемо

• Ф₂ = С®А - Преступление есть общественно опасное деяние

• Ф₃ = D®C - Дача взятки – преступление

• Ф₄ = D®B - Дача взятки наказуема

3. Определим формально постановку задачи:

Ф₁, Ф₂, Ф₃

Ф₄

Таким образом, надо определить, истинно ли Ф₄, т.е. доказать истинность Ф₄.

4. Выполним по шагам дедуктивный вывод:

· Заключение по формулам Ф₁ и Ф₂ и правилам П9 (силлогизма) и m.p.:

Ф₂=(С®А), Ф₁=(А®В)

Ф₅=(С®В)

· Заключение по формулам Ф₃ и Ф₅ и правилам П9 и m.p.:

Ф₃=(D®C), Ф₅=(С®В)

Ф₄=(D®B)

Возможно графическое представление схемы вывода:

А®В

С®А

D®С

С®В

D®В

П9

П9

2. Доказать истинность заключения:

Решение:

1. Для удобства пронумеруем посылки:

1 - (AÚB),

2 - (A®C),

3 - (B®D).

2. Выполним по шагам дедуктивный вывод, нумеруя получаемые формулы с учетом номеров посылок:

4 - (ØA®B) – заключение по посылке 1 и правилам эквивалентных преобразований,

5 - (ØB®A) - заключение по формуле 4 и правилу П6,

6 - (ØB®С) - заключение по формулам 2 и 5 и правилу П9,

7 - (ØС®B) - заключение по формуле 6 и правилу П6,

8 - (ØС®D) - заключение по формулам 3 и 7 и правилу П9,

9 - (CÚD) – заключение по формуле 8, ч.т.д.[1]

Данному выводу соответствует граф:

(АÚВ)

А®С

B®D

П9

П6

(ØА®В)

(ØВ®С))

(ØB®А)

П6

(ØС®В)

(ØС®D)

(СÚD)

П9

П6

3. Доказать истинность заключения:

Решение:

1. Пронумеруем посылки:

1 - (AÚB)®C,

2 - C®(DÚE),

3 - E®F,

4 - ØD&ØF.

2. Выполним по шагам дедуктивный вывод, нумеруя получаемые формулы:

5 - ØD – заключение по посылке 4 и правилу П2,

6 - ØF – заключение по посылке 4 и правилу П2,

7 - ØE – заключение по посылке 3, формуле 6 и правилу m.t.,

8 - (ØD&ØE) –заключение по формулам 5 и 7 и правилу П1,

9 – Ø(DÚE) – заключение по формуле 8 и правилам эквивалентных преобразований,

10 - ØC – заключение по посылке 2, формуле 9 и правилу m.t.,

11 - (AÚB)®(DÚE) – заключение по посылкам 1 и 2 и правилу П9,

12 - Ø(AÚB) – заключение по формулам 9, 11 и правилу m.t.,

13 - (ØA&ØB) –заключение по формуле 12 и закону де Моргана,

14 - ØA – заключение по формуле 13 и правилу П2,

15 - ØA&ØC – заключение по формулам 14 и 10 и правилу П1, ч.т.д.

Данному выводу соответствует граф:

(АÚВ)®С

С®(DÚE)

E®F

П1

ØD

(ØD&ØE)

Ø(АÚВ)

П2

П9

ØD&ØF

ØF

ØE

m.t.

Ø(DÚE)

ØC

(АÚВ)®(DÚE)

m.t.

(ØА&ØВ)

ØA

ØА&ØC

m.t.

П2

П1

4. Доказать истинность заключения:

Решение:

1. Пронумеруем посылки:

1 - (AÚB),

2 - (A®B),

3 - (B®A).

2. Выполним по шагам дедуктивный вывод, нумеруя получаемые формулы:

4 - (ØA®B) – заключение по посылке 1 и правилам эквивалентных преобразований формул,

5 - (ØA®A) – заключение по посылке 3, формуле 4 и правилу П9,

6 - (AÚA) – заключение по формуле 5 и правилам эквивалентных преобразований,

7 - A – заключение по формуле 6 и закону идемпотентности,

8 - (ØB®ØA) – заключение по посылке 2 и правилу П6,

9 - (ØB®B) – заключение по формулам 8,4 и правилу П9,

10 - (BÚB) – заключение по формуле 9 и правилам эквивалентных преобразований,

11 - B – заключение по формуле 10 и закону идемпотентности,

12 - (A&B) – заключение по формулам 7,11 и правилу П1, ч.т.д.

Данному выводу соответствует граф:

(АÚВ)

(А®В)

B®А

П9

(ØA®A)

(АÚА)

П6

(ØВ®ØA)

A

(ØА®В)

(ØВ®В)

А&B

П9

(ВÚВ)

B

П1

5. Доказать истинность заключения:

Решение:

1. Пронумеруем посылки:

1 - ((AÚB)®C&D),

2 - ((DÚB)®F).

2. Выполним по шагам дедуктивный вывод, нумеруя получаемые формулы:

3 - (ØAÚC)&(ØBÚC)&(ØAÚD)&(ØBÚD) – заключение по посылке 1 и правилам эквивалентных преобразований,

4 - (A®D) – заключение по формуле 3, правилам эквивалентных преобразований и правилу П2,

5 - (D®F)&(B®F) – заключение по посылке 2 и правилам эквивалентных преобразований,

6 - (D®F) – заключение по формуле 5 и правилу П2,

7 - (A®F) – заключение по формулам 4, 6 и правилу П9, ч.т.д.

Данному выводу соответствует граф:

((АÚВ)®С&D)

((DÚB)®F)

П2

(D®F)&(B®F)

(D®F)

(ØАÚС)&(ØBÚС)&(ØAÚD)&(ØBÚD)

(А®F)

П2

(А®D)

П9

6. Доказать истинность заключения:

Решение:

1. Пронумеруем посылки:

1 - (A®B),

2 - (C®D),

3 - (AÚC),

4 - (A®ØD),

5 - (C®ØB).

3. Выполним по шагам дедуктивный вывод, нумеруя получаемые формулы:

6 - (ØB®ØA) – заключение по посылке 1 и правилу П6,

7 - (ØA®C) – заключение по посылке 3 и правилам эквивалентных преобразований,

8 - (ØB®C) – заключение по формулам 6, 7 и правилу П9,

9 - (ØB®D) – заключение по посылке 2, формуле 8 и правилу П9,

10 - (D®ØA) – заключение по посылке 4 и правилу П6,

11 - (D®С) – заключение по формулам 7, 10 и правилу П9,

12 - (D®ØВ) – заключение по посылке 5, формуле 11 и правилу П9,

13 - (D«ØВ) – заключение по формулам 12,9 и правилу П10, ч.т.д.

Данному выводу соответствует граф:

П9

П6

(А®В)

(A®ØD)

П9

(D®ØA)

(D®С)

(ØВ®ØA)

(ØВ®D)

(ØВ®C)

П9

(С®D)

(АÚС)

(C®ØB)

П6

(ØA®C)

(D®ØВ)

П9

(D«ØB)

П10

Возможна ли автоматизация дедуктивного вывода? Сложность заключается в том, что в рассмотренных примерах на каждом шаге вывода сознательно выбиралось такое правило, которое через конечное число шагов приводило к результату – известному заключению. Подобный подход к решению задачи требует применения интуиции и целенаправленности в решении задачи, что свойственно человеческому интеллекту.

Тем не менее, важной особенностью дедуктивного метода является то, что он применяется либо для доказательства правильности некоторого полученного ранее заключения, как в рассмотренных примерах, либо для вывода множества возможных заключений из заданных посылок. Последнее свойство дедуктивного метода позволяет развивать базы знаний, порождая новые знания из тех фактов и аксиом, которые в них заложены, что активно используется в интеллектуальных информационных системах. Для иллюстрации этого свойства дедукции вернемся к рассмотренному ранее примеру:

Дано сложное высказывание: «Всякое общественно опасное деяние наказуемо. Преступление есть общественно опасное деяние. Дача взятки – преступление».

Какие выводы можно сделать из этих посылок?

Решение:

В задаче использовались обозначения:

А:= «Существуют общественно опасные деяния»

В:= «Есть наказуемость»

С:= «Имеются преступления»

D:= «Имеет место дача взятки»

Ф₁ = А®В:= «Всякое общественно опасное деяние наказуемо»

Ф₂ = С®А:= «Преступление есть общественно опасное деяние»

Ф₃ = D®C:= «Дача взятки – преступление»

Применим метод дедукции и представим в виде графа вывод, отличный от приведенного ранее:

А®В

С®А

D®С

D®А

П9

По правилу силлогизма получена формула D®A, соответствующая высказыванию: «Дача взятки – общественно опасное деяние». Видно, что такое высказывание отсутствует среди известных и заданных в задаче. Следует отметить, что в выводе не использована одна из посылок, но это не является логической ошибкой.

Таким образом, общая схема дедуктивного вывода с заданным множеством посылок может быть представлена следующим алгоритмом построения дерева логических формул:

1) Все заданные посылки принимаются за нулевой уровень иерархии – корень дерева;

2) Ко всем посылкам применяются все возможные правила введения и удаления логических связок – получается множество формул, образующих первый уровень иерархии;

3) К выведенным формулам и посылкам вновь применяются все возможные правила введения и удаления логических связок – получается множество формул, образующих следующий уровень иерархии;

4) Шаг 3) выполняется многократно, пока ни будут формироваться уже полученные ранее выводимые формулы – в таком случае дальнейший вывод бессмыслен.

Этой схеме соответствует граф:

Посылки – нулевой уровень дерева

Выведенные формулы – первый уровень дерева

…

Выведенные формулы – n-ый уровень дерева

Получаемые в процессе вывода формулы и есть новые факты, выводимые из заданной системы посылок. Именно они обогащают базу знаний интеллектуальной информационной системы.

Дата добавления: 2014-01-04