JC WSEZ w A
odzi
Wykład 13
Treść wykładu
Klasyczny rachunek zdań
1) Pojęcie pełności funkcyjnej
2) Uwagi na temat notacji beznawiasowej
3) Spójniki ekstensjonalne vs. spójniki intensjonalne
1
JC WSEZ w A
odzi
Pełność funkcyjna
Pełność funkcyjna jest jedną z własności, które posiada
klasyczny rachunek zdań. Jej istota tkwi w ekstensjonalnym
charakterze spójników klasycznych, z których każdy jest
definiowalny przy użyciu tabelek prawdziwościowych.
Używając kilku wybranych spójników zdaniowych (w
pewnych przypadkach wystarcza tylko jeden taki spójnik),
możemy zdefiniować pozostałe spójniki prawdziwościowe
klasycznego rachunku zdań. Omawianą własność opisał,
jako jeden z pierwszych, niejaki Emil Post. Zbiory
spójników zapewniających funkcyjną pełność nazywamy są
klasami Posta.
W praktyce, nie rozważa się wszystkich klas Posta. Na
ogół, bierze się pod uwagę następujące zbiory:
1) negacji i alternatywy {~, ("}
2) negacji i koniunkcji {~, '"}
3) negacji i implikacji {~, }
4) negacja łączna { }
5) spójnik Sheffera {/}
Przy pomocy negacji i koniunkcji, w celu ilustracji
omawianego zagadnienia, scharakteryzujmy spójniki:
alternatywy, implikacji oraz równoważności.
2
JC WSEZ w A
odzi
Spójnik alternatywy charakteryzujemy:
ą (" � = <" (<" ą '" <" �).
Dlaczego właśnie w ten sposób rozumiemy alternatywę?
Odpowiedz
stanowi matryca:
ą � ą (" � <" ą <" � <" ą '" <" � <" (<" ą '" <" �)
1 1 1 0 0 0 1
1 0 1 0 1 0 1
0 1 1 1 0 0 1
0 0 0 1 1 1 0
Kolumny zaznaczone kolorem żółtym są identyczne (mają
dokładnie taką samą postać). Obydwa wyrażenia, tj. ą (" �
oraz <" (<" ą '" <" �), są więc równoważne na gruncie
semantyki klasycznego rachunku zdań.
Zbudujmy kolejne tabelki, tym razem dla:
ą � = <" (ą '" <" �)
ą "! � = <" (ą '" <" �) '" <" (<" ą '" �).
3
JC WSEZ w A
odzi
Matryca dla ą � = <" (ą '" <" �).
ą � ą � <" � ą '" <" � <" (ą '" <" �)
1 1 1 0 0 1
1 0 0 1 1 0
0 1 1 0 0 1
0 0 1 1 0 1
Matryca dla ą "! � = <" (ą '" <" �) '" <" (<" ą '" �).
<" (ą '" <" �)
ą � ą "! � <" ą <" � ą '" <" � <" (ą '" <" �) <" ą '" � <" (<" ą '" �) '"
<" (<" ą '" �)
1 1 1 0 0 0 1 0 1 1
1 0 0 0 1 1 0 0 1 0
0 1 0 1 0 0 1 1 0 0
0 0 1 1 1 0 1 0 1 1
Kolumny oznaczone kolorem żółtym mają dokładnie taką
samą postać.
4
JC WSEZ w A
odzi
Ciekawy przykład stanowi spójnik tzw. negacji łącznej
(zwanej także binegacją), który jako jeden z nielicznych
spójników klasycznych sam jeden wystarcza do
zdefiniowania wszystkich pozostałych spójników
klasycznych, tj. tworzy klasę Posta.
Spójnik negacji łącznej oznaczamy przez . Jest to spójnik
dwuargumentowy, który czytamy zwykle jako  ani ...,
ani .... . Na przykład w zdaniu Ani nie byłem w kinie, ani
nie byłem w teatrze mamy do czynienia (przy pewnej
interpretacji) właśnie z negacją łączną.
Tabelka prawdziwościowa dla negacji łącznej
ą � ą �
1 1 0
1 0 0
0 1 0
0 0 1
Negacja łączna jest prawdziwa tylko w jednym przypadku:
kiedy obydwa jej argumenty są zdaniami fałszywymi.
Scharakteryzujmy za pomocą negacji łącznej negację,
koniunkcję, alternatywę, implikację oraz równoważność.
5
JC WSEZ w A
odzi
Matryca dla <" ą = ą ą.
ą <" ą ą ą
1 0 0
0 1 1
Matryca dla ą '" � = (ą ą) (� �)
ą � ą '" � ą ą � � (ą ą) (� �)
1 1 1 0 0 1
1 0 0 0 1 0
0 1 0 1 0 0
0 0 0 1 1 0
Matryca dla ą (" � = (ą �) (� ą).
ą � ą (" � ą � � ą (ą �) (� ą)
1 1 1 0 0 1
1 0 1 0 0 1
0 1 1 0 0 1
0 0 0 1 1 0
6
JC WSEZ w A
odzi
Analogiczną własność posiada spójnik dysjunkcji (tzw.
kreska Sheffera), który podobnie jak negacja łączna, sam
jeden tworzy klasę Posta.
Dysjunkcję oznaczamy zwykle przez  / i czytamy  nie jest
prawdą, że zarówno ..., jaki i ... .
Tabelka prawdziwościowa dla dysjunkcja
ą � ą / �
1 1 0
1 0 1
0 1 1
0 0 1
Dysjunkcja jest prawdziwa wtedy, gdy co najmniej jeden z
jej argumentów jest zdaniem fałszywym. Dysjunkcja jest
fałszywa tylko w jednym przypadku: gdy obydwa jej
argumenty są zdaniami prawdziwymi.
Zdefiniujmy za pomocą kreski Sheffera spójniki: negacji,
alternatywy, implikacji oraz równoważności.
7
JC WSEZ w A
odzi
<" ą = ą / ą
ą '" � = (ą / �) / (ą / �)
ą (" � = (ą / ą) / (� / �)
ą � = ą / (� / �)
Matryca dla <" ą = ą / ą.
ą <" ą ą / ą
1 0 0
0 1 1
Matryca dla ą '" � = (ą / �) / (ą / �).
ą � ą '" � ą / � (ą / �) / (ą / �)
1 1 1 0 1
1 0 0 1 0
0 1 0 1 0
0 0 0 1 0
8
JC WSEZ w A
odzi
Notacja polska (beznawiasowa, A
ukasiewicza)
W podręcznikach do nauki logiki, szczególnie tych
starszych, można natknąć się na inny zapis spójników
klasycznych. Różnica może wyrażać się nie tylko w
zastosowaniu odmiennych symboli, ale również w składni
języka. Dobry przykład stanowi tzw. notacja polska, w
której nie ma potrzeby używania nawiasów oraz, co jest
bardziej istotne, symbol spójnika występuje zawsze przed
jego argumentami.
Ną to inny zapis negacji <" ą
�ą� to inny zapis koniunkcji ą '" �
Aą� to inny zapis alternatywy ą (" �
Cą� to inny zapis implikacji ą �
Eą� to inny zapis równoważności ą"! �
Przykładowo tzw. prawo niesprzeczności <" (<" p '" p)
zapiszemy w notacji polskiej: NKNpp, z kolei prawo
wyłączonego środka <" p (" p jako ANpp.
9
JC WSEZ w A
odzi
Spójniki ekstensjonalne. Spójniki intensjonalne
Spójniki ekstensjonalne (np. wszystkie spójniki
klasycznego rachunku zdań) są to takie spójniki,
których wartość logiczna zależy wyłącznie od
wartości logicznej argumentów tych spójników. Dla
przykładu, wartość logiczna zdania pq zależy
wyłącznie od wartości logicznej zdań:  p oraz  q .
Spójniki intensjonalne są to takie spójniki, których
wartość logiczna nie zależy wyłącznie od wartości
logicznej argumentów tych spójników, ale również od
denotacji (treści, itp.). Spójniki intensjonalne nie
występują w klasycznym rachunku zdań, występować
jednak mogą w jego rozszerzeniach.
Modalne spójniki intensjonalne:
 spójnik M rozumiany jako  możliwe, że ... . Zdanie
Możliwe, że zdam egzamin z logiki zawiera taki
właśnie spójnik
 spójnik L rozumiany jako  konieczne, że ... .
Zdanie Jest rzeczą konieczną, aby to zrobić zawiera
spójnik konieczności.
10
JC WSEZ w A
odzi
Powstaje pytanie: Czy spójniki modalne można opisać przy
użyciu tabelek zero-jedynkowych? Odpowiedz
jest
przecząca.
ą Mą
1 ?
0 ?
ą Lą
1 ?
0 ?
Przykłady innych spójników intensjonalnych:
 spójniki B rozumiany jako  wierzę, że ... (od
angielskiego zwrotu to believe that ...), spójnik K
rozumiany jako  wiem, że ... (z ang. to know ...)
 spójnik O rozumiany jako  jest obowiązkowe, żeby ... (z
ang. obligatory that ...)
 spójnik H rozumiany jako  zawsze było tak, że ... , G
 zawsze będzie tak, że ... , P  zdarzyło się tak, że ... , F
 zdarzy się tak, że ...
11