Klasyczny rachunek zdań Adekwatność

background image

Klasyczny Rachunek Zdań (część III)

LOGIKA

Klasyczny Rachunek Zdań (część III)

Poprawność i pełność KRZ

Robert Trypuz

Katedra Logiki KUL

31 marca 2011

background image

Klasyczny Rachunek Zdań (część III)

Zarys

1

Wprowadzenie

2

Dowód trafności KRZ

3

Dowód pełności KRZ

4

Podsumowanie dowodów trafności i pełności KRZ

background image

Klasyczny Rachunek Zdań (część III)

Zarys

1

Wprowadzenie

2

Dowód trafności KRZ

3

Dowód pełności KRZ

4

Podsumowanie dowodów trafności i pełności KRZ

background image

Klasyczny Rachunek Zdań (część III)

Zarys

1

Wprowadzenie

2

Dowód trafności KRZ

3

Dowód pełności KRZ

4

Podsumowanie dowodów trafności i pełności KRZ

background image

Klasyczny Rachunek Zdań (część III)

Zarys

1

Wprowadzenie

2

Dowód trafności KRZ

3

Dowód pełności KRZ

4

Podsumowanie dowodów trafności i pełności KRZ

background image

Klasyczny Rachunek Zdań (część III)

Wprowadzenie

Tautologie i tezy

teza = wyrażenie +

dowód

prawo logiki (tautologia) = wyrażenie +

prawda

background image

Klasyczny Rachunek Zdań (część III)

Wprowadzenie

Tautologie i tezy

teza = wyrażenie +

dowód

prawo logiki (tautologia) = wyrażenie +

prawda

background image

Klasyczny Rachunek Zdań (część III)

Wprowadzenie

Trafność i pełność KRZ

Jeżeli w teorii logicznej T każda teza jest tautologią, to T jest
trafna.

Jeżeli w teorii logicznej T każda tautologia jest tezą, to T jest pełna.

KRZ jest trafny i pełny, tj. dla ϕ będącego formułą KRZ zachodzi:

` ϕ →  ϕ
 ϕ → ` ϕ

Dowody trafności są zazwyczaj dużo prostsze niż dowody pełności.

background image

Klasyczny Rachunek Zdań (część III)

Wprowadzenie

Trafność i pełność KRZ

Jeżeli w teorii logicznej T każda teza jest tautologią, to T jest
trafna.

Jeżeli w teorii logicznej T każda tautologia jest tezą, to T jest pełna.

KRZ jest trafny i pełny, tj. dla ϕ będącego formułą KRZ zachodzi:

` ϕ →  ϕ
 ϕ → ` ϕ

Dowody trafności są zazwyczaj dużo prostsze niż dowody pełności.

background image

Klasyczny Rachunek Zdań (część III)

Wprowadzenie

Trafność i pełność KRZ

Jeżeli w teorii logicznej T każda teza jest tautologią, to T jest
trafna.

Jeżeli w teorii logicznej T każda tautologia jest tezą, to T jest pełna.

KRZ jest trafny i pełny, tj. dla ϕ będącego formułą KRZ zachodzi:

` ϕ →  ϕ
 ϕ → ` ϕ

Dowody trafności są zazwyczaj dużo prostsze niż dowody pełności.

background image

Klasyczny Rachunek Zdań (część III)

Wprowadzenie

Trafność i pełność KRZ

Jeżeli w teorii logicznej T każda teza jest tautologią, to T jest
trafna.

Jeżeli w teorii logicznej T każda tautologia jest tezą, to T jest pełna.

KRZ jest trafny i pełny, tj. dla ϕ będącego formułą KRZ zachodzi:

` ϕ →  ϕ
 ϕ → ` ϕ

Dowody trafności są zazwyczaj dużo prostsze niż dowody pełności.

background image

Klasyczny Rachunek Zdań (część III)

Wprowadzenie

Trafność i pełność KRZ

Jeżeli w teorii logicznej T każda teza jest tautologią, to T jest
trafna.

Jeżeli w teorii logicznej T każda tautologia jest tezą, to T jest pełna.

KRZ jest trafny i pełny, tj. dla ϕ będącego formułą KRZ zachodzi:

` ϕ →  ϕ
 ϕ → ` ϕ

Dowody trafności są zazwyczaj dużo prostsze niż dowody pełności.

background image

Klasyczny Rachunek Zdań (część III)

Dowód trafności KRZ

Dowód trafności KRZ

Dowodzimy, że

dla ϕ będącego formułą KRZ zachodzi: ` ϕ →

 ϕ

Dowód trafności KRZ jest indukcyjny:

1

Każda teza pierwszego rzędu KRZ jest tautologią KRZ.

2

Jeżeli wszystkie tezy KRZ rzędów od 1 do k są tautologiami KRZ, to
każda teza KRZ k-tego rzędu jest tautologią KRZ.

background image

Klasyczny Rachunek Zdań (część III)

Dowód trafności KRZ

Przykład tezy 1-go rzędu

Dowód, że ` (¬p q) ∧ ¬q p

1.

p q) ∧ ¬q

z.

2.

¬p

z.d .n.

3.

¬p q

OK : 1

4.

¬q

OK : 1

5.

q

RO : 3, 2

sprz. :4, 5

Wyrażenie dowodzone jest tezą pierwszego rzędu KRZ, bo istnieje ciąg:

1

p q) ∧ ¬q

2

¬p

3

¬p q

4

¬q

5

q

który spełnia warunki definicji tezy pierwszego rzędu.

background image

Klasyczny Rachunek Zdań (część III)

Dowód trafności KRZ

Przykład tezy 1-go rzędu

Dowód, że ` (¬p q) ∧ ¬q p

1.

p q) ∧ ¬q

z.

2.

¬p

z.d .n.

3.

¬p q

OK : 1

4.

¬q

OK : 1

5.

q

RO : 3, 2

sprz. :4, 5

Wyrażenie dowodzone jest tezą pierwszego rzędu KRZ, bo istnieje ciąg:

1

p q) ∧ ¬q

2

¬p

3

¬p q

4

¬q

5

q

który spełnia warunki definicji tezy pierwszego rzędu.

background image

Klasyczny Rachunek Zdań (część III)

Dowód trafności KRZ

Przykład tezy 1-go rzędu

Dowód, że ` (¬p q) ∧ ¬q p

1.

p q) ∧ ¬q

z.

2.

¬p

z.d .n.

3.

¬p q

OK : 1

4.

¬q

OK : 1

5.

q

RO : 3, 2

sprz. :4, 5

Wyrażenie dowodzone jest tezą pierwszego rzędu KRZ, bo istnieje ciąg:

1

p q) ∧ ¬q

2

¬p

3

¬p q

4

¬q

5

q

który spełnia warunki definicji tezy pierwszego rzędu.

background image

Klasyczny Rachunek Zdań (część III)

Dowód trafności KRZ

Każda teza 1-go rzędu jest tautologią KRZ

Niech wyrażenie ϕ o postaci: ϕ

1

