3050.

17.a

TEKST ZADATKA

Dokazati da je formula tautologija: (p⇒(q1∧q2∧q3))⇔((p⇒q1)∧(p⇒q2)∧(p⇒q3)) (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⇒(q1∧q2∧q3)p \Rightarrow (q_1 \land q_2 \land q_3)

Koristimo definiciju implikacije, koja glasi A⇒B≡¬A∨B, A \Rightarrow B \equiv \neg A \lor B , kako bismo eliminisali znak implikacije.

¬p∨(q1∧q2∧q3)\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∨(B∧C∧D)≡(A∨B)∧(A∨C)∧(A∨D). A \lor (B \land C \land D) \equiv (A \lor B) \land (A \lor C) \land (A \lor D) .

(¬p∨q1)∧(¬p∨q2)∧(¬p∨q3)(\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 (¬A∨B≡A⇒B \neg A \lor B \equiv A \Rightarrow B ), na svaku od tri zagrade pojedinačno.

(p⇒q1)∧(p⇒q2)∧(p⇒q3)(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⇒(q1∧q2∧q3))⇔((p⇒q1)∧(p⇒q2)∧(p⇒q3))≡⊤(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