Jeśli zdanie α jest prawdziwe to zapisujemy to symbo-
licznie:

1

Jeśli zdanie α jest prawdziwe to zapisujemy to symbo-
licznie:

α = 1

2

Jeśli zdanie α jest prawdziwe to zapisujemy to symbo-
licznie:

α = 1

lub

α

1

3

Jeśli zdanie α jest prawdziwe to zapisujemy to symbo-
licznie:

α = 1

lub

α

1

Analogicznie, jeśli α jest fałszywe to piszemy:

4

Jeśli zdanie α jest prawdziwe to zapisujemy to symbo-
licznie:

α = 1

lub

α

1

Analogicznie, jeśli α jest fałszywe to piszemy:

α = 0

5

Jeśli zdanie α jest prawdziwe to zapisujemy to symbo-
licznie:

α = 1

lub

α

1

Analogicznie, jeśli α jest fałszywe to piszemy:

α = 0

lub

α

0

6

Jak zapisać, że zdanie p → q jest prawdziwe?

7

Jak zapisać, że zdanie p → q jest prawdziwe?

•

czy tak:

p → q

1

?

8

Jak zapisać, że zdanie p → q jest prawdziwe?

•

czy tak:

p → q

1

?

NIE! (to by oznaczało, że p jest prawdziwe)

9

Jak zapisać, że zdanie p → q jest prawdziwe?

•

czy tak:

p → q

1

?

NIE! (to by oznaczało, że p jest prawdziwe)

•

więc też nie tak:

p → q

1

10

Jak zapisać, że zdanie p → q jest prawdziwe?

•

czy tak:

p → q

1

?

NIE! (to by oznaczało, że p jest prawdziwe)

•

więc też nie tak:

p → q

1

(to by oznaczało, że q jest prawdziwe)

11

Jak zapisać, że zdanie p → q jest prawdziwe?

•

czy tak:

p → q

1

?

NIE! (to by oznaczało, że p jest prawdziwe)

•

więc też nie tak:

p → q

1

(to by oznaczało, że q jest prawdziwe)

•

bez nieporozumienia zapiszemy zatem:

12

Jak zapisać, że zdanie p → q jest prawdziwe?

•

czy tak:

p → q

1

?

NIE! (to by oznaczało, że p jest prawdziwe)

•

więc też nie tak:

p → q

1

(to by oznaczało, że q jest prawdziwe)

•

bez nieporozumienia zapiszemy zatem:

p → q

1

13

Jak zapisać, że zdanie ¬(p ∧ q) jest fałszywe?

14

Jak zapisać, że zdanie ¬(p ∧ q) jest fałszywe?

¬ ( p ∧ q )

0

15

Jak zapisać, że zdanie ¬(p ∧ q) jest fałszywe?

¬ ( p ∧ q )

0

Czyli nad spójnikiem głównym!

16

Jak zapisać, że zdanie ¬(p ∧ q) jest fałszywe?

¬ ( p ∧ q )

0

Czyli nad spójnikiem głównym!
Jak zapisać, że zdanie ¬(p ∨ q) ↔ (¬r → q) jest
prawdziwe?

17

Jak zapisać, że zdanie ¬(p ∧ q) jest fałszywe?

¬ ( p ∧ q )

0

Czyli nad spójnikiem głównym!
Jak zapisać, że zdanie ¬(p ∨ q) ↔ (¬r → q) jest
prawdziwe?

¬ ( p ∨ q ) ↔ ( ¬ r → q )

1

18

Jak zapisać, że zdanie ¬(p ∧ q) jest fałszywe?

¬ ( p ∧ q )

0

Czyli nad spójnikiem głównym!
Jak zapisać, że zdanie ¬(p ∨ q) ↔ (¬r → q) jest
prawdziwe?

¬ ( p ∨ q ) ↔ ( ¬ r → q )

1

Jak zapisać, że zdanie ¬¬(r → s) jest prawdziwe?

19

Jak zapisać, że zdanie ¬(p ∧ q) jest fałszywe?

¬ ( p ∧ q )

0

Czyli nad spójnikiem głównym!
Jak zapisać, że zdanie ¬(p ∨ q) ↔ (¬r → q) jest
prawdziwe?

¬ ( p ∨ q ) ↔ ( ¬ r → q )

1

Jak zapisać, że zdanie ¬¬(r → s) jest prawdziwe?

¬ ¬ ( r → s )

1

20

Jak wartości logiczne składników wpływają na wartość
logiczną zdania złożonego?

21

Jak wartości logiczne składników wpływają na wartość
logiczną zdania złożonego?

Przykład.

22

Jak wartości logiczne składników wpływają na wartość
logiczną zdania złożonego?

Przykład. Wiemy, że Jan był w kinie, ale nie był w
teatrze. Jaką wartość logiczną ma zdanie:

23

Jak wartości logiczne składników wpływają na wartość
logiczną zdania złożonego?

Przykład. Wiemy, że Jan był w kinie, ale nie był w
teatrze. Jaką wartość logiczną ma zdanie:

Jan był w kinie i Jan był w teatrze

24

Jak wartości logiczne składników wpływają na wartość
logiczną zdania złożonego?

Przykład. Wiemy, że Jan był w kinie, ale nie był w
teatrze. Jaką wartość logiczną ma zdanie:

Jan był w kinie i Jan był w teatrze

a zdanie

Jan był w kinie lub Jan był w teatrze

25

Jak wartości logiczne składników wpływają na wartość
logiczną zdania złożonego?

Przykład. Wiemy, że Jan był w kinie, ale nie był w
teatrze. Jaką wartość logiczną ma zdanie:

Jan był w kinie i Jan był w teatrze

a zdanie

Jan był w kinie lub Jan był w teatrze

a zdanie

Nieprawda, że Jan był w kinie

26

Tabelki prawdziwościowe

dla spójników zdaniowych

27

p q ¬p p ∧ q p ∨ q p → q p ↔ q
0 0
0 1
1 0
1 1

28

p q ¬p p ∧ q p ∨ q p → q p ↔ q
0 0
0 1
1 0
1 1 0

29

p q ¬p p ∧ q p ∨ q p → q p ↔ q
0 0
0 1
1 0 0
1 1 0

30

p q ¬p p ∧ q p ∨ q p → q p ↔ q
0 0
0 1 1
1 0 0
1 1 0

31

p q ¬p p ∧ q p ∨ q p → q p ↔ q
0 0 1
0 1 1
1 0 0
1 1 0

32

p q ¬p p ∧ q p ∨ q p → q p ↔ q
0 0 1
0 1 1
1 0 0
1 1 0

1

33

p q ¬p p ∧ q p ∨ q p → q p ↔ q
0 0 1
0 1 1
1 0 0

0

1 1 0

1

34

p q ¬p p ∧ q p ∨ q p → q p ↔ q
0 0 1
0 1 1

0

1 0 0

0

1 1 0

1

35

p q ¬p p ∧ q p ∨ q p → q p ↔ q
0 0 1

0

0 1 1

0

1 0 0

0

1 1 0

1

36

p q ¬p p ∧ q p ∨ q p → q p ↔ q
0 0 1

0

0 1 1

0

1 0 0

0

1 1 0

1

1

37

p q ¬p p ∧ q p ∨ q p → q p ↔ q
0 0 1

0

0 1 1

0

1 0 0

0

1

1 1 0

1

1

38

p q ¬p p ∧ q p ∨ q p → q p ↔ q
0 0 1

0

0 1 1

0

1

1 0 0

0

1

1 1 0

1

1

39

p q ¬p p ∧ q p ∨ q p → q p ↔ q
0 0 1

0

0

0 1 1

0

1

1 0 0

0

1

1 1 0

1

1

40

p q ¬p p ∧ q p ∨ q p → q p ↔ q
0 0 1

0

0

0 1 1

0

1

1 0 0

0

1

1 1 0

1

1

1

41

p q ¬p p ∧ q p ∨ q p → q p ↔ q
0 0 1

0

0

0 1 1

0

1

1 0 0

0

1

0

1 1 0

1

1

1

42

p q ¬p p ∧ q p ∨ q p → q p ↔ q
0 0 1

0

0

0 1 1

0

1

1

1 0 0

0

1

0

1 1 0

1

1

1

