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
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
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
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:
darkstone
Inne pliki z tego folderu:
M6_zadania.pdf
(129 KB)
M6_przyklady.pdf
(207 KB)
M6.pdf
(558 KB)
M5_zadania.pdf
(298 KB)
M5_przyklady.pdf
(322 KB)
Inne foldery tego chomika:
semestr IV
Zgłoś jeśli
naruszono regulamin