14026 Scan0019

2.5 Zadania 27

• reguła dowodzenia MP (modus ponens):

A, A=> B B ‘

W systemie Hilberta mamy tylko dwa funktory: implikację i negację. Ponieważ tworzą one zbiór funkcjonalnie pełny, stąd za ich pomocą można zdefiniować wszystkie pozostałe funktory.

Przykład 2.7 Dowieść w systemie hilbertowskim, ze A => A.

1.	A => ((A =>■ A) => A)	Ai : B/ (A => A)
2.	[a => ((A =$> A) => A)^	A2:B/(A=>A), C/A
	((A => (A => Tl)) =>• (A => A))
3.	(a => (A => A)^j => (A => A)	MP : dla formuł 1 i 2
4.	A (A Tl)	Ai : B/A
5.	A=> A	MP : dla formuł 3 i 4

Widać, że metoda aksjomatyczna prowadzi do trudniejszych rachunków niż metoda zero-jedynkowa. Wymyślenie dowodu nie jest proste i wymaga pomysłowości, a niekiedy też zależy od szczęścia.

2.5 Zadania

1. Sprawdzić, czy formuła (p V q) => (~ p => q) jest tautologią.

Rozwiązanie:

(a) metoda zero-jedynkowa

V	Q	pV q			(pV?)^(~p^g)
0	0	0	1	0	1
0	1	1	1	1	1
1	0	1	0	1	1
1	1	1	0	1	1