1 Główne pojęcia logiki

2 Język klasycznego rachunku zdańAlfabet: zmienne zdaniowe: p, q, r… Pojęcia logiki

3 Język klasycznego rachunku zdańAlfabet: zmienne zdaniowe: p, q, r… spójniki: , , , ,  (lub, i, nie, jeżeli…to, wtedy i tylko wtedy gdy) Pojęcia logiki

4 Język klasycznego rachunku zdańAlfabet: zmienne zdaniowe: p, q, r… spójniki: , , , ,  (lub, i, nie, jeżeli…to, wtedy i tylko wtedy gdy) nawiasy Pojęcia logiki

5 Język klasycznego rachunku zdańAlfabet: zmienne zdaniowe: p, q, r… spójniki: , , , ,  (lub, i, nie, jeżeli…to, wtedy i tylko wtedy gdy) nawiasy Reguły tworzenia wyrażeń poprawnych: jeżeli A jest zmienną zdaniowa, to A jest formułą poprawnie zbudowaną Pojęcia logiki

6 Język klasycznego rachunku zdańAlfabet: zmienne zdaniowe: p, q, r… spójniki: , , , ,  (lub, i, nie, jeżeli…to, wtedy i tylko wtedy gdy) nawiasy Reguły tworzenia wyrażeń poprawnych: jeżeli A jest zmienną zdaniowa, to A jest formułą poprawnie zbudowaną jeżeli A i B są formułami poprawnie zbudowanymi to poprawnie zbudowane są: A  B, A  B, A, A  B, A  B Pojęcia logiki

7 Język klasycznego rachunku zdańAlfabet: zmienne zdaniowe: p, q, r… spójniki: , , , ,  (lub, i, nie, jeżeli…to, wtedy i tylko wtedy gdy) nawiasy Reguły tworzenia wyrażeń poprawnych: jeżeli A jest zmienną zdaniowa, to A jest formułą poprawnie zbudowaną jeżeli A i B są formułami poprawnie zbudowanymi to poprawnie zbudowane są: A  B, A  B, A, A  B, A  B Przykłady: p  q  r, Pojęcia logiki

8 Język klasycznego rachunku zdańAlfabet: zmienne zdaniowe: p, q, r… spójniki: , , , ,  (lub, i, nie, jeżeli…to, wtedy i tylko wtedy gdy) nawiasy Reguły tworzenia wyrażeń poprawnych: jeżeli A jest zmienną zdaniowa, to A jest formułą poprawnie zbudowaną jeżeli A i B są formułami poprawnie zbudowanymi to poprawnie zbudowane są: A  B, A  B, A, A  B, A  B Przykłady: p  q  r, p  (q  r) Pojęcia logiki

9 Język klasycznego rachunku zdańAlfabet: zmienne zdaniowe: p, q, r… spójniki: , , , ,  (lub, i, nie, jeżeli…to, wtedy i tylko wtedy gdy) nawiasy Reguły tworzenia wyrażeń poprawnych: jeżeli A jest zmienną zdaniowa, to A jest formułą poprawnie zbudowaną jeżeli A i B są formułami poprawnie zbudowanymi to poprawnie zbudowane są: A  B, A  B, A, A  B, A  B Przykłady: p  q  r, p  (q  r), p  r, Pojęcia logiki

10 Język klasycznego rachunku zdańAlfabet: zmienne zdaniowe: p, q, r… spójniki: , , , ,  (lub, i, nie, jeżeli…to, wtedy i tylko wtedy gdy) nawiasy Reguły tworzenia wyrażeń poprawnych: jeżeli A jest zmienną zdaniowa, to A jest formułą poprawnie zbudowaną jeżeli A i B są formułami poprawnie zbudowanymi to poprawnie zbudowane są: A  B, A  B, A, A  B, A  B Przykłady: p  q  r, p  (q  r), p  r, p  q  r, Pojęcia logiki

11 Język klasycznego rachunku zdańAlfabet: zmienne zdaniowe: p, q, r… spójniki: , , , ,  (lub, i, nie, jeżeli…to, wtedy i tylko wtedy gdy) nawiasy Reguły tworzenia wyrażeń poprawnych: jeżeli A jest zmienną zdaniowa, to A jest formułą poprawnie zbudowaną jeżeli A i B są formułami poprawnie zbudowanymi to poprawnie zbudowane są: A  B, A  B, A, A  B, A  B Przykłady: p  q  r, p  (q  r), p  r, p  q  r, (p  q)  r, p  (q  r). Pojęcia logiki

12 Konwencje notacyjne Hierarchia spójników: , , , , ., , , . Pojęcia logiki

