Resolution proof reduction via local context rewriting
ಪ್ರೂಫ್ ಥಿಯರಿಯಲ್ಲಿ, ಗಣಿತದ ತರ್ಕದ ಒಂದು ಕ್ಷೇತ್ರ, ಸ್ಥಳೀಯ ಸಂದರ್ಭದ ಮರುಬರಹದ ಮೂಲಕ ರೆಸಲ್ಯೂಶನ್ ಪ್ರೂಫ್ ರಿಡಕ್ಷನ್ ಎಂಬುದು ಸ್ಥಳೀಯ ಸಂದರ್ಭದ ಮರುಬರಹದ ಮೂಲಕ ರೆಸಲ್ಯೂಶನ್ ಪ್ರೂಫ್ ರಿಡಕ್ಷನ್ ಮಾಡುವ ತಂತ್ರವಾಗಿದೆ. ಈ ಪ್ರೂಫ್ ಕಂಪ್ರೆಷನ್ ವಿಧಾನವನ್ನು ರೆಡ್ಯೂಸ್ ಆಂಡ್ ರಿಕನ್ಸ್ಟ್ರಕ್ಟ್ ಎಂಬ ಅಲ್ಗಾರಿದಮ್ ಆಗಿ ಪ್ರಸ್ತುತಪಡಿಸಲಾಗಿದೆ, ಇದು ರೆಸಲ್ಯೂಶನ್ ಪ್ರೂಫ್ಗಳ ಪೋಸ್ಟ್-ಪ್ರೊಸೆಸಿಂಗ್ ಆಗಿ ಕಾರ್ಯನಿರ್ವಹಿಸುತ್ತದೆ. ರಿಡ್ಯೂಸ್ ಆಂಡ್ ರಿಕನ್ಸ್ಟ್ರಕ್ಟ್ ಸ್ಥಳೀಯ ಪ್ರೂಫ್ ರೀರೈಟಿಂಗ್ ನಿಯಮಗಳ ಒಂದು ಗುಂಪನ್ನು ಆಧರಿಸಿದೆ, ಅದು ಸಬ್ ಪ್ರೂಫ್ ಅನ್ನು ಸಮಾನ ಅಥವಾ ಬಲವಾದದ್ದಾಗಿ ಪರಿವರ್ತಿಸುತ್ತದೆ. ಪ್ರತಿಯೊಂದು ನಿಯಮವನ್ನು ನಿರ್ದಿಷ್ಟ ಸಂದರ್ಭಕ್ಕೆ ಹೊಂದುವಂತೆ ವ್ಯಾಖ್ಯಾನಿಸಲಾಗಿದೆ. ಒಂದು ಸನ್ನಿವೇಶವು ಎರಡು ಪಿವೋಟ್ಗಳನ್ನು (ಮತ್ತು) ಮತ್ತು ಐದು ಷರತ್ತುಗಳನ್ನು (,,, ಮತ್ತು) ಒಳಗೊಂಡಿರುತ್ತದೆ. ಸಂದರ್ಭದ ರಚನೆಯನ್ನು () ನಲ್ಲಿ ತೋರಿಸಲಾಗಿದೆ. ಇದು ಮತ್ತು (ವಿರುದ್ಧ ಧ್ರುವೀಯತೆಯೊಂದಿಗೆ) ಮತ್ತು ಮತ್ತು (ವಿರುದ್ಧ ಧ್ರುವೀಯತೆಯೊಂದಿಗೆ) ಒಳಗೊಂಡಿರುವುದನ್ನು ಸೂಚಿಸುತ್ತದೆ ಎಂಬುದನ್ನು ಗಮನಿಸಿ. ಕೆಳಗಿನ ಕೋಷ್ಟಕವು ಸಿಮೋನ್ ಮತ್ತು ಇತರರು ಪ್ರಸ್ತಾಪಿಸಿದ ಮರುಬರಹ ನಿಯಮಗಳನ್ನು ತೋರಿಸುತ್ತದೆ. ಈ ನಿಯಮಗಳನ್ನು ಅವಕಾಶವಾದಿಯಾಗಿ ಅನ್ವಯಿಸುವ ಮೂಲಕ ಪುರಾವೆಯ ಗಾತ್ರವನ್ನು ಕಡಿಮೆ ಮಾಡುವುದು ಅಲ್ಗಾರಿದಮ್ನ ಉದ್ದೇಶವಾಗಿದೆ. ಮೊದಲ ಐದು ನಿಯಮಗಳನ್ನು ಹಿಂದಿನ ಪತ್ರಿಕೆಯಲ್ಲಿ ಪರಿಚಯಿಸಲಾಯಿತು. ಇದಲ್ಲದೆಃ ನಿಯಮ ಎ2 ತನ್ನಷ್ಟಕ್ಕೆ ತಾನೇ ಯಾವುದೇ ಕಡಿತವನ್ನು ಮಾಡುವುದಿಲ್ಲ. ಆದಾಗ್ಯೂ, ಇದು ಇನ್ನೂ ಉಪಯುಕ್ತವಾಗಿದೆ, ಏಕೆಂದರೆ ಅದರ "ಷಫ್ಲಿಂಗ್" ಪರಿಣಾಮವು ಇತರ ನಿಯಮಗಳನ್ನು ಅನ್ವಯಿಸಲು ಹೊಸ ಅವಕಾಶಗಳನ್ನು ಸೃಷ್ಟಿಸುತ್ತದೆ; ನಿಯಮ A1 ಅನ್ನು ಆಚರಣೆಯಲ್ಲಿ ಬಳಸಲಾಗುವುದಿಲ್ಲ, ಏಕೆಂದರೆ ಇದು ಪುರಾವೆಯ ಗಾತ್ರವನ್ನು ಹೆಚ್ಚಿಸಬಹುದು; ನಿಯಮಗಳು B1, B2, B2 'ಮತ್ತು B3 ಕಡಿತಕ್ಕೆ ನೇರವಾಗಿ ಕಾರಣವಾಗಿವೆ, ಏಕೆಂದರೆ ಅವು ಮೂಲಕ್ಕಿಂತ ಬಲವಾದ ರೂಪಾಂತರಗೊಂಡ ಮೂಲ ಷರತ್ತನ್ನು ಉತ್ಪಾದಿಸುತ್ತವೆ; B ನಿಯಮದ ಅನ್ವಯವು ಕಾನೂನುಬಾಹಿರ ಪುರಾವೆಗೆ ಕಾರಣವಾಗಬಹುದು (ಕೆಳಗಿನ ಉದಾಹರಣೆಯನ್ನು ನೋಡಿ), ಏಕೆಂದರೆ ರೂಪಾಂತರಗೊಂಡ ಮೂಲ ಷರತ್ತಿನಲ್ಲಿ ಕಾಣೆಯಾದ ಕೆಲವು ಅಕ್ಷರಗಳು ಪುರಾವೆಯ ಮಾರ್ಗದ ಉದ್ದಕ್ಕೂ ಮತ್ತೊಂದು ರೆಸಲ್ಯೂಶನ್ ಹಂತದಲ್ಲಿ ಒಳಗೊಂಡಿರಬಹುದು. ಆದ್ದರಿಂದ, ಇದು ಸಂಭವಿಸಿದಾಗ ಅಲ್ಗಾರಿದಮ್ ಕಾನೂನು ಪುರಾವೆಯನ್ನು "ಪುನರ್ನಿರ್ಮಿಸಬೇಕಾಗುತ್ತದೆ". ಈ ಕೆಳಗಿನ ಉದಾಹರಣೆಯು ಬಿ2 ನಿಯಮವನ್ನು ಅನ್ವಯಿಸಿದ ನಂತರ ಪುರಾವೆಯು ಕಾನೂನುಬಾಹಿರವಾಗುವ ಪರಿಸ್ಥಿತಿಯನ್ನು ತೋರಿಸುತ್ತದೆಃ ಪ್ರಮುಖವಾದ ಸಂದರ್ಭಕ್ಕೆ ನಿಯಮ ಬಿ2 ಅನ್ನು ಅನ್ವಯಿಸುವುದುಃ ರೂಪಾಂತರಗೊಂಡ ಮೂಲ ಷರತ್ತಿನಿಂದ ಅಕ್ಷರಶಃ ಕಾಣೆಯಾಗಿರುವುದರಿಂದ ಪುರಾವೆಯು ಈಗ ಕಾನೂನುಬಾಹಿರವಾಗಿದೆ. ಪುರಾವೆಯನ್ನು ಪುನರ್ನಿರ್ಮಿಸಲು, ಕೊನೆಯ ರೆಸಲ್ಯೂಶನ್ ಹಂತದೊಂದಿಗೆ ತೆಗೆದುಹಾಕಬಹುದು (ಅದು ಈಗ ಅನಗತ್ಯವಾಗಿದೆ). ಅಂತಿಮ ಫಲಿತಾಂಶವು ಈ ಕೆಳಗಿನ ಕಾನೂನುಬದ್ಧ (ಮತ್ತು ಬಲವಾದ) ಪುರಾವೆಯಾಗಿದೆಃ ನಿಯಮ ಬಿ 2 ಅನ್ನು ಅನ್ವಯಿಸಲು ಹೊಸ ಅವಕಾಶವನ್ನು ಸೃಷ್ಟಿಸಲು ನಿಯಮ ಎ 2 ಅನ್ನು ಅನ್ವಯಿಸುವ ಮೂಲಕ ಈ ಪುರಾವೆಯನ್ನು ಮತ್ತಷ್ಟು ಕಡಿಮೆ ಮಾಡುವುದು. ಸಾಮಾನ್ಯವಾಗಿ ಎ2 ನಿಯಮವನ್ನು ಅನ್ವಯಿಸಬಹುದಾದ ಹೆಚ್ಚಿನ ಸಂಖ್ಯೆಯ ಸಂದರ್ಭಗಳಿವೆ, ಆದ್ದರಿಂದ ಸಮಗ್ರ ವಿಧಾನವು ಸಾಮಾನ್ಯವಾಗಿ ಕಾರ್ಯಸಾಧ್ಯವಲ್ಲ. ಒಂದು ಪ್ರಸ್ತಾಪವೆಂದರೆ ರಿಡ್ಯೂಸ್ ಆಂಡ್ ರಿಕನ್ಸ್ಟ್ರಕ್ಟ್ ಅನ್ನು ಎರಡು ಮುಕ್ತಾಯ ಮಾನದಂಡಗಳೊಂದಿಗೆ ಲೂಪ್ ಆಗಿ ಕಾರ್ಯಗತಗೊಳಿಸುವುದುಃ ಪುನರಾವರ್ತನೆಗಳ ಸಂಖ್ಯೆ ಮತ್ತು ಟೈಮ್ಔಟ್ (ಮೊದಲು ತಲುಪಿರುವುದು). ಕೆಳಗಿನ ಸೂಡೊಕೋಡ್ ಇದನ್ನು ತೋರಿಸುತ್ತದೆ. 1 ಕಾರ್ಯ ರಿಡ್ಯೂಸ್ ಆಂಡ್ ರಿಕನ್ಸ್ಟ್ರಕ್ಟ್ (/* ಒಂದು ಪುರಾವೆ */, ಟೈಮ್ಲಿಮಿಟ್, ಗರಿಷ್ಠ ಪುನರಾವರ್ತನೆಗಳು): i = 1 ರಿಂದ ಗರಿಷ್ಠಕ್ಕೆ 2 ಪುನರಾವರ್ತನೆಗಳನ್ನು ಮಾಡಿ 3 ರಿಡ್ಯೂಸ್ ಆಂಡ್ ರಿಕನ್ಸ್ಟ್ರಕ್ಟ್ ಲೂಪ್ () ಮಾಡಿ; 4 ಸಮಯ> ಟೈಮ್ಲಿಮಿಟ್ ಆಗಿದ್ದರೆ// ಟೈಮ್ಔಟ್ 5 ಬ್ರೇಕ್; 7 ಅಂತಿಮ ಕಾರ್ಯಕ್ಕಾಗಿ 6 ಎಂಡ್ ರಿಡ್ಯೂಸ್ ಆಂಡ್ ರಿಕನ್ಸ್ಟ್ರಕ್ಟ್ ರಿಡ್ಯೂಸ್ ಆಂಡ್ ರಿಕನ್ಸ್ಟ್ರಕ್ಟ್ ಲೂಪ್ ಕಾರ್ಯವನ್ನು ಬಳಸುತ್ತದೆ, ಇದನ್ನು ಕೆಳಗೆ ನಿರ್ದಿಷ್ಟಪಡಿಸಲಾಗಿದೆ. ಅಲ್ಗಾರಿದಮ್ನ ಮೊದಲ ಭಾಗವು ರೆಸಲ್ಯೂಶನ್ ಗ್ರಾಫ್ನ ಟೋಪೋಲಾಜಿಕಲ್ ಕ್ರಮವನ್ನು ಮಾಡುತ್ತದೆ (ಅಂಚುಗಳು ಪೂರ್ವವರ್ತಿಗಳಿಂದ ರೆಸಲ್ವೆಂಟ್ಗಳಿಗೆ ಹೋಗುತ್ತವೆ ಎಂದು ಪರಿಗಣಿಸಿ). ಪ್ರತಿ ನೋಡ್ಗೆ ಅದರ ಪೂರ್ವವರ್ತಿಗಳ ನಂತರ ಭೇಟಿ ನೀಡಲಾಗಿದೆಯೆ ಎಂದು ಖಚಿತಪಡಿಸಿಕೊಳ್ಳಲು ಇದನ್ನು ಮಾಡಲಾಗುತ್ತದೆ (ಈ ರೀತಿಯಲ್ಲಿ, ಮುರಿದ ರೆಸಲ್ಯೂಶನ್ ಹಂತಗಳನ್ನು ಯಾವಾಗಲೂ ಕಂಡುಹಿಡಿಯಲಾಗುತ್ತದೆ ಮತ್ತು ಸರಿಪಡಿಸಲಾಗುತ್ತದೆ). 1 ಫಂಕ್ಷನ್ ರಿಡ್ಯೂಸ್ ಆಂಡ್ ರಿಕನ್ಸ್ಟ್ರಕ್ಟ್ ಲೂಪ್ (/* ಒಂದು ಪ್ರೂಫ್ */): 2 ಟಿಎಸ್ = ಟೋಪೋಲಾಜಿಕಲ್ ಸಾರ್ಟಿಂಗ್ (); ಟಿಎಸ್ 4ರಲ್ಲಿನ ಪ್ರತಿ ನೋಡ್ಗೆ 3 ಲೀಫ್ ಅಲ್ಲದಿದ್ದರೆ 5 ಆಗಿದ್ದರೆ ಮತ್ತು ನಂತರ 6 = ರೆಸಲ್ಯೂಶನ್ (,); 7 ಎಡಭಾಗದ ಸನ್ನಿವೇಶವನ್ನು ನಿರ್ಧರಿಸಿ, ಯಾವುದಾದರೂ ಇದ್ದರೆ; 8 ಸರಿಯಾದ ಸಂದರ್ಭವನ್ನು ನಿರ್ಧರಿಸಿ, ಯಾವುದಾದರೂ ಇದ್ದರೆ; 9 ಹ್ಯೂರಿಸ್ಟಿಕ್ ಆಗಿ ಒಂದು ಸಂದರ್ಭವನ್ನು ಆಯ್ಕೆ ಮಾಡಿ (ಯಾವುದಾದರೂ ಇದ್ದರೆ) ಮತ್ತು ಅನುಗುಣವಾದ ನಿಯಮವನ್ನು ಅನ್ವಯಿಸಿ; 10 ಇಲ್ಲದಿದ್ದರೆ ಮತ್ತು ನಂತರ 11 ಅನ್ನು ಬದಲಿಸಿ; 12 ಇಲ್ಲದಿದ್ದರೆ ಮತ್ತು ನಂತರ 13 ಅನ್ನು ಬದಲಿಸಿ; 14 ಇಲ್ಲದಿದ್ದರೆ ಮತ್ತು ನಂತರ 15 ಹ್ಯೂರಿಸ್ಟಿಕ್ ಆಗಿ ಪೂರ್ವವರ್ತಿಯನ್ನು ಆಯ್ಕೆ ಮಾಡಿ ಅಥವಾ; 16 ಅಥವಾ ಅದರೊಂದಿಗೆ ಬದಲಿಸಿ; 18 ಅಂತಿಮ ಕಾರ್ಯಕ್ಕಾಗಿ 17 ಅಂತ್ಯಗಳು ಇನ್ಪುಟ್ ಪುರಾವೆ ಮರವಲ್ಲದಿದ್ದರೆ (ಸಾಮಾನ್ಯವಾಗಿ, ರೆಸಲ್ಯೂಶನ್ ಗ್ರಾಫ್ಗಳು) ಈ ಸಂದರ್ಭದಲ್ಲಿ, ಮರುಬರಹ ನಿಯಮದ ಅನ್ವಯವು ಇತರ ರೆಸಲ್ಯೂಶನ್ ಹಂತಗಳಲ್ಲಿ ಹಸ್ತಕ್ಷೇಪ ಮಾಡುವುದಿಲ್ಲ ಎಂದು ಖಚಿತಪಡಿಸಿಕೊಳ್ಳಲು, ಷರತ್ತು ಪ್ರತಿನಿಧಿಸುವ ನೋಡ್ನ ನಕಲನ್ನು ರಚಿಸುವುದು ಸುರಕ್ಷಿತ ಪರಿಹಾರವಾಗಿದೆ. ಈ ದ್ರಾವಣವು ಪುರಾವೆಯ ಗಾತ್ರವನ್ನು ಹೆಚ್ಚಿಸುತ್ತದೆ ಮತ್ತು ಇದನ್ನು ಮಾಡುವಾಗ ಸ್ವಲ್ಪ ಎಚ್ಚರಿಕೆಯ ಅಗತ್ಯವಿದೆ. ಉತ್ತಮ ಸಂಕೋಚನ ಕಾರ್ಯಕ್ಷಮತೆಯನ್ನು ಸಾಧಿಸಲು ನಿಯಮಗಳ ಆಯ್ಕೆಯ ಶೋಧನೆ ಮುಖ್ಯವಾಗಿದೆ. ಸಿಮೋನ್ ಮತ್ತು ಇತರರು. ನಿಯಮಗಳಿಗೆ ಈ ಕೆಳಗಿನ ಆದ್ಯತೆಯ ಕ್ರಮವನ್ನು ಬಳಸಿ (ಕೊಟ್ಟಿರುವ ಸಂದರ್ಭಕ್ಕೆ ಅನ್ವಯಿಸಿದರೆ): B2> B3> {B2 ', B1}> A1'> A2 (X> Y ಎಂದರೆ Y ಗಿಂತ X ಗೆ ಆದ್ಯತೆ ನೀಡಲಾಗುತ್ತದೆ). ರೆಡ್ಯೂಸ್ ಆಂಡ್ ರಿಕನ್ಸ್ಟ್ರಕ್ಟ್ ಮಾತ್ರವೇ ರೀಸೈಕಲ್ಪೈವಾಟ್ಸ್ ಅಲ್ಗಾರಿದಮ್ಗಿಂತ ಕೆಟ್ಟ ಸಂಕೋಚನ/ಸಮಯದ ಅನುಪಾತವನ್ನು ಹೊಂದಿದೆ ಎಂದು ಪ್ರಯೋಗಗಳು ತೋರಿಸಿವೆ. ಆದಾಗ್ಯೂ, ರೀಸೈಕಲ್ಪೈವಾಟ್ಗಳನ್ನು ಪುರಾವೆಗೆ ಒಮ್ಮೆ ಮಾತ್ರ ಅನ್ವಯಿಸಬಹುದಾದರೂ, ಉತ್ತಮ ಸಂಕೋಚನವನ್ನು ಉತ್ಪಾದಿಸಲು ರಿಡ್ಯೂಸ್ ಮತ್ತು ರಿಕನ್ಸ್ಟ್ರಕ್ಟ್ ಅನ್ನು ಅನೇಕ ಬಾರಿ ಅನ್ವಯಿಸಬಹುದು. ರಿಡ್ಯೂಸ್ ಆಂಡ್ ರಿಕನ್ಸ್ಟ್ರಕ್ಟ್ ಮತ್ತು ರೀಸೈಕಲ್ಪೈವಾಟ್ಸ್ ಕ್ರಮಾವಳಿಗಳನ್ನು ಸಂಯೋಜಿಸುವ ಪ್ರಯತ್ನವು ಉತ್ತಮ ಫಲಿತಾಂಶಗಳಿಗೆ ಕಾರಣವಾಗಿದೆ. ಸೂಡೊಕೋಡ್ ಪ್ರೂಫ್ ಸಿದ್ಧಾಂತದ ಉದಾಹರಣೆಗಳೊಂದಿಗೆ ಟಿಪ್ಪಣಿಗಳು ಲೇಖನಗಳು