Tseytin transformation
ಪರ್ಯಾಯವಾಗಿ ಟ್ಸೈಟಿನ್ ರೂಪಾಂತರ ಎಂದು ಬರೆಯಲಾಗುವ ಟ್ಸೈಟಿನ್ ರೂಪಾಂತರವು, ಒಂದು ಅನಿಯಂತ್ರಿತ ಸಂಯೋಜಿತ ತರ್ಕ ಸರ್ಕ್ಯೂಟ್ ಅನ್ನು ಇನ್ಪುಟ್ ಆಗಿ ತೆಗೆದುಕೊಳ್ಳುತ್ತದೆ ಮತ್ತು ಕಾಂಜಂಕ್ಟಿವ್ ನಾರ್ಮಲ್ ರೂಪದಲ್ಲಿ (ಸಿಎನ್ಎಫ್) ಸಮಂಜಸವಾದ ಬೂಲಿಯನ್ ಸೂತ್ರವನ್ನು ಉತ್ಪಾದಿಸುತ್ತದೆ. ಸೂತ್ರದ ಉದ್ದವು ಸರ್ಕ್ಯೂಟ್ನ ಗಾತ್ರದಲ್ಲಿ ರೇಖೀಯವಾಗಿರುತ್ತದೆ. ಸರ್ಕ್ಯೂಟ್ ಔಟ್ಪುಟ್ ಅನ್ನು "ನಿಜ" ವನ್ನಾಗಿ ಮಾಡುವ ಇನ್ಪುಟ್ ವಾಹಕಗಳು ಸೂತ್ರವನ್ನು ತೃಪ್ತಿಪಡಿಸುವ ಕಾರ್ಯಯೋಜನೆಗಳೊಂದಿಗೆ 1 ರಿಂದ 1 ರ ಅನುಪಾತದಲ್ಲಿರುತ್ತವೆ. ಇದು ಯಾವುದೇ ಸರ್ಕ್ಯೂಟ್ನಲ್ಲಿ (ಯಾವುದೇ ಸೂತ್ರವನ್ನು ಒಳಗೊಂಡಂತೆ) ಸರ್ಕ್ಯೂಟ್ ತೃಪ್ತಿಯ ಸಮಸ್ಯೆಯನ್ನು 3-ಸಿಎನ್ಎಫ್ ಸೂತ್ರಗಳಲ್ಲಿನ ತೃಪ್ತಿಯ ಸಮಸ್ಯೆಗೆ ಕಡಿಮೆ ಮಾಡುತ್ತದೆ. ಇದನ್ನು ರಷ್ಯಾದ ವಿಜ್ಞಾನಿ ಗ್ರಿಗೊರಿ ತ್ಸೈಟಿನ್ ಕಂಡುಹಿಡಿದಿದ್ದಾರೆ. ಸರ್ಕ್ಯೂಟ್ ಅನ್ನು ಬೂಲಿಯನ್ ಅಭಿವ್ಯಕ್ತಿಯಾಗಿ ಬರೆಯುವುದು ಮತ್ತು ಅದನ್ನು ಸಿಎನ್ಎಫ್ ಆಗಿ ಪರಿವರ್ತಿಸಲು ಡಿ ಮೋರ್ಗನ್ ನಿಯಮ ಮತ್ತು ವಿತರಣಾ ಗುಣಲಕ್ಷಣವನ್ನು ಬಳಸುವುದು ನಿಷ್ಕಪಟ ವಿಧಾನವಾಗಿದೆ. ಆದಾಗ್ಯೂ, ಇದು ಸಮೀಕರಣದ ಗಾತ್ರದಲ್ಲಿ ಘಾತೀಯ ಹೆಚ್ಚಳಕ್ಕೆ ಕಾರಣವಾಗಬಹುದು. ಸೈಟಿನ್ ರೂಪಾಂತರವು ಒಂದು ಸೂತ್ರವನ್ನು ಉತ್ಪಾದಿಸುತ್ತದೆ, ಅದರ ಗಾತ್ರವು ಇನ್ಪುಟ್ ಸರ್ಕ್ಯೂಟ್ಗಳಿಗೆ ರೇಖೀಯವಾಗಿ ಬೆಳೆಯುತ್ತದೆ. ಔಟ್ಪುಟ್ ಸಮೀಕರಣವು ಅಭಿವ್ಯಕ್ತಿಗೆ ಸಮಾನವಾದ ಸ್ಥಿರಾಂಕ 1 ಸೆಟ್ ಆಗಿದೆ. ಈ ಅಭಿವ್ಯಕ್ತಿಯು ಉಪ-ಅಭಿವ್ಯಕ್ತಿಗಳ ಸಂಯೋಜನೆಯಾಗಿದೆ, ಅಲ್ಲಿ ಪ್ರತಿ ಉಪ-ಅಭಿವ್ಯಕ್ತಿಯ ತೃಪ್ತಿಯು ಇನ್ಪುಟ್ ಸರ್ಕ್ಯೂಟ್ನಲ್ಲಿ ಒಂದೇ ಗೇಟ್ನ ಸರಿಯಾದ ಕಾರ್ಯಾಚರಣೆಯನ್ನು ಜಾರಿಗೊಳಿಸುತ್ತದೆ. ಸಂಪೂರ್ಣ ಔಟ್ಪುಟ್ ಅಭಿವ್ಯಕ್ತಿಯ ತೃಪ್ತಿಯು ಇಡೀ ಇನ್ಪುಟ್ ಸರ್ಕ್ಯೂಟ್ ಸರಿಯಾಗಿ ಕಾರ್ಯನಿರ್ವಹಿಸುತ್ತಿದೆ ಎಂದು ಒತ್ತಾಯಿಸುತ್ತದೆ. ಪ್ರತಿ ಗೇಟ್ಗೆ, ಅದರ ಔಟ್ಪುಟ್ ಅನ್ನು ಪ್ರತಿನಿಧಿಸುವ ಹೊಸ ವೇರಿಯೇಬಲ್ ಅನ್ನು ಪರಿಚಯಿಸಲಾಗುತ್ತದೆ. ಇನ್ಪುಟ್ಗಳು ಮತ್ತು ಔಟ್ಪುಟ್ಗಳನ್ನು ಸಂಬಂಧಿಸುವ ಒಂದು ಸಣ್ಣ ಪೂರ್ವ-ಲೆಕ್ಕಾಚಾರದ ಸಿಎನ್ಎಫ್ ಅಭಿವ್ಯಕ್ತಿಯನ್ನು ಔಟ್ಪುಟ್ ಅಭಿವ್ಯಕ್ತಿಗೆ ("ಮತ್ತು" ಕಾರ್ಯಾಚರಣೆಯ ಮೂಲಕ) ಸೇರಿಸಲಾಗುತ್ತದೆ. ಈ ಗೇಟ್ಗಳಿಗೆ ಇನ್ಪುಟ್ಗಳು ಮೂಲ ಅಕ್ಷರಗಳಾಗಿರಬಹುದು ಅಥವಾ ಉಪ-ಗೇಟ್ಗಳ ಔಟ್ಪುಟ್ಗಳನ್ನು ಪ್ರತಿನಿಧಿಸುವ ಪರಿಚಯಿಸಲಾದ ಅಸ್ಥಿರಗಳಾಗಿರಬಹುದು ಎಂಬುದನ್ನು ಗಮನಿಸಿ. ಔಟ್ಪುಟ್ ಅಭಿವ್ಯಕ್ತಿಯು ಇನ್ಪುಟ್ಗಿಂತ ಹೆಚ್ಚಿನ ಅಸ್ಥಿರಗಳನ್ನು ಹೊಂದಿದ್ದರೂ, ಅದು ಸಮಾನವಾಗಿ ತೃಪ್ತಿಕರವಾಗಿ ಉಳಿಯುತ್ತದೆ, ಅಂದರೆ ಮೂಲ ಇನ್ಪುಟ್ ಸಮೀಕರಣವು ತೃಪ್ತಿಕರವಾಗಿದ್ದರೆ ಮಾತ್ರ ಅದು ತೃಪ್ತಿಕರವಾಗಿರುತ್ತದೆ. ಅಸ್ಥಿರಗಳ ತೃಪ್ತಿಕರ ನಿಯೋಜನೆ ಕಂಡುಬಂದಾಗ, ಪರಿಚಯಿಸಲಾದ ಅಸ್ಥಿರಗಳಿಗೆ ಆ ನಿಯೋಜನೆಗಳನ್ನು ಸರಳವಾಗಿ ತಿರಸ್ಕರಿಸಬಹುದು. ಅಂತಿಮ ಷರತ್ತನ್ನು ಒಂದೇ ಅಕ್ಷರದೊಂದಿಗೆ ಸೇರಿಸಲಾಗುತ್ತದೆಃ ಅಂತಿಮ ಗೇಟ್ನ ಔಟ್ಪುಟ್ ವೇರಿಯೇಬಲ್. ಈ ಅಕ್ಷರಶಃ ಪೂರಕವಾಗಿದ್ದರೆ, ಈ ಷರತ್ತಿನ ತೃಪ್ತಿಯು ಔಟ್ಪುಟ್ ಅಭಿವ್ಯಕ್ತಿಯನ್ನು ಸುಳ್ಳು ಎಂದು ಒತ್ತಾಯಿಸುತ್ತದೆ; ಇಲ್ಲದಿದ್ದರೆ ಅಭಿವ್ಯಕ್ತಿಯು ಬಲವಾಗಿ ನಿಜವಾಗುತ್ತದೆ. ಉದಾಹರಣೆಗಳು ಈ ಕೆಳಗಿನ ಸೂತ್ರವನ್ನು ಪರಿಗಣಿಸಿ. ಎಲ್ಲಾ ಉಪಸೂತ್ರಗಳನ್ನು ಪರಿಗಣಿಸಿ (ಸರಳ ಅಸ್ಥಿರಗಳನ್ನು ಹೊರತುಪಡಿಸಿ): ಪ್ರತಿ ಉಪಸೂತ್ರಕ್ಕೆ ಹೊಸ ಚಲಪರಿಮಾಣವನ್ನು ಪರಿಚಯಿಸಿಃ ಎಲ್ಲಾ ಪರ್ಯಾಯಗಳನ್ನು ಸಂಯೋಜಿಸಿ ಮತ್ತು ಇದಕ್ಕೆ ಪರ್ಯಾಯವಾಗಿಃ ಎಲ್ಲಾ ಪರ್ಯಾಯಗಳನ್ನು ಸಿ. ಎನ್. ಎಫ್. ಆಗಿ ಪರಿವರ್ತಿಸಬಹುದು, ಉದಾಹರಣೆಗೆ. ಪಟ್ಟಿ ಮಾಡಲಾದ ಗೇಟ್ ಉಪ-ಅಭಿವ್ಯಕ್ತಿಗಳು ವಿವಿಧ ಲಾಜಿಕ್ ಗೇಟ್ಗಳಿಗಾಗಿ ರಚಿಸಬಹುದಾದ ಕೆಲವು ಸಂಭಾವ್ಯ ಉಪ-ಅಭಿವ್ಯಕ್ತಿಗಳಾಗಿವೆ. ಕಾರ್ಯಾಚರಣೆಯ ಅಭಿವ್ಯಕ್ತಿಯಲ್ಲಿ, ಸಿ ಒಂದು ಔಟ್ಪುಟ್ ಆಗಿ ಕಾರ್ಯನಿರ್ವಹಿಸುತ್ತದೆ; ಸಿಎನ್ಎಫ್ ಉಪ ಅಭಿವ್ಯಕ್ತಿಯಲ್ಲಿ, ಸಿ ಹೊಸ ಬೂಲಿಯನ್ ವೇರಿಯೇಬಲ್ ಆಗಿ ಕಾರ್ಯನಿರ್ವಹಿಸುತ್ತದೆ. ಪ್ರತಿ ಕಾರ್ಯಾಚರಣೆಗೆ, ಸಿ ಎಲ್ಲಾ ಸಂಭಾವ್ಯ ಇನ್ಪುಟ್ ಮೌಲ್ಯಗಳಿಗೆ ಬೂಲಿಯನ್ ಕಾರ್ಯಾಚರಣೆಯ ಒಪ್ಪಂದಕ್ಕೆ ಬದ್ಧವಾಗಿದ್ದರೆ ಮಾತ್ರ ಸಿಎನ್ಎಫ್ ಉಪ-ಅಭಿವ್ಯಕ್ತಿಯು ನಿಜವಾಗಿದೆ. ಸರಳ ಸಂಯೋಜಿತ ತರ್ಕ ಈ ಕೆಳಗಿನ ಸರ್ಕ್ಯೂಟ್ ಕನಿಷ್ಠ ಅದರ ಕೆಲವು ಇನ್ಪುಟ್ಗಳು ನಿಜವಾಗಿದ್ದಾಗ, ಆದರೆ ಒಂದು ಸಮಯದಲ್ಲಿ ಎರಡಕ್ಕಿಂತ ಹೆಚ್ಚಿರದಿದ್ದಾಗ ನಿಜವಾಗುತ್ತದೆ. ಇದು ಸಮೀಕರಣವನ್ನು ಕಾರ್ಯಗತಗೊಳಿಸುತ್ತದೆ. ಪ್ರತಿ ಗೇಟ್ನ ಔಟ್ಪುಟ್ಗೆ ವೇರಿಯೇಬಲ್ ಅನ್ನು ಪರಿಚಯಿಸಲಾಗಿದೆ; ಇಲ್ಲಿ ಪ್ರತಿಯೊಂದನ್ನು ಕೆಂಪು ಬಣ್ಣದಲ್ಲಿ ಗುರುತಿಸಲಾಗಿದೆಃ x ಅನ್ನು ಇನ್ಪುಟ್ ಆಗಿ ಹೊಂದಿರುವ ಇನ್ವರ್ಟರ್ನ ಔಟ್ಪುಟ್ ಎರಡು ವೇರಿಯೇಬಲ್ಗಳನ್ನು ಪರಿಚಯಿಸಿದೆ ಎಂಬುದನ್ನು ಗಮನಿಸಿ. ಇದು ಅನಗತ್ಯವಾಗಿದ್ದರೂ, ಇದು ಫಲಿತಾಂಶದ ಸಮೀಕರಣದ ಸಮಾನತೆಯ ಮೇಲೆ ಪರಿಣಾಮ ಬೀರುವುದಿಲ್ಲ. ಈಗ ಪ್ರತಿ ಗೇಟ್ ಅನ್ನು ಅದರ ಸೂಕ್ತವಾದ ಸಿಎನ್ಎಫ್ ಉಪ-ಅಭಿವ್ಯಕ್ತಿಯೊಂದಿಗೆ ಬದಲಿಸಿಃ ಅಂತಿಮ ಔಟ್ಪುಟ್ ವೇರಿಯೇಬಲ್ ಗೇಟ್ 8 ಆಗಿರುತ್ತದೆ, ಆದ್ದರಿಂದ ಈ ಸರ್ಕ್ಯೂಟ್ನ ಔಟ್ಪುಟ್ ನಿಜವಾಗುವಂತೆ ಮಾಡಲು, ಒಂದು ಅಂತಿಮ ಸರಳ ಷರತ್ತನ್ನು ಸೇರಿಸಲಾಗುತ್ತದೆಃ (ಗೇಟ್ 8). ಈ ಸಮೀಕರಣಗಳನ್ನು ಸಂಯೋಜಿಸುವುದರಿಂದ ಎಸ್. ಎ. ಟಿ. ಯ ಅಂತಿಮ ನಿದರ್ಶನದಲ್ಲಿ ಫಲಿತಾಂಶಗಳು ಕಂಡುಬರುತ್ತವೆಃ (ಗೇಟ್1 * x1) * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * ಇಲ್ಲಿ, ನಿಜವಾದ ಔಟ್ಪುಟ್ ಮಾಡಲು ಮೂಲ ಸರ್ಕ್ಯೂಟ್ನ ಮಾನದಂಡಗಳನ್ನು ಪೂರೈಸುತ್ತದೆ. ಬೇರೆ ಉತ್ತರವನ್ನು ಕಂಡುಹಿಡಿಯಲು, ಷರತ್ತನ್ನು (x1 * x2 *) ಸೇರಿಸಬಹುದು ಮತ್ತು SAT ಪರಿಹಾರಕವನ್ನು ಮತ್ತೆ ಕಾರ್ಯಗತಗೊಳಿಸಬಹುದು. ಕೆಲವು ಆಯ್ದ ಗೇಟ್ಗಳಿಗೆ ಸಿ. ಎನ್. ಎಫ್. ಉಪ-ಅಭಿವ್ಯಕ್ತಿಯ ಒಂದು ಸಂಭಾವ್ಯ ವ್ಯುತ್ಪತ್ತಿಯೆಂದರೆ ಪ್ರಸ್ತುತಪಡಿಸಿದ ವ್ಯುತ್ಪತ್ತಿಯಾಗಿದೆಃ ಅಥವಾ ಎರಡು ಇನ್ಪುಟ್ಗಳಾದ ಎ ಮತ್ತು ಬಿ ಮತ್ತು ಒಂದು ಔಟ್ಪುಟ್ ಸಿ ಹೊಂದಿರುವ ಗೇಟ್ ಆನ್ ಓಆರ್ ಗೇಟ್ ಈ ಕೆಳಗಿನ ಷರತ್ತುಗಳನ್ನು ತೃಪ್ತಿಪಡಿಸುತ್ತದೆಃ ಔಟ್ಪುಟ್ ಸಿ ನಿಜವಾಗಿದ್ದರೆ, ಅದರ ಕನಿಷ್ಠ ಒಂದು ಇನ್ಪುಟ್ ಎ ಅಥವಾ ಬಿ ನಿಜವಾಗಿದೆ, ಔಟ್ಪುಟ್ ಸಿ ತಪ್ಪಾಗಿದ್ದರೆ, ಅದರ ಎರಡೂ ಇನ್ಪುಟ್ಗಳಾದ ಎ ಮತ್ತು ಬಿ ತಪ್ಪಾಗಿವೆ. ನಾವು ಈ ಎರಡು ಷರತ್ತುಗಳನ್ನು ಎರಡು ಪರಿಣಾಮಗಳ ಸಂಯೋಜನೆಯಾಗಿ ವ್ಯಕ್ತಪಡಿಸಬಹುದುಃ ಕೇವಲ ಸಂಯೋಗಗಳು, ವಿಭಜನೆಗಳು ಮತ್ತು ನಿರಾಕರಣೆಗಳನ್ನು ಒಳಗೊಂಡಿರುವ ಸಮಾನ ಅಭಿವ್ಯಕ್ತಿಗಳೊಂದಿಗೆ ಪರಿಣಾಮಗಳನ್ನು ಬದಲಾಯಿಸುವುದು ಈಗಾಗಲೇ ಬಹುತೇಕ ಸಂಯೋಗದ ಸಾಮಾನ್ಯ ರೂಪದಲ್ಲಿದೆ. ಬಲಭಾಗದ ಷರತ್ತನ್ನು ಎರಡು ಬಾರಿ ವಿತರಿಸುವುದರಿಂದ ಮತ್ತು ಸಂಯೋಜನೆಯ ಅಸೋಸಿಯೇಟಿವಿಟಿಯನ್ನು ಅನ್ವಯಿಸುವುದರಿಂದ ಸಿಎನ್ಎಫ್ ಸೂತ್ರವನ್ನು ನೀಡುತ್ತದೆ ನಾಟ್ ಗೇಟ್ ಅದರ ಇನ್ಪುಟ್ ಮತ್ತು ಔಟ್ಪುಟ್ ಪರಸ್ಪರ ವಿರೋಧಿಸಿದಾಗ ನಾಟ್ ಗೇಟ್ ಸರಿಯಾಗಿ ಕಾರ್ಯನಿರ್ವಹಿಸುತ್ತಿದೆ. ಅಂದರೆಃ ಔಟ್ಪುಟ್ ಸಿ ನಿಜವಾಗಿದ್ದರೆ, ಔಟ್ಪುಟ್ ಸಿ ತಪ್ಪಾಗಿದ್ದರೆ ಇನ್ಪುಟ್ ಎ ತಪ್ಪಾಗಿದೆ, ಇನ್ಪುಟ್ ಎ ನಿಜವಾಗಿದ್ದರೆ ಈ ಷರತ್ತುಗಳನ್ನು ತೃಪ್ತಿಪಡಿಸಬೇಕಾದ ಅಭಿವ್ಯಕ್ತಿಯಾಗಿ ವ್ಯಕ್ತಪಡಿಸಿಃ ಎನ್ಒಆರ್ ಗೇಟ್ ಈ ಕೆಳಗಿನ ಷರತ್ತುಗಳು ಇದ್ದಾಗ ಎನ್ಒಆರ್ ಗೇಟ್ ಸರಿಯಾಗಿ ಕಾರ್ಯನಿರ್ವಹಿಸುತ್ತಿದೆಃ ಔಟ್ಪುಟ್ ಸಿ ನಿಜವಾಗಿದ್ದರೆ, ಔಟ್ಪುಟ್ ಸಿ ತಪ್ಪಾಗಿದ್ದರೆ ಎ ಅಥವಾ ಬಿ ಎರಡೂ ನಿಜವಾಗುವುದಿಲ್ಲ, ನಂತರ ಎ ಮತ್ತು ಬಿ ಕನಿಷ್ಠ ಒಂದು ನಿಜವಾಗಿದ್ದರೆ ಈ ಷರತ್ತುಗಳನ್ನು ತೃಪ್ತಿಪಡಿಸಬೇಕಾದ ಅಭಿವ್ಯಕ್ತಿಯಾಗಿ ವ್ಯಕ್ತಪಡಿಸಿಃ ಉಲ್ಲೇಖಗಳು ಜಿ. ಎಸ್. ತ್ಸೈಟಿನ್ಃ ಪ್ರೊಪೊಸಿಷನಲ್ ಕ್ಯಾಲ್ಕುಲಸ್ನಲ್ಲಿ ವ್ಯುತ್ಪತ್ತಿಯ ಸಂಕೀರ್ಣತೆಯ ಬಗ್ಗೆ. ರಲ್ಲಿಃ ಸ್ಲಿಸೆಂಕೊ, ಎ. ಓ. (ಎಡಿ.) ಸ್ಟಡೀಸ್ ಇನ್ ಕನ್ಸ್ಟ್ರಕ್ಟಿವ್ ಮ್ಯಾಥಮ್ಯಾಟಿಕ್ಸ್ ಅಂಡ್ ಮ್ಯಾಥಮ್ಯಾಟಿಕಲ್ ಲಾಜಿಕ್, ಪಾರ್ಟ್ II, ಸೆಮಿನಾರ್ಸ್ ಇನ್ ಮ್ಯಾಥಮ್ಯಾಟಿಕ್ಸ್, pp. 115-125. ಸ್ಟೆಕ್ಲೋವ್ ಮ್ಯಾಥಮೆಟಿಕಲ್ ಇನ್ಸ್ಟಿಟ್ಯೂಟ್ (1970). ರಷ್ಯನ್ ಭಾಷೆಯಿಂದ ಅನುವಾದಿಸಲಾಗಿದೆಃ ಜಪಿಸ್ಕಿ ನೌಚ್ನಿಖ್ ಸೆಮಿನಾರೋವ್ ಲೋಮಿ 8 (1968), ಪುಟಗಳು. 234-259. ಜಿ. ಎಸ್. ತ್ಸೈಟಿನ್ಃ ಪ್ರೊಪೊಸಿಷನಲ್ ಕ್ಯಾಲ್ಕುಲಸ್ನಲ್ಲಿ ವ್ಯುತ್ಪತ್ತಿಯ ಸಂಕೀರ್ಣತೆಯ ಬಗ್ಗೆ. 1966ರ ಸೆಪ್ಟೆಂಬರ್ನಲ್ಲಿ ನಡೆದ ಗಣಿತದ ತರ್ಕಶಾಸ್ತ್ರದ ಕುರಿತ ಲೆನಿನ್ಗ್ರಾಡ್ ವಿಚಾರಸಂಕಿರಣದಲ್ಲಿ ಪ್ರಸ್ತುತಪಡಿಸಲಾಯಿತು. ಕಂಪ್ಯೂಟರ್ ವಿಜ್ಞಾನದಲ್ಲಿ ಲಾಜಿಕ್ ಗೇಟ್ಸ್ ಲಾಜಿಕ್