13 Konwencje notacyjne Hierarchia spójników: , , , , ., , , . Alternatywne oznaczenia: ~ …, & , ; ,  Pojęcia logiki

14 Język klasycznego rachunku zdańReguły wnioskowania: reguła odrywania: A A  B B Pojęcia logiki

15 Język klasycznego rachunku zdańReguły wnioskowania: reguła odrywania: A A  B B reguła podstawiania: A(α|β) Pojęcia logiki

16 Język klasycznego rachunku zdańReguły wnioskowania: reguła odrywania: A A  B B reguła podstawiania: A(α|β) Na przykład: p  q  p |- (p  q)  q  p  q Pojęcia logiki

17 Język klasycznego rachunku zdańReguły wnioskowania: reguła odrywania: A A  B B reguła podstawiania: A(α|β) Na przykład: p  q  p |- (p  q)  q  p  q jest wyprowadzalne z Pojęcia logiki

18 Pojęcie dowodu DF: Dowodem formuły A na gruncie zbioru aksjomatów X nazywa się ciąg formuł B1, …, Bn taki, że Bn = A oraz Pojęcia logiki

19 Pojęcie dowodu DF: Dowodem formuły A na gruncie zbioru aksjomatów X nazywa się ciąg formuł B1, …, Bn taki, że Bn = A oraz dla każdej formuły Bi B1, …, Bi-1 |- Bi lub Pojęcia logiki

20 Pojęcie dowodu DF: Dowodem formuły A na gruncie zbioru aksjomatów X nazywa się ciąg formuł B1, …, Bn taki, że Bn = A oraz dla każdej formuły Bi B1, …, Bi-1 |- Bi lub Bi  X Pojęcia logiki

21 Funkcje prawdziwościoweq p  q 1 Pojęcia logiki

22 Funkcje prawdziwościoweq p  q 1 p q p  q 1 Pojęcia logiki

23 Funkcje prawdziwościoweq p  q 1 p q p  q 1 p q p  q 1 Pojęcia logiki

24 Funkcje prawdziwościoweq p  q 1 p q p  q 1 p q p  q 1 p q p  q 1 Pojęcia logiki

25 Wynikanie logiczne DF: X |= A wtw nie istnieje taka interpretacja,w której wszystkie zdania ze zbioru X (przesłanki) są prawdziwe, a (wniosek) A jest fałszywy. Pojęcia logiki

26 Wynikanie logiczne DF: X |= A wtw nie istnieje taka interpretacja,w której wszystkie zdania ze zbioru X (przesłanki) są prawdziwe, a (wniosek) A jest fałszywy. Na przykład: Jeżeli Funio kocha Kundzię, to się z nią ożeni. Funio nie żeni się z Kundzią. Zatem Funio nie kocha Kundzi. Pojęcia logiki

27 Wynikanie logiczne DF: X |= A wtw nie istnieje taka interpretacja,w której wszystkie zdania ze zbioru X (przesłanki) są prawdziwe, a (wniosek) A jest fałszywy. Na przykład: Jeżeli Funio kocha Kundzię, to się z nią ożeni. Funio nie żeni się z Kundzią. Zatem Funio nie kocha Kundzi. Ale nie: Jeżeli Funio kocha Kundzię, to się z nią ożeni. Funio nie kocha Kundzi. Zatem Funio nie ożeni się z Kundzią. Pojęcia logiki

28 Prawa logiki DF: Prawem logiki nazywa się formuła prawdziwa w dowolnej interpretacji. Przykład: prawo kontrapozycji: (p  q)  ( q   p) Pojęcia logiki

29 Prawa logiki DF: Prawem logiki nazywa się formuła prawdziwa w dowolnej interpretacji. Przykład: prawo kontrapozycji: (p  q)  ( q   p) p q 1 Pojęcia logiki

30 Prawa logiki DF: Prawem logiki nazywa się formuła prawdziwa w dowolnej interpretacji. Przykład: prawo kontrapozycji: (p  q)  ( q   p) p q p  q 1 Pojęcia logiki

31 Prawa logiki DF: Prawem logiki nazywa się formuła prawdziwa w dowolnej interpretacji. Przykład: prawo kontrapozycji: (p  q)  ( q   p) p q p  q p 1 Pojęcia logiki

32 Prawa logiki DF: Prawem logiki nazywa się formuła prawdziwa w dowolnej interpretacji. Przykład: prawo kontrapozycji: (p  q)  ( q   p) p q p  q p 1 Pojęcia logiki

33 Prawa logiki DF: Prawem logiki nazywa się formuła prawdziwa w dowolnej interpretacji. Przykład: prawo kontrapozycji: (p  q)  ( q   p) p q p  q p q 1 Pojęcia logiki

