Sprowadzanie do DNF

[zekori]

Sprowadź formułę \(\displaystyle{ ((p \wedge q) \Rightarrow (p \vee q))}\) do postaci DNF.
Tego typu \(\displaystyle{ ((p \wedge q) \wedge p}\) wiem jak zrobić, ale powyższego przykładu nie mam pojęcia.

[Jan Kraszewski]

Zacznij od prawa eliminacji implikacji.

JK

[zekori]

czyli \(\displaystyle{ \left( \neg p \wedge \neg q \right) \vee \left( p \wedge q\right) }\)?
jeżeli tak, to co dalej?

[Jan Kraszewski]

czyli \(\displaystyle{ \left( \neg p \wedge \neg q \right) \vee \left( p \wedge q\right) }\)?

A skąd Ty to wziąłeś?!

JK

[zekori]

A implikacji nie eliminuje się poprzez negację pierwszego wyrazu, wstawienia alternatywy zamiast znaku implikacji i przepisaniu drugiego wyrazu? Nie mam pojęcia jak o robić na nawiasach

[Jan Kraszewski]

A implikacji nie eliminuje się poprzez negację pierwszego wyrazu, wstawienia alternatywy zamiast znaku implikacji i przepisaniu drugiego wyrazu?

Tak, ale to zdecydowanie nie jest to, co zrobiłeś.

Nie mam pojęcia jak o robić na nawiasach

Systematycznie. Jak nie umiesz inaczej, to zrób podstawienie:

\(\displaystyle{ p\land q=\heartsuit,\ p\lor q=\clubsuit}\)

potem zastosuj metodę, którą podałeś, potem podstawienie zwrotne, potem prawo de Morgana (ale poprawnie!) itd.

JK

[zekori]

\(\displaystyle{ \neg p \vee \neg q \vee \left( p \vee q\right) }\) i na tym koniec?
czy trzeba dalej to rozpisywać? czyli \(\displaystyle{ \left( \neg p \vee p\right) \vee \left( \neg p \vee q\right) \vee \left( \neg q \vee p\right) \vee \left( \neg q \vee q\right)}\)
Wybacz za błędy, ale pierwszy raz robię taki przykład

[Jan Kraszewski]

\(\displaystyle{ \neg p \vee \neg q \vee \left( p \vee q\right) }\) i na tym koniec?

W sensie zastosowania eliminacji implikacji - tak. Poza tym formuła \(\displaystyle{ \neg p \vee \neg q \vee p \vee q }\) jest w postaci DNF. Natomiast łatwo można zauważyć, że rozpatrywana formuła jest tautologią, wystarczy zatem wziąć dowolną tautologię w postaci DNF, np. \(\displaystyle{ p\lor \neg p}\).

Kod: Zaznacz cały

https://math.stackexchange.com/questions/64473/what-is-the-conjunction-normal-form-of-a-tautology

masz dyskusję na podobny temat.

czy trzeba dalej to rozpisywać? czyli \(\displaystyle{ \left( \neg p \vee p\right) \vee \left( \neg p \vee q\right) \vee \left( \neg q \vee p\right) \vee \left( \neg q \vee q\right)}\)

Nie trzeba.

JK