Klasyczny Rachunek Zdań (część I)

Logika dla informatyków

Klasyczny Rachunek Zdań (część I)

Robert Trypuz

Katedra Logiki KUL

17 marca 2011

Klasyczny Rachunek Zdań (część I)

Zarys

1

Krótka historia klasycznego rachunku zdań (KRZ)

2

Język KRZ

Alfabet KRZ
Formuła KRZ

3

Zrozumieć KRZ – metoda 0-1

Czym jest KRZ?
Odczytanie funktorów języka KRZ
Język KRZ jako schemat niektórych zdań języka polskiego
Skrócona metoda P-F

Klasyczny Rachunek Zdań (część I)

Zarys

1

Krótka historia klasycznego rachunku zdań (KRZ)

2

Język KRZ

Alfabet KRZ
Formuła KRZ

3

Zrozumieć KRZ – metoda 0-1

Czym jest KRZ?
Odczytanie funktorów języka KRZ
Język KRZ jako schemat niektórych zdań języka polskiego
Skrócona metoda P-F

Klasyczny Rachunek Zdań (część I)

Zarys

1

Krótka historia klasycznego rachunku zdań (KRZ)

2

Język KRZ

Alfabet KRZ
Formuła KRZ

3

Zrozumieć KRZ – metoda 0-1

Czym jest KRZ?
Odczytanie funktorów języka KRZ
Język KRZ jako schemat niektórych zdań języka polskiego
Skrócona metoda P-F

Klasyczny Rachunek Zdań (część I)

Krótka historia klasycznego rachunku zdań (KRZ)

Krótka historia klasycznego rachunku zdań

filozofia stoicka (III w. przed Chr.) – zmienne zdaniowe!

współczesna ujęcie: Gottlob Frege (Begriffsschrift, 1879)

Polacy: Jan Łukasiewicz, Alfred Tarski

Klasyczny Rachunek Zdań (część I)

Język KRZ

Alfabet KRZ

Alfabet KRZ

Alfabet KRZ zawiera:

nieskończony zbiór zmiennych zdaniowych:
p, q, r , ..., p

1

, q

1

, r

1

, ..., p

2

, q

2

, r

2

, ...

skończony zbiór funktorów prawdziwościowych: ¬, ∧, ∨, →, ≡,

nawiasy: (, ).

Klasyczny Rachunek Zdań (część I)

Język KRZ

Alfabet KRZ

Alfabet KRZ

Alfabet KRZ zawiera:

nieskończony zbiór zmiennych zdaniowych:
p, q, r , ..., p

1

, q

1

, r

1

, ..., p

2

, q

2

, r

2

, ...

skończony zbiór funktorów prawdziwościowych: ¬, ∧, ∨, →, ≡,

nawiasy: (, ).

Klasyczny Rachunek Zdań (część I)

Język KRZ

Formuła KRZ

Definicja indukcyjna formuły KRZ

Formuła , wyrażenie sensowene / gramatycznie poprawne KRZ.

Niech ϕ, ψ będą zmiennymi metajęzykowymi reprezentującymi dowolną
formułę KRZ. Wówczas:

1

Każde z wyrażeń p, q, r , ..., p

1

, q

1

, r

1

, ... jest formułą KRZ

2

Jeżeli ϕ jest formułą KRZ, to jest też nią p¬ϕq

3

Jeżeli ϕ i ψ są formułami KRZ, to są też nimi pϕ → ψq, pϕ ∨ ψq,
pϕ ∧ ψq, pϕ ≡ ψq

Definicja formuła KRZ w BNF

<formula> ::= <formula prosta> | [”(”]<formula zlozona>[”)”]
<formula prosta> ::= ”p” | ”q” | ”r” | ”s” | ”p

1

” | . . . | ”p

n

”

<formula zlozona> ::= ”¬”<formula> | <formula><funktor dwuarg><formula>
<funktor dwuarg> ::= ”∧” | ”∨” | ”→” | ”≡”

Wyprowadzenie formuły z gramatyki można zilustrować za pomocą
drzewa wywodu i drzewa struktury.