34 Prawa logiki DF: Prawem logiki nazywa się formuła prawdziwa w dowolnej interpretacji. Przykład: prawo kontrapozycji: (p  q)  ( q   p) p q p  q p q 1 Pojęcia logiki

35 Prawa logiki DF: Prawem logiki nazywa się formuła prawdziwa w dowolnej interpretacji. Przykład: prawo kontrapozycji: (p  q)  ( q   p) p q p  q p q  q   p 1 Pojęcia logiki

36 Prawa logiki DF: Prawem logiki nazywa się formuła prawdziwa w dowolnej interpretacji. Przykład: prawo kontrapozycji: (p  q)  ( q   p) p q p  q p q  q   p 1 Pojęcia logiki

37 Prawa logiki DF: Prawem logiki nazywa się formuła prawdziwa w dowolnej interpretacji. Przykład: prawo kontrapozycji: (p  q)  ( q   p) p q p  q p q  q   p (p  q)  ( q   p) 1 Pojęcia logiki

38 Prawa logiki DF: Prawem logiki nazywa się formuła prawdziwa w dowolnej interpretacji. Przykład: prawo kontrapozycji: (p  q)  ( q   p) p q p  q p q  q   p (p  q)  ( q   p) 1 Pojęcia logiki

39 Twierdzenie o dedukcjiX1, …, Xn |= A wtw X1  …  Xn  A jest prawem logiki Pojęcia logiki

40 Twierdzenie o dedukcjiX1, …, Xn |= A wtw X1  …  Xn  A jest prawem logiki Twierdzenie o pełności X |= A wtw X |- A przy odpowiednim doborze aksjomatów i reguł wnioskowania (takie reguły nazywają się niezawodne) Pojęcia logiki

41 Język rachunku predykatówAlfabet: stałe i zmienne indywiduowe: a, b, c…, x, y, z… Pojęcia logiki

42 Język rachunku predykatówAlfabet: stałe i zmienne indywiduowe: a, b, c…, x, y, z… stałe predykatowe: P, Q, R… Pojęcia logiki

43 Język rachunku predykatówAlfabet: stałe i zmienne indywiduowe: a, b, c…, x, y, z… stałe predykatowe: P, Q, R… spójniki: , , , ,  Pojęcia logiki

44 Język rachunku predykatówAlfabet: stałe i zmienne indywiduowe: a, b, c…, x, y, z… stałe predykatowe: P, Q, R… spójniki: , , , ,  kwantyfikatory: ,  (dla każdego, istnieje) Pojęcia logiki

45 Język rachunku predykatówAlfabet: stałe i zmienne indywiduowe: a, b, c…, x, y, z… stałe predykatowe: P, Q, R… spójniki: , , , ,  kwantyfikatory: ,  (dla każdego, istnieje) nawiasy Pojęcia logiki

46 Język rachunku predykatówAlfabet: stałe i zmienne indywiduowe: a, b, c…, x, y, z… stałe predykatowe: P, Q, R… spójniki: , , , ,  kwantyfikatory: ,  (dla każdego, istnieje) nawiasy Reguły tworzenia wyrażeń poprawnych: P(t1, …, tn) jest formułą poprawnie zbudowaną Pojęcia logiki

47 Język rachunku predykatówAlfabet: stałe i zmienne indywiduowe: a, b, c…, x, y, z… stałe predykatowe: P, Q, R… spójniki: , , , ,  kwantyfikatory: ,  (dla każdego, istnieje) nawiasy Reguły tworzenia wyrażeń poprawnych: P(t1, …, tn) jest formułą poprawnie zbudowaną jeżeli A i B są formułami poprawnie zbudowanymi, to poprawnie zbudowane są: A  B, A  B, A, A  B, A  B Pojęcia logiki

48 Język rachunku predykatówAlfabet: stałe i zmienne indywiduowe: a, b, c…, x, y, z… stałe predykatowe: P, Q, R… spójniki: , , , ,  kwantyfikatory: ,  (dla każdego, istnieje) nawiasy Reguły tworzenia wyrażeń poprawnych: P(t1, …, tn) jest formułą poprawnie zbudowaną jeżeli A i B są formułami poprawnie zbudowanymi, to poprawnie zbudowane są: A  B, A  B, A, A  B, A  B jeżeli A jest formułą poprawnie zbudowaną, to poprawnie zbudowane są: xA, xA Pojęcia logiki

49 Przykłady zapisu symbolicznego zdań języka potocznegoP = „…jest krukiem”, Q = „…jest czarny” x (P(x)  Q(x)) Pojęcia logiki

