Witam, czy jest ktoś w stanie pomóc mi doprowadzić to zadanie do końca? Mam zastosować metodę przekształceń równoważnościowych i sprowadzić to do KPN:
\(\displaystyle{ (p \Rightarrow q) \Rightarrow ((r \Rightarrow q) \Rightarrow (p \vee r \Rightarrow q))}\)
\(\displaystyle{ \neg (p \Rightarrow q) \vee ((r \Rightarrow q) \Rightarrow (p \vee r \Rightarrow q))}\)
\(\displaystyle{ \neg ( \neg p \vee q) \vee ( \neg (r \Rightarrow q) \vee (p \vee r \Rightarrow q))}\)
\(\displaystyle{ \neg ( \neg p \vee q) \vee ( \neg ( \neg r \vee q) \vee ( \neg (p \vee r) \vee q))}\)
\(\displaystyle{ (p \wedge \neg q) \vee ((r \wedge \neg q) \vee (( \neg p \wedge \neg r) \vee q))}\)
\(\displaystyle{ (p \wedge \neg q) \vee ((r \wedge \neg q) \vee (( \neg p \vee q) \wedge ( \neg r \vee q))}\)
Sprowadzenie do postaci normalnej
-
- Administrator
- Posty: 34331
- Rejestracja: 20 mar 2006, o 21:54
- Płeć: Mężczyzna
- Lokalizacja: Wrocław
- Podziękował: 3 razy
- Pomógł: 5204 razy
Re: Sprowadzenie do postaci normalnej
Zgubiłeś jeden nawias.
Teraz czeka Cię wielokrotne (i uważne) stosowanie praw rozdzielności.
JK
Re: Sprowadzenie do postaci normalnej
Tak, dzięki
Te nawiasy właśnie sprawiają że nie wiem co tam najpierw zrobić i jak sprawić by ten podwójny nawias zniknął z tego miejsca:
\(\displaystyle{ ...(( \neg p \vee q) \wedge ( \neg r \vee q))}\)
bo jak robię to prawami rodzielności to i tak wychodzą takie rzeczy, że potem nie jestem w stanie dojść do KPN właśnie przez ten fragment
Te nawiasy właśnie sprawiają że nie wiem co tam najpierw zrobić i jak sprawić by ten podwójny nawias zniknął z tego miejsca:
\(\displaystyle{ ...(( \neg p \vee q) \wedge ( \neg r \vee q))}\)
bo jak robię to prawami rodzielności to i tak wychodzą takie rzeczy, że potem nie jestem w stanie dojść do KPN właśnie przez ten fragment
-
- Administrator
- Posty: 34331
- Rejestracja: 20 mar 2006, o 21:54
- Płeć: Mężczyzna
- Lokalizacja: Wrocław
- Podziękował: 3 razy
- Pomógł: 5204 razy
Re: Sprowadzenie do postaci normalnej
Bo to trzeba trochę sprytu.
Weź przedostatnią linijkę:
\(\displaystyle{ (p \wedge \neg q) \vee ((r \wedge \neg q) \vee (( \neg p \wedge \neg r) \vee q)).}\)
Zauważ, że jest równoważna (dwukrotnie łączność):
\(\displaystyle{ \blue{(}(p \wedge \neg q) \vee (r \wedge \neg q)\blue{)} \vee ( \neg p \wedge \neg r) \vee q.}\)
W niebieskich nawiasach zwijam z rozdzielności, korzystam z przemienności (i łączności) i mam
\(\displaystyle{ \red{(}\blue{(}(p \lor r)\, \green{\wedge}\, \neg q)\blue{)}\, \magenta{\vee}\, q\red{)}\vee ( \neg p \wedge \neg r).}\)
Teraz rozdzielność alternatywy względem koniunkcji w czerwonych nawiasach i mam
\(\displaystyle{ \red{(}(p \lor r\lor q)\, \green{\wedge}\, (\neg q\lor q)\red{)}\vee ( \neg p \wedge \neg r),}\)
czyli, po uproszczeniu,
\(\displaystyle{ p \lor r\lor q\vee ( \neg p \wedge \neg r),}\)
skąd dostaję za pomocą rozdzielności
\(\displaystyle{ (p \lor r\lor q\vee \neg p) \wedge (p \lor r\lor q\vee\neg r)}\)
czyli pożądaną KPN.
Inna sprawa, że (zwłaszcza z tej końcowej postaci) nietrudno zauważyć, że rozważany schemat zdaniowy jest tautologią, więc ma dużo innych prostszych wersji KPN...
JK
Weź przedostatnią linijkę:
\(\displaystyle{ (p \wedge \neg q) \vee ((r \wedge \neg q) \vee (( \neg p \wedge \neg r) \vee q)).}\)
Zauważ, że jest równoważna (dwukrotnie łączność):
\(\displaystyle{ \blue{(}(p \wedge \neg q) \vee (r \wedge \neg q)\blue{)} \vee ( \neg p \wedge \neg r) \vee q.}\)
W niebieskich nawiasach zwijam z rozdzielności, korzystam z przemienności (i łączności) i mam
\(\displaystyle{ \red{(}\blue{(}(p \lor r)\, \green{\wedge}\, \neg q)\blue{)}\, \magenta{\vee}\, q\red{)}\vee ( \neg p \wedge \neg r).}\)
Teraz rozdzielność alternatywy względem koniunkcji w czerwonych nawiasach i mam
\(\displaystyle{ \red{(}(p \lor r\lor q)\, \green{\wedge}\, (\neg q\lor q)\red{)}\vee ( \neg p \wedge \neg r),}\)
czyli, po uproszczeniu,
\(\displaystyle{ p \lor r\lor q\vee ( \neg p \wedge \neg r),}\)
skąd dostaję za pomocą rozdzielności
\(\displaystyle{ (p \lor r\lor q\vee \neg p) \wedge (p \lor r\lor q\vee\neg r)}\)
czyli pożądaną KPN.
Inna sprawa, że (zwłaszcza z tej końcowej postaci) nietrudno zauważyć, że rozważany schemat zdaniowy jest tautologią, więc ma dużo innych prostszych wersji KPN...
JK
-
- Użytkownik
- Posty: 22229
- Rejestracja: 15 maja 2011, o 20:55
- Płeć: Mężczyzna
- Lokalizacja: Bydgoszcz
- Podziękował: 38 razy
- Pomógł: 3757 razy
Re: Sprowadzenie do postaci normalnej
Albo tak"Jan Kraszewski pisze: ↑20 wrz 2023, o 15:54Zgubiłeś jeden nawias.
Teraz czeka Cię wielokrotne (i uważne) stosowanie praw rozdzielności.
JK
Oznaczmy \(\displaystyle{ a=(p \wedge \neg q), b=(r \wedge \neg q)}\)
wtedy
\(\displaystyle{ (p \wedge \neg q) \vee ((r \wedge \neg q) \vee (( \neg p \vee q) \wedge ( \neg r \vee q))) \Leftrightarrow a\vee b\vee (\neg a\wedge \neg b)
\Leftrightarrow (a\vee b)\vee \neg(a\vee b) \Leftrightarrow 1}\)