Klasyczny Rachunek Zdań (część I)

Język KRZ

Formuła KRZ

Definicja indukcyjna formuły KRZ

Formuła , wyrażenie sensowene / gramatycznie poprawne KRZ.

Niech ϕ, ψ będą zmiennymi metajęzykowymi reprezentującymi dowolną
formułę KRZ. Wówczas:

1

Każde z wyrażeń p, q, r , ..., p

1

, q

1

, r

1

, ... jest formułą KRZ

2

Jeżeli ϕ jest formułą KRZ, to jest też nią p¬ϕq

3

Jeżeli ϕ i ψ są formułami KRZ, to są też nimi pϕ → ψq, pϕ ∨ ψq,
pϕ ∧ ψq, pϕ ≡ ψq

Definicja formuła KRZ w BNF

<formula> ::= <formula prosta> | [”(”]<formula zlozona>[”)”]
<formula prosta> ::= ”p” | ”q” | ”r” | ”s” | ”p

1

” | . . . | ”p

n

”

<formula zlozona> ::= ”¬”<formula> | <formula><funktor dwuarg><formula>
<funktor dwuarg> ::= ”∧” | ”∨” | ”→” | ”≡”

Wyprowadzenie formuły z gramatyki można zilustrować za pomocą
drzewa wywodu i drzewa struktury.

Klasyczny Rachunek Zdań (część I)

Język KRZ

Formuła KRZ

Definicja indukcyjna formuły KRZ

Formuła , wyrażenie sensowene / gramatycznie poprawne KRZ.

Niech ϕ, ψ będą zmiennymi metajęzykowymi reprezentującymi dowolną
formułę KRZ. Wówczas:

1

Każde z wyrażeń p, q, r , ..., p

1

, q

1

, r

1

, ... jest formułą KRZ

2

Jeżeli ϕ jest formułą KRZ, to jest też nią p¬ϕq

3

Jeżeli ϕ i ψ są formułami KRZ, to są też nimi pϕ → ψq, pϕ ∨ ψq,
pϕ ∧ ψq, pϕ ≡ ψq

Definicja formuła KRZ w BNF

<formula> ::= <formula prosta> | [”(”]<formula zlozona>[”)”]
<formula prosta> ::= ”p” | ”q” | ”r” | ”s” | ”p

1

” | . . . | ”p

n

”

<formula zlozona> ::= ”¬”<formula> | <formula><funktor dwuarg><formula>
<funktor dwuarg> ::= ”∧” | ”∨” | ”→” | ”≡”

Wyprowadzenie formuły z gramatyki można zilustrować za pomocą
drzewa wywodu i drzewa struktury.

Klasyczny Rachunek Zdań (część I)

Język KRZ

Formuła KRZ

Definicja indukcyjna formuły KRZ

Formuła , wyrażenie sensowene / gramatycznie poprawne KRZ.

Niech ϕ, ψ będą zmiennymi metajęzykowymi reprezentującymi dowolną
formułę KRZ. Wówczas:

1

Każde z wyrażeń p, q, r , ..., p

1

, q

1

, r

1

, ... jest formułą KRZ

2

Jeżeli ϕ jest formułą KRZ, to jest też nią p¬ϕq

3

Jeżeli ϕ i ψ są formułami KRZ, to są też nimi pϕ → ψq, pϕ ∨ ψq,
pϕ ∧ ψq, pϕ ≡ ψq

Definicja formuła KRZ w BNF

<formula> ::= <formula prosta> | [”(”]<formula zlozona>[”)”]
<formula prosta> ::= ”p” | ”q” | ”r” | ”s” | ”p

1

” | . . . | ”p

n

”

<formula zlozona> ::= ”¬”<formula> | <formula><funktor dwuarg><formula>
<funktor dwuarg> ::= ”∧” | ”∨” | ”→” | ”≡”

Wyprowadzenie formuły z gramatyki można zilustrować za pomocą
drzewa wywodu i drzewa struktury.

Klasyczny Rachunek Zdań (część I)