43

p q ¬p p ∧ q p ∨ q p → q p ↔ q
0 0 1

0

0

1

0 1 1

0

1

1

1 0 0

0

1

0

1 1 0

1

1

1

44

p q ¬p p ∧ q p ∨ q p → q p ↔ q
0 0 1

0

0

1

0 1 1

0

1

1

1 0 0

0

1

0

1 1 0

1

1

1

1

45

p q ¬p p ∧ q p ∨ q p → q p ↔ q
0 0 1

0

0

1

0 1 1

0

1

1

1 0 0

0

1

0

0

1 1 0

1

1

1

1

46

p q ¬p p ∧ q p ∨ q p → q p ↔ q
0 0 1

0

0

1

0 1 1

0

1

1

0

1 0 0

0

1

0

0

1 1 0

1

1

1

1

47

p q ¬p p ∧ q p ∨ q p → q p ↔ q
0 0 1

0

0

1

1

0 1 1

0

1

1

0

1 0 0

0

1

0

0

1 1 0

1

1

1

1

48

Jak to zapamiętać?

p q ¬p p ∧ q p ∨ q p → q p ↔ q
0 0 1

0

0

1

1

0 1 1

0

1

1

0

1 0 0

0

1

0

0

1 1 0

1

1

1

1

49

Jak to zapamiętać?

p q ¬p p ∧ q p ∨ q p → q p ↔ q
0 0 1

0

0

1

1

0 1 1

0

1

1

0

1 0 0

0

1

0

0

1 1 0

1

1

1

1

50

Znając wartości logiczne zdań atomowych można obli-
czyć wartość logiczną zdania złożonego.

51

Znając wartości logiczne zdań atomowych można obli-
czyć wartość logiczną zdania złożonego.

Przyład 1. Rozważmy zdanie o schemacie:

52

Znając wartości logiczne zdań atomowych można obli-
czyć wartość logiczną zdania złożonego.

Przyład 1. Rozważmy zdanie o schemacie:

¬(p ∨ q) ↔ (¬s → (q ∧ p)),

53

Znając wartości logiczne zdań atomowych można obli-
czyć wartość logiczną zdania złożonego.

Przyład 1. Rozważmy zdanie o schemacie:

¬(p ∨ q) ↔ (¬s → (q ∧ p)),

przy czym p = 1, q = 0, s = 0.

54

Znając wartości logiczne zdań atomowych można obli-
czyć wartość logiczną zdania złożonego.

Przyład 1. Rozważmy zdanie o schemacie:

¬(p ∨ q) ↔ (¬s → (q ∧ p)),

przy czym p = 1, q = 0, s = 0. Zatem:

55

Znając wartości logiczne zdań atomowych można obli-
czyć wartość logiczną zdania złożonego.

Przyład 1. Rozważmy zdanie o schemacie:

¬(p ∨ q) ↔ (¬s → (q ∧ p)),

przy czym p = 1, q = 0, s = 0. Zatem:

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

1

0

0

0

1

56

Znając wartości logiczne zdań atomowych można obli-
czyć wartość logiczną zdania złożonego.

Przyład 1. Rozważmy zdanie o schemacie:

¬(p ∨ q) ↔ (¬s → (q ∧ p)),

przy czym p = 1, q = 0, s = 0. Zatem:

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

1 1 0

0

0

1

57

Znając wartości logiczne zdań atomowych można obli-
czyć wartość logiczną zdania złożonego.

Przyład 1. Rozważmy zdanie o schemacie:

¬(p ∨ q) ↔ (¬s → (q ∧ p)),

przy czym p = 1, q = 0, s = 0. Zatem:

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

0

1 1 0

0

0

1

58

Znając wartości logiczne zdań atomowych można obli-
czyć wartość logiczną zdania złożonego.

Przyład 1. Rozważmy zdanie o schemacie:

¬(p ∨ q) ↔ (¬s → (q ∧ p)),

przy czym p = 1, q = 0, s = 0. Zatem:

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

0

1 1 0

1 0

0

1

59

Znając wartości logiczne zdań atomowych można obli-
czyć wartość logiczną zdania złożonego.

Przyład 1. Rozważmy zdanie o schemacie:

¬(p ∨ q) ↔ (¬s → (q ∧ p)),

przy czym p = 1, q = 0, s = 0. Zatem:

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

0

1 1 0

1 0

0 0 1

60

Znając wartości logiczne zdań atomowych można obli-
czyć wartość logiczną zdania złożonego.

Przyład 1. Rozważmy zdanie o schemacie:

¬(p ∨ q) ↔ (¬s → (q ∧ p)),

przy czym p = 1, q = 0, s = 0. Zatem:

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

0

1 1 0

1 0 0

0 0 1

61

Znając wartości logiczne zdań atomowych można obli-
czyć wartość logiczną zdania złożonego.

Przyład 1. Rozważmy zdanie o schemacie:

¬(p ∨ q) ↔ (¬s → (q ∧ p)),

przy czym p = 1, q = 0, s = 0. Zatem:

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

0

1 1 0

1

1 0 0

0 0 1

62

Przyład 2. Rozważmy zdanie o schemacie:

¬¬(¬p ↔ (s ∧ q)) ∨ (q → ¬(p ∧ s)),

przy czym p = 0, q = 0, s = 1.

63

Przyład 2. Rozważmy zdanie o schemacie:

¬¬(¬p ↔ (s ∧ q)) ∨ (q → ¬(p ∧ s)),

przy czym p = 0, q = 0, s = 1. Zatem obliczamy:

64

Przyład 2. Rozważmy zdanie o schemacie:

¬¬(¬p ↔ (s ∧ q)) ∨ (q → ¬(p ∧ s)),

przy czym p = 0, q = 0, s = 1. Zatem obliczamy:

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

65

Przyład 2. Rozważmy zdanie o schemacie:

¬¬(¬p ↔ (s ∧ q)) ∨ (q → ¬(p ∧ s)),

przy czym p = 0, q = 0, s = 1. Zatem obliczamy:

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

0

1

0

0

0

1

66

Przyład 2. Rozważmy zdanie o schemacie:

¬¬(¬p ↔ (s ∧ q)) ∨ (q → ¬(p ∧ s)),

przy czym p = 0, q = 0, s = 1. Zatem obliczamy:

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

1 0

1

0

0

0

1

67

Przyład 2. Rozważmy zdanie o schemacie:

¬¬(¬p ↔ (s ∧ q)) ∨ (q → ¬(p ∧ s)),

przy czym p = 0, q = 0, s = 1. Zatem obliczamy:

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

1 0

1 0 0

0

0

1

68

Przyład 2. Rozważmy zdanie o schemacie:

¬¬(¬p ↔ (s ∧ q)) ∨ (q → ¬(p ∧ s)),

przy czym p = 0, q = 0, s = 1. Zatem obliczamy:

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

1 0 0

1 0 0

0

0

1

69

Przyład 2. Rozważmy zdanie o schemacie:

¬¬(¬p ↔ (s ∧ q)) ∨ (q → ¬(p ∧ s)),

przy czym p = 0, q = 0, s = 1. Zatem obliczamy:

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

1

1 0 0

1 0 0

0

0

1

70

Przyład 2. Rozważmy zdanie o schemacie:

¬¬(¬p ↔ (s ∧ q)) ∨ (q → ¬(p ∧ s)),

przy czym p = 0, q = 0, s = 1. Zatem obliczamy:

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

0 1

1 0 0

1 0 0

0

0

1

71

Przyład 2. Rozważmy zdanie o schemacie:

¬¬(¬p ↔ (s ∧ q)) ∨ (q → ¬(p ∧ s)),

przy czym p = 0, q = 0, s = 1. Zatem obliczamy:

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

0 1

1 0 0

1 0 0

0

0 0 1

72

Przyład 2. Rozważmy zdanie o schemacie:

¬¬(¬p ↔ (s ∧ q)) ∨ (q → ¬(p ∧ s)),

przy czym p = 0, q = 0, s = 1. Zatem obliczamy:

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

0 1

1 0 0

1 0 0

0

1

0 0 1

73

Przyład 2. Rozważmy zdanie o schemacie:

¬¬(¬p ↔ (s ∧ q)) ∨ (q → ¬(p ∧ s)),

