Iskazni račun

Tautologije

Ekvivalencije

• Dvostruka negacija amath $I \Leftrightarrow \neg \neg I $ endmath
• Zakon komutativnosti
  • amath $(I \wedge II) \Leftrightarrow (II \wedge I)$ endmath
  • amath $(I \vee II) \Leftrightarrow (II \vee I)$ endmath
• Zakon asocijativnosti amath $I \Leftrightarrow II$ endmath
  • amath $((I \wedge II) \wedge III) \Leftrightarrow (I \wedge (II \wedge III))$ endmath
  • amath $((I \vee II) \vee III) \Leftrightarrow (I \vee (II \vee III))$ endmath
• Zakon distributivnosti
  • amath $(I \wedge (II \vee III)) \Leftrightarrow ((I \wedge II) \vee (I \wedge III))$ endmath
  • amath $(I \vee (II \wedge III)) \Leftrightarrow ((I \vee II) \wedge (I \vee III))$ endmath
• De Morganovi zakoni
  • amath $\neg (I \wedge II) \Leftrightarrow (\neg I \vee \neg II)$ endmath
  • amath $\neg (I \vee II) \Leftrightarrow (\neg I \wedge \neg II)$ endmath
• Kontrapozicija amath $(I \Rightarrow II) \Leftrightarrow (\neg II \Rightarrow \neg I)$ endmath
• Ekvivalent implikacije amath $(I \Rightarrow II) \Leftrightarrow (\neg I \vee II)$ endmath
• Negacija implikacije amath $\neg (I \Rightarrow II) \Leftrightarrow (I \wedge \neg II)$ endmath
• Ekvivalent ekvivalencije amath $(I \Leftrightarrow II) \Leftrightarrow ((I \Rightarrow II) \wedge (II \Rightarrow I))$ endmath

Implikacije

• Modus ponens amath $(I \wedge (I \Rightarrow II)) \Rightarrow II$ endmath
• Modus tollens amath $(\neg II \wedge (I \Rightarrow II)) \Rightarrow \neg I$ endmath
• Modus tollendo ponens amath $((I \vee II) \wedge \neg I) \Rightarrow II$ endmath
• Pojednostavljenje amath $(I \wedge II) \Rightarrow I$ endmath
• Dodavanje amath $I \Rightarrow (I \vee II)$ endmath
• Spajanje amath $I \wedge II \Rightarrow (I \wedge II)$ endmath

Predikatski račun

Zakoni

1. amath $(\forall x)P \Leftrightarrow\neg(\exists x)\neg P$ endmath "Svaki amath $x$endmath je amath $P$endmath" je isto kao "Ne postoji amath $x$ endmath koji nije amath $P$endmath"
2. amath $(\exists x)P \Leftrightarrow\neg(\forall x)\neg P$endmath "Postoji amath $x$ endmath koji je amath $P$endmath" je isto kao "Nije tačno da 'svaki' (nijedan) amath $x$ endmath nije amath $P$endmath"
3. amath $(\forall x)(\forall y)P \Leftrightarrow(\forall y)(\forall x)P$ endmath "Redosled univerzalnih kvantifikatora nije bitan"
4. amath $(\exists x)(\exists y)P \Leftrightarrow(\exists y)(\exists x)P$ endmath "Redosled egzistencijalnih kvantifikatora nije bitan"
5. amath $(\exists x)(\forall y)P \Rightarrow(\forall y)(\exists x)P$ endmath !! "Ako postoji neki (jedan te isti) za sve, onda za svakog postoji neki. Obrnuto ne važi, tj. ako za svakog postoji neki to ne znači da postoji istovetan neki za sve"
6. amath $(\forall x)(P\wedge Q) \Leftrightarrow(\forall x)P\wedge (\forall x)Q$ endmath
7. amath $(\forall x)P\vee (\forall x)Q \Rightarrow (\forall x)(P\vee Q)$ endmath !! "Ako bar jedno od tvrđenja amath $P$ endmath i amath $Q$ endmath važi za sve elemente domena, onda i amath $P\vee Q$ endmath važi za sve elemente domena. Obrnuto ne važi, jer iako amath $P\vee Q$ endmath važi za sve elemente domena, može da se desi da se domen može razbiti na dva podskupa tako da na jednom važi samo amath $P$endmath, a na drugom samo amath $Q$ endmath"
8. amath $(\exists x)(P\vee Q) \Leftrightarrow (\exists x)P\vee (\exists x)Q$ endmath
9. amath $(\exists x)(P\wedge Q) \Rightarrow (\exists x)P\wedge (\exists x)Q$ endmath !! "Ako postoji element domena amath $x$ endmath za koji važi amath $P\vee Q$endmath, tada je jasno da oba tvrđenja amath $P$ endmath i amath $Q$ endmath važe za taj element amath $x$ endmath (konjukcija iskaza je tačna jedino ako su oba iskaza tačna). Obrnuta implikacija ne važi, jer vrednost amath $x$ endmath iz domena za koju je tačno amath $P$ ne mora biti ista vrednost domena za koju važi amath $Q$endmath. Ono što deluje zbunjujuće je da na desnoj strani implikacije u zakonu promenljiva amath $x$ endmath može istovremeno da uzme dve različite vrednosti domena. To zapravo i jeste tačno jer se istinitost formula amath $(\exists x)P endmath i amath $(\exists x)Q$ računa nezavisno jedna od druge, a promenljiva koju posmatramo je vezana, pa je situacija ista kao da bismo imali dve različite promenljive sa istim nadimkom. Drugim rečima, amath $(\exists x)P\wedge (\exists x)Q \Leftrightarrow (\exists x)P\wedge (\exists y)R$endmath, gde je amath $R$endmath formula dobijena od formule Q zamenom svakog pojavljivanja vezane promenljive amath $x$endmath vezanom promenljivom amath $y$endmath."
10. Ako se x ne pojavljuje u P onda amath $(P \vee(\forall x)Q)\Leftrightarrow (\forall x)(P \vee Q)$ endmath
11. Ako se x ne pojavljuje u P onda amath $(P \wedge(\forall x)Q)\Leftrightarrow (\forall x)(P \wedge Q)$ endmath
12. Ako se x ne pojavljuje u P onda amath $(P \vee(\exists x)Q)\Leftrightarrow (\exists x)(P \vee Q)$ endmath
13. Ako se x ne pojavljuje u P onda amath $(P \wedge(\exists x)Q)\Leftrightarrow (\exists x)(P \wedge Q)$ endmath
14. Ako se x ne pojavljuje u P onda amath $(P \Rightarrow(\forall x)Q)\Leftrightarrow (\forall x)(P \Rightarrow Q)$ endmath
15. Ako se x ne pojavljuje u P onda amath $(P \Rightarrow(\exists x)Q)\Leftrightarrow (\exists x)(P \Rightarrow Q)$ endmath
16. Ako se x ne pojavljuje u Q onda amath $((\exists x)P \Rightarrow Q)\Leftrightarrow (\forall x)(P \Rightarrow Q)$ endmath
17. Ako se x ne pojavljuje u Q onda amath $((\forall x)P \Rightarrow Q)\Leftrightarrow (\exists x)(P \Rightarrow Q)$ endmath