Język KRZ

Formuła KRZ

Definicja indukcyjna formuły KRZ

Formuła , wyrażenie sensowene / gramatycznie poprawne KRZ.

Niech ϕ, ψ będą zmiennymi metajęzykowymi reprezentującymi dowolną
formułę KRZ. Wówczas:

1

Każde z wyrażeń p, q, r , ..., p

1

, q

1

, r

1

, ... jest formułą KRZ

2

Jeżeli ϕ jest formułą KRZ, to jest też nią p¬ϕq

3

Jeżeli ϕ i ψ są formułami KRZ, to są też nimi pϕ → ψq, pϕ ∨ ψq,
pϕ ∧ ψq, pϕ ≡ ψq

Definicja formuła KRZ w BNF

<formula> ::= <formula prosta> | [”(”]<formula zlozona>[”)”]
<formula prosta> ::= ”p” | ”q” | ”r” | ”s” | ”p

1

” | . . . | ”p

n

”

<formula zlozona> ::= ”¬”<formula> | <formula><funktor dwuarg><formula>
<funktor dwuarg> ::= ”∧” | ”∨” | ”→” | ”≡”

Wyprowadzenie formuły z gramatyki można zilustrować za pomocą
drzewa wywodu i drzewa struktury.

Klasyczny Rachunek Zdań (część I)

Język KRZ

Formuła KRZ

Przykład formuł KRZ

Umowa:

W ciągu symboli: ¬, ∧, ∨, →, ≡ każdy symbol wiąże silniej niż symbole
występujące po nim.

r

(p → q) ∧ p → q

¬(p ∧ ¬s)

p ∨ ¬p

(p → q) → ((q → r ) → (p → r ))

Klasyczny Rachunek Zdań (część I)

Zrozumieć KRZ – metoda 0-1

Czym jest KRZ?

Czym jest KRZ?

KRZ jest zbiorem pewnych formuł.

KRZ jest zbiorem formuł. . .

takich, które przyjmują wartość prawdy przy każdym wartościowaniu
(metoda P-F)

takich, które dadzą się udowodnić na gruncie założeniowego
rachunku KRZ

takich, które dadzą się udowodnić na gruncie aksjomatycznego
rachunku KRZ J. Łukasiewicza (lub innych równoważnych)

takich, że istnieje tablica analityczna zamknięta dla ich negacji

Klasyczny Rachunek Zdań (część I)

Zrozumieć KRZ – metoda 0-1

Czym jest KRZ?

Czym jest KRZ?

KRZ jest zbiorem pewnych formuł.

KRZ jest zbiorem formuł. . .

takich, które przyjmują wartość prawdy przy każdym wartościowaniu
(metoda P-F)

takich, które dadzą się udowodnić na gruncie założeniowego
rachunku KRZ

takich, które dadzą się udowodnić na gruncie aksjomatycznego
rachunku KRZ J. Łukasiewicza (lub innych równoważnych)

takich, że istnieje tablica analityczna zamknięta dla ich negacji

Klasyczny Rachunek Zdań (część I)

Zrozumieć KRZ – metoda 0-1

Czym jest KRZ?

Czym jest KRZ?

KRZ jest zbiorem pewnych formuł.

KRZ jest zbiorem formuł. . .

takich, które przyjmują wartość prawdy przy każdym wartościowaniu
(metoda P-F)

takich, które dadzą się udowodnić na gruncie założeniowego
rachunku KRZ

takich, które dadzą się udowodnić na gruncie aksjomatycznego
rachunku KRZ J. Łukasiewicza (lub innych równoważnych)

takich, że istnieje tablica analityczna zamknięta dla ich negacji

Klasyczny Rachunek Zdań (część I)

Zrozumieć KRZ – metoda 0-1

Czym jest KRZ?

Czym jest KRZ?

KRZ jest zbiorem pewnych formuł.

KRZ jest zbiorem formuł. . .

takich, które przyjmują wartość prawdy przy każdym wartościowaniu
(metoda P-F)