przy czym p = 0, q = 0, s = 1. Zatem obliczamy:

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

0 1

1 0 0

1 0 0

0 1 1

0 0 1

74

Przyład 2. Rozważmy zdanie o schemacie:

¬¬(¬p ↔ (s ∧ q)) ∨ (q → ¬(p ∧ s)),

przy czym p = 0, q = 0, s = 1. Zatem obliczamy:

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

0 1

1 0 0

1 0 0

1

0 1 1

0 0 1

75

Przyład 3. Co można powiedzieć o wartości logicznej
składników, jeśli implikacja p → q jest fałszywa?

76

Przyład 3. Co można powiedzieć o wartości logicznej
składników, jeśli implikacja p → q jest fałszywa?

p → q

77

Przyład 3. Co można powiedzieć o wartości logicznej
składników, jeśli implikacja p → q jest fałszywa?

p → q

0

78

Przyład 3. Co można powiedzieć o wartości logicznej
składników, jeśli implikacja p → q jest fałszywa?

p → q
1 0 0

79

Przyład 4. Co można powiedzieć o wartości logicznej
składników, jeśli implikacja p → q jest prawdziwa?

80

Przyład 4. Co można powiedzieć o wartości logicznej
składników, jeśli implikacja p → q jest prawdziwa?

p → q

1

81

Przyład 4. Co można powiedzieć o wartości logicznej
składników, jeśli implikacja p → q jest prawdziwa?

p → q

1

Nic!

82

Przyład 5. Co można powiedzieć o wartości logicznej
składników, jeśli formuła

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

jest fałszywa?

83

Przyład 5. Co można powiedzieć o wartości logicznej
składników, jeśli formuła

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

jest fałszywa? Obliczamy:

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

84

Przyład 5. Co można powiedzieć o wartości logicznej
składników, jeśli formuła

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

jest fałszywa? Obliczamy:

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

0

85

Przyład 5. Co można powiedzieć o wartości logicznej
składników, jeśli formuła

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

jest fałszywa? Obliczamy:

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

0

0

86

Przyład 5. Co można powiedzieć o wartości logicznej
składników, jeśli formuła

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

jest fałszywa? Obliczamy:

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

0

0

0

87

Przyład 5. Co można powiedzieć o wartości logicznej
składników, jeśli formuła

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

jest fałszywa? Obliczamy:

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

0

0

1

0

88

Przyład 5. Co można powiedzieć o wartości logicznej
składników, jeśli formuła

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

jest fałszywa? Obliczamy:

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

0

0

1

0 0

89

Przyład 5. Co można powiedzieć o wartości logicznej
składników, jeśli formuła

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

jest fałszywa? Obliczamy:

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

0

0

0

1

0 0

90

Przyład 5. Co można powiedzieć o wartości logicznej
składników, jeśli formuła

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

jest fałszywa? Obliczamy:

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

0

0

0

0

1

0 0

91

Przyład 5. Co można powiedzieć o wartości logicznej
składników, jeśli formuła

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

jest fałszywa? Obliczamy:

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

1 0

0

0

0

1

0 0

92

Przyład 5. Co można powiedzieć o wartości logicznej
składników, jeśli formuła

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

jest fałszywa? Obliczamy:

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

1 1 0

0

0

0

1

0 0

93

Przyład 5. Co można powiedzieć o wartości logicznej
składników, jeśli formuła

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

jest fałszywa? Obliczamy:

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

1 1 0

0

0 0

0

1

0 0

94

Przyład 5. Co można powiedzieć o wartości logicznej
składników, jeśli formuła

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

jest fałszywa? Obliczamy:

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

1 1 0

0

1

0 0

0

1

0 0

95

Przyład 5. Co można powiedzieć o wartości logicznej
składników, jeśli formuła

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

jest fałszywa? Obliczamy:

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

1 1 0

0

1 0 0 0

0

1

0 0

96

Przyład 5. Co można powiedzieć o wartości logicznej
składników, jeśli formuła

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

jest fałszywa? Obliczamy:

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

1 1 0

0

1 0 0 0

0

0 1

0 0

97

Przyład 5. Co można powiedzieć o wartości logicznej
składników, jeśli formuła

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

jest fałszywa? Obliczamy:

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

1 1 0

0

1 0 0 0

0

1 0 1

0 0

98

Przyład 5. Co można powiedzieć o wartości logicznej
składników, jeśli formuła

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

jest fałszywa? Obliczamy:

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

1 1 0

0

1 0 0 0

0

1 0 1

0 0

Zatem:

99

Przyład 5. Co można powiedzieć o wartości logicznej
składników, jeśli formuła

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

jest fałszywa? Obliczamy:

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

1 1 0

0

1 0 0 0

0

1 0 1

0 0

Zatem:

p = 0,

r = 0,

q =?

100

Stanosz 7, 8, 9, 10, 11

101

Łamigłówka 1. Na rozprawie sądowej zapytano świad-
ka:
„Czy to prawda, że jeśli Abacki był na miejscu zbrodni,
to Babacki też był na miejscu zbrodni?”,
ten zaś zgodnie z prawdą odpowiedział:
„Jeśli to prawda, to Abacki był na miejscu zbrodni”.

Który z pary podejrzanych był na pewno na miejscu
zbrodni?

102

Łamigłówka 2. Ktoś o kim wiadomo, że jest „praw-
dziwkiem” albo „fałszywkiem”, mówi:
„Jestem filatelistą”,
„Nie jestem filatelistą lub jestem melomanem”,
„Jeżeli nie jestem brydżystą to nie jestem melomanem”.

Czy ten ktoś jest „prawdziwkiem” czy „fałszywkiem”?

103

Łamigłówka 3. W dokładnie jednym z trzech pudełek znajduje
się szaragd. Pozostałe dwa są puste. Na pudełkach umieszczone są
napisy; na pierwszym:
„W tym pudełku nie ma szmaragdu”,
„Szmaragd jest w drugim pudełku”,
na drugim:
„W pierwszym pudełku nie ma szmaragdu”,
„Szmaragd jest trzecim pudełku”,
na trzecim:
„W tym pudełku nie ma szmaragdu”,
„Szmaragd jest w pierwszym pudełku”.

W jednej z par napisów oba zdania są prawdziwe, w jednej — oba
fałszywe, a w jednej jedno zdanie jest prawdziwe, a jedno fałszywe.
W którym pudełku jest szmaragd?

104

Łamigłówka 4. Wiadomo że:
Jeżeli Jan jest kawalerem, to Stefan też jest kawalerem.
Jeżeli Paweł nie jest kawalerem, to Jan jest kawalerem.
Nie jest prawdą, że jeśli Stefan jest kawalerem lub Pa-
weł jest kawalerem, to Jan jest kawalerem.

Który z nich jest na pewno kawalerem, a który na pewno
nie jest?

105

Definicja. Przypisanie wartości logicznych wszystkim
zdaniom prostym występującym w zdaniu α nazywamy
wartościowaniem zdania α.

106

Przykład 1. Rozważmy formułę (p ∨ r) → (p ∧ r).
Mamy cztery wartościowania dla tego zdania:

107

Przykład 1. Rozważmy formułę (p ∨ r) → (p ∧ r).
Mamy cztery wartościowania dla tego zdania:
p = 0, r = 0,

108

Przykład 1. Rozważmy formułę (p ∨ r) → (p ∧ r).
Mamy cztery wartościowania dla tego zdania:
p = 0, r = 0,

p = 0, r = 1

109

Przykład 1. Rozważmy formułę (p ∨ r) → (p ∧ r).
Mamy cztery wartościowania dla tego zdania:
p = 0, r = 0,

p = 0, r = 1

p = 1, r = 0,

110

Przykład 1. Rozważmy formułę (p ∨ r) → (p ∧ r).
Mamy cztery wartościowania dla tego zdania:
p = 0, r = 0,

p = 0, r = 1

p = 1, r = 0,

p = 1, r = 1

111

Przykład 1. Rozważmy formułę (p ∨ r) → (p ∧ r).
Mamy cztery wartościowania dla tego zdania:
p = 0, r = 0,

p = 0, r = 1

p = 1, r = 0,

p = 1, r = 1

Obliczamy:

112

