Математическая логика и теория алгоритмов

(31) 1 Р ИЗ (4) И (5); (32)1 е из (4) и (6); (33)1Pv l6 из (4) и (7); (34) 1 Pvl Q из (4) и (8); (35)1P V 1q из(4)и(9); (36)1Pv l6 из (4) и (10); (37) (2 из (5) и (7); (38)2 из (5) и (9); (39) О из (5) и (12). Было поронодено много не относящихся к делу и лишних дизъ­ юнктов. Например, (7), (8), (9) и (10) - тавтологии. Так как тавтология всегда истинна, то, если вычеркиваем тавтологию из невыполнимого множества дизъюнктов, оставшееся множество все еще должно быть невыполнимо. Следовательно, тавтология есть не относящийся к делу дизъюнкт и не должна порождаться. Если же она порождается, то (за исключением очень немногих случаев) ее следует вычеркнуть. Далее дизъюнкты Р, g, 1 Р, 1 g порождаются неоднократно. Также имеются другие повторяющиеся дизъюнкты (см. (13) - (16), (20) - (23), (26) - (29) и (33) - (36)). На самом деле, чтобы получить доказа­ тельство для S, нужно породить дизъюнкты (5), (12) и (39). Для сокращения избыточности рассмотрим стратегию вычеркивания. Всякое ограничение осчаотивливает. А. Шопенгауэр § 5. Стратегия вычеркивания Дизъюнкт D называется поддизъюнктом D* (или D поглощает D*), если D является некоторой частью дизъюнкта D* При этом D* называется наддизыонктом для1>. Пример, Пусть D=P, D*-P\fQ, Ясно, что D поддизъюнкт для дизъюнкта D*,aD*- наддизъюнкт для D. 96