Minimal axioms for Boolean algebra
ಗಣಿತದ ತರ್ಕಶಾಸ್ತ್ರದಲ್ಲಿ, ಬೂಲಿಯನ್ ಬೀಜಗಣಿತದ ಕನಿಷ್ಠ ಸೂತ್ರಗಳು ಬೂಲಿಯನ್ ಬೀಜಗಣಿತದ (ಅಥವಾ ಪ್ರೊಪೊಸಿಷನಲ್ ಕ್ಯಾಲ್ಕುಲಸ್) ಸೂತ್ರಗಳಿಗೆ ಸಮಾನವಾದ ಊಹೆಗಳಾಗಿದ್ದು, ಸಾಧ್ಯವಾದಷ್ಟು ಚಿಕ್ಕದಾಗಿರಲು ಆಯ್ಕೆ ಮಾಡಲಾಗುತ್ತದೆ. ಉದಾಹರಣೆಗೆ, ಆರು NAND ಕಾರ್ಯಾಚರಣೆಗಳು ಮತ್ತು ಮೂರು ಅಸ್ಥಿರಗಳನ್ನು ಹೊಂದಿರುವ ಸೂತ್ರವು ಬೂಲಿಯನ್ ಬೀಜಗಣಿತಕ್ಕೆ ಸಮನಾಗಿರುತ್ತದೆಃ ಅಲ್ಲಿ ಲಂಬವಾದ ಪಟ್ಟಿಯು NAND ತಾರ್ಕಿಕ ಕಾರ್ಯಾಚರಣೆಯನ್ನು ಪ್ರತಿನಿಧಿಸುತ್ತದೆ (ಇದನ್ನು ಶೆಫರ್ ಸ್ಟ್ರೋಕ್ ಎಂದೂ ಕರೆಯಲಾಗುತ್ತದೆ). ಇದು ಸ್ಟೀಫನ್ ವೋಲ್ಫ್ರಾಮ್ ಗುರುತಿಸಿದ ಈ ಆಸ್ತಿಯ 25 ಅಭ್ಯರ್ಥಿ ಸಿದ್ಧಾಂತಗಳಲ್ಲಿ ಒಂದಾಗಿದೆ, ನಾಲ್ಕು ಅಥವಾ ಅದಕ್ಕಿಂತ ಕಡಿಮೆ ಅಸ್ಥಿರಗಳೊಂದಿಗೆ ಯಾವುದೇ ಸಂವಹನ ಮಾಡದ ಮಾದರಿಗಳನ್ನು ಹೊಂದಿರದ 15 ಅಂಶಗಳಿಗೆ (ಕನ್ನಡಿ ಚಿತ್ರಗಳನ್ನು ಹೊರತುಪಡಿಸಿ) ಕಡಿಮೆ ಅಥವಾ ಸಮಾನ ಉದ್ದದ ಶೆಫರ್ ಗುರುತುಗಳನ್ನು ಎಣಿಸುವ ಮೂಲಕ, ಮತ್ತು ಇದನ್ನು ಮೊದಲು ವಿಲಿಯಂ ಮೆಕ್ಯೂನ್, ಬ್ರಾಂಡನ್ ಫಿಟಲ್ಸನ್ ಮತ್ತು ಲ್ಯಾರಿ ವೋಸ್ ಅವರು ಸಮಾನವೆಂದು ಸಾಬೀತುಪಡಿಸಿದರು. ವೋಲ್ಫ್ರಾಮ್ಗೆ ಸಂಬಂಧಿಸಿದ ಒಂದು ತಾಣವಾದ ಮ್ಯಾಥ್ ವರ್ಲ್ಡ್, ಈ ಸಿದ್ಧಾಂತಕ್ಕೆ "ವೋಲ್ಫ್ರಾಮ್ ಸಿದ್ಧಾಂತ" ಎಂದು ಹೆಸರಿಟ್ಟಿದೆ. ಮೆಕ್ಯುನ್ ಮತ್ತು ಇತರರು. ವಿಭಜನೆ ಮತ್ತು ನಿರಾಕರಣೆಯ ಆಧಾರದ ಮೇಲೆ ಬೂಲಿಯನ್ ಬೀಜಗಣಿತಕ್ಕೆ ದೀರ್ಘವಾದ ಒಂದೇ ಸೂತ್ರವನ್ನು ಸಹ ಕಂಡುಹಿಡಿದಿದೆ. 1933ರಲ್ಲಿ, ಎಡ್ವರ್ಡ್ ವರ್ಮಿಲಿ ಹಂಟಿಂಗ್ಟನ್, OR ಕಾರ್ಯಾಚರಣೆಯ ಕಮ್ಯುಟೇಟಿವಿಟಿ ಮತ್ತು ಅಸೋಸಿಯೇಟಿವಿಟಿಯ ಊಹೆಯೊಂದಿಗೆ ಸಂಯೋಜಿಸಿದಾಗ, ಈ ಸಿದ್ಧಾಂತವು ಬೂಲಿಯನ್ ಬೀಜಗಣಿತಕ್ಕೆ ಸಮಾನವಾಗಿದೆ ಎಂದು ಗುರುತಿಸಿದರು. ಹರ್ಬರ್ಟ್ ರಾಬಿನ್ಸ್ ಅವರು ಹಂಟಿಂಗ್ಟನ್ನ ಸಿದ್ಧಾಂತವನ್ನು ಬದಲಾಯಿಸಬಹುದೆಂದು ಊಹಿಸಿದರು, ಇದಕ್ಕೆ ತಾರ್ಕಿಕ ನಿರಾಕರಣೆ ನಿರ್ವಾಹಕನ ಒಂದು ಕಡಿಮೆ ಬಳಕೆಯ ಅಗತ್ಯವಿರುತ್ತದೆ. ರಾಬಿನ್ಸ್ ಅಥವಾ ಹಂಟಿಂಗ್ಟನ್ ಇಬ್ಬರೂ ಈ ಊಹೆಯನ್ನು ಸಾಬೀತುಪಡಿಸಲು ಸಾಧ್ಯವಾಗಲಿಲ್ಲ; ಅಥವಾ ನಂತರ ಅದರಲ್ಲಿ ಗಣನೀಯ ಆಸಕ್ತಿಯನ್ನು ಹೊಂದಿದ್ದ ಆಲ್ಫ್ರೆಡ್ ಟಾರ್ಸ್ಕಿಗೂ ಸಾಧ್ಯವಾಗಲಿಲ್ಲ. ಈ ಊಹೆಯನ್ನು ಅಂತಿಮವಾಗಿ 1996ರಲ್ಲಿ ಪ್ರಮೇಯ-ಸಾಬೀತುಪಡಿಸುವ ತಂತ್ರಾಂಶದ ಸಹಾಯದಿಂದ ಸಾಬೀತುಪಡಿಸಲಾಯಿತು. ಈ ಪುರಾವೆಯು ರಾಬಿನ್ಸ್ ಸಿದ್ಧಾಂತವು, ಸಹವರ್ತಿ ಮತ್ತು ಸಂವಹನದೊಂದಿಗೆ, ಬೂಲಿಯನ್ ಬೀಜಗಣಿತಕ್ಕೆ 3-ಆಧಾರವನ್ನು ರೂಪಿಸುತ್ತದೆ ಎಂದು ದೃಢಪಡಿಸಿತು. 2-ಆಧಾರದ ಅಸ್ತಿತ್ವವನ್ನು 1967 ರಲ್ಲಿ ಕ್ಯಾರೆವ್ ಆರ್ಥರ್ ಮೆರೆಡಿತ್ ಸ್ಥಾಪಿಸಿದರುಃ ಮುಂದಿನ ವರ್ಷ, ಮೆರೆಡಿತ್ ಶೆಫರ್ ಸ್ಟ್ರೋಕ್ನ ವಿಷಯದಲ್ಲಿ 2-ಆಧಾರವನ್ನು ಕಂಡುಕೊಂಡರುಃ 1973 ರಲ್ಲಿ, ಪದ್ಮನಾಭನ್ ಮತ್ತು ಕ್ವಾಕೆನ್ಬುಶ್, ತಾತ್ವಿಕವಾಗಿ, ಬೂಲಿಯನ್ ಬೀಜಗಣಿತಕ್ಕೆ 1-ಆಧಾರವನ್ನು ನೀಡುವ ವಿಧಾನವನ್ನು ಪ್ರದರ್ಶಿಸಿದರು. ಈ ವಿಧಾನವನ್ನು ನೇರವಾದ ರೀತಿಯಲ್ಲಿ ಅನ್ವಯಿಸುವುದರಿಂದ "ಅಗಾಧ ಉದ್ದದ ಸಿದ್ಧಾಂತಗಳು" ದೊರೆತವು, ಇದರಿಂದಾಗಿ ಎಷ್ಟು ಚಿಕ್ಕ ಸೂತ್ರಗಳನ್ನು ಕಂಡುಹಿಡಿಯಬಹುದು ಎಂಬ ಪ್ರಶ್ನೆಯನ್ನು ಪ್ರೇರೇಪಿಸುತ್ತದೆ. ಈ ಹುಡುಕಾಟವು ಮೇಲೆ ನೀಡಲಾದ ಶೆಫರ್ ಸ್ಟ್ರೋಕ್ನ ವಿಷಯದಲ್ಲಿ 1-ಆಧಾರವನ್ನು ಮತ್ತು OR ಮತ್ತು NOT ಪರಿಭಾಷೆಯಲ್ಲಿ ಬರೆಯಲಾದ 1-ಆಧಾರವನ್ನು ನೀಡಿತು. ಉಲ್ಲೇಖಗಳು ಬೂಲಿಯನ್ ಬೀಜಗಣಿತ ತರ್ಕಶಾಸ್ತ್ರದ ಇತಿಹಾಸ NAND ಗೇಟ್ ಪ್ರೊಪೊಸಿಷನಲ್ ಕ್ಯಾಲ್ಕುಲಸ್