Przykład 1. Rozważmy formułę (p ∨ r) → (p ∧ r).
Mamy cztery wartościowania dla tego zdania:
p = 0, r = 0,

p = 0, r = 1

p = 1, r = 0,

p = 1, r = 1

Obliczamy:

( p ∨ r ) → ( p ∧ r )

0

0

0

0

113

Przykład 1. Rozważmy formułę (p ∨ r) → (p ∧ r).
Mamy cztery wartościowania dla tego zdania:
p = 0, r = 0,

p = 0, r = 1

p = 1, r = 0,

p = 1, r = 1

Obliczamy:

( p ∨ r ) → ( p ∧ r )

0 0 0

0

0

114

Przykład 1. Rozważmy formułę (p ∨ r) → (p ∧ r).
Mamy cztery wartościowania dla tego zdania:
p = 0, r = 0,

p = 0, r = 1

p = 1, r = 0,

p = 1, r = 1

Obliczamy:

( p ∨ r ) → ( p ∧ r )

0 0 0

0 0 0

115

Przykład 1. Rozważmy formułę (p ∨ r) → (p ∧ r).
Mamy cztery wartościowania dla tego zdania:
p = 0, r = 0,

p = 0, r = 1

p = 1, r = 0,

p = 1, r = 1

Obliczamy:

( p ∨ r ) → ( p ∧ r )

0 0 0

1

0 0 0

116

Przykład 1. Rozważmy formułę (p ∨ r) → (p ∧ r).
Mamy cztery wartościowania dla tego zdania:
p = 0, r = 0,

p = 0, r = 1

p = 1, r = 0,

p = 1, r = 1

Obliczamy:

( p ∨ r ) → ( p ∧ r )

0 0 0

1

0 0 0

0

1

0

1

117

Przykład 1. Rozważmy formułę (p ∨ r) → (p ∧ r).
Mamy cztery wartościowania dla tego zdania:
p = 0, r = 0,

p = 0, r = 1

p = 1, r = 0,

p = 1, r = 1

Obliczamy:

( p ∨ r ) → ( p ∧ r )

0 0 0

1

0 0 0

0 1 1

0

1

118

Przykład 1. Rozważmy formułę (p ∨ r) → (p ∧ r).
Mamy cztery wartościowania dla tego zdania:
p = 0, r = 0,

p = 0, r = 1

p = 1, r = 0,

p = 1, r = 1

Obliczamy:

( p ∨ r ) → ( p ∧ r )

0 0 0

1

0 0 0

0 1 1

0 0 1

119

Przykład 1. Rozważmy formułę (p ∨ r) → (p ∧ r).
Mamy cztery wartościowania dla tego zdania:
p = 0, r = 0,

p = 0, r = 1

p = 1, r = 0,

p = 1, r = 1

Obliczamy:

( p ∨ r ) → ( p ∧ r )

0 0 0

1

0 0 0

0 1 1

0

0 0 1

120

Przykład 1. Rozważmy formułę (p ∨ r) → (p ∧ r).
Mamy cztery wartościowania dla tego zdania:
p = 0, r = 0,

p = 0, r = 1

p = 1, r = 0,

p = 1, r = 1

Obliczamy:

( p ∨ r ) → ( p ∧ r )

0 0 0

1

0 0 0

0 1 1

0

0 0 1

1

0

1

0

121

Przykład 1. Rozważmy formułę (p ∨ r) → (p ∧ r).
Mamy cztery wartościowania dla tego zdania:
p = 0, r = 0,

p = 0, r = 1

p = 1, r = 0,

p = 1, r = 1

Obliczamy:

( p ∨ r ) → ( p ∧ r )

0 0 0

1

0 0 0

0 1 1

0

0 0 1

1 1 0

1

0

122

Przykład 1. Rozważmy formułę (p ∨ r) → (p ∧ r).
Mamy cztery wartościowania dla tego zdania:
p = 0, r = 0,

p = 0, r = 1

p = 1, r = 0,

p = 1, r = 1

Obliczamy:

( p ∨ r ) → ( p ∧ r )

0 0 0

1

0 0 0

0 1 1

0

0 0 1

1 1 0

1 0 0

123

Przykład 1. Rozważmy formułę (p ∨ r) → (p ∧ r).
Mamy cztery wartościowania dla tego zdania:
p = 0, r = 0,

p = 0, r = 1

p = 1, r = 0,

p = 1, r = 1

Obliczamy:

( p ∨ r ) → ( p ∧ r )

0 0 0

1

0 0 0

0 1 1

0

0 0 1

1 1 0

0

1 0 0

124

Przykład 1. Rozważmy formułę (p ∨ r) → (p ∧ r).
Mamy cztery wartościowania dla tego zdania:
p = 0, r = 0,

p = 0, r = 1

p = 1, r = 0,

p = 1, r = 1

Obliczamy:

( p ∨ r ) → ( p ∧ r )

0 0 0

1

0 0 0

0 1 1

0

0 0 1

1 1 0

0

1 0 0

1

1

1

1

125

Przykład 1. Rozważmy formułę (p ∨ r) → (p ∧ r).
Mamy cztery wartościowania dla tego zdania:
p = 0, r = 0,

p = 0, r = 1

p = 1, r = 0,

p = 1, r = 1

Obliczamy:

( p ∨ r ) → ( p ∧ r )

0 0 0

1

0 0 0

0 1 1

0

0 0 1

1 1 0

0

1 0 0

1 1 1

1

1

126

Przykład 1. Rozważmy formułę (p ∨ r) → (p ∧ r).
Mamy cztery wartościowania dla tego zdania:
p = 0, r = 0,

p = 0, r = 1

p = 1, r = 0,

p = 1, r = 1

Obliczamy:

( p ∨ r ) → ( p ∧ r )

0 0 0

1

0 0 0

0 1 1

0

0 0 1

1 1 0

0

1 0 0

1 1 1

1 1 1

127

Przykład 1. Rozważmy formułę (p ∨ r) → (p ∧ r).
Mamy cztery wartościowania dla tego zdania:
p = 0, r = 0,

p = 0, r = 1

p = 1, r = 0,

p = 1, r = 1

Obliczamy:

( p ∨ r ) → ( p ∧ r )

0 0 0

1

0 0 0

0 1 1

0

0 0 1

1 1 0

0

1 0 0

1 1 1

1

1 1 1

128

Przykład 1. Rozważmy formułę (p ∨ r) → (p ∧ r).
Mamy cztery wartościowania dla tego zdania:
p = 0, r = 0,

p = 0, r = 1

p = 1, r = 0,

p = 1, r = 1

Obliczamy:

( p ∨ r ) → ( p ∧ r )

0 0 0

1

0 0 0

0 1 1

0

0 0 1

1 1 0

0

1 0 0

1 1 1

1

1 1 1

Wartościowanie I i IV potwierdza (weryfikuje) zdanie,

129

Przykład 1. Rozważmy formułę (p ∨ r) → (p ∧ r).
Mamy cztery wartościowania dla tego zdania:
p = 0, r = 0,

p = 0, r = 1

p = 1, r = 0,

p = 1, r = 1

Obliczamy:

( p ∨ r ) → ( p ∧ r )

0 0 0

1

0 0 0

0 1 1

0

0 0 1

1 1 0

0

1 0 0

1 1 1

1

1 1 1

Wartościowanie I i IV potwierdza (weryfikuje) zdanie,
a wartościowanie II i III je obala (falsyfikuje)

130

Przykład 2. Formuła (p → q) ↔ r posiada 8 warto-
ściowań:

131

Przykład 2. Formuła (p → q) ↔ r posiada 8 warto-
ściowań:

p = 0, q = 0, r = 0,
p = 0, q = 0, r = 1,
p = 0, q = 1, r = 0,
p = 0, q = 1, r = 1,
p = 1, q = 0, r = 0,
p = 1, q = 0, r = 1,
p = 1, q = 1, r = 0,

p = 1, q = 1, r = 1

132

Ile wartościowań posiada formuła (p → q) ∧ (r ↔ s)?

133

Ile wartościowań posiada formuła (p → q) ∧ (r ↔ s)?

16

134

Ile wartościowań posiada formuła (p → q) ∧ (r ↔ s)?

16

czyli

2

4

135

Ile wartościowań posiada formuła (p → q) ∧ (r ↔ s)?

