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

Из Википедије, слободне енциклопедије

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

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

Примјер логичког исказа[уреди]

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

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

Формално установљење[уреди]

Исказни рачун се формално дефинише као алгебарска структура \mathcal{L} = \mathcal{L}\ (\Alpha,\ \Omega,\ \Zeta,\ \Iota) са сљедећим својствима:

  • \Alpha је коначан скуп логичких промјенљивих, које се најчешће представљају малим латиничним штампаним словима p, q, r, ....
  • \Omega је коначан скуп логичких операција, који представља унију дисјунктних подскупова \{ \Omega_0, \Omega_1, \ldots, \Omega_n, \ldots \}, гдје n-ти подскуп представља подскуп n-арних операција. Тако, \Omega_1 представља скуп унарних операција, \Omega_2 бинарних, итд. Уобичајени симболи логичких операција из одговарајућих подскупова су сљедећи:
\Omega_0 = \{ \top, \bot \}
\Omega_1 = \{ \lnot \} \,,
\Omega_2 = \{ \land, \lor, \Rightarrow, \Leftrightarrow \} \,.
Интересантно је примијетити да се логичке константе дефинишу као нуларне операције.
Исказне формуле се формирају од елемената скупа \Alpha користећи операције скупа \Omega на основу сљедећих правила:
  1. Елементи скупа \Alpha су логички искази.
  2. За сваку операцију из скупа \Omega, резултат те операције је логички исказ, ако су и операнди логички искази.
  3. логички искази се не могу формирати ни на један други начин осим помоћу правила 1. и 2.
Тако, на примјер, ако су p, q и r елементи скупа \Alpha, и ако користимо стандардне симболе за логичке операције, онда су p, q, r, \lnot p, p \land q, q \Rightarrow (p \land q) све исказне формуле.
  • Скуп \Zeta је коначан скуп правила трансформације логичких исказа. Ова правила поближе одређују особине операција и њихово понашање у додиру са другим операцијама, односно одређују на који начин се један логички исказ може свести на други, најчешће једноставнији, исказ.
  • Скуп \Iota је коначан скуп аксиома - по дефиницији истинитих тврдњи - у вези са логичким исказима.

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

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

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

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

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

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

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

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

Примјена[уреди]

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

Рачунарство[уреди]

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

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

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

Види још[уреди]

Спољашње везе[уреди]