Исказни рачун

У математичкој логици, исказни рачун представља формални систем у коме се формуле, односно логички искази, који се називају још и исказне формуле, граде од логичких промјенљивих и других логичких исказа, користећи логичке операције у складу са правилима тих операција.

Упроштено говорећи, исказни рачун је рад са логичким исказима који се формирају као и обични алгебарски изрази, користећи операције и промјенљиве.

Примјер логичког исказа

Слиједи примјер једног логичког исказа: ${\displaystyle (p\lor q)\land s\Rightarrow (p\land s)\lor (q\land s)}$

Исказ се чита на сљедећи начин: „ако су тврдње ${\displaystyle p}$ или ${\displaystyle q}$ тачне и ${\displaystyle s}$ је тачно, одатле слиједи да су искази ${\displaystyle p}$ и ${\displaystyle s}$ тачни или да су искази ${\displaystyle q}$ и ${\displaystyle s}$ тачни“. Чешће, израз се кратко чита „ако је ${\displaystyle p}$ или ${\displaystyle q}$, и ${\displaystyle s}$, слиједи ${\displaystyle p}$ и ${\displaystyle s}$, или ${\displaystyle q}$ и ${\displaystyle s}$“.

Формално установљење

Исказни рачун се формално дефинише као алгебарска структура ${\displaystyle {\mathcal {L}}={\mathcal {L}}\ (\mathrm {A} ,\ \Omega ,\ \mathrm {Z} ,\ \mathrm {I} )}$ са сљедећим својствима:

• ${\displaystyle \mathrm {A} }$ је коначан скуп логичких промјенљивих, које се најчешће представљају малим латиничним штампаним словима ${\displaystyle p,q,r,...}$.
• ${\displaystyle \Omega }$ је коначан скуп логичких операција, који представља унију дисјунктних подскупова ${\displaystyle \{\Omega _{0},\Omega _{1},\ldots ,\Omega _{n},\ldots \}}$, гдје ${\displaystyle n}$-ти подскуп представља подскуп -арних операција. Тако, ${\displaystyle \Omega _{1}}$ представља скуп унарних операција, ${\displaystyle \Omega _{2}}$ бинарних, итд. Уобичајени симболи логичких операција из одговарајућих подскупова су сљедећи:

${\displaystyle \Omega _{0}=\{\top ,\bot \}}$

${\displaystyle \Omega _{1}=\{\lnot \}\,,}$

${\displaystyle \Omega _{2}=\{\land ,\lor ,\Rightarrow ,\Leftrightarrow \}\,.}$

Интересантно је примијетити да се логичке константе дефинишу као нуларне операције.

Исказне формуле се формирају од елемената скупа ${\displaystyle \mathrm {A} }$ користећи операције скупа ${\displaystyle \Omega }$ на основу сљедећих правила:

1. Елементи скупа ${\displaystyle \mathrm {A} }$ су логички искази.
2. За сваку операцију из скупа ${\displaystyle \Omega }$, резултат те операције је логички исказ, ако су и операнди логички искази.
3. логички искази се не могу формирати ни на један други начин осим помоћу правила 1. и 2.

Тако, на примјер, ако су ${\displaystyle p,q}$ и ${\displaystyle r}$ елементи скупа ${\displaystyle \mathrm {A} }$, и ако користимо стандардне симболе за логичке операције, онда су ${\displaystyle p,q,r,\lnot p,p\land q,q\Rightarrow (p\land q)}$ све исказне формуле.

• Скуп ${\displaystyle \mathrm {Z} }$ је коначан скуп правила трансформације логичких исказа. Ова правила поближе одређују особине операција и њихово понашање у додиру са другим операцијама, односно одређују на који начин се један логички исказ може свести на други, најчешће једноставнији, исказ.
• Скуп ${\displaystyle \mathrm {I} }$ је коначан скуп аксиома - по дефиницији истинитих тврдњи - у вези са логичким исказима.

Вриједности логичких израза и доказивања

