M1_przyklady.pdf

(324 KB) Pobierz
Przykłady.indd
Przykłady
Przykład 1
Rozważmy formułę ( p ⇒ r ) ⇒ ( ¬ s ∨ q ). Głównym spójnikiem tej formuły jest implikacja. Łączy ona
dwie podformuły p ⇒ r oraz ¬ s ∨ q . Podformuła ( p ⇒ r ) jest implikacją o poprzedniku p i następniku
r . Podformuła ¬ s ∨ q jest alternatywą o składnikach ¬ s oraz q . Po rozważeniu powyższego możemy
dokonać graficznego rozkładu formuły ( p ⇒ r ) ⇒ ( ¬ s ∨ q ) na podformuły w sposób następujący:
( p ⇒ r ) ⇒ ( ¬ s ∨ q )
⇒
p ⇒ r
¬ s ∨ q
⇒
∨
p
r
¬ s
q
¬
s
Rozkład formuły ¬ ( p ∨ q ) ⇒ s ∨ ¬ p na podformuły jest następujący:
¬ ( p ∨ q ) ⇒ s ∨ ¬ p
⇒
¬ ( p ∨ q )
s ∨ ¬ p
¬
∨
p ∨ q
s
¬ p
∨
¬
p q
p
39537989.013.png 39537989.014.png 39537989.015.png
Przykład 2
Przekształcenie formuł z poprzednich przykładów do notacji polskiej przedstawia się następująco (dla
uproszczenia przedstawiamy odpowiednie drzewo odwrotnie):
Formuła ( p ⇒ r ) ⇒ ( ¬ s ∨ q )
CCprANsq
C
Cpr
ANsq
C
A
p
r
Ns
q
N
s
Formuła ¬ ( p ∨ q ) ⇒ s ∨ ¬ p
CNApqAsNp
C
NApq
AsNp
N
A
Apq
s
Np
A
N
p
q
p
39537989.016.png 39537989.001.png 39537989.002.png
Przykład 3
Rozważmy formułę ENKNpqCANqsNCp Nq . Niżej przedstawiamy kolejne kroki przekształcania
formuły do postaci tradycyjnej (w każdym kroku niebieskim kolorem oznaczamy podformułę, którą
należy przekształcić w kolejnym kroku).
1. Nq przekształcamy w ¬ q ( ENKNpqCANqsN Cp ¬ q ).
2. Cp ¬ q przekształcamy w p ⇒ ¬ q ( ENKNpqCANqs N ( p ⇒ ¬ q ) ).
3. N ( p ⇒ ¬ q ) przekształcamy w ¬ ( p ⇒ ¬ q ) ( ENKNpqCA Nq s ¬ ( p ⇒ ¬ q )).
4. Nq przekształcamy w ¬ q ( ENKNpqC A ¬ qs ¬ ( p ⇒ ¬ q )).
5. A ¬ qs przekształcamy w ¬ q ∨ s ( ENKNpq C ( ¬ q ∨ s) ¬ ( p ⇒ ¬ q ) ).
6. C ( ¬ q ∨ s ) ¬ ( p ⇒ ¬ q ) przekształcamy w ( ¬ q ∨ s ) ⇒ ¬ ( p ⇒ ¬ q ) ( ENK Np q [( ¬ q ∨ s ) ⇒ ¬ ( p ⇒ ¬ q )]).
7. Np przekształcamy w ¬ p ( EN K ¬ pq [( ¬ q ∨ s ) ⇒ ¬ ( p ⇒ ¬ q )]).
8. K ¬ pq przekształcamy w ¬ p ∧ q ( E N ( ¬ p ∧ q ) [( ¬ q ∨ s ) ⇒ ¬ ( p ⇒ ¬ q )]).
9. N ( ¬ p ∧ q ) przekształcamy w ¬ ( ¬ p ∧ q ) ( E ¬ ( ¬ p ∧ q ) [( ¬ q ∨ s ) ⇒ ¬ ( p ⇒ ¬ q )] ).
10. E ¬ ( ¬ p ∧ q ) [( ¬ q ∨ s ) ⇒ ¬ ( p ⇒ ¬ q )] przekształcamy w ¬ ( ¬ p ∧ q ) ⇔ [( ¬ q ∨ s ) ⇒ ¬ ( p ⇒ ¬ q )].
Przykład 4
Rozważmy formułę p ∨ ( q ⇒ ¬ p ). Tabelka wartości logicznych przedstawia się następująco:
p q ¬ p q ⇒ ¬ p p ∨ ( q ⇒ ¬ p )
0 0 1
1
1
0 1 1
1
1
1 0 0
1
1
1 1 0
0
1
Przykład 5
Rozważmy formułę ¬ ( p ⇒ q ) ∧ ( ¬ p ∨ s ) (trzy zmienne zdaniowe, 2 3 wartościowań).
p q s
p ⇒ q ¬ ( p ⇒ q ) ¬ p ¬ p ∨ s
¬ ( p ⇒ q ) ∧ ( ¬ p ∨ s )
0 0 0 1
0
1
1
0
0 0 1 1
0
1
1
0
0 1 0 1
0
1
1
0
0 1 1 1
0
1
1
0
1 0 0 0
1
0
0
0
1 0 1 0
1
0
1
1
1 1 0 1
0
0
0
0
1 1 1 1
0
0
1
0
39537989.003.png 39537989.004.png 39537989.005.png 39537989.006.png 39537989.007.png 39537989.008.png 39537989.009.png 39537989.010.png 39537989.011.png 39537989.012.png
Przykład 6
Rozważmy formułę ¬ [( p ⇒ q ) ∧ ¬ ( q ∨ ¬ r )]. Załóżmy, że formuła ta ma wartość 0.
1. w ( ¬ [( p ⇒ q ) ∧ ¬ ( q ∨ ¬ r )]) = 0 (założenie).
2. w (( p ⇒ q ) ∧ ¬ ( q ∨ ¬ r ) ) = 1 (wniosek z 1, jeżeli negacja jest fałszywa, to jej podformuła jest
prawdziwa).
3. w( p ⇒ q ) = 1 (wniosek z 2, jeżeli koniunkcja jest prawdziwa, to ma prawdziwe czynniki).
4. w ( ¬ ( q ∨ ¬ r ) = 1 (wniosek z 2, jeżeli koniunkcja jest prawdziwa, to ma prawdziwe czynniki).
5. w ( q ∨ ¬ r ) = 0 (wniosek z 4, jeżeli negacja jest prawdziwa, to jej podformuła jest fałszywa).
6. w ( q ) = 0 (wniosek z 5, jeżeli alternatywa jest fałszywa, to ma fałszywe składniki).
7. w ( ¬ r ) = 0 (wniosek z 5, jeżeli alternatywa jest fałszywa, to ma fałszywe składniki).
8. w ( r ) = 1 (wniosek z 7, jeżeli negacja jest fałszywa, to jej podformuła jest prawdziwa).
9. w ( p ) = 0 (wniosek z 3 i 6, jeżeli implikacja ma fałszywy następnik i jest prawdziwa, to musi mieć
fałszywy poprzednik).
We wnioskowaniu nie ma sprzeczności, a wartości wszystkich zmiennych zostały określone. Formuła
nie jest tautologią.
Przykład 7
Rozważmy formułę ( p ∨ ¬ s ∨ s ) ∧ ( ¬ p ∨ t ∨ p ) ∧ ( ¬ q ∨ q ). Jest ona koniunkcją alternatyw złożonych
z samych zmiennych lub ich negacji, jest zatem w koniunkcyjnej postaci normalnej. Zauważmy
również, że w każdej alternatywie znajduje się para: zmienna i jej negacja, zatem formuła jest
tautologią.
Przykład 8
Rozważmy formułę ( p ∨ ¬ r ∨ s ) ∧ ( ¬ p ∨ t ∨ p ) ∧ ( ¬ q ∨ ¬ p ). Jest ona koniunkcją alternatyw złożonych
z samych zmiennych lub ich negacji, jest zatem w koniunkcyjnej postaci normalnej. Zauważmy
również, że nie w każdej alternatywie znajduje się para: zmienna i jej negacja, zatem formuła nie jest
tautologią.
Przykład 9
Rozważmy formułę ( t ∧ ¬ s ∧ s ) ∨ ( ¬ p ∧ p ) ∨ ( ¬ q ∧ ¬ s ∧ q ). Jest ona alternatywą koniunkcji złożonych
z samych zmiennych lub ich negacji jest zatem w alternatywnej postaci normalnej. Zauważmy również,
że w każdej koniunkcji znajduje się para: zmienna i jej negacja, zatem formuła jest kontrtautologią.
Przykład 10
Rozważmy formułę ( p ∧ ¬ s ∧ s ) ∨ ( ¬ p ∧ t ∧ s ) ∨ ( ¬ q ∧ ¬ q ). Jest ona alternatywą koniunkcji złożonych
z samych zmiennych lub ich negacji, jest zatem w alternatywnej postaci normalnej. Zauważmy
również, że nie w każdej koniunkcji znajduje się para: zmienna i jej negacja, zatem formuła nie jest
kontrtautologią.

Plik z chomika:

Inne pliki z tego folderu:

Inne foldery tego chomika:

Zgłoś jeśli naruszono regulamin