16

czyli

2

4

Analogicznie, formuła w której występuje n zdań pro-
stych posiada

136

Ile wartościowań posiada formuła (p → q) ∧ (r ↔ s)?

16

czyli

2

4

Analogicznie, formuła w której występuje n zdań pro-
stych posiada

2

n

wartościowań.

137

Definicja. Tautologią nazywamy zdanie, które jest
prawdziwe przy każdym wartościowaniu.

138

Definicja. Tautologią nazywamy zdanie, które jest
prawdziwe przy każdym wartościowaniu.

Innymi słowy, tautologia to takie zdanie, które jest we-
ryfikowane przez dowolne wartościowanie.

139

Definicja. Tautologią nazywamy zdanie, które jest
prawdziwe przy każdym wartościowaniu.

Innymi słowy, tautologia to takie zdanie, które jest we-
ryfikowane przez dowolne wartościowanie.

Analogicznie, kontrtautologia to formuła, która jest
fałszywa przy każdym wartościowaniu.

140

Definicja. Tautologią nazywamy zdanie, które jest
prawdziwe przy każdym wartościowaniu.

Innymi słowy, tautologia to takie zdanie, które jest we-
ryfikowane przez dowolne wartościowanie.

Analogicznie, kontrtautologia to formuła, która jest
fałszywa przy każdym wartościowaniu.

Czyli, każde wartościowanie falsyfikuje kontrtautologię.

141

Ćwiczenie 1. Sprawdzić czy formuła
¬(p ∧ q) ↔ (¬p ∧ ¬q) jest tautologią.

142

Ćwiczenie 1. Sprawdzić czy formuła
¬(p ∧ q) ↔ (¬p ∧ ¬q) jest tautologią.

Rozważamy wszystkie (cztery) wartościowania:

143

Ćwiczenie 1. Sprawdzić czy formuła
¬(p ∧ q) ↔ (¬p ∧ ¬q) jest tautologią.

Rozważamy wszystkie (cztery) wartościowania:

¬ ( p ∧ q ) ↔ ( ¬ p ∧ ¬ q )

144

Ćwiczenie 1. Sprawdzić czy formuła
¬(p ∧ q) ↔ (¬p ∧ ¬q) jest tautologią.

Rozważamy wszystkie (cztery) wartościowania:

¬ ( p ∧ q ) ↔ ( ¬ p ∧ ¬ q )

0

0

0

0

145

Ćwiczenie 1. Sprawdzić czy formuła
¬(p ∧ q) ↔ (¬p ∧ ¬q) jest tautologią.

Rozważamy wszystkie (cztery) wartościowania:

¬ ( p ∧ q ) ↔ ( ¬ p ∧ ¬ q )

0 0 0

0

0

146

Ćwiczenie 1. Sprawdzić czy formuła
¬(p ∧ q) ↔ (¬p ∧ ¬q) jest tautologią.

Rozważamy wszystkie (cztery) wartościowania:

¬ ( p ∧ q ) ↔ ( ¬ p ∧ ¬ q )

1

0 0 0

0

0

147

Ćwiczenie 1. Sprawdzić czy formuła
¬(p ∧ q) ↔ (¬p ∧ ¬q) jest tautologią.

Rozważamy wszystkie (cztery) wartościowania:

¬ ( p ∧ q ) ↔ ( ¬ p ∧ ¬ q )

1

0 0 0

1 0

0

148

Ćwiczenie 1. Sprawdzić czy formuła
¬(p ∧ q) ↔ (¬p ∧ ¬q) jest tautologią.

Rozważamy wszystkie (cztery) wartościowania:

¬ ( p ∧ q ) ↔ ( ¬ p ∧ ¬ q )

1

0 0 0

1 0

1 0

149

Ćwiczenie 1. Sprawdzić czy formuła
¬(p ∧ q) ↔ (¬p ∧ ¬q) jest tautologią.

Rozważamy wszystkie (cztery) wartościowania:

¬ ( p ∧ q ) ↔ ( ¬ p ∧ ¬ q )

1

0 0 0

1 0 1 1 0

150

Ćwiczenie 1. Sprawdzić czy formuła
¬(p ∧ q) ↔ (¬p ∧ ¬q) jest tautologią.

Rozważamy wszystkie (cztery) wartościowania:

¬ ( p ∧ q ) ↔ ( ¬ p ∧ ¬ q )

1

0 0 0

1

1 0 1 1 0

151

Ćwiczenie 1. Sprawdzić czy formuła
¬(p ∧ q) ↔ (¬p ∧ ¬q) jest tautologią.

Rozważamy wszystkie (cztery) wartościowania:

¬ ( p ∧ q ) ↔ ( ¬ p ∧ ¬ q )

1

0 0 0

1

1 0 1 1 0

0

1

0

1

152

Ćwiczenie 1. Sprawdzić czy formuła
¬(p ∧ q) ↔ (¬p ∧ ¬q) jest tautologią.

Rozważamy wszystkie (cztery) wartościowania:

¬ ( p ∧ q ) ↔ ( ¬ p ∧ ¬ q )

1

0 0 0

1

1 0 1 1 0

0 0 1

0

1

153

Ćwiczenie 1. Sprawdzić czy formuła
¬(p ∧ q) ↔ (¬p ∧ ¬q) jest tautologią.

Rozważamy wszystkie (cztery) wartościowania:

¬ ( p ∧ q ) ↔ ( ¬ p ∧ ¬ q )

1

0 0 0

1

1 0 1 1 0

1

0 0 1

0

1

154

Ćwiczenie 1. Sprawdzić czy formuła
¬(p ∧ q) ↔ (¬p ∧ ¬q) jest tautologią.

Rozważamy wszystkie (cztery) wartościowania:

¬ ( p ∧ q ) ↔ ( ¬ p ∧ ¬ q )

1

0 0 0

1

1 0 1 1 0

1

0 0 1

1 0

1

155

Ćwiczenie 1. Sprawdzić czy formuła
¬(p ∧ q) ↔ (¬p ∧ ¬q) jest tautologią.

Rozważamy wszystkie (cztery) wartościowania:

¬ ( p ∧ q ) ↔ ( ¬ p ∧ ¬ q )

1

0 0 0

1

1 0 1 1 0

1

0 0 1

1 0

0 1

156

Ćwiczenie 1. Sprawdzić czy formuła
¬(p ∧ q) ↔ (¬p ∧ ¬q) jest tautologią.

Rozważamy wszystkie (cztery) wartościowania:

¬ ( p ∧ q ) ↔ ( ¬ p ∧ ¬ q )

1

0 0 0

1

1 0 1 1 0

1

0 0 1

1 0 0 0 1

157

Ćwiczenie 1. Sprawdzić czy formuła
¬(p ∧ q) ↔ (¬p ∧ ¬q) jest tautologią.

Rozważamy wszystkie (cztery) wartościowania:

¬ ( p ∧ q ) ↔ ( ¬ p ∧ ¬ q )

1

0 0 0

1

1 0 1 1 0

1

0 0 1

0

1 0 0 0 1

158

Ćwiczenie 1. Sprawdzić czy formuła
¬(p ∧ q) ↔ (¬p ∧ ¬q) jest tautologią.

Rozważamy wszystkie (cztery) wartościowania:

¬ ( p ∧ q ) ↔ ( ¬ p ∧ ¬ q )

1

0 0 0

1

1 0 1 1 0

1

0 0 1

0

1 0 0 0 1

1

0

1

0

159

Ćwiczenie 1. Sprawdzić czy formuła
¬(p ∧ q) ↔ (¬p ∧ ¬q) jest tautologią.

Rozważamy wszystkie (cztery) wartościowania:

¬ ( p ∧ q ) ↔ ( ¬ p ∧ ¬ q )

1

0 0 0

1

1 0 1 1 0

1

0 0 1

0

1 0 0 0 1

1 0 0

1

0

160

Ćwiczenie 1. Sprawdzić czy formuła
¬(p ∧ q) ↔ (¬p ∧ ¬q) jest tautologią.

Rozważamy wszystkie (cztery) wartościowania:

¬ ( p ∧ q ) ↔ ( ¬ p ∧ ¬ q )

1

0 0 0

1

1 0 1 1 0

