Tautologije iskaznog računa

Ekvivalencije

Sledeći zakoni se mogu primenjivati u oba smera, tj. i sleva nadesno i zdesna nalevo, tj. bilo koja (leva ili desna) strana ekvivalencije se može zameniti onom drugom.

Dvostruka negacija (kao da je i nema)
amath $I \Leftrightarrow \neg \neg I $ endmath
Komutativni zakon (zamena mesta operanada ne menja rezultat operacije)
- za konjunkciju
  amath $(I \wedge II) \Leftrightarrow (II \wedge I)$ endmath
- za disjunkciju
  amath $(I \vee II) \Leftrightarrow (II \vee I)$ endmath
Asocijativni zakon (rezultat operacije ne zavisi od grupisanja, udruživanja operanada)
- za konjunkciju
  amath $((I \wedge II) \wedge III) \Leftrightarrow (I \wedge (II \wedge III))$ endmath
- za disjunkciju
  amath $((I \vee II) \vee III) \Leftrightarrow (I \vee (II \vee III))$ endmath
Distributivni zakon
- konjunkcije u odnosu na disjunkciju
  amath $(I \wedge (II \vee III)) \Leftrightarrow ((I \wedge II) \vee (I \wedge III))$ endmath
- disjunkcije u odnosu na konjunkciju
  amath $(I \vee (II \wedge III)) \Leftrightarrow ((I \vee II) \wedge (I \vee III))$ endmath
De Morganovi zakoni
- negacija konjunkcije
  amath $\neg (I \wedge II) \Leftrightarrow (\neg I \vee \neg II)$ endmath
- negacija disjunkcije
  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

Sledeći zakoni se mogu primenjivati isključivo sleva nadesno, tj. iz leve strane implikacije se izvodi desna strana.

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

Zamena univerzalnog kvantifikatora egzistencijalnim
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
Zamena egzistencijalnog kvantifikatora univerzalnim
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
Redosled uzastopnih univerzalnih kvantifikatora nije bitan
amath $(\forall x)(\forall y)P \Leftrightarrow(\forall y)(\forall x)P$ endmath
Redosled uzastopnih egzistencijalnih kvantifikatora nije bitan
amath $(\exists x)(\exists y)P \Leftrightarrow(\exists y)(\exists x)P$ endmath
uzastopni univerzalni i egzistencijalni kvantifikator ne mogu da zamene mesta
amath $(\exists x)(\forall y)P \Rightarrow(\forall y)(\exists x)P$ endmath !!
Ako postoji neki (jedan te isti) koji važi za sve, onda za svakog postoji neki koji važi. Obrnuto nije tačno uvek, tj. ako za svakog postoji neki koji važi, to ne znači da je to jedan te isti za sve"
Univerzalni kvantifikator je uopštena konjunkcija, pa se može preraspodeliti na delove konjunkcije
amath $(\forall x)(P\wedge Q) \Leftrightarrow(\forall x)P\wedge (\forall x)Q$ endmath
Univerzalni kvantifikator je uopštena konjunkcija, pa se ne može preraspodeliti na delove disjunkcije, ali se delovi disjunkcije sa posebnim univerzalnim kvantifikatorom mogu spojiti tako da imaju zajednički kvantifikator
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
Egzistencijalni kvantifikator je uopštena disjunkcija, pa se može preraspodeliti na delove disjunkcije
amath $(\exists x)(P\vee Q) \Leftrightarrow (\exists x)P\vee (\exists x)Q$ endmath
Egzistencijalni kvantifikator je uopštena disjunkcija, ali se može preraspodeliti na delove konjunkcije, ali ne i obrnuto (delovi konjunkcije sa posebnim egzistencijalnim kvantifikatorom ne mogu se spojiti tako da imaju zajednički kvantifikator)
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 (konjunkcija iskaza je tačna jedino ako su oba iskaza tačna). Obrnuta implikacija ne važi, jer vrednost $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 u zakonu je utisak da na desnoj strani implikacije 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.
Ako se x ne pojavljuje u P onda
amath $(P \vee(\forall x)Q)\Leftrightarrow (\forall x)(P \vee Q)$ endmath
Ako se x ne pojavljuje u P onda
amath $(P \wedge(\forall x)Q)\Leftrightarrow (\forall x)(P \wedge Q)$ endmath
Ako se x ne pojavljuje u P onda
amath $(P \vee(\exists x)Q)\Leftrightarrow (\exists x)(P \vee Q)$ endmath
Ako se x ne pojavljuje u P onda
amath $(P \wedge(\exists x)Q)\Leftrightarrow (\exists x)(P \wedge Q)$ endmath
Ako se x ne pojavljuje u P onda
amath $(P \Rightarrow(\forall x)Q)\Leftrightarrow (\forall x)(P \Rightarrow Q)$ endmath
Ako se x ne pojavljuje u P onda
amath $(P \Rightarrow(\exists x)Q)\Leftrightarrow (\exists x)(P \Rightarrow Q)$ endmath
Ako se x ne pojavljuje u Q onda
amath $((\exists x)P \Rightarrow Q)\Leftrightarrow (\forall x)(P \Rightarrow Q)$ endmath
Ako se x ne pojavljuje u Q onda
amath $((\forall x)P \Rightarrow Q)\Leftrightarrow (\exists x)(P \Rightarrow Q)$ endmath