takich, które dadzą się udowodnić na gruncie założeniowego
rachunku KRZ

takich, które dadzą się udowodnić na gruncie aksjomatycznego
rachunku KRZ J. Łukasiewicza (lub innych równoważnych)

takich, że istnieje tablica analityczna zamknięta dla ich negacji

Klasyczny Rachunek Zdań (część I)

Zrozumieć KRZ – metoda 0-1

Odczytanie funktorów języka KRZ

Zrozumieć KRZ przez prawidłowe odczytanie formuł

¬ — nie jest tak, że . . . (negacja)

∧ — ... i ... (koniunkcja)

∨ — . . . lub . . . (alternatywa)

→ — jeżeli . . . , to . . . (implikacja)

≡ — . . . wtedy i tylko wtedy, gdy . . . (równoważność)

Klasyczny Rachunek Zdań (część I)

Zrozumieć KRZ – metoda 0-1

Język KRZ jako schemat niektórych zdań języka polskiego

Zrozumieć KRZ przez prawidłowe odczytanie formuł

Nie jest tak, że
|

{z

}

¬

słońce świeci
|

{z

}

p

.

Świeci słońce
|

{z

}

p

i

|{z}

∧

nie (jest tak, że)
|

{z

}

¬

pada deszcz
|

{z

}

q

.

Jeżeli pada deszcz,

|

{z

}

p

to

|{z}

→

szosa jest mokra
|

{z

}

q

.

Pójdziemy do kina
|

{z

}

p

lub

|{z}

∨

zabiorę cię na zakupy
|

{z

}

q

.

Klasyczny Rachunek Zdań (część I)

Zrozumieć KRZ – metoda 0-1

Język KRZ jako schemat niektórych zdań języka polskiego

Zrozumieć KRZ przez metodę P-F

1 – prawda

0 – fałsz

p

¬p

1

0

0

1

p

q

p ∧ q

p ∨ q

p → q

p ≡ q

1

1

1

1

1

1

1

0

0

1

0

0

0

1

0

1

1

0

0

0

0

0

1

1

Klasyczny Rachunek Zdań (część I)

Zrozumieć KRZ – metoda 0-1

Język KRZ jako schemat niektórych zdań języka polskiego

Metoda P-F; prawo logiki

Prawo logiki (na gruncie rachunku zdań) jest to

wyrażenie zdaniowe, zbudowane wyłącznie ze stałych logicznych,
zmiennych i ewentualnie nawiasów, które przyjmuje wartość 1 dla
każdego układu wartości 1 i 0 przyporządkowanych występującym w nim
zmiennym zdaniowym.

p

¬p

p ∨ ¬p

1

0

1

0

1

1

p

q

p → q

(p → q) ∧ p

(p → q) ∧ p → q

1

1

1

1

1

1

0

0

0

1

0

1

1

0

1

0

0

1

0

1

Klasyczny Rachunek Zdań (część I)

Zrozumieć KRZ – metoda 0-1

Język KRZ jako schemat niektórych zdań języka polskiego

Prawo logiki (na gruncie rachunku zdań) – uwagi

Dla wyrażenie zawierającego n różnych zmiennych zdaniowych istnieje 2

n

różnych

sposobów przyporządkowania im (tj. zmiennym zdaniowym) wartości 1 i 0.

To, że posługujemy się jedynie dwoma wartościami, 1 i 0, jest konsekwencją przyjętej
przez nas zasady dwuwartościowości.

Prawa logiki nazywa się również tautologiami.

O wyrażenie rachunku zdań, które jest prawem logiki mówimy, że jest prawdziwym
wyrażeniem rachunku zdań.

Prawdziwość wyrażenia (nie tylko rachunku zdań) będziemy oznaczać znakiem “”.
Na przykład:

 p ∨ ¬p

 (p → q) → (¬q → ¬p)

Klasyczny Rachunek Zdań (część I)

Zrozumieć KRZ – metoda 0-1

Język KRZ jako schemat niektórych zdań języka polskiego

Prawo logiki (na gruncie rachunku zdań) – uwagi

