Tautologija

PostPoslato: Petak, 30. Mart 2018, 22:47
od geostorm
Dokazati da je sledeća formula tautologija preko zakona:
[dispmath]\bigl((p\;\Longrightarrow\;q)\land(r\;\Longrightarrow\;q)\bigr)\;\Longrightarrow\;\bigl((p\land r\;\Longrightarrow\;q)\land(p\lor r\;\Longrightarrow\;q)\bigr)[/dispmath]
[dispmath]\lnot\bigl((\lnot p\lor q)\land(\lnot r \lor q)\bigr)\lor\Bigl(\bigl(\lnot(p\land r)\lor q\bigr)\land\bigl(\lnot(p\lor r)\lor q\bigr)\Bigr)\\
\bigl((p\land\lnot q)\lor(r\land\lnot q)\bigr)\lor\Bigl((\lnot p\lor\lnot r\lor q)\land\bigl((\lnot p\land\lnot r)\lor q\bigr)\Bigr)\\
\Bigl(\bigl(\lnot q\land(p\lor r)\bigl)\lor(\lnot p\lor\lnot r\lor q)\bigr)\land\Bigl(\bigl(\lnot q\land(p\lor r)\lor(\lnot p\land\lnot r)\lor q\bigr)\Bigr)\\
\top\land\top\land\Bigl(\top\land\bigl((\lnot p\land\lnot r)\lor q\lor p\lor r\bigr)\Bigr)\\
\top\land\Bigl(\bigl((p\lor\lnot p)\land(p\lor\lnot r)\bigr)\lor q\lor r\Bigr)\\
\Bigl(\bigl((r\lor\top)\land(p\lor\lnot r\lor r)\bigr)\lor q\Bigr)\\
\bigl((\top\land\top)\lor q\bigr)\\
\top[/dispmath] Mislim da bi trebalo ovako da ide. Malo teži zadatak ali možda će nekom da zatreba. Ne znam da li ima kraći način, ali ako postoji kraći ili postoji neka greška u načinu rada vi napišite. Naravno, ovo može da se proveri preko tablice.

Re: Tautologija

PostPoslato: Subota, 31. Mart 2018, 00:47
od Daniel
Mislim da će ovo biti malo jednostavnije:
[dispmath]\bigl((p\;\Longrightarrow\;q)\land(r\;\Longrightarrow\;q)\bigr)\;\Longrightarrow\;\bigl((p\land r\;\Longrightarrow\;q)\land(p\lor r\;\Longrightarrow\;q)\bigr)\\
\bigl((\lnot p\lor q)\land(\lnot r\lor q)\bigr)\;\Longrightarrow\;\Bigl(\bigl(\lnot(p\land r)\lor q\bigr)\land\bigl(\lnot(p\lor r)\lor q\bigr)\Bigr)\\
\bigl((\lnot p\land\lnot r)\lor q\bigr)\;\Longrightarrow\;\Bigl(\bigl(\lnot(p\land r)\land\lnot(p\lor r)\bigr)\lor q\Bigr)\\
\bigl(\lnot(p\lor r)\lor q\bigr)\;\Longrightarrow\;\Bigl(\lnot\bigl((p\land r)\lor(p\lor r)\bigr)\lor q\Bigr)\\
\bigl(\lnot(p\lor r)\lor q\bigr)\;\Longrightarrow\;\bigl(\lnot(p\lor r)\lor q\bigr)[/dispmath] I, pošto su obe strane implikacije jednake (tj. ili je [inlmath]\top\;\Longrightarrow\;\top[/inlmath] ili je [inlmath]\bot\;\Longrightarrow\;\bot[/inlmath]), implikacija mora biti tačna.