→ (ϕ

2

→ (· · · → (ϕ

n−1

→ ϕ

n

) . . . )

będzie tezą 1-go rzędu.

Istnieje wtedy założeniowy dowód nie wprost wyrażenia ϕ, w którym
z założeń dowodu ϕ

1

, ϕ

2

, . . . , ϕ

n−1

, ¬ϕ

n

wyprowadzamy dwa

wyrażenia sprzeczne (ψ, ¬ψ) za pomocą pierwotnych reguł
dołączania nowych wierszy do dowodu.

Reguły pierwotne dołączania nowy wierszy do dowodu prowadzą od
wyrażeń prawdziwych do wyrażeń prawdziwych.

Na przykład Reguła Odrywania:

RO

ϕ → ψ
ϕ
ψ

Jeżeli ϕ → ψ i ϕ są prawdziwe, to prawdziwe jest też wyrażenie ψ.
Podobnie pokazujemy dla innych reguł.

Dwa wyrażenia sprzeczne nie są zarazem prawdziwe.

A zatem wyrażenia ϕ

1

, ϕ

2

, . . . , ϕ

n−1

, ¬ϕ

n

nie mogą być (i nie są)

zarazem prawdziwe.

background image

Klasyczny Rachunek Zdań (część III)

Dowód trafności KRZ

Każda teza 1-go rzędu jest tautologią KRZ

Niech wyrażenie ϕ o postaci: ϕ

1

→ (ϕ

2

→ (· · · → (ϕ

n−1

→ ϕ

n

) . . . )

będzie tezą 1-go rzędu.

Istnieje wtedy założeniowy dowód nie wprost wyrażenia ϕ, w którym
z założeń dowodu ϕ

1

, ϕ

2

, . . . , ϕ

n−1

, ¬ϕ

n

wyprowadzamy dwa

wyrażenia sprzeczne (ψ, ¬ψ) za pomocą pierwotnych reguł
dołączania nowych wierszy do dowodu.

Reguły pierwotne dołączania nowy wierszy do dowodu prowadzą od
wyrażeń prawdziwych do wyrażeń prawdziwych.

Na przykład Reguła Odrywania:

RO

ϕ → ψ
ϕ
ψ

Jeżeli ϕ → ψ i ϕ są prawdziwe, to prawdziwe jest też wyrażenie ψ.
Podobnie pokazujemy dla innych reguł.

Dwa wyrażenia sprzeczne nie są zarazem prawdziwe.

A zatem wyrażenia ϕ

1

, ϕ

2

, . . . , ϕ

n−1

, ¬ϕ

n

nie mogą być (i nie są)

zarazem prawdziwe.

background image

Klasyczny Rachunek Zdań (część III)

Dowód trafności KRZ

Każda teza 1-go rzędu jest tautologią KRZ

Niech wyrażenie ϕ o postaci: ϕ

1

→ (ϕ

2

→ (· · · → (ϕ

n−1

→ ϕ

n

) . . . )

będzie tezą 1-go rzędu.

Istnieje wtedy założeniowy dowód nie wprost wyrażenia ϕ, w którym
z założeń dowodu ϕ

1

, ϕ

2

, . . . , ϕ

n−1

, ¬ϕ

n

wyprowadzamy dwa

wyrażenia sprzeczne (ψ, ¬ψ) za pomocą pierwotnych reguł
dołączania nowych wierszy do dowodu.

Reguły pierwotne dołączania nowy wierszy do dowodu prowadzą od
wyrażeń prawdziwych do wyrażeń prawdziwych.

Na przykład Reguła Odrywania:

RO

ϕ → ψ
ϕ
ψ

Jeżeli ϕ → ψ i ϕ są prawdziwe, to prawdziwe jest też wyrażenie ψ.
Podobnie pokazujemy dla innych reguł.

Dwa wyrażenia sprzeczne nie są zarazem prawdziwe.

A zatem wyrażenia ϕ

1

, ϕ

2

, . . . , ϕ

n−1

, ¬ϕ

n

nie mogą być (i nie są)

zarazem prawdziwe.

background image

Klasyczny Rachunek Zdań (część III)

Dowód trafności KRZ

Każda teza 1-go rzędu jest tautologią KRZ

Niech wyrażenie ϕ o postaci: ϕ

1

→ (ϕ

2

→ (· · · → (ϕ

n−1

→ ϕ

n

) . . . )

będzie tezą 1-go rzędu.

Istnieje wtedy założeniowy dowód nie wprost wyrażenia ϕ, w którym
z założeń dowodu ϕ

1

, ϕ

2

, . . . , ϕ

n−1

, ¬ϕ

n

wyprowadzamy dwa

wyrażenia sprzeczne (ψ, ¬ψ) za pomocą pierwotnych reguł
dołączania nowych wierszy do dowodu.

Reguły pierwotne dołączania nowy wierszy do dowodu prowadzą od
wyrażeń prawdziwych do wyrażeń prawdziwych.

Na przykład Reguła Odrywania:

RO

ϕ → ψ
ϕ
ψ

Jeżeli ϕ → ψ i ϕ są prawdziwe, to prawdziwe jest też wyrażenie ψ.
Podobnie pokazujemy dla innych reguł.

Dwa wyrażenia sprzeczne nie są zarazem prawdziwe.

A zatem wyrażenia ϕ

1

, ϕ

2

, . . . , ϕ

n−1

, ¬ϕ

n

nie mogą być (i nie są)

zarazem prawdziwe.

background image

Klasyczny Rachunek Zdań (część III)

Dowód trafności KRZ

Każda teza 1-go rzędu jest tautologią KRZ

Niech wyrażenie ϕ o postaci: ϕ

1

→ (ϕ

2

→ (· · · → (ϕ

n−1

→ ϕ

n

) . . . )

będzie tezą 1-go rzędu.

Istnieje wtedy założeniowy dowód nie wprost wyrażenia ϕ, w którym
z założeń dowodu ϕ

1

, ϕ

2

, . . . , ϕ

n−1

, ¬ϕ

n

wyprowadzamy dwa

wyrażenia sprzeczne (ψ, ¬ψ) za pomocą pierwotnych reguł
dołączania nowych wierszy do dowodu.

Reguły pierwotne dołączania nowy wierszy do dowodu prowadzą od
wyrażeń prawdziwych do wyrażeń prawdziwych.

Na przykład Reguła Odrywania:

RO

ϕ → ψ
ϕ
ψ

Jeżeli ϕ → ψ i ϕ są prawdziwe, to prawdziwe jest też wyrażenie ψ.
Podobnie pokazujemy dla innych reguł.

Dwa wyrażenia sprzeczne nie są zarazem prawdziwe.

A zatem wyrażenia ϕ

1

, ϕ

2

, . . . , ϕ

n−1

, ¬ϕ

n

nie mogą być (i nie są)

zarazem prawdziwe.

background image

Klasyczny Rachunek Zdań (część III)

Dowód trafności KRZ

Każda teza 1-go rzędu jest tautologią KRZ

Niech wyrażenie ϕ o postaci: ϕ

1

→ (ϕ

2

→ (· · · → (ϕ

n−1

→ ϕ

n

) . . . )

będzie tezą 1-go rzędu.

Istnieje wtedy założeniowy dowód nie wprost wyrażenia ϕ, w którym
z założeń dowodu ϕ

1

, ϕ

2

, . . . , ϕ

n−1

, ¬ϕ

n

wyprowadzamy dwa

wyrażenia sprzeczne (ψ, ¬ψ) za pomocą pierwotnych reguł
dołączania nowych wierszy do dowodu.

Reguły pierwotne dołączania nowy wierszy do dowodu prowadzą od
wyrażeń prawdziwych do wyrażeń prawdziwych.

Na przykład Reguła Odrywania:

RO

ϕ → ψ
ϕ
ψ

Jeżeli ϕ → ψ i ϕ są prawdziwe, to prawdziwe jest też wyrażenie ψ.
Podobnie pokazujemy dla innych reguł.

Dwa wyrażenia sprzeczne nie są zarazem prawdziwe.

A zatem wyrażenia ϕ

1

, ϕ

2

, . . . , ϕ

n−1

, ¬ϕ

n

nie mogą być (i nie są)

zarazem prawdziwe.

background image

Klasyczny Rachunek Zdań (część III)

Dowód trafności KRZ

Każda teza 1-go rzędu jest tautologią KRZ

Niech wyrażenie ϕ o postaci: ϕ

1

→ (ϕ

2

→ (· · · → (ϕ

n−1

→ ϕ

n

) . . . )

będzie tezą 1-go rzędu.

Istnieje wtedy założeniowy dowód nie wprost wyrażenia ϕ, w którym
z założeń dowodu ϕ

1

, ϕ

2

, . . . , ϕ

n−1

, ¬ϕ

n

wyprowadzamy dwa

wyrażenia sprzeczne (ψ, ¬ψ) za pomocą pierwotnych reguł
dołączania nowych wierszy do dowodu.

Reguły pierwotne dołączania nowy wierszy do dowodu prowadzą od
wyrażeń prawdziwych do wyrażeń prawdziwych.

Na przykład Reguła Odrywania:

RO

ϕ → ψ
ϕ
ψ

Jeżeli ϕ → ψ i ϕ są prawdziwe, to prawdziwe jest też wyrażenie ψ.
Podobnie pokazujemy dla innych reguł.

Dwa wyrażenia sprzeczne nie są zarazem prawdziwe.

A zatem wyrażenia ϕ

1

, ϕ

2

, . . . , ϕ

n−1

, ¬ϕ

n

nie mogą być (i nie są)

zarazem prawdziwe.

background image

Klasyczny Rachunek Zdań (część III)

Dowód trafności KRZ

Każda teza 1-go rzędu jest tautologią KRZ

Czy istnieje taka wartość logiczna wyrażeń ϕ

1

, ϕ

2

, . . . , ϕ

n−1

, ¬ϕ

n

przy której:

spełnione jest ograniczenie, że nie są one zarazem prawdziwe
wyrażenie ϕ, o postaci: ϕ

1

→ (ϕ

2

→ (· · · → (ϕ

n−1

→ ϕ

n

) . . . ) jest

fałszywe?

Zobaczmy zatem kiedy ϕ jest fałszywe:

( ϕ

1

|{z}

P

→ ( ϕ

2

|{z}

P

→ ( ϕ

3

|{z}

P

→ (· · · → (ϕ

n−1

| {z }

P

→ ϕ

n

|{z}

F

) . . . )

Zauważmy, że ϕ

n

jest fałszywe, gdy ¬ϕ

n

jest prawdziwe.

A zatem ϕ jest fałszywe jedynie wówczas, kiedy wyrażenia
ϕ

1

, ϕ

2

, . . . , ϕ

n−1

, ¬ϕ

n

zarazem prawdziwe, co nie jest możliwe,

gdy ϕ jest tezą 1-go rzędu KRZ.
Inaczej rzecz ujmując, jeżeli wyrażenia ϕ

1

, ϕ

2

, . . . , ϕ

n−1

prawdziwe, to wyrażenie ϕ

n

jest również prawdziwe. Ostatecznie

wyrażenie ϕ jest też prawdziwe. Q.E.D.

(quod erat demonstrandum)

background image

Klasyczny Rachunek Zdań (część III)

Dowód trafności KRZ

Każda teza 1-go rzędu jest tautologią KRZ

Czy istnieje taka wartość logiczna wyrażeń ϕ

1

, ϕ

2

, . . . , ϕ

n−1

, ¬ϕ

n

przy której:

spełnione jest ograniczenie, że nie są one zarazem prawdziwe
wyrażenie ϕ, o postaci: ϕ

1

→ (ϕ

2

→ (· · · → (ϕ

n−1

→ ϕ

n

) . . . ) jest

fałszywe?

Zobaczmy zatem kiedy ϕ jest fałszywe:

( ϕ

1

|{z}

P

→ ( ϕ

2

|{z}

P

→ ( ϕ

3

|{z}

P

→ (· · · → (ϕ

n−1

| {z }

P

→ ϕ

n

|{z}

F

) . . . )

Zauważmy, że ϕ

n

jest fałszywe, gdy ¬ϕ

n

jest prawdziwe.

A zatem ϕ jest fałszywe jedynie wówczas, kiedy wyrażenia
ϕ

1

, ϕ

2

, . . . , ϕ

n−1

, ¬ϕ

n

zarazem prawdziwe, co nie jest możliwe,

gdy ϕ jest tezą 1-go rzędu KRZ.
Inaczej rzecz ujmując, jeżeli wyrażenia ϕ

1

, ϕ

2

, . . . , ϕ

n−1

prawdziwe, to wyrażenie ϕ

n

jest również prawdziwe. Ostatecznie

wyrażenie ϕ jest też prawdziwe. Q.E.D.

(quod erat demonstrandum)

background image

Klasyczny Rachunek Zdań (część III)

Dowód trafności KRZ

Każda teza 1-go rzędu jest tautologią KRZ

Czy istnieje taka wartość logiczna wyrażeń ϕ

1

, ϕ

2

, . . . , ϕ

n−1

, ¬ϕ

n

przy której:

spełnione jest ograniczenie, że nie są one zarazem prawdziwe
wyrażenie ϕ, o postaci: ϕ

1

→ (ϕ

2

→ (· · · → (ϕ

n−1

→ ϕ

n

) . . . ) jest

fałszywe?

Zobaczmy zatem kiedy ϕ jest fałszywe:

( ϕ

1

|{z}

P

→ ( ϕ

2

|{z}

P

→ ( ϕ

3

|{z}

P

→ (· · · → (ϕ

n−1

| {z }

P

→ ϕ

n

|{z}

F

) . . . )

Zauważmy, że ϕ

n

jest fałszywe, gdy ¬ϕ

n

jest prawdziwe.

A zatem ϕ jest fałszywe jedynie wówczas, kiedy wyrażenia
ϕ

1

, ϕ

2

, . . . , ϕ

n−1

, ¬ϕ

n

zarazem prawdziwe, co nie jest możliwe,

gdy ϕ jest tezą 1-go rzędu KRZ.
Inaczej rzecz ujmując, jeżeli wyrażenia ϕ

1

, ϕ

2

, . . . , ϕ

n−1

prawdziwe, to wyrażenie ϕ

n

jest również prawdziwe. Ostatecznie

wyrażenie ϕ jest też prawdziwe. Q.E.D.

(quod erat demonstrandum)

background image

Klasyczny Rachunek Zdań (część III)

Dowód trafności KRZ

Każda teza 1-go rzędu jest tautologią KRZ

Czy istnieje taka wartość logiczna wyrażeń ϕ

1

, ϕ

2

, . . . , ϕ

n−1

, ¬ϕ

n

przy której:

spełnione jest ograniczenie, że nie są one zarazem prawdziwe
wyrażenie ϕ, o postaci: ϕ

1

→ (ϕ

2

→ (· · · → (ϕ

n−1

→ ϕ

n

) . . . ) jest

fałszywe?

Zobaczmy zatem kiedy ϕ jest fałszywe:

( ϕ

1

|{z}

P

→ ( ϕ

2

|{z}

P

→ ( ϕ

3

|{z}

P

→ (· · · → (ϕ

n−1

| {z }

P

→ ϕ

n

|{z}

F

) . . . )

Zauważmy, że ϕ

n

jest fałszywe, gdy ¬ϕ

n

jest prawdziwe.

A zatem ϕ jest fałszywe jedynie wówczas, kiedy wyrażenia
ϕ

1

, ϕ

2

, . . . , ϕ

n−1

, ¬ϕ

n

zarazem prawdziwe, co nie jest możliwe,

gdy ϕ jest tezą 1-go rzędu KRZ.

Inaczej rzecz ujmując, jeżeli wyrażenia ϕ

1

, ϕ

2

, . . . , ϕ

n−1

prawdziwe, to wyrażenie ϕ

n

jest również prawdziwe. Ostatecznie

wyrażenie ϕ jest też prawdziwe. Q.E.D.

(quod erat demonstrandum)

background image

Klasyczny Rachunek Zdań (część III)

Dowód trafności KRZ

Każda teza 1-go rzędu jest tautologią KRZ

Czy istnieje taka wartość logiczna wyrażeń ϕ

1

, ϕ

2

, . . . , ϕ

n−1

, ¬ϕ

n

przy której:

spełnione jest ograniczenie, że nie są one zarazem prawdziwe
wyrażenie ϕ, o postaci: ϕ

1

→ (ϕ

2

→ (· · · → (ϕ

n−1

→ ϕ

n

) . . . ) jest

fałszywe?

Zobaczmy zatem kiedy ϕ jest fałszywe:

( ϕ

1

|{z}

P

→ ( ϕ

2

|{z}

P

→ ( ϕ

3

|{z}

P

→ (· · · → (ϕ

n−1

| {z }

P

→ ϕ

n

|{z}

F

) . . . )

Zauważmy, że ϕ

n

jest fałszywe, gdy ¬ϕ

n

jest prawdziwe.

A zatem ϕ jest fałszywe jedynie wówczas, kiedy wyrażenia
ϕ

1

, ϕ

2

, . . . , ϕ

n−1

, ¬ϕ

n

zarazem prawdziwe, co nie jest możliwe,

gdy ϕ jest tezą 1-go rzędu KRZ.
Inaczej rzecz ujmując, jeżeli wyrażenia ϕ

1

, ϕ

2

, . . . , ϕ

n−1

prawdziwe, to wyrażenie ϕ

n

jest również prawdziwe. Ostatecznie

wyrażenie ϕ jest też prawdziwe. Q.E.D.

(quod erat demonstrandum)

background image

Klasyczny Rachunek Zdań (część III)

Dowód trafności KRZ

Każda teza k-go rzędu jest tautologią KRZ

Niech wyrażenie ϕ o postaci: ϕ

1

→ (ϕ

2

→ (· · · → (ϕ

n−1

→ ϕ

n

) . . . )

będzie tezą k-go rzędu.

Zakładamy, że wszystkie tezy rzędów od 1 do k − 1 są wyrażeniami
prawdziwymi.

Istnieje wtedy założeniowy dowód nie wprost wyrażenia ϕ, w którym
z założeń dowodu ϕ

1

, ϕ

2

, . . . , ϕ

n−1

, ¬ϕ

n

i tez T

1

, . . . , T

m

rzędów

mniejszych od k wyprowadzamy dwa wyrażenia sprzeczne za pomocą
pierwotnych reguł dołączania nowych wierszy do dowodu.

Reguły pierwotne dołączania nowy wierszy do dowodu prowadzą od
wyrażeń prawdziwych do wyrażeń prawdziwych.

Tezy T

1

, . . . , T

m

na mocy założenia są wyrażeniami prawdziwymi.

Podobnie jak wcześniej, dochodzimy do wniosku, że jeżeli wyrażenia
ϕ

1

, ϕ

2

, . . . , ϕ

n−1

są prawdziwe, to wyrażenie ϕ

n

jest również

prawdziwe. Ostatecznie wyrażenie ϕ jest też prawdziwe. Q.E.D.

background image

Klasyczny Rachunek Zdań (część III)

Dowód trafności KRZ

Każda teza k-go rzędu jest tautologią KRZ

Niech wyrażenie ϕ o postaci: ϕ

1

→ (ϕ

2

→ (· · · → (ϕ

n−1

→ ϕ

n

) . . . )

będzie tezą k-go rzędu.

Zakładamy, że wszystkie tezy rzędów od 1 do k − 1 są wyrażeniami
prawdziwymi.

Istnieje wtedy założeniowy dowód nie wprost wyrażenia ϕ, w którym
z założeń dowodu ϕ

1

, ϕ

2

, . . . , ϕ

n−1

, ¬ϕ

n

i tez T

1

, . . . , T

m

rzędów

mniejszych od k wyprowadzamy dwa wyrażenia sprzeczne za pomocą
pierwotnych reguł dołączania nowych wierszy do dowodu.

Reguły pierwotne dołączania nowy wierszy do dowodu prowadzą od
wyrażeń prawdziwych do wyrażeń prawdziwych.

Tezy T

1

, . . . , T

m

na mocy założenia są wyrażeniami prawdziwymi.

Podobnie jak wcześniej, dochodzimy do wniosku, że jeżeli wyrażenia
ϕ

1

, ϕ

2

, . . . , ϕ

n−1

są prawdziwe, to wyrażenie ϕ

n

jest również

prawdziwe. Ostatecznie wyrażenie ϕ jest też prawdziwe. Q.E.D.

background image

Klasyczny Rachunek Zdań (część III)

Dowód trafności KRZ

Każda teza k-go rzędu jest tautologią KRZ

Niech wyrażenie ϕ o postaci: ϕ

1

→ (ϕ

2

→ (· · · → (ϕ

n−1

→ ϕ

n

) . . . )

będzie tezą k-go rzędu.

Zakładamy, że wszystkie tezy rzędów od 1 do k − 1 są wyrażeniami
prawdziwymi.

Istnieje wtedy założeniowy dowód nie wprost wyrażenia ϕ, w którym
z założeń dowodu ϕ

1

, ϕ

2

, . . . , ϕ

n−1

, ¬ϕ

n

i tez T

1

, . . . , T

m

rzędów

mniejszych od k wyprowadzamy dwa wyrażenia sprzeczne za pomocą
pierwotnych reguł dołączania nowych wierszy do dowodu.

Reguły pierwotne dołączania nowy wierszy do dowodu prowadzą od
wyrażeń prawdziwych do wyrażeń prawdziwych.

Tezy T

1

, . . . , T

m

na mocy założenia są wyrażeniami prawdziwymi.

Podobnie jak wcześniej, dochodzimy do wniosku, że jeżeli wyrażenia
ϕ

1

, ϕ

2

, . . . , ϕ

n−1

są prawdziwe, to wyrażenie ϕ

n

jest również

prawdziwe. Ostatecznie wyrażenie ϕ jest też prawdziwe. Q.E.D.

background image

Klasyczny Rachunek Zdań (część III)

Dowód trafności KRZ

Każda teza k-go rzędu jest tautologią KRZ

Niech wyrażenie ϕ o postaci: ϕ

1

→ (ϕ

2

→ (· · · → (ϕ

n−1

→ ϕ

n

) . . . )

będzie tezą k-go rzędu.

Zakładamy, że wszystkie tezy rzędów od 1 do k − 1 są wyrażeniami
prawdziwymi.

Istnieje wtedy założeniowy dowód nie wprost wyrażenia ϕ, w którym
z założeń dowodu ϕ

1

, ϕ

2

, . . . , ϕ

n−1

, ¬ϕ

n

i tez T

1

, . . . , T

m

rzędów

mniejszych od k wyprowadzamy dwa wyrażenia sprzeczne za pomocą
pierwotnych reguł dołączania nowych wierszy do dowodu.

Reguły pierwotne dołączania nowy wierszy do dowodu prowadzą od
wyrażeń prawdziwych do wyrażeń prawdziwych.

Tezy T

1

, . . . , T

m

na mocy założenia są wyrażeniami prawdziwymi.

Podobnie jak wcześniej, dochodzimy do wniosku, że jeżeli wyrażenia
ϕ

1

, ϕ

2

, . . . , ϕ

n−1

są prawdziwe, to wyrażenie ϕ

n

jest również

prawdziwe. Ostatecznie wyrażenie ϕ jest też prawdziwe. Q.E.D.

background image

Klasyczny Rachunek Zdań (część III)

Dowód trafności KRZ

Każda teza k-go rzędu jest tautologią KRZ

Niech wyrażenie ϕ o postaci: ϕ

1

→ (ϕ

2

→ (· · · → (ϕ

n−1

→ ϕ

n

) . . . )

będzie tezą k-go rzędu.

Zakładamy, że wszystkie tezy rzędów od 1 do k − 1 są wyrażeniami
prawdziwymi.

Istnieje wtedy założeniowy dowód nie wprost wyrażenia ϕ, w którym
z założeń dowodu ϕ

1

, ϕ

2

, . . . , ϕ

n−1

, ¬ϕ

n

i tez T

1

, . . . , T

m

rzędów

mniejszych od k wyprowadzamy dwa wyrażenia sprzeczne za pomocą
pierwotnych reguł dołączania nowych wierszy do dowodu.

Reguły pierwotne dołączania nowy wierszy do dowodu prowadzą od
wyrażeń prawdziwych do wyrażeń prawdziwych.

Tezy T

1

, . . . , T

m

na mocy założenia są wyrażeniami prawdziwymi.

Podobnie jak wcześniej, dochodzimy do wniosku, że jeżeli wyrażenia
ϕ

1

, ϕ

2

, . . . , ϕ

n−1

są prawdziwe, to wyrażenie ϕ

n

jest również

prawdziwe. Ostatecznie wyrażenie ϕ jest też prawdziwe. Q.E.D.

background image

Klasyczny Rachunek Zdań (część III)

Dowód trafności KRZ

Każda teza k-go rzędu jest tautologią KRZ

Niech wyrażenie ϕ o postaci: ϕ

1

→ (ϕ

2

→ (· · · → (ϕ

n−1

→ ϕ

n

) . . . )

będzie tezą k-go rzędu.

Zakładamy, że wszystkie tezy rzędów od 1 do k − 1 są wyrażeniami
prawdziwymi.

Istnieje wtedy założeniowy dowód nie wprost wyrażenia ϕ, w którym
z założeń dowodu ϕ

1

, ϕ

2

, . . . , ϕ

n−1

, ¬ϕ

n

i tez T

1

, . . . , T

m

rzędów

mniejszych od k wyprowadzamy dwa wyrażenia sprzeczne za pomocą
pierwotnych reguł dołączania nowych wierszy do dowodu.

Reguły pierwotne dołączania nowy wierszy do dowodu prowadzą od
wyrażeń prawdziwych do wyrażeń prawdziwych.

Tezy T

1

, . . . , T

m

na mocy założenia są wyrażeniami prawdziwymi.

Podobnie jak wcześniej, dochodzimy do wniosku, że jeżeli wyrażenia
ϕ

1

, ϕ

2

, . . . , ϕ

n−1

są prawdziwe, to wyrażenie ϕ

n

jest również

prawdziwe. Ostatecznie wyrażenie ϕ jest też prawdziwe. Q.E.D.

background image

Klasyczny Rachunek Zdań (część III)

Dowód trafności KRZ

Każda teza k-go rzędu jest tautologią KRZ

Niech wyrażenie ϕ o postaci: ϕ

1

→ (ϕ

2

→ (· · · → (ϕ

n−1

→ ϕ

n

) . . . )

będzie tezą k-go rzędu.

Zakładamy, że wszystkie tezy rzędów od 1 do k − 1 są wyrażeniami
prawdziwymi.

Istnieje wtedy założeniowy dowód nie wprost wyrażenia ϕ, w którym
z założeń dowodu ϕ

1

, ϕ

2

, . . . , ϕ

n−1

, ¬ϕ

n

i tez T

1

, . . . , T

m

rzędów

mniejszych od k wyprowadzamy dwa wyrażenia sprzeczne za pomocą
pierwotnych reguł dołączania nowych wierszy do dowodu.

Reguły pierwotne dołączania nowy wierszy do dowodu prowadzą od
wyrażeń prawdziwych do wyrażeń prawdziwych.

Tezy T

1

, . . . , T

m

na mocy założenia są wyrażeniami prawdziwymi.

Podobnie jak wcześniej, dochodzimy do wniosku, że jeżeli wyrażenia
ϕ

1

, ϕ

2

, . . . , ϕ

n−1

są prawdziwe, to wyrażenie ϕ

n

jest również

prawdziwe. Ostatecznie wyrażenie ϕ jest też prawdziwe. Q.E.D.

background image

Klasyczny Rachunek Zdań (część III)

Dowód pełności KRZ

Dowód pełności KRZ

Dowód pełności składa się z dwóch części

1

dowodu, że dla każdej formuły ϕ KRZ, istnieje taka formuła K KRZ,
która:

jest równoważna ϕ (tzn. ` ϕ ≡ K),
ma pewną specjalną budowę, zwaną koniunkcyjną postacią normalną.

2

dowodu, że jeżeli ϕ ma koniunkcyjną postać normalną i  ϕ, to ` ϕ.

background image

Klasyczny Rachunek Zdań (część III)

Dowód pełności KRZ

Dowód pełności KRZ

Dowód pełności składa się z dwóch części

1

dowodu, że dla każdej formuły ϕ KRZ, istnieje taka formuła K KRZ,
która:

jest równoważna ϕ (tzn. ` ϕ ≡ K),
ma pewną specjalną budowę, zwaną koniunkcyjną postacią normalną.

2

dowodu, że jeżeli ϕ ma koniunkcyjną postać normalną i  ϕ, to ` ϕ.

background image

Klasyczny Rachunek Zdań (część III)

Dowód pełności KRZ

Dowód pełności KRZ

Dowód pełności składa się z dwóch części

1

dowodu, że dla każdej formuły ϕ KRZ, istnieje taka formuła K KRZ,
która:

jest równoważna ϕ (tzn. ` ϕ ≡ K),
ma pewną specjalną budowę, zwaną koniunkcyjną postacią normalną.

2

dowodu, że jeżeli ϕ ma koniunkcyjną postać normalną i  ϕ, to ` ϕ.

background image

Klasyczny Rachunek Zdań (część III)

Dowód pełności KRZ

Dowód pełności KRZ

Dowód pełności składa się z dwóch części

1

dowodu, że dla każdej formuły ϕ KRZ, istnieje taka formuła K KRZ,
która:

jest równoważna ϕ (tzn. ` ϕ ≡ K),

ma pewną specjalną budowę, zwaną koniunkcyjną postacią normalną.

2

dowodu, że jeżeli ϕ ma koniunkcyjną postać normalną i  ϕ, to ` ϕ.

background image

Klasyczny Rachunek Zdań (część III)

Dowód pełności KRZ

Dowód pełności KRZ

Dowód pełności składa się z dwóch części

1

dowodu, że dla każdej formuły ϕ KRZ, istnieje taka formuła K KRZ,
która:

jest równoważna ϕ (tzn. ` ϕ ≡ K),
ma pewną specjalną budowę, zwaną koniunkcyjną postacią normalną.

2

dowodu, że jeżeli ϕ ma koniunkcyjną postać normalną i  ϕ, to ` ϕ.

background image

Klasyczny Rachunek Zdań (część III)

Dowód pełności KRZ

Dowód pełności KRZ

Dowód pełności składa się z dwóch części

1

dowodu, że dla każdej formuły ϕ KRZ, istnieje taka formuła K KRZ,
która:

jest równoważna ϕ (tzn. ` ϕ ≡ K),
ma pewną specjalną budowę, zwaną koniunkcyjną postacią normalną.

2

dowodu, że jeżeli ϕ ma koniunkcyjną postać normalną i  ϕ, to ` ϕ.

background image

Klasyczny Rachunek Zdań (część III)

Dowód pełności KRZ

Ogólnie o koniunkcyjnej postaci normalnej

Koniunkcyjna postać normalna (KPN) jest formułą KRZ
Koniunkcyjna postać normalna jest wieloczynnikową koniunkcją
wieloskładnikowych alternatyw zmiennych zdaniowych lub ich
negacji.

W skrajnym przypadku taka wieloczynnikowa koniunkcja ma tylko
jeden czynnik: jedną wieloskładnikową alternatywą.

W skrajnym przypadku taka wieloskładnikowa alternatywna ma tylko
jeden składnik: zmienną zdaniową lub negację zmiennej zdaniowej.

background image

Klasyczny Rachunek Zdań (część III)

Dowód pełności KRZ

Ogólnie o koniunkcyjnej postaci normalnej

Koniunkcyjna postać normalna (KPN) jest formułą KRZ

Koniunkcyjna postać normalna jest wieloczynnikową koniunkcją
wieloskładnikowych alternatyw zmiennych zdaniowych lub ich
negacji.

W skrajnym przypadku taka wieloczynnikowa koniunkcja ma tylko
jeden czynnik: jedną wieloskładnikową alternatywą.

W skrajnym przypadku taka wieloskładnikowa alternatywna ma tylko
jeden składnik: zmienną zdaniową lub negację zmiennej zdaniowej.

background image

Klasyczny Rachunek Zdań (część III)

Dowód pełności KRZ

Ogólnie o koniunkcyjnej postaci normalnej

Koniunkcyjna postać normalna (KPN) jest formułą KRZ
Koniunkcyjna postać normalna jest wieloczynnikową koniunkcją
wieloskładnikowych alternatyw zmiennych zdaniowych lub ich
negacji.

W skrajnym przypadku taka wieloczynnikowa koniunkcja ma tylko
jeden czynnik: jedną wieloskładnikową alternatywą.

W skrajnym przypadku taka wieloskładnikowa alternatywna ma tylko
jeden składnik: zmienną zdaniową lub negację zmiennej zdaniowej.

background image

Klasyczny Rachunek Zdań (część III)

Dowód pełności KRZ

Ogólnie o koniunkcyjnej postaci normalnej

Koniunkcyjna postać normalna (KPN) jest formułą KRZ
Koniunkcyjna postać normalna jest wieloczynnikową koniunkcją
wieloskładnikowych alternatyw zmiennych zdaniowych lub ich
negacji.

W skrajnym przypadku taka wieloczynnikowa koniunkcja ma tylko
jeden czynnik: jedną wieloskładnikową alternatywą.

W skrajnym przypadku taka wieloskładnikowa alternatywna ma tylko
jeden składnik: zmienną zdaniową lub negację zmiennej zdaniowej.

background image

Klasyczny Rachunek Zdań (część III)

Dowód pełności KRZ

Ogólnie o koniunkcyjnej postaci normalnej

Koniunkcyjna postać normalna (KPN) jest formułą KRZ
Koniunkcyjna postać normalna jest wieloczynnikową koniunkcją
wieloskładnikowych alternatyw zmiennych zdaniowych lub ich
negacji.

W skrajnym przypadku taka wieloczynnikowa koniunkcja ma tylko
jeden czynnik: jedną wieloskładnikową alternatywą.

W skrajnym przypadku taka wieloskładnikowa alternatywna ma tylko
jeden składnik: zmienną zdaniową lub negację zmiennej zdaniowej.

background image

Klasyczny Rachunek Zdań (część III)

Dowód pełności KRZ

Koniunkcyjne postaci normalne

Definicja

Alternatywą elementarną jest:

każda zmienna zdaniowa,

każda negacja zmiennej zdaniowej,

każda n-składnikowa alternatywa zmiennych lub ich negacji (n > 1).

Definicja

Koniunkcyjną postacią normalną jest k-czynnikowa koniunkcja alternatyw
elementarnych.

background image

Klasyczny Rachunek Zdań (część III)

Dowód pełności KRZ

Koniunkcyjne postaci normalne

Definicja

Alternatywą elementarną jest:

każda zmienna zdaniowa,

każda negacja zmiennej zdaniowej,

każda n-składnikowa alternatywa zmiennych lub ich negacji (n > 1).

Definicja

Koniunkcyjną postacią normalną jest k-czynnikowa koniunkcja alternatyw
elementarnych.

background image

Klasyczny Rachunek Zdań (część III)

Dowód pełności KRZ

Koniunkcyjne postaci normalne

Definicja

Alternatywą elementarną jest:

każda zmienna zdaniowa,

każda negacja zmiennej zdaniowej,

każda n-składnikowa alternatywa zmiennych lub ich negacji (n > 1).

Definicja

Koniunkcyjną postacią normalną jest k-czynnikowa koniunkcja alternatyw
elementarnych.

background image

Klasyczny Rachunek Zdań (część III)

Dowód pełności KRZ

KPN – przykłady

Tabela:

Przykłady KPN i non-KPN

KPN

non − KPN

p

¬¬p

p q

p p q

p ∧ (p q) ∧ (q r ∨ ¬p)

p q

background image

Klasyczny Rachunek Zdań (część III)

Dowód pełności KRZ

Formuła KRZ a KPN

Fakt

Każda formuła KRZ (zanotowana za pomocą zmiennych i co najwyżej
znaków
¬, →, ∧, ∨, ≡) jest równoważna pewnej koniunkcyjnej postaci
normalnej
K.

Aby dowolną formułę ϕ KRZ przekształcić na KPN należy użyć
praw:

1

` ¬¬ϕ ≡ ϕ,

2

` ϕ ∧ ψ ≡ ψ ∧ ϕ, ` ϕ ∨ ψ ≡ ψ ∨ ϕ,

3

` ϕ ∧ ψ ∨ χ ≡ (ϕ ∨ χ) ∧ (ψ ∨ χ), ` (ϕ ∨ ψ) ∧ χ ≡ ϕ ∧ χ ∨ ψ ∧ χ,

4

` ϕ → ψ ≡ ¬ϕ ∨ ψ ≡ ¬(ϕ ∧ ¬ψ),

5

` ϕ ≡ ψ ≡ (¬ϕ ∨ ψ) ∧ (¬ψ ∨ ϕ),

6

` ¬(ϕ ∧ ψ) ≡ ¬ϕ ∨ ¬ψ, ` ¬(ϕ ∨ ψ) ≡ ¬ϕ ∧ ¬ψ

oraz wtórnej reguły ekstensjonalności:

ϕ ≡ ψ

ϕ ≡ ψ

χ

χ ≡ χ(ϕ//ψ)

χ(ϕ//ψ)

gdzie “χ(ϕ//ψ)” to wyrażenie, które powstaje z wyrażenia χ przez zastąpienie ϕ
przez ψ.

background image

Klasyczny Rachunek Zdań (część III)

Dowód pełności KRZ

Formuła KRZ a KPN

Fakt

Każda formuła KRZ (zanotowana za pomocą zmiennych i co najwyżej
znaków
¬, →, ∧, ∨, ≡) jest równoważna pewnej koniunkcyjnej postaci
normalnej
K.

Aby dowolną formułę ϕ KRZ przekształcić na KPN należy użyć
praw:

1

` ¬¬ϕ ≡ ϕ,

2

` ϕ ∧ ψ ≡ ψ ∧ ϕ, ` ϕ ∨ ψ ≡ ψ ∨ ϕ,

3

` ϕ ∧ ψ ∨ χ ≡ (ϕ ∨ χ) ∧ (ψ ∨ χ), ` (ϕ ∨ ψ) ∧ χ ≡ ϕ ∧ χ ∨ ψ ∧ χ,

4

` ϕ → ψ ≡ ¬ϕ ∨ ψ ≡ ¬(ϕ ∧ ¬ψ),

5

` ϕ ≡ ψ ≡ (¬ϕ ∨ ψ) ∧ (¬ψ ∨ ϕ),

6

` ¬(ϕ ∧ ψ) ≡ ¬ϕ ∨ ¬ψ, ` ¬(ϕ ∨ ψ) ≡ ¬ϕ ∧ ¬ψ

oraz wtórnej reguły ekstensjonalności:

ϕ ≡ ψ

ϕ ≡ ψ

χ

χ ≡ χ(ϕ//ψ)

χ(ϕ//ψ)

gdzie “χ(ϕ//ψ)” to wyrażenie, które powstaje z wyrażenia χ przez zastąpienie ϕ
przez ψ.

background image

Klasyczny Rachunek Zdań (część III)

Dowód pełności KRZ

Formuła KRZ a KPN

Fakt

Każda formuła KRZ (zanotowana za pomocą zmiennych i co najwyżej
znaków
¬, →, ∧, ∨, ≡) jest równoważna pewnej koniunkcyjnej postaci
normalnej
K.

Aby dowolną formułę ϕ KRZ przekształcić na KPN należy użyć
praw:

1

` ¬¬ϕ ≡ ϕ,

2

` ϕ ∧ ψ ≡ ψ ∧ ϕ, ` ϕ ∨ ψ ≡ ψ ∨ ϕ,

3

` ϕ ∧ ψ ∨ χ ≡ (ϕ ∨ χ) ∧ (ψ ∨ χ), ` (ϕ ∨ ψ) ∧ χ ≡ ϕ ∧ χ ∨ ψ ∧ χ,

4

` ϕ → ψ ≡ ¬ϕ ∨ ψ ≡ ¬(ϕ ∧ ¬ψ),

5

` ϕ ≡ ψ ≡ (¬ϕ ∨ ψ) ∧ (¬ψ ∨ ϕ),

6

` ¬(ϕ ∧ ψ) ≡ ¬ϕ ∨ ¬ψ, ` ¬(ϕ ∨ ψ) ≡ ¬ϕ ∧ ¬ψ

oraz wtórnej reguły ekstensjonalności:

ϕ ≡ ψ

ϕ ≡ ψ

χ

χ ≡ χ(ϕ//ψ)

χ(ϕ//ψ)

gdzie “χ(ϕ//ψ)” to wyrażenie, które powstaje z wyrażenia χ przez zastąpienie ϕ
przez ψ.

background image

Klasyczny Rachunek Zdań (część III)

Dowód pełności KRZ

Od dowolnej formuły KRZ do jej KPN – przykład

1

` ¬¬ϕ ≡ ϕ,

2

` ϕ ∧ ψ ≡ ψ ∧ ϕ, ` ϕ ∨ ψ ≡ ψ ∨ ϕ,

3

` ϕ ∧ ψ ∨ χ ≡ (ϕ ∨ χ) ∧ (ψ ∨ χ), ` (ϕ ∨ ψ) ∧ χ ≡ ϕ ∧ χ ∨ ψ ∧ χ,

4

` ϕ → ψ ≡ ¬ϕ ∨ ψ ≡ ¬(ϕ ∧ ¬ψ),

5

` ϕ ≡ ψ ≡ (¬ϕ ∨ ψ) ∧ (¬ψ ∨ ϕ),

6

` ¬(ϕ ∧ ψ) ≡ ¬ϕ ∨ ¬ψ, ` ¬(ϕ ∨ ψ) ≡ ¬ϕ ∧ ¬ψ

Przykład

(p q) ∧ p q ≡ ¬((p q) ∧ p) ∨ q ≡ ¬(p q) ∨ ¬p q
p ∧ ¬q ∨ ¬p q ≡ (p ∨ ¬p q) ∧ (¬q ∨ ¬p q)

background image

Klasyczny Rachunek Zdań (część III)

Dowód pełności KRZ

Od dowolnej formuły KRZ do jej KPN – przykład

1

` ¬¬ϕ ≡ ϕ,

2

` ϕ ∧ ψ ≡ ψ ∧ ϕ, ` ϕ ∨ ψ ≡ ψ ∨ ϕ,

3

` ϕ ∧ ψ ∨ χ ≡ (ϕ ∨ χ) ∧ (ψ ∨ χ), ` (ϕ ∨ ψ) ∧ χ ≡ ϕ ∧ χ ∨ ψ ∧ χ,

4

` ϕ → ψ ≡ ¬ϕ ∨ ψ ≡ ¬(ϕ ∧ ¬ψ),

5

` ϕ ≡ ψ ≡ (¬ϕ ∨ ψ) ∧ (¬ψ ∨ ϕ),

6

` ¬(ϕ ∧ ψ) ≡ ¬ϕ ∨ ¬ψ, ` ¬(ϕ ∨ ψ) ≡ ¬ϕ ∧ ¬ψ

Przykład

(p q) ∧ p q

≡ ¬((p q) ∧ p) ∨ q ≡ ¬(p q) ∨ ¬p q

p ∧ ¬q ∨ ¬p q ≡ (p ∨ ¬p q) ∧ (¬q ∨ ¬p q)

background image

Klasyczny Rachunek Zdań (część III)

Dowód pełności KRZ

Od dowolnej formuły KRZ do jej KPN – przykład

1

` ¬¬ϕ ≡ ϕ,

2

` ϕ ∧ ψ ≡ ψ ∧ ϕ, ` ϕ ∨ ψ ≡ ψ ∨ ϕ,

3

` ϕ ∧ ψ ∨ χ ≡ (ϕ ∨ χ) ∧ (ψ ∨ χ), ` (ϕ ∨ ψ) ∧ χ ≡ ϕ ∧ χ ∨ ψ ∧ χ,

4

` ϕ → ψ ≡ ¬ϕ ∨ ψ ≡ ¬(ϕ ∧ ¬ψ),

5

` ϕ ≡ ψ ≡ (¬ϕ ∨ ψ) ∧ (¬ψ ∨ ϕ),

6

` ¬(ϕ ∧ ψ) ≡ ¬ϕ ∨ ¬ψ, ` ¬(ϕ ∨ ψ) ≡ ¬ϕ ∧ ¬ψ

Przykład

(p q) ∧ p q ≡ ¬((p q) ∧ p) ∨ q

≡ ¬(p q) ∨ ¬p q

p ∧ ¬q ∨ ¬p q ≡ (p ∨ ¬p q) ∧ (¬q ∨ ¬p q)

background image

Klasyczny Rachunek Zdań (część III)

Dowód pełności KRZ

Od dowolnej formuły KRZ do jej KPN – przykład

1

` ¬¬ϕ ≡ ϕ,

2

` ϕ ∧ ψ ≡ ψ ∧ ϕ, ` ϕ ∨ ψ ≡ ψ ∨ ϕ,

3

` ϕ ∧ ψ ∨ χ ≡ (ϕ ∨ χ) ∧ (ψ ∨ χ), ` (ϕ ∨ ψ) ∧ χ ≡ ϕ ∧ χ ∨ ψ ∧ χ,

4

` ϕ → ψ ≡ ¬ϕ ∨ ψ ≡ ¬(ϕ ∧ ¬ψ),

5

` ϕ ≡ ψ ≡ (¬ϕ ∨ ψ) ∧ (¬ψ ∨ ϕ),

6

` ¬(ϕ ∧ ψ) ≡ ¬ϕ ∨ ¬ψ, ` ¬(ϕ ∨ ψ) ≡ ¬ϕ ∧ ¬ψ

Przykład

(p q) ∧ p q ≡ ¬((p q) ∧ p) ∨ q ≡ ¬(p q) ∨ ¬p q

p ∧ ¬q ∨ ¬p q ≡ (p ∨ ¬p q) ∧ (¬q ∨ ¬p q)

background image

Klasyczny Rachunek Zdań (część III)

Dowód pełności KRZ

Od dowolnej formuły KRZ do jej KPN – przykład

1

` ¬¬ϕ ≡ ϕ,

2

` ϕ ∧ ψ ≡ ψ ∧ ϕ, ` ϕ ∨ ψ ≡ ψ ∨ ϕ,

3

` ϕ ∧ ψ ∨ χ ≡ (ϕ ∨ χ) ∧ (ψ ∨ χ), ` (ϕ ∨ ψ) ∧ χ ≡ ϕ ∧ χ ∨ ψ ∧ χ,

4

` ϕ → ψ ≡ ¬ϕ ∨ ψ ≡ ¬(ϕ ∧ ¬ψ),

5

` ϕ ≡ ψ ≡ (¬ϕ ∨ ψ) ∧ (¬ψ ∨ ϕ),

6

` ¬(ϕ ∧ ψ) ≡ ¬ϕ ∨ ¬ψ, ` ¬(ϕ ∨ ψ) ≡ ¬ϕ ∧ ¬ψ

Przykład

(p q) ∧ p q ≡ ¬((p q) ∧ p) ∨ q ≡ ¬(p q) ∨ ¬p q
p ∧ ¬q ∨ ¬p q

≡ (p ∨ ¬p q) ∧ (¬q ∨ ¬p q)

background image

Klasyczny Rachunek Zdań (część III)

Dowód pełności KRZ

Od dowolnej formuły KRZ do jej KPN – przykład

1

` ¬¬ϕ ≡ ϕ,

2

` ϕ ∧ ψ ≡ ψ ∧ ϕ, ` ϕ ∨ ψ ≡ ψ ∨ ϕ,

3

` ϕ ∧ ψ ∨ χ ≡ (ϕ ∨ χ) ∧ (ψ ∨ χ), ` (ϕ ∨ ψ) ∧ χ ≡ ϕ ∧ χ ∨ ψ ∧ χ,

4

` ϕ → ψ ≡ ¬ϕ ∨ ψ ≡ ¬(ϕ ∧ ¬ψ),

5

` ϕ ≡ ψ ≡ (¬ϕ ∨ ψ) ∧ (¬ψ ∨ ϕ),

6

` ¬(ϕ ∧ ψ) ≡ ¬ϕ ∨ ¬ψ, ` ¬(ϕ ∨ ψ) ≡ ¬ϕ ∧ ¬ψ

Przykład

(p q) ∧ p q ≡ ¬((p q) ∧ p) ∨ q ≡ ¬(p q) ∨ ¬p q
p ∧ ¬q ∨ ¬p q ≡ (p ∨ ¬p q) ∧ (¬q ∨ ¬p q)

background image

Klasyczny Rachunek Zdań (część III)

Dowód pełności KRZ

Kiedy koniunkcyjna postać normalna jest tautologią?

Fakt

Koniunkcyjna postać normalna K jest tautologią wtedy i tylko wtedy gdy,
w każdej alternatywie elementarnej, która jest częścią
K, przynajmniej
jedna zmienna zdaniowa występuje raz ze znakiem negacji, a raz bez
znaku negacji.

Dowód oczywisty, wystarczy spojrzeć i chwilę pomyśleć:
 (p

i

1

p

i

2

∨ · · · ∨

p

i

k

∨ · · · ∨

¬p

i

k

∨ · · · ∨ p

i

n1

) ∧ (p

j

1

p

j

2

∨ · · · ∨

p

j

n

· · · ∨

¬p

j

n

∨ · · · ∨ p

j

n2

) ∧ · · · ∧ (p

l

1

p

l

2

∨ · · · ∨

p

l

m

∨ · · · ∨

¬p

l

m

∨ · · · ∨ p

l

nr

)

background image

Klasyczny Rachunek Zdań (część III)

Dowód pełności KRZ

Kiedy koniunkcyjna postać normalna jest tautologią?

Fakt

Koniunkcyjna postać normalna K jest tautologią wtedy i tylko wtedy gdy,
w każdej alternatywie elementarnej, która jest częścią
K, przynajmniej
jedna zmienna zdaniowa występuje raz ze znakiem negacji, a raz bez
znaku negacji.

Dowód oczywisty, wystarczy spojrzeć i chwilę pomyśleć:
 (p

i

1

p

i

2

∨ · · · ∨

p

i

k

∨ · · · ∨

¬p

i

k

∨ · · · ∨ p

i

n1

) ∧ (p

j

1

p

j

2

∨ · · · ∨

p

j

n

· · · ∨

¬p

j

n

∨ · · · ∨ p

j

n2

) ∧ · · · ∧ (p

l

1

p

l

2

∨ · · · ∨

p

l

m

∨ · · · ∨

¬p

l

m

∨ · · · ∨ p

l

nr

)

background image

Klasyczny Rachunek Zdań (część III)

Dowód pełności KRZ

Kiedy koniunkcyjna postać normalna jest tautologią?

Fakt

Koniunkcyjna postać normalna K jest tautologią wtedy i tylko wtedy gdy,
w każdej alternatywie elementarnej, która jest częścią
K, przynajmniej
jedna zmienna zdaniowa występuje raz ze znakiem negacji, a raz bez
znaku negacji.

Dowód oczywisty, wystarczy spojrzeć i chwilę pomyśleć:
 (p

i

1

p

i

2

∨ · · · ∨

p

i

k

∨ · · · ∨

¬p

i

k

∨ · · · ∨ p

i

n1

) ∧ (p

j

1

p

j

2

∨ · · · ∨

p

j

n

· · · ∨

¬p

j

n

∨ · · · ∨ p

j

n2

) ∧ · · · ∧ (p

l

1

p

l

2

∨ · · · ∨

p

l

m

∨ · · · ∨

¬p

l

m

∨ · · · ∨ p

l

nr

)

background image

Klasyczny Rachunek Zdań (część III)

Dowód pełności KRZ

Kiedy koniunkcyjna postać normalna jest tezą?

Fakt

Każda prawdziwa koniunkcyjna postać normalna K jest tezą
założeniowego systemu KRZ.

Należy pokazać, że:
` (p

i

1

p

i

2

∨ · · · ∨

p

i

k

∨ · · · ∨

¬p

i

k

∨ · · · ∨ p

i

n1

) ∧ (p

j

1

p

j

2

∨ · · · ∨

p

j

n

· · · ∨

¬p

j

n

∨ · · · ∨ p

j

n2

) ∧ · · · ∧ (p

l

1

p

l

2

∨ · · · ∨

p

l

m

∨ · · · ∨

¬p

l

m

∨ · · · ∨ p

l

nr

)

background image

Klasyczny Rachunek Zdań (część III)

Dowód pełności KRZ

Kiedy koniunkcyjna postać normalna jest tezą?

Fakt

Każda prawdziwa koniunkcyjna postać normalna K jest tezą
założeniowego systemu KRZ.

Należy pokazać, że:
` (p

i

1

p

i

2

∨ · · · ∨

p

i

k

∨ · · · ∨

¬p

i

k

∨ · · · ∨ p

i

n1

) ∧ (p

j

1

p

j

2

∨ · · · ∨

p

j

n

· · · ∨

¬p

j

n

∨ · · · ∨ p

j

n2

) ∧ · · · ∧ (p

l

1

p

l

2

∨ · · · ∨

p

l

m

∨ · · · ∨

¬p

l

m

∨ · · · ∨ p

l

nr

)

background image

Klasyczny Rachunek Zdań (część III)

Dowód pełności KRZ

Kiedy koniunkcyjna postać normalna jest tezą?

Fakt

Każda prawdziwa koniunkcyjna postać normalna K jest tezą
założeniowego systemu KRZ.

Należy pokazać, że:
` (p

i

1

p

i

2

∨ · · · ∨

p

i

k

∨ · · · ∨

¬p

i

k

∨ · · · ∨ p

i

n1

) ∧ (p

j

1

p

j

2

∨ · · · ∨

p

j

n

· · · ∨

¬p

j

n

∨ · · · ∨ p

j

n2

) ∧ · · · ∧ (p

l

1

p

l

2

∨ · · · ∨

p

l

m

∨ · · · ∨

¬p

l

m

∨ · · · ∨ p

l

nr

)

background image

Klasyczny Rachunek Zdań (część III)

Dowód pełności KRZ

Kiedy koniunkcyjna postać normalna jest tezą?

We¨

umy pierwszy człon koniunkcji wyrażenia z poprzedniego slajdu, tj.

p

i

1

p

i

2

∨ · · · ∨ p

i

k

∨ · · · ∨ ¬p

i

k

∨ · · · ∨ p

i

n1

Pokażemy, że to wyrażenie jest tezą:

1.

¬(p

i

1

p

i

2

∨ · · · ∨ p

i

k

∨ · · · ∨ ¬p

i

k

∨ · · · ∨ p

i

n1

)

z.d .n.

2.

¬p

i

1

NA : 1

3.

¬p

i

2

NA : 1

. . .

. . .

NA : 1

k + 1.

¬p

i

k

NA : 1

. . .

. . .

NA : 1

l .

¬¬p

i

k

NA : 1

. . .

. . .

NA : 1

n

1

.

¬p

i

n1

NA : 1

sprz. : k + 1, l

Podobnie dowodzimy dla wszystkich członów KPN z poprzedniego
slajdu.

background image

Klasyczny Rachunek Zdań (część III)

Dowód pełności KRZ

Kiedy koniunkcyjna postać normalna jest tezą?

We¨

umy pierwszy człon koniunkcji wyrażenia z poprzedniego slajdu, tj.

p

i

1

p

i

2

∨ · · · ∨ p

i

k

∨ · · · ∨ ¬p

i

k

∨ · · · ∨ p

i

n1

Pokażemy, że to wyrażenie jest tezą:

1.

¬(p

i

1

p

i

2

∨ · · · ∨ p

i

k

∨ · · · ∨ ¬p

i

k

∨ · · · ∨ p

i

n1

)

z.d .n.

2.

¬p

i

1

NA : 1

3.

¬p

i

2

NA : 1

. . .

. . .

NA : 1

k + 1.

¬p

i

k

NA : 1

. . .

. . .

NA : 1

l .

¬¬p

i

k

NA : 1

. . .

. . .

NA : 1

n

1

.

¬p

i

n1

NA : 1

sprz. : k + 1, l

Podobnie dowodzimy dla wszystkich członów KPN z poprzedniego
slajdu.

background image

Klasyczny Rachunek Zdań (część III)

Dowód pełności KRZ

Kiedy koniunkcyjna postać normalna jest tezą?

We¨

umy pierwszy człon koniunkcji wyrażenia z poprzedniego slajdu, tj.

p

i

1

p

i

2

∨ · · · ∨ p

i

k

∨ · · · ∨ ¬p

i

k

∨ · · · ∨ p

i

n1

Pokażemy, że to wyrażenie jest tezą:

1.

¬(p

i

1

p

i

2

∨ · · · ∨ p

i

k

∨ · · · ∨ ¬p

i

k

∨ · · · ∨ p

i

n1

)

z.d .n.

2.

¬p

i

1

NA : 1

3.

¬p

i

2

NA : 1

. . .

. . .

NA : 1

k + 1.

¬p

i

k

NA : 1

. . .

. . .

NA : 1

l .

¬¬p

i

k

NA : 1

. . .

. . .

NA : 1

n

1

.

¬p

i

n1

NA : 1

sprz. : k + 1, l

Podobnie dowodzimy dla wszystkich członów KPN z poprzedniego
slajdu.

background image

Klasyczny Rachunek Zdań (część III)

Dowód pełności KRZ

Kiedy koniunkcyjna postać normalna jest tezą?

We¨

umy pierwszy człon koniunkcji wyrażenia z poprzedniego slajdu, tj.

p

i

1

p

i

2

∨ · · · ∨ p

i

k

∨ · · · ∨ ¬p

i

k

∨ · · · ∨ p

i

n1

Pokażemy, że to wyrażenie jest tezą:

1.

¬(p

i

1

p

i

2

∨ · · · ∨ p

i

k

∨ · · · ∨ ¬p

i

k

∨ · · · ∨ p

i

n1

)

z.d .n.

2.

¬p

i

1

NA : 1

3.

¬p

i

2

NA : 1

. . .

. . .

NA : 1

k + 1.

¬p

i

k

NA : 1

. . .

. . .

NA : 1

l .

¬¬p

i

k

NA : 1

. . .

. . .

NA : 1

n

1

.

¬p

i

n1

NA : 1

sprz. : k + 1, l

Podobnie dowodzimy dla wszystkich członów KPN z poprzedniego
slajdu.

background image

Klasyczny Rachunek Zdań (część III)

Dowód pełności KRZ

Kiedy koniunkcyjna postać normalna jest tezą?

We¨

umy pierwszy człon koniunkcji wyrażenia z poprzedniego slajdu, tj.

p

i

1

p

i

2

∨ · · · ∨ p

i

k

∨ · · · ∨ ¬p

i

k

∨ · · · ∨ p

i

n1

Pokażemy, że to wyrażenie jest tezą:

1.

¬(p

i

1

p

i

2

∨ · · · ∨ p

i

k

∨ · · · ∨ ¬p

i

k

∨ · · · ∨ p

i

n1

)

z.d .n.

2.

¬p

i

1

NA : 1

3.

¬p

i

2

NA : 1

. . .

. . .

NA : 1

k + 1.

¬p

i

k

NA : 1

. . .

. . .

NA : 1

l .

¬¬p

i

k

NA : 1

. . .

. . .

NA : 1

n

1

.

¬p

i

n1

NA : 1

sprz. : k + 1, l

Podobnie dowodzimy dla wszystkich członów KPN z poprzedniego
slajdu.

background image

Klasyczny Rachunek Zdań (część III)

Dowód pełności KRZ

Kiedy koniunkcyjna postać normalna jest tezą?

We¨

umy pierwszy człon koniunkcji wyrażenia z poprzedniego slajdu, tj.

p

i

1

p

i

2

∨ · · · ∨ p

i

k

∨ · · · ∨ ¬p

i

k

∨ · · · ∨ p

i

n1

Pokażemy, że to wyrażenie jest tezą:

1.

¬(p

i

1

p

i

2

∨ · · · ∨ p

i

k

∨ · · · ∨ ¬p

i

k

∨ · · · ∨ p

i

n1

)

z.d .n.

2.

¬p

i

1

NA : 1

3.

¬p

i

2

NA : 1

. . .

. . .

NA : 1

k + 1.

¬p

i

k

NA : 1

. . .

. . .

NA : 1

l .

¬¬p

i

k

NA : 1

. . .

. . .

NA : 1

n

1

.

¬p

i

n1

NA : 1

sprz. : k + 1, l

Podobnie dowodzimy dla wszystkich członów KPN z poprzedniego
slajdu.

background image

Klasyczny Rachunek Zdań (część III)

Dowód pełności KRZ

Kiedy koniunkcyjna postać normalna jest tezą?

We¨

umy pierwszy człon koniunkcji wyrażenia z poprzedniego slajdu, tj.

p

i

1

p

i

2

∨ · · · ∨ p

i

k

∨ · · · ∨ ¬p

i

k

∨ · · · ∨ p

i

n1

Pokażemy, że to wyrażenie jest tezą:

1.

¬(p

i

1

p

i

2

∨ · · · ∨ p

i

k

∨ · · · ∨ ¬p

i

k

∨ · · · ∨ p

i

n1

)

z.d .n.

2.

¬p

i

1

NA : 1

3.

¬p

i

2

NA : 1

. . .

. . .

NA : 1

k + 1.

¬p

i

k

NA : 1

. . .

. . .

NA : 1

l .

¬¬p

i

k

NA : 1

. . .

. . .

NA : 1

n

1

.

¬p

i

n1

NA : 1

sprz. : k + 1, l

Podobnie dowodzimy dla wszystkich członów KPN z poprzedniego
slajdu.

background image

Klasyczny Rachunek Zdań (część III)

Dowód pełności KRZ

Kiedy koniunkcyjna postać normalna jest tezą?

We¨

umy pierwszy człon koniunkcji wyrażenia z poprzedniego slajdu, tj.

p

i

1

p

i

2

∨ · · · ∨ p

i

k

∨ · · · ∨ ¬p

i

k

∨ · · · ∨ p

i

n1

Pokażemy, że to wyrażenie jest tezą:

1.

¬(p

i

1

p

i

2

∨ · · · ∨ p

i

k

∨ · · · ∨ ¬p

i

k

∨ · · · ∨ p

i

n1

)

z.d .n.

2.

¬p

i

1

NA : 1

3.

¬p

i

2

NA : 1

. . .

. . .

NA : 1

k + 1.

¬p

i

k

NA : 1

. . .

. . .

NA : 1

l .

¬¬p

i

k

NA : 1

. . .

. . .

NA : 1

n

1

.

¬p

i

n1

NA : 1

sprz. : k + 1, l

Podobnie dowodzimy dla wszystkich członów KPN z poprzedniego
slajdu.

background image

Klasyczny Rachunek Zdań (część III)

Dowód pełności KRZ

Kiedy koniunkcyjna postać normalna jest tezą?

We¨

umy pierwszy człon koniunkcji wyrażenia z poprzedniego slajdu, tj.

p

i

1

p

i

2

∨ · · · ∨ p

i

k

∨ · · · ∨ ¬p

i

k

∨ · · · ∨ p

i

n1

Pokażemy, że to wyrażenie jest tezą:

1.

¬(p

i

1

p

i

2

∨ · · · ∨ p

i

k

∨ · · · ∨ ¬p

i

k

∨ · · · ∨ p

i

n1

)

z.d .n.

2.

¬p

i

1

NA : 1

3.

¬p

i

2

NA : 1

. . .

. . .

NA : 1

k + 1.

¬p

i

k

NA : 1

. . .

. . .

NA : 1

l .

¬¬p

i

k

NA : 1

. . .

. . .

NA : 1

n

1

.

¬p

i

n1

NA : 1

sprz. : k + 1, l

Podobnie dowodzimy dla wszystkich członów KPN z poprzedniego
slajdu.

background image

Klasyczny Rachunek Zdań (część III)

Dowód pełności KRZ

Kiedy koniunkcyjna postać normalna jest tezą?

We¨

umy pierwszy człon koniunkcji wyrażenia z poprzedniego slajdu, tj.

p

i

1

p

i

2

∨ · · · ∨ p

i

k

∨ · · · ∨ ¬p

i

k

∨ · · · ∨ p

i

n1

Pokażemy, że to wyrażenie jest tezą:

1.

¬(p

i

1

p

i

2

∨ · · · ∨ p

i

k

∨ · · · ∨ ¬p

i

k

∨ · · · ∨ p

i

n1

)

z.d .n.

2.

¬p

i

1

NA : 1

3.

¬p

i

2

NA : 1

. . .

. . .

NA : 1

k + 1.

¬p

i

k

NA : 1

. . .

. . .

NA : 1

l .

¬¬p

i

k

NA : 1

. . .

. . .

NA : 1

n

1

.

¬p

i

n1

NA : 1

sprz. : k + 1, l

Podobnie dowodzimy dla wszystkich członów KPN z poprzedniego
slajdu.

background image

Klasyczny Rachunek Zdań (część III)

Dowód pełności KRZ

Kiedy koniunkcyjna postać normalna jest tezą?

We¨

umy pierwszy człon koniunkcji wyrażenia z poprzedniego slajdu, tj.

p

i

1

p

i

2

∨ · · · ∨ p

i

k

∨ · · · ∨ ¬p

i

k

∨ · · · ∨ p

i

n1

Pokażemy, że to wyrażenie jest tezą:

1.

¬(p

i

1

p

i

2

∨ · · · ∨ p

i

k

∨ · · · ∨ ¬p

i

k

∨ · · · ∨ p

i

n1

)

z.d .n.

2.

¬p

i

1

NA : 1

3.

¬p

i

2

NA : 1

. . .

. . .

NA : 1

k + 1.

¬p

i

k

NA : 1

. . .

. . .

NA : 1

l .

¬¬p

i

k

NA : 1

. . .

. . .

NA : 1

n

1

.

¬p

i

n1

NA : 1

sprz. : k + 1, l

Podobnie dowodzimy dla wszystkich członów KPN z poprzedniego
slajdu.

background image

Klasyczny Rachunek Zdań (część III)

Dowód pełności KRZ

Kiedy koniunkcyjna postać normalna jest tezą?

We¨

umy pierwszy człon koniunkcji wyrażenia z poprzedniego slajdu, tj.

p

i

1

p

i

2

∨ · · · ∨ p

i

k

∨ · · · ∨ ¬p

i

k

∨ · · · ∨ p

i

n1

Pokażemy, że to wyrażenie jest tezą:

1.

¬(p

i

1

p

i

2

∨ · · · ∨ p

i

k

∨ · · · ∨ ¬p

i

k

∨ · · · ∨ p

i

n1

)

z.d .n.

2.

¬p

i

1

NA : 1

3.

¬p

i

2

NA : 1

. . .

. . .

NA : 1

k + 1.

¬p

i

k

NA : 1

. . .

. . .

NA : 1

l .

¬¬p

i

k

NA : 1

. . .

. . .

NA : 1

n

1

.

¬p

i

n1

NA : 1

sprz. : k + 1, l

Podobnie dowodzimy dla wszystkich członów KPN z poprzedniego
slajdu.

background image

Klasyczny Rachunek Zdań (część III)

Dowód pełności KRZ

Kiedy koniunkcyjna postać normalna jest tezą?

We¨

umy pierwszy człon koniunkcji wyrażenia z poprzedniego slajdu, tj.

p

i

1

p

i

2

∨ · · · ∨ p

i

k

∨ · · · ∨ ¬p

i

k

∨ · · · ∨ p

i

n1

Pokażemy, że to wyrażenie jest tezą:

1.

¬(p

i

1

p

i

2

∨ · · · ∨ p

i

k

∨ · · · ∨ ¬p

i

k

∨ · · · ∨ p

i

n1

)

z.d .n.

2.

¬p

i

1

NA : 1

3.

¬p

i

2

NA : 1

. . .

. . .

NA : 1

k + 1.

¬p

i

k

NA : 1

. . .

. . .

NA : 1

l .

¬¬p

i

k

NA : 1

. . .

. . .

NA : 1

n

1

.

¬p

i

n1

NA : 1

sprz. : k + 1, l

Podobnie dowodzimy dla wszystkich członów KPN z poprzedniego
slajdu.

background image

Klasyczny Rachunek Zdań (część III)

Dowód pełności KRZ

Kiedy koniunkcyjna postać normalna jest tezą?

We¨

umy pierwszy człon koniunkcji wyrażenia z poprzedniego slajdu, tj.

p

i

1

p

i

2

∨ · · · ∨ p

i

k

∨ · · · ∨ ¬p

i

k

∨ · · · ∨ p

i

n1

Pokażemy, że to wyrażenie jest tezą:

1.

¬(p

i

1

p

i

2

∨ · · · ∨ p

i

k

∨ · · · ∨ ¬p

i

k

∨ · · · ∨ p

i

n1

)

z.d .n.

2.

¬p

i

1

NA : 1

3.

¬p

i

2

NA : 1

. . .

. . .

NA : 1

k + 1.

¬p

i

k

NA : 1

. . .

. . .

NA : 1

l .

¬¬p

i

k

NA : 1

. . .

. . .

NA : 1

n

1

.

¬p

i

n1

NA : 1

sprz. : k + 1, l

Podobnie dowodzimy dla wszystkich członów KPN z poprzedniego
slajdu.

background image

Klasyczny Rachunek Zdań (część III)

Dowód pełności KRZ

Kiedy koniunkcyjna postać normalna jest tezą?

Ostatecznie dowodzimy, że każda tautologia o postaci KPN jest tezą
KRZ w następujący sposób:

1.

p

i

1

p

i

2

∨ · · · ∨ p

i

n1

teza

2.

p

j

1

p

j

2

∨ · · · ∨ p

j

n2

teza

. . . .

. . .

teza

n

r

.

(p

l

1

p

l

2

∨ · · · ∨ p

l

nr

)

teza

(p

i

1

p

i

2

∨ · · · ∨ p

i

n1

)∧

∧(p

j

1

p

j

2

∨ · · · ∨ p

j

n2

) ∧ . . .

· · · ∧ (p

l

1

p

l

2

∨ · · · ∨ p

l

nr

)

n × DK : 1, 2, . . . , n

r

background image

Klasyczny Rachunek Zdań (część III)

Dowód pełności KRZ

Kiedy koniunkcyjna postać normalna jest tezą?

Ostatecznie dowodzimy, że każda tautologia o postaci KPN jest tezą
KRZ w następujący sposób:

1.

p

i

1

p

i

2

∨ · · · ∨ p

i

n1

teza

2.

p

j

1

p

j

2

∨ · · · ∨ p

j

n2

teza

. . . .

. . .

teza

n

r

.

(p

l

1

p

l

2

∨ · · · ∨ p

l

nr

)

teza

(p

i

1

p

i

2

∨ · · · ∨ p

i

n1

)∧

∧(p

j

1

p

j

2

∨ · · · ∨ p

j

n2

) ∧ . . .

· · · ∧ (p

l

1

p

l

2

∨ · · · ∨ p

l

nr

)

n × DK : 1, 2, . . . , n

r

background image

Klasyczny Rachunek Zdań (część III)

Dowód pełności KRZ

Kiedy koniunkcyjna postać normalna jest tezą?

Ostatecznie dowodzimy, że każda tautologia o postaci KPN jest tezą
KRZ w następujący sposób:

1.

p

i

1

p

i

2

∨ · · · ∨ p

i

n1

teza

2.

p

j

1

p

j

2

∨ · · · ∨ p

j

n2

teza

. . . .

. . .

teza

n

r

.

(p

l

1

p

l

2

∨ · · · ∨ p

l

nr

)

teza

(p

i

1

p

i

2

∨ · · · ∨ p

i

n1

)∧

∧(p

j

1

p

j

2

∨ · · · ∨ p

j

n2

) ∧ . . .

· · · ∧ (p

l

1

p

l

2

∨ · · · ∨ p

l

nr

)

n × DK : 1, 2, . . . , n

r

background image

Klasyczny Rachunek Zdań (część III)

Dowód pełności KRZ

Kiedy koniunkcyjna postać normalna jest tezą?

Ostatecznie dowodzimy, że każda tautologia o postaci KPN jest tezą
KRZ w następujący sposób:

1.

p

i

1

p

i

2

∨ · · · ∨ p

i

n1

teza

2.

p

j

1

p

j

2

∨ · · · ∨ p

j

n2

teza

. . . .

. . .

teza

n

r

.

(p

l

1

p

l

2

∨ · · · ∨ p

l

nr

)

teza

(p

i

1

p

i

2

∨ · · · ∨ p

i

n1

)∧

∧(p

j

1

p

j

2

∨ · · · ∨ p

j

n2

) ∧ . . .

· · · ∧ (p

l

1

p

l

2

∨ · · · ∨ p

l

nr

)

n × DK : 1, 2, . . . , n

r

background image

Klasyczny Rachunek Zdań (część III)

Dowód pełności KRZ

Kiedy koniunkcyjna postać normalna jest tezą?

Ostatecznie dowodzimy, że każda tautologia o postaci KPN jest tezą
KRZ w następujący sposób:

1.

p

i

1

p

i

2

∨ · · · ∨ p

i

n1

teza

2.

p

j

1

p

j

2

∨ · · · ∨ p

j

n2

teza

. . . .

. . .

teza

n

r

.

(p

l

1

p

l

2

∨ · · · ∨ p

l

nr

)

teza

(p

i

1

p

i

2

∨ · · · ∨ p

i

n1

)∧

∧(p

j

1

p

j

2

∨ · · · ∨ p

j

n2

) ∧ . . .

· · · ∧ (p

l

1

p

l

2

∨ · · · ∨ p

l

nr

)

n × DK : 1, 2, . . . , n

r

background image

Klasyczny Rachunek Zdań (część III)

Dowód pełności KRZ

Podsumowanie dowódu pełności KRZ

Załóżmy, że ϕ jest wyrażeniem prawdziwym KRZ (tj.  ϕ).
Wówczas istnieje równoważna mu koniunkcyjna postać normalna K
(tj. K ∈ KPN i ` ϕ ≡ K).
Z powayższego otrzymujemy, że:

ϕ ≡ K jest wyrażeniem prawdziwym (tj.  ϕ ≡ K)
− − −− > patrz dowód trafności!

K jest wyrażeniem prawdziwym (tj.  K).

Ponieważ K jest wyrażeniem prawdziwym i KPN, to jest tezą (tj.
` K).
Wówczas tezą jest również ϕ (tj. ` ϕ). Q.E.D.

background image

Klasyczny Rachunek Zdań (część III)

Dowód pełności KRZ

Podsumowanie dowódu pełności KRZ

Załóżmy, że ϕ jest wyrażeniem prawdziwym KRZ (tj.  ϕ).

Wówczas istnieje równoważna mu koniunkcyjna postać normalna K
(tj. K ∈ KPN i ` ϕ ≡ K).
Z powayższego otrzymujemy, że:

ϕ ≡ K jest wyrażeniem prawdziwym (tj.  ϕ ≡ K)
− − −− > patrz dowód trafności!

K jest wyrażeniem prawdziwym (tj.  K).

Ponieważ K jest wyrażeniem prawdziwym i KPN, to jest tezą (tj.
` K).
Wówczas tezą jest również ϕ (tj. ` ϕ). Q.E.D.

background image

Klasyczny Rachunek Zdań (część III)

Dowód pełności KRZ

Podsumowanie dowódu pełności KRZ

Załóżmy, że ϕ jest wyrażeniem prawdziwym KRZ (tj.  ϕ).
Wówczas istnieje równoważna mu koniunkcyjna postać normalna K
(tj. K ∈ KPN i ` ϕ ≡ K).

Z powayższego otrzymujemy, że:

ϕ ≡ K jest wyrażeniem prawdziwym (tj.  ϕ ≡ K)
− − −− > patrz dowód trafności!

K jest wyrażeniem prawdziwym (tj.  K).

Ponieważ K jest wyrażeniem prawdziwym i KPN, to jest tezą (tj.
` K).
Wówczas tezą jest również ϕ (tj. ` ϕ). Q.E.D.

background image

Klasyczny Rachunek Zdań (część III)

Dowód pełności KRZ

Podsumowanie dowódu pełności KRZ

Załóżmy, że ϕ jest wyrażeniem prawdziwym KRZ (tj.  ϕ).
Wówczas istnieje równoważna mu koniunkcyjna postać normalna K
(tj. K ∈ KPN i ` ϕ ≡ K).
Z powayższego otrzymujemy, że:

ϕ ≡ K jest wyrażeniem prawdziwym (tj.  ϕ ≡ K)
− − −− > patrz dowód trafności!

K jest wyrażeniem prawdziwym (tj.  K).

Ponieważ K jest wyrażeniem prawdziwym i KPN, to jest tezą (tj.
` K).
Wówczas tezą jest również ϕ (tj. ` ϕ). Q.E.D.

background image

Klasyczny Rachunek Zdań (część III)

Dowód pełności KRZ

Podsumowanie dowódu pełności KRZ

Załóżmy, że ϕ jest wyrażeniem prawdziwym KRZ (tj.  ϕ).
Wówczas istnieje równoważna mu koniunkcyjna postać normalna K
(tj. K ∈ KPN i ` ϕ ≡ K).
Z powayższego otrzymujemy, że:

ϕ ≡ K jest wyrażeniem prawdziwym (tj.  ϕ ≡ K)
− − −− > patrz dowód trafności!

K jest wyrażeniem prawdziwym (tj.  K).

Ponieważ K jest wyrażeniem prawdziwym i KPN, to jest tezą (tj.
` K).
Wówczas tezą jest również ϕ (tj. ` ϕ). Q.E.D.

background image

Klasyczny Rachunek Zdań (część III)

Dowód pełności KRZ

Podsumowanie dowódu pełności KRZ

Załóżmy, że ϕ jest wyrażeniem prawdziwym KRZ (tj.  ϕ).
Wówczas istnieje równoważna mu koniunkcyjna postać normalna K
(tj. K ∈ KPN i ` ϕ ≡ K).
Z powayższego otrzymujemy, że:

ϕ ≡ K jest wyrażeniem prawdziwym (tj.  ϕ ≡ K)
− − −− > patrz dowód trafności!

K jest wyrażeniem prawdziwym (tj.  K).

Ponieważ K jest wyrażeniem prawdziwym i KPN, to jest tezą (tj.
` K).
Wówczas tezą jest również ϕ (tj. ` ϕ). Q.E.D.

background image

Klasyczny Rachunek Zdań (część III)

Dowód pełności KRZ

Podsumowanie dowódu pełności KRZ

Załóżmy, że ϕ jest wyrażeniem prawdziwym KRZ (tj.  ϕ).
Wówczas istnieje równoważna mu koniunkcyjna postać normalna K
(tj. K ∈ KPN i ` ϕ ≡ K).
Z powayższego otrzymujemy, że:

ϕ ≡ K jest wyrażeniem prawdziwym (tj.  ϕ ≡ K)
− − −− > patrz dowód trafności!

K jest wyrażeniem prawdziwym (tj.  K).

Ponieważ K jest wyrażeniem prawdziwym i KPN, to jest tezą (tj.
` K).

Wówczas tezą jest również ϕ (tj. ` ϕ). Q.E.D.

background image

Klasyczny Rachunek Zdań (część III)

Dowód pełności KRZ

Podsumowanie dowódu pełności KRZ

Załóżmy, że ϕ jest wyrażeniem prawdziwym KRZ (tj.  ϕ).
Wówczas istnieje równoważna mu koniunkcyjna postać normalna K
(tj. K ∈ KPN i ` ϕ ≡ K).
Z powayższego otrzymujemy, że:

ϕ ≡ K jest wyrażeniem prawdziwym (tj.  ϕ ≡ K)
− − −− > patrz dowód trafności!

K jest wyrażeniem prawdziwym (tj.  K).

Ponieważ K jest wyrażeniem prawdziwym i KPN, to jest tezą (tj.
` K).
Wówczas tezą jest również ϕ (tj. ` ϕ). Q.E.D.

background image

Klasyczny Rachunek Zdań (część III)

Podsumowanie dowodów trafności i pełności KRZ

Podsumowanie dowodów trafności i pełności KRZ

Definicja

System logiczny, który jest trafny i pełny nazywamy adekwatnym.

Fakt

KRZ jest systemem adekwatnym.

Fakt

Zbiory tez oraz tautologii KRZ są identyczne.

background image

Klasyczny Rachunek Zdań (część III)

Podsumowanie dowodów trafności i pełności KRZ

Podsumowanie dowodów trafności i pełności KRZ

Definicja

System logiczny, który jest trafny i pełny nazywamy adekwatnym.

Fakt

KRZ jest systemem adekwatnym.

Fakt

Zbiory tez oraz tautologii KRZ są identyczne.

background image

Klasyczny Rachunek Zdań (część III)

Podsumowanie dowodów trafności i pełności KRZ

Podsumowanie dowodów trafności i pełności KRZ

Definicja

System logiczny, który jest trafny i pełny nazywamy adekwatnym.

Fakt

KRZ jest systemem adekwatnym.

Fakt

Zbiory tez oraz tautologii KRZ są identyczne.

background image

Klasyczny Rachunek Zdań (część III)

Podsumowanie dowodów trafności i pełności KRZ

Podsumowanie dowodów trafności i pełności KRZ

Definicja

System logiczny, który jest trafny i pełny nazywamy adekwatnym.

Fakt

KRZ jest systemem adekwatnym.

Fakt

Zbiory tez oraz tautologii KRZ są identyczne.

background image

Klasyczny Rachunek Zdań (część III)

Podsumowanie dowodów trafności i pełności KRZ

Podsumowanie dowodów trafności i pełności KRZ

Definicja

System logiczny jest niesprzeczny wtedy i tylko wtedy, gdy wśród jego
tez nie występują dwa wyrażenia sprzeczne.

Fakt

KRZ jest systemem niesprzecznym.

Powyższy fakt wynika bezpośrednio z trafności KRZ oraz faktu, że dwa
wyrażenia sprzeczne nie są zarazem prawdziwe.

background image

Klasyczny Rachunek Zdań (część III)

Podsumowanie dowodów trafności i pełności KRZ

Podsumowanie dowodów trafności i pełności KRZ

Definicja

System logiczny jest niesprzeczny wtedy i tylko wtedy, gdy wśród jego
tez nie występują dwa wyrażenia sprzeczne.

Fakt

KRZ jest systemem niesprzecznym.

Powyższy fakt wynika bezpośrednio z trafności KRZ oraz faktu, że dwa
wyrażenia sprzeczne nie są zarazem prawdziwe.

background image

Klasyczny Rachunek Zdań (część III)

Podsumowanie dowodów trafności i pełności KRZ

Podsumowanie dowodów trafności i pełności KRZ

Definicja

System logiczny jest niesprzeczny wtedy i tylko wtedy, gdy wśród jego
tez nie występują dwa wyrażenia sprzeczne.

Fakt

KRZ jest systemem niesprzecznym.

Powyższy fakt wynika bezpośrednio z trafności KRZ oraz faktu, że dwa
wyrażenia sprzeczne nie są zarazem prawdziwe.

background image

Klasyczny Rachunek Zdań (część III)

Podsumowanie dowodów trafności i pełności KRZ

Podsumowanie dowodów trafności i pełności KRZ

Definicja

System logiczny jest niesprzeczny wtedy i tylko wtedy, gdy wśród jego
tez nie występują dwa wyrażenia sprzeczne.

Fakt

KRZ jest systemem niesprzecznym.

Powyższy fakt wynika bezpośrednio z trafności KRZ oraz faktu, że dwa
wyrażenia sprzeczne nie są zarazem prawdziwe.


Document Outline


Wyszukiwarka

Podobne podstrony:
03 Klasyczny rachunek zdań świat fcji prawdziwościowychid 4395
Logika, KLASYCZNY RACHUNEK ZDAŃ
moduł 3 Klasyczny rachunek zdań, LOGIKA 2006
Modul 3 Klasyczny rachunek zdan
logika klasyczny rachunek zdan(1)
Klasyczny rachunek zdań Dedukcja naturalna
03 Klasyczny rachunek zdań świat fcji prawdziwościowychid 4395

więcej podobnych podstron