Логичке промјенљиве могу имати вриједност „тачно“ и „нетачно“ (${\displaystyle \top }$ или ${\displaystyle \bot }$), па се и сви резултати логичких операција ограничавају на истом скупу. Водећи се правилима формирања логичких израза, закључујемо да сви искази имају вриједности тачно или нетачно, тј. да је сваки исказ или тачан или нетачан.

Ако додијелимо неке конкретне вриједности свим промјенљивама које учествују у датом логичком исказу, користећи дефиниције логичких операција и датих вриједности можемо израчунати да ли је дати исказ тачан или није. Тада кажемо да је исказ нпр. тачан за дате вриједности промјенљивих.

Међутим, користећи правила трансформације и аксиоме исказног рачуна, логички искази се могу транформисати у једноставније логичке исказе, што израчунавање њихових вриједности чини краћим и једноставнијим.

Таутологије и контрадикције

Посебан чланак: Таутологија

Чест посао у исказном рачуну је доказивање да ли је одређени логички исказ увијек тачан, тј. за све комбинације вриједности промјенљивих, као и доказивање да ли је одређени логички исказ за све комбинације вриједности промјенљивих нетачан. Ако је исказ увијек тачан, називамо га таутологијом, док у супротном случају, када је исказ увијек нетачан, називамо га контрадикцијом.

Док доказивање таутологије и контрадикције може да се докаже ручним провјеравањем вриједности исказа за све комбинације параметара, најчешће користећи истинитосне табеле, у општем случају, када то није практично оствариво због броја промјенљивих, се користе правила исказног рачуна и аксиоме да се исказ сведе на једноставнији исказ и евентуално докаже да ли је таутологија/контрадикција или не.

Примјена

Сувишно је спомињати да логичко закључивање има примјену у свакодневном животу и свим гранама људског дјеловања. Вјештина у раду са исказним рачуном свакако побољшава и свакодневне вјештине логичког закључивања. Осим тога, међутим, исказни рачун и математичка логика уопште имају велику примјену у већини природних наука.

Рачунарство

Очигледан примјер примјене исказног рачуна је и употреба у рачунарству, како у електроници тако и у програмирању.

Свођење одређеног логичког исказа на краћу и једноставнију форму помаже да одређена компонента рачунара израчунава мање и самим тиме ради брже. На идентичан начин, у програмирању, редуковањем често коришћеног услова гранања или петље на једноставнију форму ће смањити посао процесорске јединице што програм чини бржим.

Осим тога, теоријско доказивање тачности одређених исказа уклања потребу за израчунавањем одређених исказа у потпуности, ако се докаже да је исказ увијек тачан или увијек нетачан.

Историја

Главни чланак: Историја логике

Премда је исказна логика (која је заменљива са пропозиционалним рачуном) наговештена у радовима ранијих филозофа, њу је развио у формалну логику (стоичка логика) Хрисип у 3. век пне^[1] и проширио његов наследник Стоик. Логика је имала фокус на пропозицијама. Овај напредак се разликовао од традиционалнеl силогистичке логике која је стављала фокус на чланове. Међутим, током касне антике исказна логака коју су развили стоици више није била у употреби.^[2] Консеквентно, систем је есенцијално поново изумео Пјер Абелар у 12. веку.^[3]

Види још

• Математичка логика
• Таутологија
• Логичке операције
• Предикатски рачун

Референце

1. Bobzien, Susanne (1. 1. 2016). „Ancient Logic”. Ур.: Zalta, Edward N. The Stanford Encyclopedia of Philosophy. Metaphysics Research Lab, Stanford University — преко Stanford Encyclopedia of Philosophy.CS1 одржавање: Формат датума (веза)
2. „Propositional Logic | Internet Encyclopedia of Philosophy” (на језику: енглески). Приступљено 2020-08-20.
3. Marenbon, John (2007). Medieval philosophy: an historical and philosophical introduction. Routledge. стр. 137.

Литература