1

0 0 1

0

1 0 0 0 1

1

1 0 0

1

0

161

Ćwiczenie 1. Sprawdzić czy formuła
¬(p ∧ q) ↔ (¬p ∧ ¬q) jest tautologią.

Rozważamy wszystkie (cztery) wartościowania:

¬ ( p ∧ q ) ↔ ( ¬ p ∧ ¬ q )

1

0 0 0

1

1 0 1 1 0

1

0 0 1

0

1 0 0 0 1

1

1 0 0

0 1

0

162

Ćwiczenie 1. Sprawdzić czy formuła
¬(p ∧ q) ↔ (¬p ∧ ¬q) jest tautologią.

Rozważamy wszystkie (cztery) wartościowania:

¬ ( p ∧ q ) ↔ ( ¬ p ∧ ¬ q )

1

0 0 0

1

1 0 1 1 0

1

0 0 1

0

1 0 0 0 1

1

1 0 0

0 1

1 0

163

Ćwiczenie 1. Sprawdzić czy formuła
¬(p ∧ q) ↔ (¬p ∧ ¬q) jest tautologią.

Rozważamy wszystkie (cztery) wartościowania:

¬ ( p ∧ q ) ↔ ( ¬ p ∧ ¬ q )

1

0 0 0

1

1 0 1 1 0

1

0 0 1

0

1 0 0 0 1

1

1 0 0

0 1 0 1 0

164

Ćwiczenie 1. Sprawdzić czy formuła
¬(p ∧ q) ↔ (¬p ∧ ¬q) jest tautologią.

Rozważamy wszystkie (cztery) wartościowania:

¬ ( p ∧ q ) ↔ ( ¬ p ∧ ¬ q )

1

0 0 0

1

1 0 1 1 0

1

0 0 1

0

1 0 0 0 1

1

1 0 0

0

0 1 0 1 0

165

Ćwiczenie 1. Sprawdzić czy formuła
¬(p ∧ q) ↔ (¬p ∧ ¬q) jest tautologią.

Rozważamy wszystkie (cztery) wartościowania:

¬ ( p ∧ q ) ↔ ( ¬ p ∧ ¬ q )

1

0 0 0

1

1 0 1 1 0

1

0 0 1

0

1 0 0 0 1

1

1 0 0

0

0 1 0 1 0

1

1

1

1

166

Ćwiczenie 1. Sprawdzić czy formuła
¬(p ∧ q) ↔ (¬p ∧ ¬q) jest tautologią.

Rozważamy wszystkie (cztery) wartościowania:

¬ ( p ∧ q ) ↔ ( ¬ p ∧ ¬ q )

1

0 0 0

1

1 0 1 1 0

1

0 0 1

0

1 0 0 0 1

1

1 0 0

0

0 1 0 1 0

1 1 1

1

1

167

Ćwiczenie 1. Sprawdzić czy formuła
¬(p ∧ q) ↔ (¬p ∧ ¬q) jest tautologią.

Rozważamy wszystkie (cztery) wartościowania:

¬ ( p ∧ q ) ↔ ( ¬ p ∧ ¬ q )

1

0 0 0

1

1 0 1 1 0

1

0 0 1

0

1 0 0 0 1

1

1 0 0

0

0 1 0 1 0

0

1 1 1

1

1

168

Ćwiczenie 1. Sprawdzić czy formuła
¬(p ∧ q) ↔ (¬p ∧ ¬q) jest tautologią.

Rozważamy wszystkie (cztery) wartościowania:

¬ ( p ∧ q ) ↔ ( ¬ p ∧ ¬ q )

1

0 0 0

1

1 0 1 1 0

1

0 0 1

0

1 0 0 0 1

1

1 0 0

0

0 1 0 1 0

0

1 1 1

0 1

1

169

Ćwiczenie 1. Sprawdzić czy formuła
¬(p ∧ q) ↔ (¬p ∧ ¬q) jest tautologią.

Rozważamy wszystkie (cztery) wartościowania:

¬ ( p ∧ q ) ↔ ( ¬ p ∧ ¬ q )

1

0 0 0

1

1 0 1 1 0

1

0 0 1

0

1 0 0 0 1

1

1 0 0

0

0 1 0 1 0

0

1 1 1

0 1

0 1

170

Ćwiczenie 1. Sprawdzić czy formuła
¬(p ∧ q) ↔ (¬p ∧ ¬q) jest tautologią.

Rozważamy wszystkie (cztery) wartościowania:

¬ ( p ∧ q ) ↔ ( ¬ p ∧ ¬ q )

1

0 0 0

1

1 0 1 1 0

1

0 0 1

0

1 0 0 0 1

1

1 0 0

0

0 1 0 1 0

0

1 1 1

0 1 0 0 1

171

Ćwiczenie 1. Sprawdzić czy formuła
¬(p ∧ q) ↔ (¬p ∧ ¬q) jest tautologią.

Rozważamy wszystkie (cztery) wartościowania:

¬ ( p ∧ q ) ↔ ( ¬ p ∧ ¬ q )

1

0 0 0

1

1 0 1 1 0

1

0 0 1

0

1 0 0 0 1

1

1 0 0

0

0 1 0 1 0

0

1 1 1

1

0 1 0 0 1

172

Ćwiczenie 1. Sprawdzić czy formuła
¬(p ∧ q) ↔ (¬p ∧ ¬q) jest tautologią.

Rozważamy wszystkie (cztery) wartościowania:

¬ ( p ∧ q ) ↔ ( ¬ p ∧ ¬ q )

1

0 0 0

1

1 0 1 1 0

1

0 0 1

0

1 0 0 0 1

1

1 0 0

0

0 1 0 1 0

0

1 1 1

1

0 1 0 0 1

Zatem to nie jest tautologia

173

Ćwiczenie 1. Sprawdzić czy formuła
¬(p ∧ q) ↔ (¬p ∧ ¬q) jest tautologią.

Rozważamy wszystkie (cztery) wartościowania:

¬ ( p ∧ q ) ↔ ( ¬ p ∧ ¬ q )

1

0 0 0

1

1 0 1 1 0

1

0 0 1

0

1 0 0 0 1

1

1 0 0

0

0 1 0 1 0

0

1 1 1

1

0 1 0 0 1

Zatem to nie jest tautologia

Nie jest to też kontrtautologia

174

Ćwiczenie 2. Sprawdzić czy poniższe zdanie jest tau-
tologią:
Jeżeli, jeśli Kolumb odkrył Amerykę, to Marco Polo nie
był w Ameryce, to jeśli Marco Polo nie był w Ameryce
to Kolumb odkrył Amerykę.

175

Ćwiczenie 2. Sprawdzić czy poniższe zdanie jest tau-
tologią:
Jeżeli, jeśli Kolumb odkrył Amerykę, to Marco Polo nie
był w Ameryce, to jeśli Marco Polo nie był w Ameryce
to Kolumb odkrył Amerykę.

Formalizujemy:

( k → ¬ m ) → ( ¬ m → k )

176

Ćwiczenie 2. Sprawdzić czy poniższe zdanie jest tau-
tologią:
Jeżeli, jeśli Kolumb odkrył Amerykę, to Marco Polo nie
był w Ameryce, to jeśli Marco Polo nie był w Ameryce
to Kolumb odkrył Amerykę.

Formalizujemy:

( k → ¬ m ) → ( ¬ m → k )

0

0

0

0

177

Ćwiczenie 2. Sprawdzić czy poniższe zdanie jest tau-
tologią:
Jeżeli, jeśli Kolumb odkrył Amerykę, to Marco Polo nie
był w Ameryce, to jeśli Marco Polo nie był w Ameryce
to Kolumb odkrył Amerykę.

Formalizujemy:

( k → ¬ m ) → ( ¬ m → k )

0

1 0

0

0

178

Ćwiczenie 2. Sprawdzić czy poniższe zdanie jest tau-
tologią:
Jeżeli, jeśli Kolumb odkrył Amerykę, to Marco Polo nie
był w Ameryce, to jeśli Marco Polo nie był w Ameryce
to Kolumb odkrył Amerykę.

Formalizujemy:

( k → ¬ m ) → ( ¬ m → k )

0 1 1 0

0

0

179

