Таутологије исказног рачуна

Еквиваленције

Следећи закони се могу примењивати у оба смера, тј. и слева надесно и здесна налево, тј. било која (лева или десна) страна еквиваленције се може заменити оном другом.

Двострука негација (као да је и нема)
amath $I \Leftrightarrow \neg \neg I $ endmath
Комутативни закон (замена места операнада не мења резултат операције)
- за конјункцију
  amath $(I \wedge II) \Leftrightarrow (II \wedge I)$ endmath
- за дисјункцију
  amath $(I \vee II) \Leftrightarrow (II \vee I)$ 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
Дистрибутивни закон
- конјункције у односу на дисјункцију
  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
Де Морганови закони
- негација конјункције
  amath $\neg (I \wedge II) \Leftrightarrow (\neg I \vee \neg II)$ endmath
- негација дисјункције
  amath $\neg (I \vee II) \Leftrightarrow (\neg I \wedge \neg II)$ endmath
Контрапозиција
amath $(I \Rightarrow II) \Leftrightarrow (\neg II \Rightarrow \neg I)$ endmath
Еквивалент импликације
amath $(I \Rightarrow II) \Leftrightarrow (\neg I \vee II)$ endmath
Негација импликације
amath $\neg (I \Rightarrow II) \Leftrightarrow (I \wedge \neg II)$ endmath
Еквивалент еквиваленције
amath $(I \Leftrightarrow II) \Leftrightarrow ((I \Rightarrow II) \wedge (II \Rightarrow I))$ endmath

Импликације

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

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
Поједностављење
amath $(I \wedge II) \Rightarrow I$ endmath
Додавање
amath $I \Rightarrow (I \vee II)$ endmath
Спајање
amath $I \wedge II \Rightarrow (I \wedge II)$ endmath

Предикатски рачун

Закони

Замена универзалног квантификатора егзистенцијалним
amath $(\forall x)P \Leftrightarrow\neg(\exists x)\neg P$ endmath
Сваки amath $x$endmath је amath $P$endmath је исто као Не постоји amath $x$ endmath који није amath $P$endmath
Замена егзистенцијалног квантификатора универзалним
amath $(\exists x)P \Leftrightarrow\neg(\forall x)\neg P$endmath
Постоји amath $x$ endmath који је amath $P$endmath је исто као Није тачно да сваки (ниједан) amath $x$ endmath није amath $P$endmath
Редослед узастопних универзалних квантификатора није битан
amath $(\forall x)(\forall y)P \Leftrightarrow(\forall y)(\forall x)P$ endmath
Редослед узастопних егзистенцијалних квантификатора није битан
amath $(\exists x)(\exists y)P \Leftrightarrow(\exists y)(\exists x)P$ endmath
узастопни универзални и егзистенцијални квантификатор не могу да замене места
amath $(\exists x)(\forall y)P \Rightarrow(\forall y)(\exists x)P$ endmath !!
Ако постоји неки (један те исти) који важи за све, онда за сваког постоји неки који важи. Обрнуто није тачно увек, тј. ако за сваког постоји неки који важи, то не значи да је то један те исти за све"
Универзални квантификатор је уопштена конјункција, па се може прерасподелити на делове конјункције
amath $(\forall x)(P\wedge Q) \Leftrightarrow(\forall x)P\wedge (\forall x)Q$ endmath
Универзални квантификатор је уопштена конјункција, па се не може прерасподелити на делове дисјункције, али се делови дисјункције са посебним универзалним квантификатором могу спојити тако да имају заједнички квантификатор
amath $(\forall x)P\vee (\forall x)Q \Rightarrow (\forall x)(P\vee Q)$ endmath !!
Ако бар једно од тврђења amath $P$ endmath и amath $Q$ endmath важи за све елементе домена, онда и amath $P\vee Q$ endmath важи за све елементе домена. Обрнуто не важи, јер иако amath $P\vee Q$ endmath важи за све елементе домена, може да се деси да се домен може разбити на два подскупа тако да на једном важи само amath $P$endmath, а на другом само amath $Q$ endmath
Егзистенцијални квантификатор је уопштена дисјункција, па се може прерасподелити на делове дисјункције
amath $(\exists x)(P\vee Q) \Leftrightarrow (\exists x)P\vee (\exists x)Q$ endmath
Егзистенцијални квантификатор је уопштена дисјункција, али се може прерасподелити на делове конјункције, али не и обрнуто (делови конјункције са посебним егзистенцијалним квантификатором не могу се спојити тако да имају заједнички квантификатор)
amath $(\exists x)(P\wedge Q) \Rightarrow (\exists x)P\wedge (\exists x)Q$ endmath !!
Ако постоји елемент домена amath $x$ endmath за који важи amath $P\vee Q$endmath, тада је јасно да оба тврђења amath $P$ endmath и amath $Q$ endmath важе за тај елемент amath $x$ endmath (конјункција исказа је тачна једино ако су оба исказа тачна). Обрнута импликација не важи, јер вредност $x$ endmath из домена за коју је тачно amath $P$ не мора бити иста вредност домена за коју важи amath $Q$endmath. Оно што делује збуњујуће у закону је утисак да на десној страни импликације променљива amath $x$ endmath може истовремено да узме две различите вредности домена. То заправо и јесте тачно јер се истинитост формула amath $(\exists x)P endmath и amath $(\exists x)Q$ рачуна независно једна од друге, а променљива коју посматрамо је везана, па је ситуација иста као да бисмо имали две различите променљиве са истим надимком. Другим речима, amath $(\exists x)P\wedge (\exists x)Q \Leftrightarrow (\exists x)P\wedge (\exists y)R$endmath, где је amath $R$endmath формула добијена од формуле Q заменом сваког појављивања везане променљиве amath $x$endmath везаном променљивом amath $y$endmath.
Ако се x не појављује у P онда
amath $(P \vee(\forall x)Q)\Leftrightarrow (\forall x)(P \vee Q)$ endmath
Ако се x не појављује у P онда
amath $(P \wedge(\forall x)Q)\Leftrightarrow (\forall x)(P \wedge Q)$ endmath
Ако се x не појављује у P онда
amath $(P \vee(\exists x)Q)\Leftrightarrow (\exists x)(P \vee Q)$ endmath
Ако се x не појављује у P онда
amath $(P \wedge(\exists x)Q)\Leftrightarrow (\exists x)(P \wedge Q)$ endmath
Ако се x не појављује у P онда
amath $(P \Rightarrow(\forall x)Q)\Leftrightarrow (\forall x)(P \Rightarrow Q)$ endmath
Ако се x не појављује у P онда
amath $(P \Rightarrow(\exists x)Q)\Leftrightarrow (\exists x)(P \Rightarrow Q)$ endmath
Ако се x не појављује у Q онда
amath $((\exists x)P \Rightarrow Q)\Leftrightarrow (\forall x)(P \Rightarrow Q)$ endmath
Ако се x не појављује у Q онда
amath $((\forall x)P \Rightarrow Q)\Leftrightarrow (\exists x)(P \Rightarrow Q)$ endmath