Podstawy logiki i teorii mnogości Ćwiczenie 2
---------------------------------------------------------------------------------------------------------------------------------------
– 1 –
ĆWICZENIE 2
Klasyczny Rachunek Zdań (KRZ): wynikanie logiczne, wnioskowanie, niezawodny
schemat wnioskowania, wnioskowanie dedukcyjne, równoważność logiczna, definiowalność
spójników za pomocą formuły.
DEF. Mówimy, że formuła A
wynika logicznie
z formuł
n
A
A
,
,
1
K
w KRZ, jeżeli nie istnieje
wartościowanie w, takie że
(((( ))))
(((( ))))
1
1
=
==
=
=
==
=
=
==
=
n
A
w
A
w
K
i
(((( ))))
0
=
==
=
A
w
.
FAKT. Formuła A wynika logicznie z formuł
n
A
A
,
,
1
K
w KRZ wtedy i tylko wtedy, gdy
A
A
A
n
→
→
→
→
∧
∧
∧
∧
∧
∧
∧
∧
K
1
jest tautologią KRZ
Tautologie implikacyjne
Prawo odrywania
(
)
p
q
p
q
→
∧ →
Prawo odrzucania
(
)
p
q
q
p
→
∧ ¬ → ¬
Prawo sylogizmu hipotetycznego
(
) (
) (
)
p
q
q
r
p
r
→
∧
→
→
→
Prawa symplifikacji
p
q
p
∧ →
p
q
q
∧ →
Prawo koniunkcji
(
)
p
q
p
q
→
→
∧
Przykłady .
Prawo sylogizmu warunkowego:
(
) (
) (
)
p
q
q
r
p
r
→
∧
→
→
→
.
Zatem p
r
→ wynika z
q
p →
→
→
→ ,
r
q →
→
→
→ .
Prawo odrywania:
(
)
p
q
p
q
→
∧ → .
Zatem q wynika z p
q
→ , p.
Podstawy logiki i teorii mnogości Ćwiczenie 2
---------------------------------------------------------------------------------------------------------------------------------------
– 2 –
DEF. Wnioskowaniem nazywamy układ zdań, z których jedno jest wyróżnione jako
wniosek, a pozostałe są przesłankami. W KRZ schematy wnioskowań zapisujemy w postaci
A
A
A
n
,
,
1
K
albo
A
A
A
n
M
1
gdzie formuły
n
A
A
,
,
1
K
nazywamy
przesłankami
a formułę A
wnioskiem
tego schematu.
DEF. Schemat wnioskowania nazywamy
niezawodnym,
jeżeli wniosek wynika logicznie z
przesłanek w KRZ. Niezawodne schematy wnioskowania nazywamy też
logicznymi regułami
wnioskowania
KRZ.
TW. O podstawianiu w niezawodnych schematach wnioskowania
Jeżeli schemat wnioskowania W jest niezawodny, to schemat W ′′′′ powstający z W przez
podstawienie za wszystkie wystąpienia pewnej zmiennej zdaniowej dowolnej formuły jest
niezawodny w KRZ.
DEF. Wnioskowanie nazywamy
dedukcyjnym
, jeżeli jego schemat jest niezawodny.
Podstawy logiki i teorii mnogości Ćwiczenie 2
---------------------------------------------------------------------------------------------------------------------------------------
– 3 –
Logiczne reguły wnioskowania
1. Reguła sylogizmu warunkowego
p
q q
r
p
r
→
→
→
,
2.Reguła odrywania (modus ponens)
p p
q
q
,
→
3. Reguła odrzucania (modus tollens)
p
q
q
p
→
¬
¬
,
4. Reguła dylematu
p
q p
r q
r
r
∨
→
→
,
,
5.Reguły opuszczania koniunkcji
p
q
p
∧
p
q
q
∧
6. Reguła wprowadzania koniunkcji
p q
p
q
,
∧
7. Reguły wprowadzania alternatywy
α
α β
∨
β
α β
∨
8. Reguła wprowadzania równoważności
p
q
q
p
p
q
→
→
↔
,
Podstawy logiki i teorii mnogości Ćwiczenie 2
---------------------------------------------------------------------------------------------------------------------------------------
– 4 –
DEF.
Mówimy, że formuła A jest
równoważna logicznie
formule B w KRZ, jeżeli
(((( )))) (((( ))))
B
w
A
w
=
==
=
dla każdego wartościowania w.
FAKT .
Formuła A jest równoważna formule B w KRZ wtedy i tylko wtedy, gdy formuła
A
B
↔
jest tautologią KRZ.
TW. O równoważności.
Jeżeli formuły
A i B są równoważne w KRZ, a formuła
C
′′′′
powstaje z
C przez zastąpienie
niektórych wystąpień formuły
A formuła B, to formuły C i
C
′′′′
są równoważne logicznie w
KRZ.
Rozważane dotychczas spójniki logiczne odpowiadały spójnikom występującym w mowie
potocznej. Możemy również zdefiniować abstrakcyjne spójniki logiczne poprzez zadanie
tabelki wartości logicznych. W przypadku spójników jednoargumentowych możemy to
uczynić na 2*2 = 4 sposobów, a w przypadku spójników dwuargumentowych na 2*2*2*2 =
16 sposobów.
Zestawienie wszystkich funktorów jednoargumentowych:
p
p
o
*
1
p
o
*
2
p
o
*
3
p
o
*
4
1
0
0
0
1
0
0
1
1
1
Podstawy logiki i teorii mnogości Ćwiczenie 2
---------------------------------------------------------------------------------------------------------------------------------------
– 5 –
Zestawienie wszystkich funktorów dwuargumentowych:
p
q
1 1 0 0
1 0 1 0
Nazwa funktora
q
o
p
1
0 0 0 0
F - falsum dwuargumentowe, „i tak źle i tak źle”
q
o
p
2
1 0 0 0
∧∧∧∧ - koniunkcja, „i”
q
o
p
3
0 1 0 0
q
o
p
4
0 0 1 0
q
o
p
5
0 0 0 1
↓
↓
↓
↓ - binegacja, „ani p ani q”
q
o
p
6
1 1 0 0
q
o
p
7
1 0 1 0
q
o
p
8
1 0 0 1
↔
↔
↔
↔
- równoważność, „
p wtedy i tylko wtedy, gdy q”
q
o
p
9
0 1 1 0
⊥⊥⊥⊥ - alternatywa rozłączna „albo”
q
o
p
10
0 1 0 1
q
o
p
11
0 0 1 1
q
o
p
12
1 1 1 0
∨∨∨∨ - alternatywa, „lub”
q
o
p
13
1 1 0 1
q
o
p
14
1 0 1 1
→
→
→
→
- implikacja, „jeżeli
p, to q”
q
o
p
15
0 1 1 1
/
- dyzjunkcja, „najwyżej jedno z dwojga”
q
o
p
16
1 1 1 1
V - zawsze prawda
Podstawy logiki i teorii mnogości Ćwiczenie 2
---------------------------------------------------------------------------------------------------------------------------------------
– 6 –
DEF
. Mówimy, że spójnik jednoargumentowy
o
jest
definiowalny
przez formułę
(((( ))))
p
A
, gdy
formuła
(((( ))))
p
o
jest równoważna logicznie formule
(((( ))))
p
A
.
Mówimy, że spójnik dwuargumentowy
o jest
definiowalny
przez formułę
(((( ))))
q
p
A
,
, gdy
formuła
((((
))))
q
p o
jest równoważna logicznie formule
(((( ))))
q
p
A
,
.
FAKT
a) przy pomocy
¬
¬
¬
¬
i
∧∧∧∧ można wyrazić wszystkie funktory prawdziwościowe,
b) przy pomocy
¬
¬
¬
¬
i
∨∨∨∨ można wyrazić wszystkie funktory prawdziwościowe,
c) przy pomocy
¬
¬
¬
¬
i
→
→
→
→
można wyrazić wszystkie funktory prawdziwościowe,
d) przy pomocy samej ↓
↓
↓
↓ można wyrazić wszystkie funktory prawdziwościowe,
e) przy pomocy samej
/
można wyrazić wszystkie funktory prawdziwościowe.
Niektóre definicje
:
1.
((((
)))) ((((
))))
q
p
q
p
def
¬
¬
¬
¬
∧∧∧∧
¬
¬
¬
¬
¬
¬
¬
¬
≡≡≡≡
∨∨∨∨
2.
((((
)))) ((((
))))
q
p
q
p
def
¬
¬
¬
¬
∧
∧
∧
∧
¬
¬
¬
¬
≡
≡≡
≡
→
→
→
→
3.
((((
)))) ((((
)))) ((((
))))
p
q
q
p
q
p
def
¬
¬
¬
¬
∧
∧
∧
∧
¬
¬
¬
¬
∧
∧
∧
∧
¬
¬
¬
¬
∧
∧
∧
∧
¬
¬
¬
¬
≡
≡
≡
≡
↔
↔
↔
↔
4.
((((
)))) ((((
))))
q
p
q
p
def
¬
¬
¬
¬
∨∨∨∨
¬
¬
¬
¬
¬
¬
¬
¬
≡≡≡≡
∧∧∧∧
5.
((((
)))) ((((
))))
q
p
q
p
def
∨
∨
∨
∨
¬
¬
¬
¬
≡
≡≡
≡
→
→
→
→
6.
((((
))))
((((
)))) ((((
))))
((((
))))
p
q
q
p
q
p
def
∨
∨
∨
∨
¬
¬
¬
¬
¬
¬
¬
¬
∨
∨
∨
∨
∨
∨
∨
∨
¬
¬
¬
¬
¬
¬
¬
¬
¬
¬
¬
¬
≡
≡
≡
≡
↔
↔
↔
↔
7.
((((
)))) ((((
))))
q
p
q
p
def
→
→
→
→
¬
¬
¬
¬
≡
≡
≡
≡
∨
∨
∨
∨
8.
((((
)))) ((((
))))
q
p
q
p
def
¬
¬
¬
¬
→
→
→
→
¬
¬
¬
¬
≡
≡≡
≡
∧
∧
∧
∧
9.
((((
))))
((((
))))
((((
))))
((((
))))
p
q
q
p
q
p
def
→
→
→
→
¬
¬
¬
¬
→
→
→
→
→
→
→
→
¬
¬
¬
¬
≡
≡
≡
≡
↔
↔
↔
↔
10.
((((
))))
p
p
p
def
↓
↓
↓
↓
≡
≡≡
≡
¬
¬
¬
¬
11.
((((
))))
(((( )))) (((( ))))
q
p
q
p
q
p
def
↓
↓
↓
↓
↓
↓
↓
↓
↓
↓
↓
↓
≡
≡≡
≡
∨
∨
∨
∨
12.
((((
))))
((((
)))) (((( ))))
q
q
p
p
q
p
def
↓
↓
↓
↓
↓
↓
↓
↓
↓
↓
↓
↓
≡
≡≡
≡
∧
∧
∧
∧
10.
((((
))))
p
p
p
def
/
≡≡≡≡
¬
¬
¬
¬
11.
((((
)))) (((( )))) (((( ))))
q
p
q
p
q
p
def
/
/
/
≡
≡≡
≡
∨
∨
∨
∨
12.
((((
)))) ((((
)))) (((( ))))
q
q
p
p
q
p
def
/
/
/
≡
≡
≡
≡
∧
∧
∧
∧
Podstawy logiki i teorii mnogości Ćwiczenie 2
---------------------------------------------------------------------------------------------------------------------------------------
– 7 –
Ćwiczenie 2: wiadomości i umiejętności
1.
Po ćwiczeniu 2 student powinien znać definicje pojęć podanych w nagłówku ćwiczenia
2.
Student powinien posiadać następujące umiejętności:
•
badać, czy dana formuła wynika logicznie ze zbioru formuł
•
sprawdzać, czy dany schemat wnioskowania jest niezawodny metodą tablicową i metodą
nie wprost
•
sprawdzać, czy dane rozumowanie jest dedukcyjne
•
wykazywać, że dany spójnik logiczny jest definiowalny za pomocą danego zbioru
spójników, tzn. że jest definiowalny przez pewną formułę, zbudowaną z wykorzystaniem
spójników z tego zbioru.
Wyszukiwarka
Podobne podstrony:
CwiczenieArcGIS 02 id 125937 Nieznany
cwiczenie 02 id 125037 Nieznany
Fizjologia Cwiczenia 02 id 1743 Nieznany
Pediatria Cwiczenia 02 id 35421 Nieznany
CwiczenieArcGIS 02 id 125937 Nieznany
HUR2006 02 id 207255 Nieznany
Choroby skory koni cwiczenie id Nieznany
02 Charakteryzowanie produkcji Nieznany (2)
02 Transmisjaid 3819 Nieznany
02 scinanieid 3779 Nieznany
cwiczenia zestaw2(1) Nieznany
2011 02 Ćwiczenie 4 Przedwzmacniacz gramofonowy RIAA
CwiczenieNr1 WprowadzenieDoProg Nieznany
26429 02 id 31504 Nieznany (2)
02 Nityid 3689 Nieznany
02 Lutyid 3666 Nieznany (2)
Grafy Grafy[02] id 704802 Nieznany
więcej podobnych podstron