Dla wyrażenie zawierającego n różnych zmiennych zdaniowych istnieje 2

n

różnych

sposobów przyporządkowania im (tj. zmiennym zdaniowym) wartości 1 i 0.

To, że posługujemy się jedynie dwoma wartościami, 1 i 0, jest konsekwencją przyjętej
przez nas zasady dwuwartościowości.

Prawa logiki nazywa się również tautologiami.

O wyrażenie rachunku zdań, które jest prawem logiki mówimy, że jest prawdziwym
wyrażeniem rachunku zdań.

Prawdziwość wyrażenia (nie tylko rachunku zdań) będziemy oznaczać znakiem “”.
Na przykład:

 p ∨ ¬p

 (p → q) → (¬q → ¬p)

Klasyczny Rachunek Zdań (część I)

Zrozumieć KRZ – metoda 0-1

Język KRZ jako schemat niektórych zdań języka polskiego

Prawo logiki (na gruncie rachunku zdań) – uwagi

Dla wyrażenie zawierającego n różnych zmiennych zdaniowych istnieje 2

n

różnych

sposobów przyporządkowania im (tj. zmiennym zdaniowym) wartości 1 i 0.

To, że posługujemy się jedynie dwoma wartościami, 1 i 0, jest konsekwencją przyjętej
przez nas zasady dwuwartościowości.

Prawa logiki nazywa się również tautologiami.

O wyrażenie rachunku zdań, które jest prawem logiki mówimy, że jest prawdziwym
wyrażeniem rachunku zdań.

Prawdziwość wyrażenia (nie tylko rachunku zdań) będziemy oznaczać znakiem “”.
Na przykład:

 p ∨ ¬p

 (p → q) → (¬q → ¬p)

Klasyczny Rachunek Zdań (część I)

Zrozumieć KRZ – metoda 0-1

Język KRZ jako schemat niektórych zdań języka polskiego

Prawo logiki (na gruncie rachunku zdań) – uwagi

Dla wyrażenie zawierającego n różnych zmiennych zdaniowych istnieje 2

n

różnych

sposobów przyporządkowania im (tj. zmiennym zdaniowym) wartości 1 i 0.

To, że posługujemy się jedynie dwoma wartościami, 1 i 0, jest konsekwencją przyjętej
przez nas zasady dwuwartościowości.

Prawa logiki nazywa się również tautologiami.

O wyrażenie rachunku zdań, które jest prawem logiki mówimy, że jest prawdziwym
wyrażeniem rachunku zdań.

Prawdziwość wyrażenia (nie tylko rachunku zdań) będziemy oznaczać znakiem “”.
Na przykład:

 p ∨ ¬p

 (p → q) → (¬q → ¬p)

Klasyczny Rachunek Zdań (część I)

Zrozumieć KRZ – metoda 0-1

Język KRZ jako schemat niektórych zdań języka polskiego

Prawo logiki (na gruncie rachunku zdań) – uwagi

Dla wyrażenie zawierającego n różnych zmiennych zdaniowych istnieje 2

n

różnych

sposobów przyporządkowania im (tj. zmiennym zdaniowym) wartości 1 i 0.

To, że posługujemy się jedynie dwoma wartościami, 1 i 0, jest konsekwencją przyjętej
przez nas zasady dwuwartościowości.

Prawa logiki nazywa się również tautologiami.

O wyrażenie rachunku zdań, które jest prawem logiki mówimy, że jest prawdziwym
wyrażeniem rachunku zdań.

Prawdziwość wyrażenia (nie tylko rachunku zdań) będziemy oznaczać znakiem “”.
Na przykład:

 p ∨ ¬p

 (p → q) → (¬q → ¬p)

Klasyczny Rachunek Zdań (część I)

Zrozumieć KRZ – metoda 0-1

Język KRZ jako schemat niektórych zdań języka polskiego

Prawo logiki (na gruncie rachunku zdań) – uwagi

Dla wyrażenie zawierającego n różnych zmiennych zdaniowych istnieje 2

n

różnych

