QPrint

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ł

w KRZ, jeżeli nie istnieje

wartościowanie w, takie że

(((( ))))

FAKT. Formuła A wynika logicznie z formuł

w KRZ wtedy i tylko wtedy, gdy

→

∧

jest tautologią KRZ

Tautologie implikacyjne

Prawo odrywania

(

)

→

∧ →

Prawo odrzucania

(

)

→

∧ ¬ → ¬

Prawo sylogizmu hipotetycznego

(

) (

)

→

∧

→

Prawa symplifikacji

∧ →

Prawo koniunkcji

(

)

→

∧

Przykłady .

Prawo sylogizmu warunkowego:

(

) (

)

→

∧

→

Zatem p

→ wynika z

p →

→

→ ,

q →

→

→ .

Prawo odrywania:

(

)

→

∧ → .

Zatem q wynika z p

→ , 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

albo

gdzie formuły

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

q q

→

2.Reguła odrywania (modus ponens)

p p

→

3. Reguła odrzucania (modus tollens)

→

4. Reguła dylematu

q p

r q

∨

→

5.Reguły opuszczania koniunkcji

∧

6. Reguła wprowadzania koniunkcji

p q

∧

7. Reguły wprowadzania alternatywy

α β

∨

α β

∨

8. Reguła wprowadzania równoważności

→

↔

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

(((( )))) (((( ))))

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

↔

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

′′′′

powstaje z

C przez zastąpienie

niektórych wystąpień formuły

A formuła B, to formuły C i

′′′′

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:

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

0 0 0 0

F - falsum dwuargumentowe, „i tak źle i tak źle”

1 0 0 0

∧∧∧∧ - koniunkcja, „i”

0 1 0 0

0 0 1 0

0 0 0 1

↓

↓ - binegacja, „ani p ani q”

1 1 0 0

1 0 1 0

1 0 0 1

↔

- równoważność, „

p wtedy i tylko wtedy, gdy q”

0 1 1 0

⊥⊥⊥⊥ - alternatywa rozłączna „albo”

0 1 0 1

0 0 1 1

1 1 1 0

∨∨∨∨ - alternatywa, „lub”

1 1 0 1

1 0 1 1

→

- implikacja, „jeżeli

p, to q”

0 1 1 1

- dyzjunkcja, „najwyżej jedno z dwojga”

1 1 1 1

V - zawsze prawda

Podstawy logiki i teorii mnogości Ćwiczenie 2
---------------------------------------------------------------------------------------------------------------------------------------

– 6 –

DEF

. Mówimy, że spójnik jednoargumentowy

jest

definiowalny

przez formułę

(((( ))))

, gdy

formuła

(((( ))))

jest równoważna logicznie formule

(((( ))))

Mówimy, że spójnik dwuargumentowy

o jest

definiowalny

przez formułę

(((( ))))

, gdy

formuła

((((

))))

p o

jest równoważna logicznie formule

(((( ))))

FAKT

a) przy pomocy

∧∧∧∧ można wyrazić wszystkie funktory prawdziwościowe,

b) przy pomocy

∨∨∨∨ można wyrazić wszystkie funktory prawdziwościowe,

c) przy pomocy

→

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

((((

)))) ((((

))))

def

∧∧∧∧

≡≡≡≡

∨∨∨∨

((((

)))) ((((

))))

def

∧

≡

≡≡

≡

→

((((

)))) ((((

))))

def

∧

≡

↔

((((

)))) ((((

))))

def

∨∨∨∨

≡≡≡≡

∧∧∧∧

((((

)))) ((((

))))

def

∨

≡

≡≡

≡

→

((((

))))

((((

)))) ((((

))))

((((

))))

def

∨

≡

↔

((((

)))) ((((

))))

def

→

≡

∨

((((

)))) ((((

))))

def

→

≡

≡≡

≡

∧

((((

))))

((((

))))

((((

))))

((((

))))

def

→

≡

↔

10.

((((

))))

def

↓

≡

≡≡

≡

11.

((((

))))

(((( )))) (((( ))))

def

↓

≡

≡≡

≡

∨

12.

((((

))))

((((

)))) (((( ))))

def

↓

≡

≡≡

≡

∧

10.

((((

))))

def

≡≡≡≡

11.

((((

)))) (((( )))) (((( ))))

def

≡

≡≡

≡

∨

12.

((((

)))) ((((

)))) (((( ))))

def

≡

∧

Podstawy logiki i teorii mnogości Ćwiczenie 2
---------------------------------------------------------------------------------------------------------------------------------------

– 7 –

Ćwiczenie 2: wiadomości i umiejętności

Po ćwiczeniu 2 student powinien znać definicje pojęć podanych w nagłówku ćwiczenia

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.