Ćwiczenie 2. Sprawdzić czy poniższe zdanie jest tau-
tologią:
Jeżeli, jeśli Kolumb odkrył Amerykę, to Marco Polo nie
był w Ameryce, to jeśli Marco Polo nie był w Ameryce
to Kolumb odkrył Amerykę.

Formalizujemy:

( k → ¬ m ) → ( ¬ m → k )

0 1 1 0

1 0

0

180

Ćwiczenie 2. Sprawdzić czy poniższe zdanie jest tau-
tologią:
Jeżeli, jeśli Kolumb odkrył Amerykę, to Marco Polo nie
był w Ameryce, to jeśli Marco Polo nie był w Ameryce
to Kolumb odkrył Amerykę.

Formalizujemy:

( k → ¬ m ) → ( ¬ m → k )

0 1 1 0

1 0 0 0

181

Ćwiczenie 2. Sprawdzić czy poniższe zdanie jest tau-
tologią:
Jeżeli, jeśli Kolumb odkrył Amerykę, to Marco Polo nie
był w Ameryce, to jeśli Marco Polo nie był w Ameryce
to Kolumb odkrył Amerykę.

Formalizujemy:

( k → ¬ m ) → ( ¬ m → k )

0 1 1 0

0

1 0 0 0

182

Ćwiczenie 2. Sprawdzić czy poniższe zdanie jest tau-
tologią:
Jeżeli, jeśli Kolumb odkrył Amerykę, to Marco Polo nie
był w Ameryce, to jeśli Marco Polo nie był w Ameryce
to Kolumb odkrył Amerykę.

Formalizujemy:

( k → ¬ m ) → ( ¬ m → k )

0 1 1 0

0

1 0 0 0

0

1

1

0

183

Ćwiczenie 2. Sprawdzić czy poniższe zdanie jest tau-
tologią:
Jeżeli, jeśli Kolumb odkrył Amerykę, to Marco Polo nie
był w Ameryce, to jeśli Marco Polo nie był w Ameryce
to Kolumb odkrył Amerykę.

Formalizujemy:

( k → ¬ m ) → ( ¬ m → k )

0 1 1 0

0

1 0 0 0

0

0 1

1

0

184

Ćwiczenie 2. Sprawdzić czy poniższe zdanie jest tau-
tologią:
Jeżeli, jeśli Kolumb odkrył Amerykę, to Marco Polo nie
był w Ameryce, to jeśli Marco Polo nie był w Ameryce
to Kolumb odkrył Amerykę.

Formalizujemy:

( k → ¬ m ) → ( ¬ m → k )

0 1 1 0

0

1 0 0 0

0 1 0 1

1

0

185

Ćwiczenie 2. Sprawdzić czy poniższe zdanie jest tau-
tologią:
Jeżeli, jeśli Kolumb odkrył Amerykę, to Marco Polo nie
był w Ameryce, to jeśli Marco Polo nie był w Ameryce
to Kolumb odkrył Amerykę.

Formalizujemy:

( k → ¬ m ) → ( ¬ m → k )

0 1 1 0

0

1 0 0 0

0 1 0 1

0 1

0

186

Ćwiczenie 2. Sprawdzić czy poniższe zdanie jest tau-
tologią:
Jeżeli, jeśli Kolumb odkrył Amerykę, to Marco Polo nie
był w Ameryce, to jeśli Marco Polo nie był w Ameryce
to Kolumb odkrył Amerykę.

Formalizujemy:

( k → ¬ m ) → ( ¬ m → k )

0 1 1 0

0

1 0 0 0

0 1 0 1

0 1 1 0

187

Ćwiczenie 2. Sprawdzić czy poniższe zdanie jest tau-
tologią:
Jeżeli, jeśli Kolumb odkrył Amerykę, to Marco Polo nie
był w Ameryce, to jeśli Marco Polo nie był w Ameryce
to Kolumb odkrył Amerykę.

Formalizujemy:

( k → ¬ m ) → ( ¬ m → k )

0 1 1 0

0

1 0 0 0

0 1 0 1

1

0 1 1 0

188

Ćwiczenie 2. Sprawdzić czy poniższe zdanie jest tau-
tologią:
Jeżeli, jeśli Kolumb odkrył Amerykę, to Marco Polo nie
był w Ameryce, to jeśli Marco Polo nie był w Ameryce
to Kolumb odkrył Amerykę.

Formalizujemy:

( k → ¬ m ) → ( ¬ m → k )

0 1 1 0

0

1 0 0 0

0 1 0 1

1

0 1 1 0

1

0

0

1

189

Ćwiczenie 2. Sprawdzić czy poniższe zdanie jest tau-
tologią:
Jeżeli, jeśli Kolumb odkrył Amerykę, to Marco Polo nie
był w Ameryce, to jeśli Marco Polo nie był w Ameryce
to Kolumb odkrył Amerykę.

Formalizujemy:

( k → ¬ m ) → ( ¬ m → k )

0 1 1 0

0

1 0 0 0

0 1 0 1

1

0 1 1 0

1

1 0

0

1

190

Ćwiczenie 2. Sprawdzić czy poniższe zdanie jest tau-
tologią:
Jeżeli, jeśli Kolumb odkrył Amerykę, to Marco Polo nie
był w Ameryce, to jeśli Marco Polo nie był w Ameryce
to Kolumb odkrył Amerykę.

Formalizujemy:

( k → ¬ m ) → ( ¬ m → k )

0 1 1 0

0

1 0 0 0

0 1 0 1

1

0 1 1 0

1 1 1 0

0

1

191

Ćwiczenie 2. Sprawdzić czy poniższe zdanie jest tau-
tologią:
Jeżeli, jeśli Kolumb odkrył Amerykę, to Marco Polo nie
był w Ameryce, to jeśli Marco Polo nie był w Ameryce
to Kolumb odkrył Amerykę.

Formalizujemy:

( k → ¬ m ) → ( ¬ m → k )

0 1 1 0

0

1 0 0 0

0 1 0 1

1

0 1 1 0

1 1 1 0

1 0

1

192

Ćwiczenie 2. Sprawdzić czy poniższe zdanie jest tau-
tologią:
Jeżeli, jeśli Kolumb odkrył Amerykę, to Marco Polo nie
był w Ameryce, to jeśli Marco Polo nie był w Ameryce
to Kolumb odkrył Amerykę.

Formalizujemy:

( k → ¬ m ) → ( ¬ m → k )

0 1 1 0

0

1 0 0 0

0 1 0 1

1

0 1 1 0

1 1 1 0

1 0 1 1

193

Ćwiczenie 2. Sprawdzić czy poniższe zdanie jest tau-
tologią:
Jeżeli, jeśli Kolumb odkrył Amerykę, to Marco Polo nie
był w Ameryce, to jeśli Marco Polo nie był w Ameryce
to Kolumb odkrył Amerykę.

Formalizujemy:

( k → ¬ m ) → ( ¬ m → k )

0 1 1 0

0

1 0 0 0

0 1 0 1

1

0 1 1 0

1 1 1 0

1

1 0 1 1

194

Ćwiczenie 2. Sprawdzić czy poniższe zdanie jest tau-
tologią:
Jeżeli, jeśli Kolumb odkrył Amerykę, to Marco Polo nie
był w Ameryce, to jeśli Marco Polo nie był w Ameryce
to Kolumb odkrył Amerykę.

Formalizujemy:

( k → ¬ m ) → ( ¬ m → k )

0 1 1 0

0

1 0 0 0

0 1 0 1

1

0 1 1 0

1 1 1 0

1

1 0 1 1

1

1

1

1

195

Ćwiczenie 2. Sprawdzić czy poniższe zdanie jest tau-
tologią:
Jeżeli, jeśli Kolumb odkrył Amerykę, to Marco Polo nie
był w Ameryce, to jeśli Marco Polo nie był w Ameryce
to Kolumb odkrył Amerykę.

Formalizujemy:

( k → ¬ m ) → ( ¬ m → k )

0 1 1 0

0

1 0 0 0

0 1 0 1

1

0 1 1 0

1 1 1 0

1

1 0 1 1

1

0 1

1

1

196