• Marenbon, John (2007). Medieval philosophy: an historical and philosophical introduction. Routledge. стр. 137.
• Bobzien, Susanne (2016). „Ancient Logic”. Ур.: Zalta, Edward N. The Stanford Encyclopedia of Philosophy. Metaphysics Research Lab, Stanford University — преко Stanford Encyclopedia of Philosophy.
• Brown, Frank Markham (2003), Boolean Reasoning: The Logic of Boolean Equations, 1st edition, Kluwer Academic Publishers, Norwell, MA. 2nd edition, Dover Publications, Mineola, NY.
• Chang, C.C. and Keisler, H.J. (1973), Model Theory, North-Holland, Amsterdam, Netherlands.
• Kohavi, Zvi (1978), Switching and Finite Automata Theory, 1st edition, McGraw–Hill, 1970. 2nd edition, McGraw–Hill, 1978.
• Korfhage, Robert R. (1974). Discrete Computational Structures. Academic Press. ISBN 978-0-12-420850-6., New York, NY.
• Lambek, J.; Scott, P.J. (1988). Introduction to Higher Order Categorical Logic. Cambridge, UK: Cambridge University Press. ISBN 978-0-521-35653-4.
• Mendelson, Elliot (1964), Introduction to Mathematical Logic, D. Van Nostrand Company.
• Hofstadter, Douglas (1979). Gödel, Escher, Bach: An Eternal Golden Braid. Basic Books. ISBN 978-0-465-02656-2.
• Rautenberg, Wolfgang (2010), A Concise Introduction to Mathematical Logic (3rd изд.), New York, NY: Springer Science+Business Media, ISBN 978-1-4419-1220-6, doi:10.1007/978-1-4419-1221-3
• Andrews, Peter B. (2002); An Introduction to Mathematical Logic and Type Theory: To Truth Through Proof, 2nd ed., Berlin: Kluwer Academic Publishers. Available from Springer.
• Avigad, Jeremy; Donnelly, Kevin; Gray, David; Raff, Paul (2007). „A formally verified proof of the prime number theorem”. ACM Transactions on Computational Logic. 9: 2. S2CID 7720253. arXiv:cs/0509025 . doi:10.1145/1297658.1297660.
• Barwise, Jon (1977). „An Introduction to First-Order Logic”. Ур.: Barwise, Jon. Handbook of Mathematical Logic. Studies in Logic and the Foundations of Mathematics. Amsterdam, NL: North-Holland (објављено 1982). ISBN 978-0-444-86388-1.
• Monk, J. Donald (1976). Mathematical Logic. New York, NY: Springer New York. ISBN 978-1-4684-9454-9. doi:10.1007/978-1-4684-9452-5.
• Barwise, Jon; and Etchemendy, John (2000); Language Proof and Logic, Stanford, CA: CSLI Publications (Distributed by the University of Chicago Press)
• Bocheński, Józef Maria (2007); A Précis of Mathematical Logic, Dordrecht, NL: D. Reidel, translated from the French and German editions by Otto Bird
• Ferreiros, Jose (2001). „The Road to Modern Logic-An Interpretation”. The Bulletin of Symbolic Logic. 7 (4): 441—484. JSTOR 2687794. S2CID 43258676. doi:10.2307/2687794. hdl:11441/38373.
• Gamut, L. T. F. (1991), Logic, Language, and Meaning, Volume 2: Intensional Logic and Logical Grammar, Chicago, Illinois: University of Chicago Press, ISBN 0-226-28088-8
• Hilbert, David; and Ackermann, Wilhelm (1950); Principles of Mathematical Logic, Chelsea (English translation of Grundzüge der theoretischen Logik, 1928 German first edition)
• Hodges, Wilfrid (2001); "Classical Logic I: First-Order Logic", in Goble, Lou (ed.); The Blackwell Guide to Philosophical Logic, Blackwell
• Ebbinghaus, Heinz-Dieter; Flum, Jörg; and Thomas, Wolfgang (1994); , Undergraduate Texts in Mathematics, Berlin, DE/New York, NY: Springer-Verlag. Ebbinghaus, H. -D; Flum, J.; Thomas, Wolfgang (14. 3. 2013). Logic (2nd изд.). Springer. ISBN 978-0-387-94258-2. Текст „Mathematical ” игнорисан (помоћ)CS1 одржавање: Формат датума (веза)
• Tarski, Alfred and Givant, Steven (1987); Tarski, Alfred; Givant, Steven R. (1987). A Formalization of Set Theory without Variables. The Society. ISBN 978-0821810415.. Vol.41 of American Mathematical Society colloquium publications, Providence RI: American Mathematical Society
• Alexander of Aphrodisias, In Aristotelis An. Pr. Lib. I Commentarium, ed. Wallies, Berlin, C.I.A.G. vol. II/1, 1882.
• Avicenna, Avicennae Opera Venice 1508.
• Boethius Commentary on the Perihermenias, Secunda Editio, ed. Meiser, Leipzig, Teubner, 1880.
• Bolzano, Bernard Wissenschaftslehre, (1837) 4 Bde, Neudr., hrsg. W. Schultz, Leipzig I-II 1929, III 1930, IV 1931 (Theory of Science, four volumes, translated by Rolf George and Paul Rusnock, New York: Oxford University Press, 2014).
• Bolzano, Bernard Theory of Science (Edited, with an introduction, by Jan Berg. Translated from the German by Burnham Terrell – D. Reidel Publishing Company, Dordrecht and Boston 1973).
• Boole, George (1847) The Mathematical Analysis of Logic (Cambridge and London); repr. in Studies in Logic and Probability, ed. R. Rhees (London 1952).
• Boole, George (1854). The Laws of Thought. London and Cambridge.. repr. as Collected Logical Works. Vol. 2, (Chicago and London: Open Court, 1940).
• Epictetus, Epicteti Dissertationes ab Arriano digestae, edited by Heinrich Schenkl, Leipzig, Teubner. 1894.
• Frege, G., Boole's Logical Calculus and the Concept Script, 1882, in Posthumous Writings transl. P. Long and R. White 1969, pp. 9–46.
• Gergonne, Joseph Diaz (1816). „Essai de dialectique rationelle”. Annales de mathématiques pures et appliquées 7, 1816/1817, 189–228..
• Jevons, W. S. The Principles of Science, London 1879.
• Ockham's Theory of Terms: Part I of the Summa Logicae, translated and introduced by Michael J. Loux (Notre Dame, IN: University of Notre Dame Press 1974). Reprinted: South Bend, IN: St. Augustine's Press, 1998.
• Ockham's Theory of Propositions. Notre Dame, IN: University of Notre Dame Press. 1980. ISBN 978-0-268-01495-7.. Part II of the Summa Logicae, translated by Alfred J. Freddoso and Henry Schuurman and introduced by Alfred J. Freddoso . . Reprinted: South Bend, IN: St. Augustine's Press, 1998.
• Carus, Paul (1897). „The Regenerated Logic”. The Monist. VII. Chicago: The Open Court Publishing Co. стр. 19—40. Пронађени су сувишни параметри: |author= и |last1= (помоћ)
• Sextus Empiricus. (2005). Against the Logicians. ISBN 0-521-53195-0.. (Adversus Mathematicos VII and VIII). Richard Bett (trans.) Cambridge: Cambridge University Press
• Zermelo, Ernst (1908). „Untersuchungen über die Grundlagen der Mengenlehre I”. Mathematische Annalen. 65 (2): 261—281. S2CID 120085563. doi:10.1007/BF01449999. Архивирано из оригинала 08. 09. 2017. г. Приступљено 26. 06. 2023. English translation in. van Heijenoort, Jean (1967). „Investigations in the foundations of set theory”. From Frege to Gödel: A Source Book in Mathematical Logic, 1879–1931. Source Books in the History of the Sciences. Harvard University Press. стр. 199–215. ISBN 978-0-674-32449-7.
• Frege, Gottlob (1879). Begriffsschrift, a formula language, modeled upon that of arithmetic, for pure thought.. translated in van Heijenoort 1967.
• Barwise, Jon, (ed.). Barwise, Jon (1982). Handbook of Mathematical Logic. North-Holland. ISBN 978-0-444-86388-1.. Studies in Logic and the Foundations of Mathematics, Amsterdam, North Holland
• Beaney, Michael, The Frege Reader, London: Blackwell 1997.
• Bochenski, I. M., A History of Formal Logic, Indiana, Notre Dame University Press, 1961.
• Boehner, Philotheus, Medieval Logic, Manchester 1950.
• Boyer, C.B. (1991) [1989], A History of Mathematics (2nd изд.), New York: Wiley, ISBN 978-0-471-54397-8
• Buroker, Jill Vance (transl. and introduction), A. Arnauld, P. Nicole (1996). Logic or the Art of Thinking. Cambridge University Press. ISBN 0-521-48249-6.CS1 одржавање: Вишеструка имена: списак аутора (веза). Cambridge University Press
• Church, Alonzo, 1936–1938. „A bibliography of symbolic logic”. Journal of Symbolic Logic 1. : 121–218; 3:178–212
• de Jong, Everard (1989), Galileo Galilei's "Logical Treatises" and Giacomo Zabarella's "Opera Logica": A Comparison, PhD dissertation, Washington, DC: Catholic University of America
• Ebbesen, Sten "Early supposition theory (12th–13th Century)" Ebbesen, Sten (1981). „Early supposition theory (12th-13th century)”. Histoire, Épistémologie, Langage. 3 (1): 35—48. doi:10.3406/hel.1981.1068..
• Farrington, B., The Philosophy of Francis Bacon, Liverpool 1964.
• Feferman, Anita B. (1999). „Alfred Tarski”. American National Biography. Oxford University Press. 1999. стр. 330–332. ISBN 978-0-19-512800-0.. 21. Oxford University Press
• Feferman, Anita B.; Feferman, Solomon (2004). Alfred Tarski: Life and Logic. Cambridge University Press. ISBN 978-0-521-80240-6. OCLC 54691904.
• Gabbay, Dov and John Woods, eds. Gabbay, Dov M.; Woods, John; Woods, John Hayden (8. 3. 2004). Handbook of the History of Logic. Elsevier Science. ISBN 0-444-51611-5.CS1 одржавање: Формат датума (веза). 2004. 1. Greek, Indian and Arabic logic; 2. Mediaeval and Renaissance logic; 3. The rise of modern logic: from Leibniz to Frege; 4. British logic in the Nineteenth century; 5. Logic from Russell to Church; 6. Sets and extensions in the Twentieth century; 7. Logic and the modalities in the Twentieth century; 8. The many-valued and nonmonotonic turn in logic; 9. Computational Logic; 10. Inductive logic; 11. Logic: A history of its central concepts; Elsevier
• Geach, P. T. Logic Matters, Blackwell 1972.
• Goodman, Lenn Evan (2003). Islamic Humanism. Oxford University Press. ISBN 0-19-513580-6.
• Goodman, Lenn Evan (1992). Avicenna. Psychology Press. ISBN 0-415-01929-X.. Routledge
• Grattan-Guinness, Ivor, 2000. The Search for Mathematical Roots 1870–1940. Princeton University Press.
• Gracia, J. G. and Noone, T. B., A Companion to Philosophy in the Middle Ages, London 2003.
• Haaparanta, Leila (ed.) . (2009). The Development of Modern Logic. Oxford University Press..
• Heath, T. L., 1949. (1949). Mathematics in Aristotle. Oxford University Press.CS1 одржавање: Вишеструка имена: списак аутора (веза).
• Heath, T. L., 1931, A Manual of Greek Mathematics, Oxford (Clarendon Press).
• Honderich, Ted (ed.). The Oxford Companion to Philosophy.
• Kneale, William and Martha (1962). The development of logic. Oxford University Press. ISBN 0-19-824773-7.
• Lukasiewicz (1957). Aristotle's Syllogistic. Oxford University Press. 1951.
• Potter, Michael (2004). Set Theory and its Philosophy. Oxford University Press. ISBN 978-0-19-155643-2..

Спољашње везе