LOGIKA
wykład 4
V. Funktory – klasyczny rachunek zdań c.d.
VI. Klasyczny rachunek kwantyfikatorów
LOGIKA
wykład 4
V. Funktory – klasyczny rachunek zdań c.d.
VI. Klasyczny rachunek kwantyfikatorów
Język k.r.z. został skonstruowany w oparciu o niektóre tylko spośród
możliwych jedno- i dwuargumentowych funktorów ekstensjonalnych
(negacja, koniunkcja, alternatywa, implikacja i równoważność).
W tej sytuacji zasadnym wydaje się być następujące pytanie:
Czy pozostałe funktory ekstensjonalne dadzą się zdefiniować przy
pomocy funktorów z tego zestawu?
Odpowiedzią na to pytanie są następujące ustalenia:
V.3 Zastępowalność funktorów w języku
I.
Przy pomocy negacji i koniunkcji można zdefiniować wszystkie
pozostałe funktory. Posługując się znakiem jako znakiem
równoważności definicyjnej możemy sformułować następujące
definicje:
)
(
)
(
)
(
]
4
[
]
3
[
]
1
[
q
p
q
p
q
p
q
p
p
p
p
p
p
p
p
p
p
1
q
p
3
q
p
4
q
p
5
q
p
6
q
)]
(
)
(
[
)
(
/
)
(
)
(
q
p
q
p
q
p
q
p
q
p
q
p
q
p
q
p
q
p
q
p
p
p
q
p
p
q
p
q
p
11
q
p
12
q
p
13
q
p
16
q
Wszystkie funktory zdefiniowane w taki sposób przy pomocy negacji i
koniunkcji mają dokładnie taką samą charakterystykę prawdziwościową
jak wyrażenia wymienione po prawej stronie znaku .
q
)
(
q
p
p
)
(
p
p
Przykładowo porównując matryce wyrażeń: oraz
a
stwierdzamy, że są one identyczne.
Podobnie przedstawia się sprawa w pozostałych przypadkach.
q
p
)
(
q
p
WL(p) WL(q) WL(¬p) WL(¬q) WL(¬p ¬q) WL(¬(¬p ¬q) WL(p q)
0
0
1
1
1
0
0
0
1
1
0
0
1
1
1
0
0
1
0
1
1
1
1
0
0
0
1
1
II.
Przy pomocy funktorów negacji i alternatywy można zdefiniować
wszystkie pozostałe funktory ekstensjonalne.
Tym razem ograniczymy się do podania definicji najważniejszych
funktorów dwuargumentowych:
)
(
/
)]
(
)
(
[
)
(
q
p
q
p
q
p
q
p
q
p
q
p
q
p
q
p
q
p
q
p
q
p
III.
Przy pomocy funktorów negacji i implikacji można zdefiniować
wszystkie pozostałe funktory ekstensjonalne.
Definicje najważniejszych funktorów dwuargumentowych przedstawiają
się następująco:
)
(
/
)]
(
)
[(
)
(
q
p
q
p
q
p
q
p
p
q
q
p
q
p
q
p
q
p
q
p
q
p
Powyższe trzy ustalenia pozwalają na zastępowanie pewnych wyrażeń
innymi im równoważnymi na mocy przedstawionych definicji i nie
zawierającymi już pewnych funktorów.
W ten sposób można (teoretycznie rzecz ujmując) wyrugować z języka
pewne funktory ekstensjonalne na rzecz innych.
Ponieważ np. przy pomocy pary funktorów ( ) można zdefiniować
wszystkie inne funktory ekstensjonalne, to każda myśl wyrażona w
języku negacji, alternatywy, koniunkcji, implikacji i równoważności
może być wyrażona tylko przy użyciu negacji i implikacji.
,
Wyobraźmy sobie, że ktoś postanowił wykluczyć ze swojego języka koniunkcję,
alternatywę i równoważność i posiłkować się jedynie negacją i implikacją.
Jeśli ów ktoś stoi przed koniecznością wyrażenia prostej myśli w rodzaju:
Mieszkam w Kielcach i jestem nauczycielem i lubię muzykę,
to korzystając z tego, że wyrażenia k.r.z.: oraz
mają
identyczną charakterystykę prawdziwościową, mógłby wyrazić swoją myśl w taki
sposób:
Nieprawda, że jeżeli nieprawda, że jeżeli mieszkam w Kielcach, to nie jestem
nauczycielem, to nie lubię muzyki.
Drugie zdanie jest równoważne zdaniu pierwszemu, lecz trudno je uznać za
komunikatywne. Z tego powodu nie powinno się rezygnować z podstawowych
środków wyrazu języka naturalnego.
r
q
p
]
)
(
[
r
q
p
Wiemy już, że przy pomocy odpowiednio dobranych dwu funktorów
ekstensjonalnych można zdefiniować wszystkie pozostałe funktory.
Czy jednak istnieją takie funktory ekstensjonalne, które same są
wystarczające do zdefiniowania wszystkich pozostałych funktorów
ekstensjonalnych?
Zostało udowodnione, że istnieją dokładnie dwa funktory o tej
własności. Są nimi dysjunkcja i binegacja.
A.
Przy pomocy samej dysjunkcji można zdefiniować negację, koniunkcję i
alternatywę w taki sposób:
Wykorzystując te definicje oraz wcześniej przytoczone definicje
funktorów przy pomocy negacji i koniunkcji, możemy zdefiniować
dowolny funktor ekstensjonalny przy pomocy samej dysjunkcji.
)
/
(
/
)
/
(
)
/
(
/
)
/
(
/
q
p
p
p
q
p
q
p
q
p
q
p
p
p
p
B.
Z kolei przy pomocy samej binegacji można zdefiniować negację,
alternatywę i koniunkcję w następujący sposób:
Tym razem także wykorzystując te definicje oraz wcześniej przytoczone
definicje funktorów przy pomocy negacji i koniunkcji, możemy
zdefiniować dowolny funktor ekstensjonalny przy pomocy samej
binegacji.
)
(
)
(
)
(
)
(
q
p
p
p
q
p
q
p
q
p
q
p
p
p
p
Odnotujmy jednak, że definicje pozostałych funktorów przy pomocy
samej dysjunkcji, albo samej binegacji byłyby dosyć skomplikowane.
Przykładowo funktor implikacji może być zdefiniowany w następujący
sposób:
)
/
(
/
)]
/
(
/
)
/
[(
)
)
((
)
)
((
q
q
p
p
p
p
q
p
q
p
p
q
p
p
q
p
Każde zdanie złożone przy pomocy spójników zdaniowych ma swój
schemat będący pewnym wyrażeniem k.r.z. i odwrotnie, każde
wyrażenie k.r.z. jest schematem pewnych zdań złożonych.
O ile jednak każde zdanie ma dokładnie jeden schemat, to każde
wyrażenie k.r.z. jest schematem wielu różnych zdań.
Przykładowo zdanie:
Jeżeli będę miał pieniądze i będę miał ochotę, to kupię samochód
lub wyjadę na wycieczkę zagraniczną,
ma schemat:
.
)
(
)
(
s
r
q
p
V.4 Schemat zdania i wartościowanie
Schemat ten jest wyrażeniem k.r.z. Wyrażenie to może być jednak
różnie interpretowane w tym sensie, że za zmienne zdaniowe p, q, r, s
można podstawić różne zdania.
Inaczej mówiąc, wyrażenie to może być schematem różnych zdań,
choćby takich jak np.:
Jeżeli a ≤ b i b ≤ c, to a < c lub a = c.
Jeżeli pada deszcz i świeci słońce, to na niebie pojawia się tęcza lub
jest jasno.
Wartość logiczna każdego zdania złożonego jest jednoznacznie
wyznaczona przez wartości logiczne zdań składowych zgodnie z
matrycową charakterystyką funktorów, występujących w tym zdaniu.
Przykładowo zdanie:
Jeżeli Warszawa nie jest stolicą Polski i Jan nie był nigdy w Warszawie, to Jan
jest kawalerem i mieszka w Londynie
jest prawdziwe. Poprzednik tej implikacji jest fałszywy niezależnie od tego, czy Jan
był kiedykolwiek w Warszawie, czy też nie, gdyż jest on koniunkcją, której
przynajmniej jeden człon (tu akurat: Warszawa nie jest stolica Polski) jest fałszywy.
Zatem cała implikacja jest prawdziwa, jako implikacja o fałszywym poprzedniku. Na
wartość logiczną rozważanego zdania nie ma również wpływu ani stan cywilny Jana,
ani jego miejsce zamieszkania.
Wyrażenia k.r.z. nie są zdaniami, lecz schematami zdań.
W związku z tym nie można im (przynajmniej niektórym z nich!)
przypisać wartości logicznych, dopóki nie przyporządkujemy takich
wartości występującym w nich zmiennym zdaniowym.
Takie przyporządkowanie określonych wartości logicznych zmiennym
zdaniowym nazywamy wartościowaniem.
Liczba możliwych wartościowań jest zależna od liczby zmiennych
zdaniowych występujących w danym wyrażeniu i wynosi 2
n
dla n
zmiennych zdaniowych.
Rzeczywiście tak jest bowiem, odpowiednio dla:
•
jednej zmiennej zdaniowej p mamy dwie wartości: 0, 1
•
dwu zmiennych zdaniowych p i q mamy cztery pary wartości:
(0,0), (0,1), (1,0), (1, 1)
•
trzech zmiennych zdaniowych mamy osiem trójek:
(0,0,0), (0,0,1), (0,1,0), (0,1,1), (1,0,0), (1,0,1), (1,1,0), (1,1, 1))
•
itd.
Przy każdym z 2
n
wartościowań, wyrażenie k.r.z. o n zmiennych
zdaniowych przyjmuje jedną z dwóch wartości logicznych: prawdę (1)
lub fałsz (0).
Charakterystyczne dla danego wyrażenia k.r.z. przyporządkowanie
wartości logicznych poszczególnym wartościowaniom zmiennych
zdaniowych można opisać przy pomocy tabeli.
Przykładowo wyrażeniu odpowiada tabela:
q
q
p
)
(
WL(p)
WL(q)
WL(p q) WL(
¬
q)
WL((p q)
¬
q)
0
0
0
1
1
0
1
1
0
0
1
0
1
1
1
1
1
1
0
0
Ostatnia kolumna tej tabeli pokazuje, jakie wartości logiczne przyjmuje
wyrażenie: dla poszczególnych wartościowań zmiennych
zdaniowych p oraz q. Kolumna trzecia i czwarta tabeli służą pośrednio
do ustalenia wartości w kolumnie ostatniej.
Analogicznie dla wyrażenia: two-
rzymy tabelę:
q
q
p
)
(
)
(
)]
(
)
[(
r
p
r
q
q
p
p q r p
q q r
¬
p
¬
r
całość
0 0 0
1
1
1
1
1
1
1
0 0 1
1
1
1
1
0
0
0
0 1 0
1
0
0
1
1
1
1
1 0 0
0
1
0
0
1
1
1
0 1 1
1
1
1
1
0
0
0
1 0 1
0
1
0
0
0
1
1
1 1 0
1
0
0
0
1
1
1
1 1 1
1
1
1
0
0
1
1
)
(
)
(
r
q
q
p
r
p
Z tabeli tej widać, że rozważane wyrażenie jest fałszywe dla
wartościowań: (0,0,1) oraz (0,1,1) i prawdziwe dla pozostałych
wartościowań.
Zastanówmy się obecnie, czy istnieją wyrażenia k.r.z. prawdziwe dla
dowolnych wartościowań zmiennych zdaniowych.
Rozważmy wobec tego wyrażenie:
a
konstruując dla niego analogiczną tabelę, opisującą wszystkie przypo-
rządkowania wartości logicznych poszczególnym wartościowaniom
zmiennych zdaniowych.
)
(
)]
(
)
[(
r
q
r
p
q
p
p
q
r
p q
p r
q r
całość
0
0
0
0
1
1
0
1
0
0
1
0
1
1
0
1
0
1
0
0
1
0
0
1
1
0
0
0
0
1
0
1
0
1
1
0
1
1
0
1
1
0
1
0
1
1
0
1
1
1
0
1
0
0
0
1
1
1
1
1
1
1
1
1
)
(
)
(
r
p
q
p
Widoczne jest, że analizowane wyrażenie jest prawdziwe dla dowolnych
wartościowań jego zmiennych zdaniowych. Nie może być ono nigdy
fałszywe. Jakiekolwiek zdania wstawimy w miejsce jego zmiennych
zdaniowych, otrzymamy zdanie prawdziwe.
Wobec tego wyrażenie to jest schematem wyłącznie prawdziwych zdań.
Wyrażenia takie jak w ostatnim przykładzie spełniają bardzo ważną rolę
w logice. Jako schematy wyłącznie zdań prawdziwych zawdzięczają
swoją prawdziwość swojej strukturze formalnej i znaczeniu
występujących w nich stałych logicznych.
Terminy
pozalogiczne,
występujące
w
zdaniach
będących
podstawieniami takich schematów, nie mają wpływu na ich wartość
logiczną. Zdania takie są prawdziwe logicznie. Jako takie stanowią
podstawę niezawodnych rozumowań.
Celem k.r.z. jest określenie zbioru wszystkich wyrażeń o tej własności.
Wyrażenia takie nazywamy tautologiami klasycznego rachunku zdań.
V.5 Tautologie; metoda zero-jedynkowa
Pojęcie tautologii k.r.z. można zdefiniować dwojako:
•
Tautologią k.r.z. nazywamy każde wyrażenie tego rachunku, będące
schematem wyłącznie zdań prawdziwych.
•
Tautologią k.r.z. nazywamy każde wyrażenie tego rachunku, które jest
prawdziwe
przy
dowolnym
wartościowaniu
zmiennych
zdaniowych.
Definicje te są sobie równoważne w świetle naszych wcześniejszych
rozważań.
Tautologie k.r.z. nazywane są też prawami k.r.z.
Przy pomocy tabeli, takich jak konstruowane poprzednio, można
rozstrzygnąć, czy dowolne wyrażenie k.r.z. jest, czy też nie jest
tautologią.
Zgodnie z tym powiemy, że zagadnienie opisane pytaniem o to, czy
dane wyrażenie jest tautologią k.r.z., jest zagadnieniem rozstrzygalnym.
Mówi się też, że k.r.z. jest teorią rozstrzygalną.
Zaprezentowana metoda rozstrzygania o tautologiczności (czy nietauto-
logiczności) wyrażeń k.r.z. nazywa się metodą zero-jedynkową.
P R Z Y K Ł A D
Rozstrzygnięcie, czy wyrażenie jest tautologią k.r.z.:
wymagałoby rozważenia 32 (
= 2
5
) różnych wartościowań i ustalenia,
poprzez wykonanie całkiem sporej liczby kroków pośrednich, jaką
wartość logiczną przyjmuje to wyrażenie przy każdym z nich.
Takie postępowanie byłoby dość czasochłonne.
Okazuje się, że pewna doza pomysłowości pozwoli w znacznym stopniu
skrócić procedurę, prowadzącą do rozstrzygnięcia czy wyrażenie to jest
tautologią.
)))]
(
(
(
[
)
(
t
s
r
q
p
t
s
r
q
p
Wyrażenie to jest implikacją o poprzedniku: i następ-
niku: Jako takie byłoby ono fałszywe, gdyby
poprzednik był prawdziwy, a następnik fałszywy.
Konieczny warunek jego fałszywości opisuje zatem metajęzykowe
wyrażenie: WL( ) = 1 i WL( )
= 0.
Ponieważ następnik jest wielokrotną implikacją, jego fałszywość
oznacza, że WL(p) = WL(q) = WL(r) = WL(s) = 1 i WL(t) = 0.
Jednak przy takim wartościowaniu poprzednik: jest
fałszywy, czyli cała implikacja jest prawdziwa.
t
s
r
q
p
))).
(
(
(
t
s
r
q
p
t
s
r
q
p
)))
(
(
(
t
s
r
q
p
t
s
r
q
p
Okazuje się zatem, że w jedynym przypadku, w którym rozważane
wyrażenie mogłoby być fałszywe, jest ono jednak prawdziwe.
Przy pozostałych 31 wartościowaniach jest ono na pewno prawdziwe,
albowiem
następnik
jest
prawdziwy,
a
jak już
wiemy, implikacja o prawdziwym następniku jest prawdziwa.
Wobec przeprowadzonego rozumowania stwierdzamy, że rozważane
wyrażenie jest prawdziwe przy dowolnych wartościowaniach
zmiennych zdaniowych, jest więc ono tautologią k.r.z.
)))
(
(
(
t
s
r
q
p
Ć W I C Z E N I E :
Zweryfikować, czy następujące wyrażenia:
a)
b)
c)
d)
e)
są tautologiami k.r.z.
Stosować zarówno metodę zero-jedynkową, jak i skróconą metodę zero-jedynkową.
))]
(
(
)
[(
)]
(
[
s
t
p
q
t
s
q
p
)))]
(
(
(
[
)))]
(
(
(
[
p
s
r
q
t
t
s
r
q
p
))]
(
)
((
[
)))]
(
(
(
[
t
s
r
q
p
t
s
r
q
p
))]
(
(
)
[(
)
(
s
q
p
s
p
q
p
)]
(
)
[(
)
(
r
p
r
q
q
p
Zbiór tautologii k.r.z. jest zbiorem nieskończonym, inaczej mówiąc,
istnieje nieskończenie wiele tautologii k.r.z.
Spośród mnogości tautologii jedynie niektóre z nich są na tyle
powszechnie stosowane, że przyjęło się stosować dla nich pewne
ustalone nazwy.
Oto wykaz niektórych podstawowych tautologii k.r.z. (w nawiasach
umieszczone są przyjęte nazwy części z nich):
1.
(
prawo tożsamości
)
2.
(
prawo wyłączonego środka
)
3.
(
prawo niesprzeczności
)
4.
(
prawo podwójnej negacji
)
5.
(
prawo idempotencji dla koniunkcji
)
6.
(
prawo idempotencji dla alternatywy
)
7.
(
pierwsze prawo redukcji do absurdu
)
8.
9.
(
prawo przemienności koniunkcji
)
10.
(
prawo przemienności alternatywy
)
p
p
p
p
)
(
p
p
p
p
)
(
p
p
p
)
(
p
p
p
p
p
p
)
(
p
p
p
)
(
)
(
)
(
p
q
q
p
)
(
)
(
p
q
q
p
(!)
(!)
(!)
(!)
(!)
(!)
(!)
(!)
11.
(
prawo przemienności równoważności
)
12.
13.
14.
15.
16.
(
paradoks implikacji
)
17.
(
paradoks implikacji
)
18.
(
prawo poprzedzania
)
19.
(
prawo przepełnienia
)
20.
(
modus ponens
)
)
(
)
(
p
q
q
p
)
(
q
p
p
)
(
q
p
q
p
q
p
)
(
q
q
p
)
(
)
(
)
(
p
q
q
p
)
(
q
p
p
)
(
p
q
p
)
(
q
p
p
q
q
p
p
)]
(
[
(!)
(!)
(!)
(!)
(!)
(!)
21.
(
modus tollens
)
22.
(
prawo Dunsa Scotta
)
23.
(
słaby dylemat destrukcyjny
)
24.
(
dylemat konstrukcyjny
)
25.
(
prawo Pierce’a
)
26.
(
prawo transpozycji
)
27.
28.
29.
30.
(
mocny dylemat konstrukcyjny
)
p
q
q
p
]
)
[(
)
(
q
p
p
]
)
[(
)
(
p
q
p
q
p
]
)
[(
)
(
q
q
p
q
p
p
p
q
p
]
)
[(
(!)
(!)
(!)
)
(
)
(
p
q
q
p
)
(
)
(
q
p
q
p
)
(
)
(
p
q
q
p
)]
(
[(
)
(
q
p
p
q
q
p
]
)
[(
)
(
p
q
p
q
p
31.
(
prawo przechodniości implikacji, prawo sylogizmu hipotetycznego
)
32.
(
sylogizm Fregego
)
33.
34.
(
prawo de Morgana
)
35.
(
prawo de Morgana
)
36.
(
prawo zaprzeczenia implikacji
)
37.
(
prawo zaprzeczenia równoważności
)
38.
)]
(
)
[(
)
(
r
p
r
q
q
p
)]
(
)
[(
)]
(
[
r
p
q
p
r
q
p
)
(
q
q
p
)
(
)
(
q
p
q
p
)
(
)
(
q
p
q
p
(!)
(!)
(!)
(!)
)
(
)
(
q
p
q
p
)]
(
)
(
[
)
(
p
q
q
p
q
p
)
(
q
q
p
39.
40.
41.
42.
43.
44.
45.
(
prawo komutacji
)
46.
(
prawo eksportacji
)
47.
(
prawo transpozycji złożonej
)
)
(
)
(
q
p
q
p
)
(
)
(
q
p
q
p
)
(
)
(
q
p
q
p
)
(
)
(
q
p
q
p
)
(
)
(
q
p
q
p
)
(
)
(
q
p
q
p
(!)
(!)
(!)
(!)
(!)
(!)
)]
(
[
)]
(
[
r
p
q
r
q
p
)]
)
[(
)]
(
[
r
q
p
r
q
p
)]
)
[(
)]
)
[(
q
r
p
r
q
p
48.
(
koniunkcyjne prawo sylogizmu hipotetycznego
)
49.
(
prawo łączności koniunkcji
)
50.
(
prawo łączności alternatywy
)
51.
(
prawo rozdzielności koniunkcji względem alternatywy
)
52.
(
prawo rozdzielności alternatywy względem koniunkcji
)
53.
54.
)
(
)]
(
)
[(
r
p
r
q
q
p
))
(
(
))
)
((
r
q
p
r
q
p
))
(
(
))
)
((
r
q
p
r
q
p
(!)
(!)
(!)
))
(
)
((
))
(
(
r
p
q
p
r
q
p
(!)
(!)
))
(
)
((
))
(
(
r
p
q
p
r
q
p
p
q
p
p
))
(
(
p
q
p
p
))
(
(
Ć W I C Z E N I E :
Spośród podanych właśnie wyrażeń wybrać kilka i wykazać, że są one
tautologiami k.r.z.
Stosować zarówno metodę zero-jedynkową, jak i skróconą metodę zero-
jedynkową.
Jak już wiemy, metoda zero-jedynkowa (w wersji pełnej czy skróconej)
pozwala w sposób efektywny rozstrzygnąć, czy dowolna formuła języka
k.r.z. jest czy też nie jest tautologią.
Ta sama metoda pozwala również efektywnie rozstrzygnąć, czy między
formułami języka k.r.z. zachodzi pewien ważny, z logicznego punktu
widzenia, związek zwany konsekwencją logiczną.
Załóżmy, że
X
jest zbiorem formuł języka k.r.z., a
α
pewną pojedynczą
formułą tego języka.
V.6 Konsekwencja logiczna
w języku rachunku zdań
Mówimy wówczas, że między zbiorem
X
a formułą
α
zachodzi relacja
konsekwencji, lub inaczej, że
α
jest konsekwencją
X
(symbolicznie:
X
╞
α
), gdy dla dowolnego wartościowania zmiennych zdaniowych
wartość logiczna formuły
α
jest równa 1, o ile wartość logiczna
wszystkich formuł ze zbioru
X
jest, przy tym wartościowaniu również
równa 1.
Podane określenie relacji ╞
jest sprecyzowaniem takiego (zgodnego
zresztą z intuicją) rozumienia konsekwencji, że istota konsekwencji
polega na „dziedziczeniu” prawdziwości danego zdania ze zbioru zdań,
których jest ono konsekwencją.
P R Z Y K Ł A D A
Załóżmy, że
i zastanówmy się, czy
α
jest konsekwencją
X, czyli czy:
╞
Definicja relacji konsekwencji pozwala odpowiedzieć na to pytanie przy
pomocy procedury, dającej się opisać następującą tabelą:
},
,
,
{
q
p
r
q
q
p
X
.
}
,
,
{
r
q
q
p
r
q
q
p
r
q
p
q
r
0
0
0
1
1
0
0
0
0
1
1
1
0
0
0
1
0
1
0
1
0
0
1
1
1
1
1
1
1
0
0
0
1
1
0
1
0
1
0
1
1
0
1
1
0
1
0
1
0
1
1
1
1
1
1
1
q
p
r
q
q
p
r
q
Analiza tabeli wskazuje, że wartościowaniami, przy których wszystkie
formuły ze zbioru
X
są prawdziwe, są: (1,1,1) i (0,1,1).
Jednak przy tych wartościowaniach formuła
jest także prawdziwa.
Zatem
α
jest konsekwencją
X
.
P R Z Y K Ł A D B
Zweryfikujmy, czy:
╞
Z tabeli, odpowiadającej temu przypadkowi:
r
q
.
}
,
{
p
r
r
q
q
p
p
q
r
0
0
0
1
1
1
0
0
1
1
1
1
0
1
0
1
0
1
0
1
1
1
1
1
1
0
0
0
1
0
1
0
1
0
1
1
1
1
0
1
0
0
1
1
1
1
1
1
q
p
r
q
p
r
łatwo odczytujemy, że badana relacja konsekwencji zachodzi.
Dzieje się tak, albowiem dla wszystkich wartościowań, przy których
formuły przyjmują wartości 1 (
a są to wartościowania:
(1,1,1), (0,1,1), (0,0,1), (0,0,0)
), formuła: również jest
prawdziwa.
P R Z Y K Ł A D C
Chcąc zweryfikować, czy
╞ załóżmy (nie
wprost), że tak nie jest, co oznacza, że istnieje takie wartościowanie
zmiennych zdaniowych, dla którego:
r
q
q
p
,
p
r
p
r
r
q
q
p
}
,
{
1) WL(p q) = 1 i 2) WL(q r) = 1 i 3) WL(¬r ¬p) = 0.
Z 3) wnioskujemy, że – przy tym wartościowaniu – 4) WL(p) = 1 i
5) WL(r) = 0. Z 1) i 4) wnioskujemy, że 6) WL(q) = 1, a z 6) i 5), że
7) WL(q r) = 0.
Otrzymana sprzeczność między 2) i 7) dowodzi, że założenie (nie
wprost) nie może być prawdziwe. Zatem badany związek zachodzi.
Ć W I C Z E N I E
Zbadać tak metodą zero-jedynkową, jak i przyjmując założenie nie
wprost, czy:
╞
.
}
)
(
,
)
(
,
{
s
q
r
p
s
r
q
q
p
Z przyjętych definicji pojęć tautologii oraz relacji konsekwencji wynika,
że dowolna formuła
α
jest tautologią k.r.z. (symbolicznie: ╞
α
) wtedy i
tylko wtedy, gdy
α
jest konsekwencją zbioru pustego ( ):
╞
α
wtedy i tylko wtedy, gdy ╞
α
.
Z definicji tych oraz z charakterystyki prawdziwościowej funktora
implikacji wynikają dodatkowo następujące zależności:
(Z1)
{
α
} ╞ β
wtedy i tylko wtedy, gdy ╞ (
α β
)
(Z2)
{
α
, β
}
╞ γ
wtedy i tylko wtedy gdy
{
α
} ╞ (
β γ
)
(Z3)
{
α
, β
}
╞ γ
wtedy i tylko wtedy gdy ╞ [
(
α (
β γ
)
]
oraz zależności ogólne:
(Z4)
{
α
1
, α
2
, ... , α
n
} ╞ β
wtedy i tylko wtedy, gdy
{
α
1
, α
2
, ... , α
n
–
1
} ╞ (
α
n
β
)
(Z5)
{
α
1
, α
2
, ... , α
n
} ╞ β
wtedy i tylko wtedy gdy
╞ (
α
1
(
α
2
... (
α
n
β
)
...
)
)
Widoczne jest, że zależności
(Z1)
i
(Z2)
są szczególnymi przypadkami
(Z4)
, natomiast
(Z3)
i
(Z5)
można otrzymać przez wielokrotne
zastosowanie
(Z4)
.
Odnotujmy, że zależność
(Z4)
jest szczególnym przypadkiem
zależności:
(TD)
╞ wtedy i tylko wtedy, gdy X ╞ (
α β
)
gdzie X oznacza dowolny (niekoniecznie skończony!) zbiór formuł
języka k.r.z.
Ta ostatnia zależność nazywana jest twierdzeniem o dedukcji dla
relacji konsekwencji ╞
.
}
{
X
VI. Klasyczny rachunek
kwantyfikatorów
Wyrażenia k.r.z. nie odzwierciedlają dostatecznie głęboko struktury
niektórych zdań języka potocznego.
Na przykład schematem zdania: Wszyscy ludzie są śmiertelni, a
niektórzy umierają młodo jest w k.r.z. wyrażenie: zaś zdania:
Wszyscy ludzie są śmiertelni oraz Niektórzy umierają młodo są tu
traktowane jako zdania proste.
Ich wewnętrzna struktura nie może być odzwierciedlona w języku k.r.z.,
a wynika to z faktu, że nie wszystkie stałe logiczne należą do leksykonu
języka k.r.z. Nie należą bowiem do niego wyrażenia kwantyfikatorowe:
wszyscy (dla każdego, dla wszystkich, każdy, wszystkie, dla dowolnego
VI.1 Tautologie rachunku kwantyfikatorów
,
q
p
itp.) oraz niektórzy (dla niektórych, dla pewnego, niektóre, istnieją takie
..., że ... itp.).
Włączenie tych stałych logicznych w całościowy system teoretyczny,
ujmujący ogół prawd logicznych o strukturze dającej się wyartykułować
w języku funktorów prawdziwościowych oraz kwantyfikatorów, stwarza
możliwość jeszcze bardziej pogłębionej analizy naszego myślenia.
W takim wzbogaconym języku strukturę rozważanego zdania
odzwierciedla wyrażenie:
.
)
(
)
(
x
Q
x
P
x
x
Systemem logicznym, służącym realizacji tak określonego celu, jest
klasyczny rachunek kwantyfikatorów (w skrócie k.r.k.).
Omówienie k.r.k. rozpoczniemy od prezentacji języka.
Do leksykonu języka k.r.k. należą następujące symbole:
1)
symbole stałych logicznych:
gdzie pierwszych pięć symboli to symbole klasycznych funktorów
prawdziwościowych, natomiast i są symbolami kwantyfi-
katorów odpowiednio ogólnego i szczegółowego;
,
,
,
,
,
,
,
2)
zmienne indywiduowe (albo zmienne nazwowe):
x, y, z, ... ,
reprezentujące przedmioty dowolnego rodzaju;
3)
stałe indywiduowe (albo stałe nazwowe):
a, b, c, ... ,
reprezentujące ustalone przedmioty rodzaju;
4)
zmienne predykatywne:
P, Q, R, S, ... ,
które są symbolami własności lub relacji.
5)
nawiasy: (, ), [, ],{, }.
Przy pomocy tych symboli konstruujemy poprawnie sformułowane
wyrażenia k.r.k.
Pomijamy jednak podanie ścisłej definicji kategorii: wyrażenie
poprawnie zbudowane k.r.k., a poprzestaniemy jedynie na podaniu
przykładów takich wyrażeń w konkretnych zastosowaniach.
Bowiem dzięki temu stanie się intuicyjnie jasne, jakie ciągi napisów są
poprawnie sformułowanymi wyrażeniami k.r.k.
Zatem przykładami wyrażeń k.r.k. są następujące ciągi napisów:
,
)
,
(
,
)
,
(
,
)
,
(
,
)
,
(
,
)
,
(
,
)
(
,
)
(
y
x
R
y
x
R
b
x
R
y
a
R
y
x
R
a
P
x
P
y
x
x
,
))
,
(
)
(
(
,
))
(
)
(
(
,
)
,
(
)
(
y
x
R
x
P
x
Q
x
P
y
x
R
x
P
y
x
x
W zbiorze wyrażeń poprawnie zbudowanych k.r.k. możemy wyróżnić
wyrażenia będące funkcjami zdaniowymi.
Przypomnijmy, że funkcją zdaniową nazywamy wyrażenie posiadające
zmienną wolną.
Przykładami funkcji zdaniowych w języku k.r.k. są:
W pierwszym wyrażeniu zmienną wolną jest x, w drugim y. W trzecim wyrażeniu
itp.
)]
(
)
(
[
))
(
)
(
(
x
Q
x
P
x
Q
x
P
x
x
x
,
)
,
(
]
))
(
)
(
(
[
,
)
,
(
,
)
,
(
,
)
(
c
x
R
y
Q
x
P
y
x
R
y
a
R
x
P
x
x
itp.
)
(
)]
,
(
)
(
[
z
Q
y
x
R
x
P
x
y
zmienną wolną jest y, zaś x jest zmienną związaną kwantyfikatorem ogólnym.
W wyrażeniu czwartym zmienną wolną jest x występujące w następniku
R(x,
c), a zmienna x występująca w poprzedniku jest związana kwantyfika-
torem ogólnym. W wyrażeniu piątym zmienną wolną jest z. Zmienna x jest
związana kwantyfikatorem ogólnym, a y – kwantyfikatorem szczegółowym.
Wszystkie wymienione wyrażenia są funkcjami zdaniowymi, ponieważ
posiadają zmienne wolne.
Dla odmiany wyrażenia:
nie są funkcjami zdaniowymi. (
Wszystkie bowiem występujące w nich zmienne
indywiduowe są związane jakimś kwantyfikatorem.)
,
)
(
))
(
)
(
(
,
)
,
(
,
)
,
(
,
)
,
(
,
)
(
a
P
x
Q
x
P
y
c
R
b
x
R
b
a
R
a
P
x
y
x
)
,
,
(
))
(
)
(
[(
,
)]
,
(
)
(
[
z
y
x
S
y
Q
x
P
y
x
R
x
P
z
y
x
y
x
Jeżeli jakaś funkcja zdaniowa k.r.k. jest schematem pewnego wyrażenia
w języku potocznym, to wyrażenie to jest również funkcją zdaniową, a
nie wyrażającym jakąś zamkniętą myśl zdaniem.
Przykładowo:
•
Funkcja zdaniowa
P(x)
jest schematem wyrażeń:
x jest miastem wojewódzkim
x jest studentem
x jest równoległobokiem itp.
•
Funkcja zdaniowa
R(x,
y)
jest schematem wyrażeń:
x jest ojcem y
x jest prostopadle do
y
x jest starszy od
y
itp.
•
Funkcja zdaniowa jest schematem wyrażeń:
Jeżeli
x
jest ojcem Jana, to
x
jest starszy od Jana
Jeżeli
x
jest dłużnikiem Pawła, to
x
unika Pawła
Jeżeli
x
jest dzielnikiem 15, to
x
< 15 itp.
•
Funkcja zdaniowa jest schematem wyrażeń:
Istnieje ktoś, kto jest ojcem
y
Niektórzy kochają się w
y
Istnieją proste prostopadle do prostej
y itp.
)
,
(
)
,
(
a
x
S
a
x
R
)
,
(
y
x
R
x
Istnieją dwa sposoby przekształcania funkcji zdaniowych w zdania:
1)
podstawienie stałych nazwowych w miejsce zmiennych wolnych,
/ K O N K R E T Y Z A C J A /
2)
związanie zmiennych wolnych jakimiś kwantyfikatorami.
/ K W A N T Y F I K A C J A /
Każde wyrażenie języka naturalnego ma swoją strukturę wyrażalną w
języku k.r.k. Wobec tego dowolnemu takiemu wyrażeniu możemy
przyporządkować jego schemat w języku k.r.k.
Podajmy dla wybranych zdań z języka potocznego przykłady takich
schematów:
Zdanie: Wszystko ma swoją przyczyną
ma schemat:
Schematem zdania: Niektórzy filozofowie są logikami
jest:
Zdanie: Wszyscy mężczyźni z Zakładu kochają się w pani Joli
ma schemat:
Zdanie: Wszyscy mężczyźni są egoistami
ma schemat:
Zdanie: Niektóre mężatki są wierne
ma schemat:
)
,
(
y
x
R
y
x
)]
(
)
(
[
x
Q
x
P
x
)]
,
(
)
(
[
a
x
R
x
P
x
)]
(
)
(
[
x
Q
x
P
x
)]
(
)
(
[
x
Q
x
P
x
Schematem zdania: Niektóre mężatki nie mają przyjaciół
jest:
Zdanie: Nikt nie jest wyższy od samego siebie
ma schemat:
Zdanie: Nikt nie podziwia wszystkich
ma schemat:
Zdanie: Niektórzy żałują wszystkiego, co robią
ma schemat:
Zdanie: Niektórzy humaniści gardzą wszystkimi matematykami
ma schemat:
)]
,
(
)
(
[
y
x
R
x
P
y
x
)
,
(
x
x
R
x
)]
,
(
[
y
x
R
y
x
)]
,
(
)
,
(
[
y
x
S
y
x
R
y
x
))]
,
(
)
(
(
)
(
[
y
x
R
y
Q
x
P
y
x
Schematem zdania: Niektórzy podziwiają swoich prześladowców
jest:
Zdanie: Każdy student tańczył z jakąś studentką
ma schemat:
Zdanie: Żadna szanująca się kobieta nie flirtuje z nieznajomymi mężczyznami
ma schemat:
Wyrażenia k.r.k. mogą być schematami wielu różnych zdań języka
naturalnego.
))]
,
(
)
,
(
[
y
x
S
y
x
R
y
x
))]
,
(
)
(
(
)
(
[
y
x
R
y
Q
x
P
y
x
))]
,
(
)
,
(
(
)
(
[
y
x
R
y
x
S
x
P
y
x
Na przykład ostatnie wyrażenie jest także schematem zdań:
Żadna liczba naturalna nie dzieli się przez liczbę, która nie jest jej kwadratem.
Żaden wykładowca nie zaliczy egzaminu studentom, którzy nie uczęszczali na jego
wykłady itp.
Może się zdarzyć, że pewne wyrażenia k.r.k. są schematami zarówno
zdań prawdziwych, jak i fałszywych.
Np. wyrażenie:
jest schematem prawdziwego zdania: Każdy nauczyciel jest człowiekiem
oraz fałszywego: Każda liczba parzysta jest podzielna przez 3
)]
(
)
(
[
x
Q
x
P
x
Wyrażenie:
jest schematem zdania prawdziwego: Każdy ma ojca
oraz fałszywego: Każdy ma żonę.
Wyrażenie:
jest schematem zdania prawdziwego: Niektóre studentki mają dzieci
i fałszywego: Niektóre koty mają partnera do gry w pokera.
Wyrażenie:
jest schematem zdania prawdziwego:
Jeżeli istnieją ludzie, którzy są mordercami, to istnieją ludzie, którzy nie są
mordercami
i fałszywego:
Jeżeli istnieją ludzie śmiertelni, to istnieją ludzie nieśmiertelni
)
,
(
y
x
R
y
x
)]
,
(
)
(
[
y
x
R
x
P
y
x
)
(
)
(
x
P
x
P
y
x
Wyrażenie:
jest schematem prawdziwego zdania:
Jeżeli istnieją figury, które są prostokątami i istnieją figury, które są
p
rombami, to istnieją figury, które są prostokątami i rombami
oraz fałszywego:
Jeżeli istnieją ludzie młodzi i istnieją, ludzie starzy, to istnieją ludzie, którzy
są jednocześnie młodzi i starzy
Rodzi się naturalne pytanie, czy wszystkie wyrażenia k.r.z. mogą być
schematem zarówno prawdziwych, jak i fałszywych zdań.
)]
(
)
(
[
)]
(
)
(
[
x
Q
x
P
x
Q
x
P
x
x
x
Spróbujmy znaleźć dwa zdania – jedno prawdziwe i jedno fałszywe,
których schematem jest wyrażenie:
Prawdziwym zdaniem o tym schemacie jest np.:
Jeżeli istnieją ludzie, którzy grają na skrzypcach i lubią logikę, to
istnieją ludzie, którzy grają na skrzypcach i istnieją ludzie, którzy
lubią logikę.
Jednak znalezienie zdania fałszywego o tym schemacie napotyka na
trudności.
)]
(
)
(
[
)]
(
)
(
[
x
Q
x
P
x
Q
x
P
x
x
x
W jakiejkolwiek bowiem dziedzinie rzeczywistości próbujemy
zinterpretować ten schemat, nasza interpretacja okazuje się prawdziwa.
Czy przyczyną tego jest nasza nieumiejętność znalezienia właściwej
kontrinterpretacji? A może takiej kontrinterpretacji po prostu nie ma?
Przeanalizujmy ten przypadek w sposób całkowicie ogólny.
Rozważane wyrażenie jest implikacją o poprzedniku i
następniku . Mogłoby ono być fałszywe jedynie w
przypadku, gdyby poprzednik był prawdziwy, a następnik fałszywy.
Załóżmy więc, że poprzednik jest prawdziwy. Oznacza to, że istnieje
(przynajmniej jeden) obiekt, który ma zarazem obie własności P oraz Q.
)]
(
)
(
[
x
Q
x
P
x
)]
(
)
(
[
x
Q
x
P
x
x
Zatem ów obiekt posiada na pewno własność P. Jeżeli tak, to istnieje
obiekt posiadający własność P (
właśnie ten, który ma obie te własności
) i
wyrażenie jest prawdziwe. Analogicznie sposób wykazujemy,
że wyrażenie: jest prawdziwe.
To zaś z kolei oznacza, że koniunkcja jest także
prawdziwa.
Wobec tego implikacja nie
może być fałszywa. Jest więc ona zawsze prawdziwa.
Rozważane wyrażenie nie może być schematem żadnego zdania
fałszywego – jest ono schematem wyłącznie zdań prawdziwych.
)
(x
P
x
)
(x
Q
x
)
(
)
(
x
Q
x
P
x
x
)]
(
)
(
[
)]
(
)
(
[
x
Q
x
P
x
Q
x
P
x
x
x
Dziękuję za uwagę!