50 Przykłady zapisu symbolicznego zdań języka potocznegoP = „…jest krukiem”, Q = „…jest czarny” x (P(x)  Q(x)) Wszystkie kruki są czarne. Pojęcia logiki

51 Przykłady zapisu symbolicznego zdań języka potocznegoP = „…jest krukiem”, Q = „…jest czarny” x (P(x)  Q(x)) x (P(x)  Q(x)) Wszystkie kruki są czarne. Pojęcia logiki

52 Przykłady zapisu symbolicznego zdań języka potocznegoP = „…jest krukiem”, Q = „…jest czarny” x (P(x)  Q(x)) x (P(x)  Q(x)) Wszystkie kruki są czarne. Każda rzecz jest czarnym krukiem. Pojęcia logiki

53 Przykłady zapisu symbolicznego zdań języka potocznegoP = „…jest krukiem”, Q = „…jest czarny” x (P(x)  Q(x)) x (P(x)  Q(x)) x (P(x)  Q(x)) Wszystkie kruki są czarne. Każda rzecz jest czarnym krukiem. Pojęcia logiki

54 Przykłady zapisu symbolicznego zdań języka potocznegoP = „…jest krukiem”, Q = „…jest czarny” x (P(x)  Q(x)) x (P(x)  Q(x)) x (P(x)  Q(x)) Wszystkie kruki są czarne. Każda rzecz jest czarnym krukiem. Niektóre kruki są czarne. Pojęcia logiki

55 Przykłady zapisu symbolicznego zdań języka potocznegoP = „…jest krukiem”, Q = „…jest czarny” x (P(x)  Q(x)) x (P(x)  Q(x)) x (P(x)  Q(x)) x (P(x)  Q(x)) Wszystkie kruki są czarne. Każda rzecz jest czarnym krukiem. Niektóre kruki są czarne. Pojęcia logiki

56 Przykłady zapisu symbolicznego zdań języka potocznegoP = „…jest krukiem”, Q = „…jest czarny” x (P(x)  Q(x)) x (P(x)  Q(x)) x (P(x)  Q(x)) x (P(x)  Q(x)) Wszystkie kruki są czarne. Każda rzecz jest czarnym krukiem. Niektóre kruki są czarne. Istnieje coś, co jeżeli jest krukiem, to jest czarne (co jest prawdą, gdy kruków w ogóle nie ma). Pojęcia logiki

57 Przykłady zapisu symbolicznego zdań języka potocznegoKażda pliszka swój ogonek chwali. Pojęcia logiki

58 Przykłady zapisu symbolicznego zdań języka potocznegoKażda pliszka swój ogonek chwali. P = „…jest pliszką”, Pojęcia logiki

59 Przykłady zapisu symbolicznego zdań języka potocznegoKażda pliszka swój ogonek chwali. P = „…jest pliszką”, Q = „…jest ogonkiem …(czyimś)”, Pojęcia logiki

60 Przykłady zapisu symbolicznego zdań języka potocznegoKażda pliszka swój ogonek chwali. P = „…jest pliszką”, Q = „…jest ogonkiem …(czyimś)”, R = „…chwali …(coś)” Pojęcia logiki