Ćwiczenie 2. Sprawdzić czy poniższe zdanie jest tau-
tologią:
Jeżeli, jeśli Kolumb odkrył Amerykę, to Marco Polo nie
był w Ameryce, to jeśli Marco Polo nie był w Ameryce
to Kolumb odkrył Amerykę.

Formalizujemy:

( k → ¬ m ) → ( ¬ m → k )

0 1 1 0

0

1 0 0 0

0 1 0 1

1

0 1 1 0

1 1 1 0

1

1 0 1 1

1 0 0 1

1

1

197

Ćwiczenie 2. Sprawdzić czy poniższe zdanie jest tau-
tologią:
Jeżeli, jeśli Kolumb odkrył Amerykę, to Marco Polo nie
był w Ameryce, to jeśli Marco Polo nie był w Ameryce
to Kolumb odkrył Amerykę.

Formalizujemy:

( k → ¬ m ) → ( ¬ m → k )

0 1 1 0

0

1 0 0 0

0 1 0 1

1

0 1 1 0

1 1 1 0

1

1 0 1 1

1 0 0 1

0 1

1

198

Ćwiczenie 2. Sprawdzić czy poniższe zdanie jest tau-
tologią:
Jeżeli, jeśli Kolumb odkrył Amerykę, to Marco Polo nie
był w Ameryce, to jeśli Marco Polo nie był w Ameryce
to Kolumb odkrył Amerykę.

Formalizujemy:

( k → ¬ m ) → ( ¬ m → k )

0 1 1 0

0

1 0 0 0

0 1 0 1

1

0 1 1 0

1 1 1 0

1

1 0 1 1

1 0 0 1

0 1 1 1

199

Ćwiczenie 2. Sprawdzić czy poniższe zdanie jest tau-
tologią:
Jeżeli, jeśli Kolumb odkrył Amerykę, to Marco Polo nie
był w Ameryce, to jeśli Marco Polo nie był w Ameryce
to Kolumb odkrył Amerykę.

Formalizujemy:

( k → ¬ m ) → ( ¬ m → k )

0 1 1 0

0

1 0 0 0

0 1 0 1

1

0 1 1 0

1 1 1 0

1

1 0 1 1

1 0 0 1

1

0 1 1 1

200

Ćwiczenie 2. Sprawdzić czy poniższe zdanie jest tau-
tologią:
Jeżeli, jeśli Kolumb odkrył Amerykę, to Marco Polo nie
był w Ameryce, to jeśli Marco Polo nie był w Ameryce
to Kolumb odkrył Amerykę.

Formalizujemy:

( k → ¬ m ) → ( ¬ m → k )

0 1 1 0

0

1 0 0 0

0 1 0 1

1

0 1 1 0

1 1 1 0

1

1 0 1 1

1 0 0 1

1

0 1 1 1

Nie jest to ani tautologia ani kontrtautologia

201

Ćwiczenie 3. Sprawdzić czy zdanie

((p → q) ∧ (q → s)) ↔ (p → s)

jest tautologią.

202

Metoda skrócona (niewprost)

203

Dowodzenie niewprost to następujący schemat:

204

Dowodzenie niewprost to następujący schemat:

•

chcemy dowieść zdania A

205

Dowodzenie niewprost to następujący schemat:

•

chcemy dowieść zdania A

•

zakładamy na odwrót, że zdanie ¬A jest prawdziwe
(jest to tzw. hipoteza niewprost)

206

Dowodzenie niewprost to następujący schemat:

•

chcemy dowieść zdania A

•

zakładamy na odwrót, że zdanie ¬A jest prawdziwe
(jest to tzw. hipoteza niewprost)

•

dedukujemy ...

207

Dowodzenie niewprost to następujący schemat:

•

chcemy dowieść zdania A

•

zakładamy na odwrót, że zdanie ¬A jest prawdziwe
(jest to tzw. hipoteza niewprost)

•

dedukujemy ...

•

w wyniku tej dedukcji uzyskujemy jakąś sprzeczność
(np. że 1=2)

208

Dowodzenie niewprost to następujący schemat:

•

chcemy dowieść zdania A

•

zakładamy na odwrót, że zdanie ¬A jest prawdziwe
(jest to tzw. hipoteza niewprost)

•

dedukujemy ...

•

w wyniku tej dedukcji uzyskujemy jakąś sprzeczność
(np. że 1=2)

•

skoro zdanie ¬A doprowadziło do absurdu, nie może
być prawdziwe

209

Dowodzenie niewprost to następujący schemat:

•

chcemy dowieść zdania A

•

zakładamy na odwrót, że zdanie ¬A jest prawdziwe
(jest to tzw. hipoteza niewprost)

•

dedukujemy ...

•

w wyniku tej dedukcji uzyskujemy jakąś sprzeczność
(np. że 1=2)

•

skoro zdanie ¬A doprowadziło do absurdu, nie może
być prawdziwe

•

zatem zdanie ¬A jest fałszywe

210

Dowodzenie niewprost to następujący schemat:

•

chcemy dowieść zdania A

•

zakładamy na odwrót, że zdanie ¬A jest prawdziwe
(jest to tzw. hipoteza niewprost)

•

dedukujemy ...

•

w wyniku tej dedukcji uzyskujemy jakąś sprzeczność
(np. że 1=2)

•

skoro zdanie ¬A doprowadziło do absurdu, nie może
być prawdziwe

•

zatem zdanie ¬A jest fałszywe

•

zatem zdanie A jest prawdziwe

211

Przykład 1. Sprawdzimy, czy formuła
((p → q) ∧ (q → r)) → (p → r)
jest tautologią.

212

Przykład 1. Sprawdzimy, czy formuła
((p → q) ∧ (q → r)) → (p → r)
jest tautologią.

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

213

Przykład 1. Sprawdzimy, czy formuła
((p → q) ∧ (q → r)) → (p → r)
jest tautologią.

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

0

214

Przykład 1. Sprawdzimy, czy formuła
((p → q) ∧ (q → r)) → (p → r)
jest tautologią.

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

1

0

215

Przykład 1. Sprawdzimy, czy formuła
((p → q) ∧ (q → r)) → (p → r)
jest tautologią.

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

1

0

0

216

Przykład 1. Sprawdzimy, czy formuła
((p → q) ∧ (q → r)) → (p → r)
jest tautologią.

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

1

1

0

0

217

Przykład 1. Sprawdzimy, czy formuła
((p → q) ∧ (q → r)) → (p → r)
jest tautologią.

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

1

1

1

0

0

218

Przykład 1. Sprawdzimy, czy formuła
((p → q) ∧ (q → r)) → (p → r)
jest tautologią.

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

1

1

1

0

1 0

219

Przykład 1. Sprawdzimy, czy formuła
((p → q) ∧ (q → r)) → (p → r)
jest tautologią.

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

1

1

1

0

1 0 0

220

Przykład 1. Sprawdzimy, czy formuła
((p → q) ∧ (q → r)) → (p → r)
jest tautologią.

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

1 1

1

1

0

1 0 0

221

Przykład 1. Sprawdzimy, czy formuła
((p → q) ∧ (q → r)) → (p → r)
jest tautologią.

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

1 1

1

1 0

0

1 0 0

222

Przykład 1. Sprawdzimy, czy formuła
((p → q) ∧ (q → r)) → (p → r)
jest tautologią.

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

1 1 1

1

1 0

0

1 0 0

223

Przykład 1. Sprawdzimy, czy formuła
((p → q) ∧ (q → r)) → (p → r)
jest tautologią.

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

1 1 1

1

1 1 0

0

1 0 0

224

Przykład 1. Sprawdzimy, czy formuła
((p → q) ∧ (q → r)) → (p → r)
jest tautologią.

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

1 1 1

1

1 1 0

0

1 0 0

Czy otrzymaliśmy sprzeczność?

225

Przykład 1. Sprawdzimy, czy formuła
((p → q) ∧ (q → r)) → (p → r)
jest tautologią.

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

1 1 1

1

1 1 0

0

1 0 0

Czy otrzymaliśmy sprzeczność?

TAK!

226

Przykład 1. Sprawdzimy, czy formuła
((p → q) ∧ (q → r)) → (p → r)
jest tautologią.

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

1 1 1

1

1 1 0

0

1 0 0

Czy otrzymaliśmy sprzeczność?

TAK!

Zatem nasze zdanie jest tautologią

227