3050. Osnovne operacije sa iskazima

TEKST ZADATKA

Dokazati da je formula tautologija: $(p \Rightarrow (q_1 \land q_2 \land q_3)) \Leftrightarrow ((p \Rightarrow q_1) \land (p \Rightarrow q_2) \land (p \Rightarrow q_3))$

REŠENJE ZADATKA

Da bismo dokazali da je data formula tautologija, pokazaćemo da su leva i desna strana ekvivalencije logički jednake. Krenućemo od leve strane izraza.

p \Rightarrow (q_1 \land q_2 \land q_3)

Koristimo definiciju implikacije, koja glasi $A \Rightarrow B \equiv \neg A \lor B ,$ kako bismo eliminisali znak implikacije.

\neg p \lor (q_1 \land q_2 \land q_3)

Primenjujemo zakon distributivnosti disjunkcije prema konjunkciji. Ovaj zakon se može proširiti na više članova: $A \lor (B \land C \land D) \equiv (A \lor B) \land (A \lor C) \land (A \lor D) .$

(\neg p \lor q_1) \land (\neg p \lor q_2) \land (\neg p \lor q_3)

Sada ponovo primenjujemo definiciju implikacije, ali u obrnutom smeru ( $\neg A \lor B \equiv A \Rightarrow B$ ), na svaku od tri zagrade pojedinačno.

(p \Rightarrow q_1) \land (p \Rightarrow q_2) \land (p \Rightarrow q_3)

Dobili smo tačno desnu stranu početne ekvivalencije. Pošto se leva strana može transformisati u desnu koristeći pravila logičke ekvivalencije, zaključujemo da je polazna formula uvek tačna, odnosno da je tautologija.

(p \Rightarrow (q_1 \land q_2 \land q_3)) \Leftrightarrow ((p \Rightarrow q_1) \land (p \Rightarrow q_2) \land (p \Rightarrow q_3)) \equiv \top

17.a