61 Przykłady zapisu symbolicznego zdań języka potocznegoKażda pliszka swój ogonek chwali. P = „…jest pliszką”, Q = „…jest ogonkiem …(czyimś)”, R = „…chwali …(coś)” x(P(x)  Pojęcia logiki

62 Przykłady zapisu symbolicznego zdań języka potocznegoKażda pliszka swój ogonek chwali. P = „…jest pliszką”, Q = „…jest ogonkiem …(czyimś)”, R = „…chwali …(coś)” x(P(x)  y(Q(y, x)  R(x, y))) Pojęcia logiki

63 Przykłady zapisu symbolicznego zdań języka potocznegoKażda pliszka swój ogonek chwali. P = „…jest pliszką”, Q = „…jest ogonkiem …(czyimś)”, R = „…chwali …(coś)” x(P(x)  y(Q(y, x)  R(x, y))) x(P(x)  y(Q(y, x)  R(x, y))) Pojęcia logiki

64 Przykłady zapisu symbolicznego zdań języka potocznegoKażda pliszka swój ogonek chwali. P = „…jest pliszką”, Q = „…jest ogonkiem …(czyimś)”, R = „…chwali …(coś)” x(P(x)  y(Q(y, x)  R(x, y))) x(P(x)  y(Q(y, x)  R(x, y))) Każda pliszka chwali wszystkie swoje ogonki. Pojęcia logiki

65 Przykłady zapisu symbolicznego zdań języka potocznegoKażda pliszka swój ogonek chwali. P = „…jest pliszką”, Q = „…jest ogonkiem …(czyimś)”, R = „…chwali …(coś)” x(P(x)  y(Q(y, x)  R(x, y))) x(P(x)  y(Q(y, x)  R(x, y))) Każda pliszka chwali wszystkie swoje ogonki. Niektóre pliszki chwalą tylko cudze ogonki. Pojęcia logiki

66 Przykłady zapisu symbolicznego zdań języka potocznegoKażda pliszka swój ogonek chwali. P = „…jest pliszką”, Q = „…jest ogonkiem …(czyimś)”, R = „…chwali …(coś)” x(P(x)  y(Q(y, x)  R(x, y))) x(P(x)  y(Q(y, x)  R(x, y))) Każda pliszka chwali wszystkie swoje ogonki. Niektóre pliszki chwalą tylko cudze ogonki. x(P(x)  Pojęcia logiki

67 Przykłady zapisu symbolicznego zdań języka potocznegoKażda pliszka swój ogonek chwali. P = „…jest pliszką”, Q = „…jest ogonkiem …(czyimś)”, R = „…chwali …(coś)” x(P(x)  y(Q(y, x)  R(x, y))) x(P(x)  y(Q(y, x)  R(x, y))) Każda pliszka chwali wszystkie swoje ogonki. Niektóre pliszki chwalą tylko cudze ogonki. x(P(x)  y(R(x, y)  Pojęcia logiki

68 Przykłady zapisu symbolicznego zdań języka potocznegoKażda pliszka swój ogonek chwali. P = „…jest pliszką”, Q = „…jest ogonkiem …(czyimś)”, R = „…chwali …(coś)” x(P(x)  y(Q(y, x)  R(x, y))) x(P(x)  y(Q(y, x)  R(x, y))) Każda pliszka chwali wszystkie swoje ogonki. Niektóre pliszki chwalą tylko cudze ogonki. x(P(x)  y(R(x, y)  z(Q(y, z) Pojęcia logiki

69 Przykłady zapisu symbolicznego zdań języka potocznegoKażda pliszka swój ogonek chwali. P = „…jest pliszką”, Q = „…jest ogonkiem …(czyimś)”, R = „…chwali …(coś)” x(P(x)  y(Q(y, x)  R(x, y))) x(P(x)  y(Q(y, x)  R(x, y))) Każda pliszka chwali wszystkie swoje ogonki. Niektóre pliszki chwalą tylko cudze ogonki. x(P(x)  y(R(x, y)  z(Q(y, z)  z  x))) Pojęcia logiki

70 Przykłady zapisu symbolicznego zdań języka potocznegoKażda pliszka swój ogonek chwali. P = „…jest pliszką”, Q = „…jest ogonkiem …(czyimś)”, R = „…chwali …(coś)” x(P(x)  y(Q(y, x)  R(x, y))) x(P(x)  y(Q(y, x)  R(x, y))) Każda pliszka chwali wszystkie swoje ogonki. Niektóre pliszki chwalą tylko cudze ogonki (jeżeli w ogóle). x(P(x)  y(R(x, y)  z(Q(y, z)  z  x))) Pojęcia logiki

71 Przykłady zapisu symbolicznego zdań języka potocznegoKażda pliszka swój ogonek chwali. P = „…jest pliszką”, Q = „…jest ogonkiem …(czyimś)”, R = „…chwali …(coś)” x(P(x)  y(Q(y, x)  R(x, y))) x(P(x)  y(Q(y, x)  R(x, y))) Każda pliszka chwali wszystkie swoje ogonki. Niektóre pliszki chwalą tylko cudze ogonki (jeżeli w ogóle). x(P(x)  y(R(x, y)  z(Q(y, z)  z  x))) x(P(x)  y(R(x, y)  z(Q(y, z)  z  x))) Pojęcia logiki

72 Przykłady zapisu symbolicznego zdań języka potocznegoKażda pliszka swój ogonek chwali. P = „…jest pliszką”, Q = „…jest ogonkiem …(czyimś)”, R = „…chwali …(coś)” x(P(x)  y(Q(y, x)  R(x, y))) x(P(x)  y(Q(y, x)  R(x, y))) Każda pliszka chwali wszystkie swoje ogonki. Niektóre pliszki chwalą tylko cudze ogonki (jeżeli w ogóle). x(P(x)  y(R(x, y)  z(Q(y, z)  z  x))) x(P(x)  y(R(x, y)  z(Q(y, z)  z  x))) Niektóre pliszki chwalą jakiś cudzy ogonek. Pojęcia logiki