p
p
SPEŁNIALNOŚĆ I TAUTOLOGIE
Mówimy, że
formuła
jest:
•
spełniona,
jeżeli dla danego wartościowania ma wartość logiczną
1,
•
spełnialna
, jeżeli istnieje wartościowanie, przy którym ma
wartość logiczną 1,
•
tautologią,
jeśli ma wartość 1 dla każdego wartościowania
zmiennych
(lub — co na jedno wychodzi — nie istnieje wartościowanie, dla którego
ma wartość 0),
•
niespełnialna
(albo
kontrtautologią
), jeżeli ma wartość 0 dla każdego
wartościowania.
O formule spełnionej przez dane wartościowanie będziemy niekiedy
mówić, że jest prawdziwa przy tym wartościowaniu, natomiast formuła nie
spełniona będzie fałszywa.
Przykład 1:
jest tautologią, jest niespełnialna
p => q
jest spełnialna, i jest spełniona przy wartościowaniu takim, że
(p) = 0
i (q) = 1, natomiast nie jest spełniona przy wartościowaniu takim,
że
(p) = 1 i (q) = 0.
Każda formuła należy do jednej z powyższych kategorii. W konkretnych
przypadkach możliwe są różne podstawienia i interpretacje, jednak po
przedstawieniu formuły w sformalizowanej postaci z użyciem symboli
zdaniowych oraz funktorów zdaniotwórczych, z reguły nie sprawia nam
kłopotu jej zaklasyfikowanie, chociaż…
p
p
1
1
1
2
2
2
WYKŁAD 4
Przykład 2
Wyobraźmy sobie, że podczas pewnej kampanii wyborczej politycy
Olek, Józek i Kazik wygłosili następujące oświadczenia:
Olek: Józek kłamie.
Józek: Kazik kłamie.
Kazik: Olek kłamie.
Co z tego wynika? Spróbujmy zapisać te wypowiedzi w języku logiki,
oznaczając przez P
O
, P
J
, P
K
fakty, że Olek, Józek, i Kazik zawsze mówią
prawdę. Wtedy wypowiedzi powyższych prominentów mają postać:
Rozważmy hipotetyczną możliwość, że Olek rzeczywiście mówi
wyłącznie prawdę. Wtedy z pewnością Józek jest kłamcą, no i niestety,
musimy przyznać, że przynajmniej „pomylił się" Kazik. Podobne
rozumowanie możemy łatwo przeprowadzić dla każdej z tych osób, a
zatem tylko jeden z nich może mieć rację i być rzeczywiście
prawdomównym. Tylko nie wiemy który, jeśli w ogóle.
J
O
J
O
P
P
inaczej
P
P
K
J
K
J
P
P
inaczej
P
P
O
K
O
K
P
P
inaczej
P
P
Przykład 3
Badamy
metodą
zerojedynkową
, czy wyrażenie (p q) (p q) jest
tautologią.
Ponieważ w ostatniej kolumnie znajdują się same wartości 1
(odpowiadające prawdzie), więc powyższe wyrażenie jest tautologią.
Przykład 4:
Badamy metodą
zerojedynkową
, czy wyrażenie:
((p q) r) (((p r) (~q)) (~p)) jest tautologią.
p
q
p q
p q
(p q) (p q)
1
1
1
1
1
1
0
0
1
1
0
1
0
1
1
0
0
0
0
1
p q r
Całe
zdanie
1 1 1
1
1
0
1
0
1
0
0
1 1 0
1
0
0
1
0
1
0
1
1 0 1
0
0
0
0
1
1
0
1
0 1 1
1
1
1
0
0
0
0
0
0 0 1
1
1
1
1
1
1
1
1
0 1 0
1
0
1
0
0
0
0
1
1 0 0
0
0
0
0
1
1
0
1
0 0 0
1
0
1
1
1
1
1
1
q
p
r
q
p
)
(
p
q
p
q
)
(
)
(
q
q
p
)
(
))
(
)
((
p
q
q
p
SKRÓCONA METODA ZEROJEDYNKOWA
[(p q) ( p ~q) ] (~p q )
0
0
1
0
)
1
1
(
)
0
0
(
)]
1
1
(
)
0
1
[(
1
0
0
0
)
1
0
(
0
))
0
0
(
0
(
))
(
(
q
q
p
p
Sprawdź, które z podanych zdań są tautologiami, a które
kontrtautologiami:
q
q
p
p
q
p
q
p
q
p
q
p
q
p
p
q
q
p
q
p
q
p
q
p
q
p
q
p
q
p
q
p
)
(
)
8
)
(
)
7
)
(
)
(
)
6
)
(
)
(
)
5
)
(
)]
(
)
[(
)
4
)
(
)
(
)
3
)
(
)
(
)
2
)
(
)
(
)
1
Przedstaw poniższe zdania przy pomocy symboli zdaniowych i
funktorów oraz określ, czy są tautologiami.
1. Jeśli Jan nie zna logiki, to jeśli Jan zna logikę, to Jan urodził się w XVI
wieku.
2. Jeśli zwierzę latające jest ptakiem i nietoperz jest zwierzęciem latającym,
to nietoperz jest ptakiem.
3. Jeśli pies jest nieprzyjacielem kota, a kot jest nieprzyjacielem myszy, to
mysz jest przyjacielem psa.
4. Jeśli 20 < 10, to 20 < 100.
5. Jeśli 2 + 2 =5, to 2 + 4 = 6.
6. Jeśli dzisiaj jest środa , to jutro jest czwartek.
7. Jeżeli figura A jest czworokątem i A ma wszystkie kąty równe, to z faktu,
iż A jest czworokątem wynika, iż A ma kąty równe.
8. Jeżeli liczba a dzieli się przez 3 i dzieli się przez 5, to z faktu, iż nie dzieli
się przez 3 wynika, iż nie dziali się przez 5.
9. Jeżeli z faktu, iż funkcja f jest różniczkowalna w punkcie x
0
wynika, że
jest ona ciągła w punkcie x
0
, to z faktu, iż funkcja f jest ciągła w punkcie
x
0
wynika, iż jest ona różniczkowalna w punkcie x
0
.
10.Jeżeli 7 jest dzielnikiem 42, to 1 = 2.
11.Jeżeli 2 dzieli 8 i 3 dzieli 8, to 6 dzieli 8.
12.Jeżeli 2 dzieli 8 lub 3 dzieli 8, to 6 dzieli 8.
