Doprowadź do najprostszej postaci (prawa logiczne)

Cześć, może ktoś rozumie i może wytłumaczyć jak powinienem wykonywać zadania tego typu, w tym rzecz, rozumiem konieczność korzystania z praw, ale nie wiem jak je odpowiednio zastosować dla przykładu np. zanegować zdanie czy muszę je rozbić na jakieś części?. Dla przykładu chciałbym rozwiązać przykład sprowadzając go do najprostszej postaci :
(p ∧ q ∧ s) ∨ (p ∧ ¬q ∧ ¬r) ∨ (p ∧ q ∧ ¬s) ∨ ¬(p ∨ r → q)

Prawa De Morgana Twoim przyjacielem ;)

Patrząc po przykładzie to jedyne co tutaj można zrobić to:

• zamienić implikację r → q na równoważne ¬r ∨ q
• zastosować prawa De Morgana dla negacji alternatywy

jw, najpierw wywal tą implikacje, a potem to już po prostu trzeba mieć "pomysł", nie ma jakiejś generalej zasady jak postępować ;]

Z tego co wiem, odpowiedź powinna wynosić p zaś na wolframie co innego pokazuje hmm

Czyli to by znaczyło, że tezą jest: (p ∧ q ∧ s) ∨ (p ∧ ¬q ∧ ¬r) ∨ (p ∧ q ∧ ¬s) ∨ ¬(p ∨ r → q) |= p?

No w takim wypadku to wpierw obie rzeczy wspomniane przeze mnie i @danek a następnie lecisz metodą Karnaugha.

W skrócie zamieniasz swoje zdanie w DNF:

(p ∧ q ∧ s) ∨ (p ∧ ¬q ∧ ¬r) ∨ (p ∧ q ∧ ¬s) ∨ ¬(p ∨ r → q) ⟺ (p ∧ q ∧ s) ∨ (p ∧ ¬q ∧ ¬r) ∨ (p ∧ q ∧ ¬s) ∨ (p ∧ ¬q) ∨ (¬q ∧ r) 

W ten sposób mamy 4 zdania:

1. p ∧ q ∧ s
2. p ∧ ¬q ∧ ¬r
3. p ∧ q ∧ ¬s
4. p ∧ ¬q
5. ¬q ∧ r

I jeśli którekolwiek z nich jest prawdziwe, to całość też jest prawdziwa. Teraz zostaje tylko 3-SAT by to rozwiązać i masz ;)

Na szybko możemy zobaczyć, że wynik nie zależy od wartości s (bo jeśli jest fałszywe to możemy spełnić zdanie 3. a jak prawdziwe to 1.), więc możemy wyeliminować z całości, co zmniejsza nam ilość różnych zdań o 1:

1. p ∧ q
2. p ∧ ¬q ∧ ¬r
3. p ∧ ¬q
4. ¬q ∧ r

Automatycznie widzimy, że 2. i 3. nie zależą od wartości r więc możemy wywalić kolejne zdanie:

1. p ∧ q
2. p ∧ ¬q
3. ¬q ∧ r

Ze zdań 1. i 2. widzimy, że nie zależą one od q, więc znów możemy zredukować:

1. p
2. ¬q ∧ r

EDIT: Wcześniejsza wersja miała błędną kolejność operatorów.