sposobów przyporządkowania im (tj. zmiennym zdaniowym) wartości 1 i 0.

To, że posługujemy się jedynie dwoma wartościami, 1 i 0, jest konsekwencją przyjętej
przez nas zasady dwuwartościowości.

Prawa logiki nazywa się również tautologiami.

O wyrażenie rachunku zdań, które jest prawem logiki mówimy, że jest prawdziwym
wyrażeniem rachunku zdań.

Prawdziwość wyrażenia (nie tylko rachunku zdań) będziemy oznaczać znakiem “”.
Na przykład:

 p ∨ ¬p

 (p → q) → (¬q → ¬p)

Klasyczny Rachunek Zdań (część I)

Zrozumieć KRZ – metoda 0-1

Język KRZ jako schemat niektórych zdań języka polskiego

Wykaż, że poniższe formuły są prawami logiki (1)

1

p → p

2

p ≡ p

3

p ∧ p → p

4

p ∨ p → p

5

p ∨ ¬p

6

¬(p ∧ ¬p)

7

(p → q) → ((q → r ) → (p → r ))

8

(p ∨ q) → (¬q → p)

9

(¬¬p → p)

10

(p → ¬¬p)

11

(p 𠪪p)

12

(p → q) ∧ (r → s) → (p ∧ r → q ∧ s)

Klasyczny Rachunek Zdań (część I)

Zrozumieć KRZ – metoda 0-1

Język KRZ jako schemat niektórych zdań języka polskiego

Wykaż, że poniższe formuły są prawami logiki (2)

1

(p → q ∧ r ) → (p → q) ∧ (p → r )

2

(p ∨ q → r ) → (p → r ) ∧ (q → r )

3

(p → ¬p) → ¬p

4

(p → q ∧ ¬q) → ¬p

5

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

6

p ∧ ¬p → q

7

¬(p ∧ q) ≡ p → ¬q

8

(p → q) ∧ (r → s) → (p ∨ r → q ∨ r )

9

(p → r ) ∧ (q → r ) ∧ (p ∨ q) → r

10

(p → q) ∧ (r → s) ∧ (p ∨ r ) → (q ∨ s)

11

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

12

(p ≡ q) ≡ (p → q) ∧ (q → p)

13

q → (p → q)

Klasyczny Rachunek Zdań (część I)

Zrozumieć KRZ – metoda 0-1

Język KRZ jako schemat niektórych zdań języka polskiego

Wykaż, że poniższe formuły są prawami logiki (3)

1

p ∧ q → r ≡ p ∧ ¬r → ¬q

2

(p → q) ∧ ¬q → ¬p

3

(p → q) ≡ (¬q → ¬p)

4

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

5

p → q ≡ ¬p ∨ q

6

p ∧ q → r ≡ p → (q → r )

7

(p → q) ∧ (q → r ) → r )

8

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

9

p → q ≡ ¬p ∨ q

10

p ∧ q → r ≡ p → (q → r )

11

(p → q) ∧ (q → r ) → (p → r )

Klasyczny Rachunek Zdań (część I)

Zrozumieć KRZ – metoda 0-1

Skrócona metoda P-F

Skrócona metoda P-F

Metoda postępowania dla dowolnego wyrażenie KRZ:

1

Zakładamy, że wyrażenie KRZ jest fałszywe.

2

Wyciągamy konsekwencje tego założenia korzystając z
charakterystyki funktorów dostarczonej przez pojęcia prawdy i fałszu.

3

Jeżeli nasze założenie doprowadzi do sprzeczności, to sprawdzane
wyrażenie jest prawem logiki.

4

Jeżeli nie, to udało się nam pokazać, że wyrażenie to nie jest zawsze
prawdziwe, a zatem nie jest też prawem logiki.

Przykład

( p

|{z}

1

4

→

|{z}

1

5

|{z}

0

q

|{z}

0

7

) ∧

|{z}

1

2

¬

|{z}

1

5

q

|{z}

0

6

→

|{z}

0

1

¬

|{z}

0

2

p

|{z}

1

3