Метод насыщения уровня

Метод насыщения уровня состоит в вычислении всех резольвент всех пар дизъюнктов из множества дизъюнктов

, добавлении этих резольвент к множеству , вычислении всех следующих резольвент и повторении этого процесса, до тех пор, пока не найдется пустой дизъюнкт ð.

Проиллюстрируем рассмотренный метод на примере множества дизъюнктов

1.

2.

3.

4.

_________________________

: 5. (1,2)

6. (1,3)

7. (1,4)

8. (1,4)

9. (2,3)

10. (2,3)

11. (2,4)

12. (3,4)

___________________________

: 13. (1,7)

14. (1,8)

15. (1,9)

16. (1,10)

17. (1,11)

18. (1,12)

19. (2,6)

20. (2,7)

21. (2,8)

22. (2,9)

23. (2,10)

24. (2,12)

25. (3,5)

26. (3,7)

27. (3,8)

28. (3,9)

29. (3,10)

30. (3,11)

31. (4,5)

32. (4,6)

33. (4,7)

34. (4,8)

35. (4,9)

36. (4,10)

37. (5,7)

38. (5,9)

39. ð (5,12)

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

Для сокращения избыточности могут использоваться различные стратегии, например, стратегия вычеркивания.

Дата добавления: 2015-06-27