Lý thuyết Logic Toán: Phần 2

Chia sẻ: Lê Na | Ngày: | Loại File: PDF | Số trang:74

Thêm vào BST

Báo xấu

75
lượt xem 13
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

Tài liệu Logic Toán có kết cầu gồm 3 chương. Phần 2 Tài liệu gồm nội dung chương 3 - hệ toán mệnh đề và vị từ. Cuối mỗi chương đều có phần bài tập ôn tập và củng cố kiến thức dành cho các bạn tự ôn tập. Mời bạn đọc tham khảo.

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Lý thuyết Logic Toán: Phần 2

CHƯƠNG Hỉ HỆ TOẮN MỆNH ĐỀ VÀ HỆ TOÁN VỊ TỪ Một trong những nguyên nhân quan trọng làm cho logic toán xuất hiện và phát triề n là sự lan truyề n rộng rãi phương pháp tiên ứồ trong việc xây đựng các lý thuyết toán học khác nhau, chẳng h ạ n : hỉnh học. SỐ học, lý thu vết nhóm, lý thuyết vành v.v... ' Đê xây dựng bằng tiên đề một lý thuyết toán học đàu tiên phải fchọn một hệ thống nào đó các khái niệm không ậuợc định nghĩa và các quan hộ giữa chúng* Những khái niệm và quan hệ này gọi,là cơ bản. Tiếp theo phải chọn một hệ thống nào đó các tính chát của các khái niệm và các quan hệ cơ bản mà khốn^ chứng minh làm tiên đề . Sau đó định nghĩa tất cả các khái niệm mặi của lý thuyết qua các khái niệm cơ bản và các khái niệm đã được định nghĩa trưặc chúng và suy ra « một cách logics tất cả các điề u khẳng định tử các tiên đề hoặc là từ các điề u khẳng định đã được chứng minh. Hệ thống các khái niệm cơ bản và các tiên đề có thề chọn tùy ý. Tuy nhiên lý thuyết chỉ được quan tâm vả là sinh động khi hệ thống các khải niệm cơ bản và các tiên dề của nỏ phân ánh những đối tượng nào đó và những liên hệ giữa chủng có thực ở trong thế giặi hiện thực. Một trong những yêu cầu cơ bản đặt ra cho một hệ thống tiên đề của một lý thuyết toán học là
[nh phi mâu thuần, tức là đòi hỏi rằng từ hệ thống le tiên đ ề đ ã chọn không thề suy ra « một cách logic » ai đ i ề u khẳng định trái ngược nhau. Một câu hỏi ược đặt r a : l ả m thể nào đề chứng minh tính phi mâu [mẫn cỉa một lý thuyết tiên (lê? Thoạt đáu người ỉa lường sử dụng p h ư ơ n g pháp mô hình (hay là s ự minh oa) cho mục đích này. Khi đỏ n g ư ờ i ta chọn làm các h á i niệm và các quan hệ cơ bản các phần tử cỉa một hợp cụ thề n à o dỏ và các quan hệ giữa chúng và ku đ ỏ nghiệm l ạ i vả xem các khái niệm và các quan 'ỳ đã chọn cố ìUiỏa m ã n qâc"fiêri đe cỉa lý thuyết ang xét hay không.. Nor một cách khác ta chọn một l ồ hình cụ the v á i các (Ịụan hệ "cơ bản làm kỹ số, trên ỊÔ h ì n h đó tất ca>e«v-* ti4n.đề cỉa lý thuyết đang XÓI it đ ú n g . Chẳng h?in ì i h i r l i i n l r học giải lích là một sự ^inh họa sỗ học, hay một mổ hình, cho hình học ơclil. lũng có t h ề xây ( l ự n o m ộ t m i n h họa sổ học cho h ì n h tộc LôKỈichet xki. Tuy nhiên cằn thận hơn trong khi nghiên cửu ván ịề này thì ta dễ dàng nhận t h á y rằng, bâng cách xây lựng mô hình ta không chứng minh được tính phi ụầu thuẫn cỉa lý thuyết mà chỉ đ ư a tính phỉ mâu t u ẫ n cỉa một lý thuyết này v$ tính phi mâu thuẫn lia một lý t h u y ế t khảo. Chẳng hạn như sự t ồ n t ạ i liệt minh họa số học cho hình học ơ c l i t có nghĩa là : lếu số học eác số thực là phi mâu thuẫn thì cả hình ọc ơ c l i t cũng phi mâu thuẫn. Đối v ớ i hỉnh học Lô íachetxki cũng có điều khẳng định t ư ơ n g t ự như vậy. Đa số các minh họa cho các lý thuyết toán học (và lặc biệt là số học) được xây dựng bằng cách dùng ^ thuyết tập hợp, vì thể tính phi mâu thuẫn cỉa toàn 4$ t o á n học thật ra là dựa vào tính phi mâu thuẫn l&a lý thuyết tập hợp. 15*
Cho đến cuối thế kỷ XỈX các nhà toán học đà xem lý thuyết tập hợp nhu là một cơ sở vững chắc của 1 toàn bộ các kiến thức- toán học. Tuy nhiên vào cuối the kỷ X I X trong chính lý thuyết l ậ p hợp cũng phát # hiện ra các mâu thuần, gọi là các nghịch lý ( ) của lý thuyết tập hợp. Trong các lặp luận dẫn t ớ i những mâu thuẫn này không hề có một sai râm logic nào. Diêu n à y làm lay động lòng tin cậy tuyệt đ ố i vào các chứng minh toán học. Đề làm thí dấ tia xét một nghịch lý dễ nhận thức nhát, (Tó là nghịch lý Ratxen. Ta phân tất cả các tập hợp r a - l à m hai l ớ p : lớp đâu gồm l ấ t cả các láp hcf\j coi nỏ là m ò i phần í ử, lớp sau gồm tất cả các tập hừ]) không coi n ó là mội phan t ư . \ - Ta xét tập hợp M mà các phân tử của nó là Lất cá các tập hợp thuộc lớp thứ hai. T h ử h ỏ i : tập hợp M thuộc vào? lớp nào trong hai l ớ p đã kê t r ê n ? Giả sử rằng nỏ thuộc vào lớp t h ứ nhất. K h i đ ỏ tập hợp M nhận nó là một phần tử. Nhưng các phần t ử của tập hop M là những phần t ử của lớp t h ứ hai. cỏ nghĩa là tập hợp M l ạ i thuộc "vào lớp thử hai. Ta đã úi t ớ i điêu mâu thuẫn. Bây giờ l ạ i giả sử rằng tập hợp M thuộc vào lớp t h ứ hai. Vì rằng tất cả các lặp hợp thuộc lớp thứ hai là những phần t ử của tập hợp M nên nó t ự coi nỏ là một phan t ử . Do đ ó n ỏ thuộc lớp t h ứ nhất, và ta cũng đi t ớ i m â u thuẫn. Như vậy tập hợp M không thuộc vào lớp thứ nhát m à cũng không thuộc vào lớp t h ứ hai, điều đỏ mâu thuẫn v ớ i điều là, tất cả các tập hợp đã được phân t h à n h hai lớp. (. ) Trong nguyên bản dùng thuật ngữ: aotinôm và paradôc trong tiêng Việt ch! có mô* thuật Jữệữ tiện ,) 154
Nghịch lý Rat xen vả các nghịch lý khác của l ý thuyết tập hợp dẫn t ớ i việc phải xem xét l ạ i những phương pháp suy luận dùng trong lý thu vết tập hợp. Trong cách lập luận dẫn t ớ i nghịch lý Hai xen có thiếu sốt gì ? Theo ý kiến của một số nhà t o á n học (Ratxen, Oait- hit), không được p h é p xác định một đ ố i tượng (tập hợp M) thông qua một sự tông hợp nào đó (tập hợp M được xác định thông quạ việc tông hợp tất cả các tập hợp và các tập hợp thuộc lớp t h ứ hai), và sau đó l ạ i tính cả đ ố i tượng đó vào tong hợp này (tập 'hợp M tính vảo lớp thứ nhất, và sau đó l ạ i tính vào lớp t h ú hai), vì rồng nhít' vậy thì hóa ra là, trong mót mức độ nhất định. nó tham gia vào định nghĩa riêng cho mình. Ratxen và Oaithit đã xây dựng cái gọi là lý thuyết các kiều đê l o ạ i t r ừ các t ậ p hợp dẫn t ớ i nghịch lý* Theo ly thuyết này thi tập hợp M (là xét trong nghịch lý Ratxe.11 1 càn phải xem như là một sự hình thành mới mà không được tính vào lợp t h ứ nhất cũng nhu* lớp t h ứ hai. Các tập hợp chỉ có thê hình t h à n h dựa trên một quá trinh chuẫn xác bồng cách chồng chất các l ớ p này lên các lớp khác theo một t r ạ i t ự nào đ ó (trật t ự các kiêu) T r ậ t t ự các kiêu do Ratxen và Oaithit xây dựng dẫn tới những hạn chế quá đáng, theo đỏ toán học trở thành rất phức tạp. T h ử nghiệm khác đê l o ạ i t r ừ các nghịch lý của lý thuyết tập hợp do Zermelo (1908) làm, ông đã xây dựng lý thuyết tập hợp theo kiêu một lý thuyết tiên đề. Những sự cải biên và h o à n chỉnh tiếp theo của lý thuyết này đã. sáng tạo ra được một lý thuyết có giá tri về tập hợp, 1Ỷ thuyết đ ỏ là cơ sở cho toán học hiệu 155
đ ạ i . Nhưng những p h ư ơ n g t i ệ n của lý thuyế t tiên đẽ không cho p h é p chứng minh t í n h phi mâu thuẫn cua lý thuy ế t tập hợp. Mội trong những khó khăn cơ bản, mà t h ế nào ta cũng g ặ p ' k h i giải quyế t vấn đ ề về t í n h phi mâu thuận của lý thuyế t, là ở chỗ, n h ư thường l ệ , một loại các p h ư ơ n g t i ệ n logic d ù n g đê xây đựng lý thuyết không được phác hửa một cách chặt chê (chính vì vậy m à khi định nghĩa tính phi mâu thuẫn của lý thuyế t ta viế t t ừ ((logic í) trong các dấu ngoặc kép). Ngay cả khi xuất phát t ử một hệ thống tiên đe đ ã cho, dù có thề* chứng minh được hai điều khắng định m â u thuẫn v ớ i nhau, cũng không thề tin ngay rằng lý thúy ốt của chúng ta có mâu thuẫn (lỡ ra nguyên nhân của m â u thuẫn là ử chỗ các phương pháp logic của chúng ta đe rút t ừ những diêu khẳng định này ra chạ đ i ề u khang định khác là kém hoàn hảo thì sao?) D. Hin be và trường phái của ông (1920 - 1930) dà phải t r i ể n những p h ư a n g ..pháp, m ớ i trong. lập. l u ậ n cùa toán hửc dựa vào việc xây dựng các lý thuyế t toán hục n h ư là những lý thuyế t cú pháp, trong đ ó tát ca các tiên đề được m ô tả bằng các công thức theo một bảng chữ cái n à o đ ó và các quy tắc suy luận tử các còng thức n à y đế n các công thức khác được chỉ ra một cách chính xác. N h ư v ậ y logic toán tham gia vào lý thuyết n h ư một bộ phận cấu t h à n h . Như vậy các phương p h á p dễ xây dựng các công thức và các suy luận từ một công thức n à y t ớ i một công thức khác phải là hữu hạn, h o à n toàn r õ rệt v à không có một sự bài bác t h ư ờ n g thấy. Vậy lý thuyế t toán hửc m à phải được chứng minh tính phi m â u thuẫn của n é đ ế n l ư ợ t minh.lại t r ỏ thành 15
l ố i tượng nghiên cứu của một lý thuyết toán*học khác được HÌỊibe gọi là mêta toán học hay là lý ỉhuyết chửnq mình. Mêta lý thuyết nghiên cứu lý thuyết cú pháp khi giải một loạt các bài toán quan trọng. Chẳng hạn như các vấn đẻ là, các hệ thống khác nhau của các còng thức dược l ẩ y làm tiên đề liên hệ v ớ i nhau như thế n à o ; các qui tắc suy luừn trong lý thuyết dó cỏ khả năng như the nào ; các qui tắc suy l u ừ n có thề dẫn t ớ i mâu thuẫn nay không (bài toán ve tính phi mâu thuẫn) và liên hệ v ớ i nhau n h ư thế n à o ; các tiên đề thừa nhừn và các qui tắc suy luừn có đủ đề nhừn được tất cả các định lý của lý thuyết đang xét hay không (bài toán về tính đ à y đ ủ ) ; v ớ i những bài toán n à o nay sinh ru trong lý thuyết cú pháp có thề x â y dựng được n h ư n g thuừt toán đê giải chúng (bài toán về tính giải dược). Vỉ rằng logic toán được trình bày n h ư là một lý thuyết cú p h á p nên đ ố i v ớ i nó ta cũng cần phải giải quyết cái* bài toán kề trên. Các câu trong m é t a lý thuyết mang đặc'tính n ộ i dung. Các định lý của nó là các câu về các đ ố i tượng cứa lý thuyết cú pháp. Các chứng minh của chúng được tiến hành thông qua các qui luừt của logic hình thức và cúc phương pháp được áp dụng trong toán học (phương pháp chứng minh phản chứng, p h ư ơ n g pháp qui nạp hoàn toàn v.v...) d ư ớ i dạng ngôn ngữ thông thường, Ỷ tưởng của Hinbe về chứng minh tính phi màu thuẫn của các lý thuyết liên đè, nói riêng là tính phi mâu thuẫn của sổ học hình thức, không thực hiện được bằng những phương pháp hữu hạn. Gơden (năm 19Ố1) đà chứng minh được một định lv R i a từ đó suy ra không the chứng minh được tính phi mâu
thuẫn tĩho Lát kỳ một iỷ thuyèt liên dẻ náo chứa sổ học bằng những phương pháp hữu hạn của Hinbe. Bằng phép qui nạp siêu hạn, phép qui nạp này không chấp nhận được với những phương pháp hữu hại), Ghenxen (nam 1936) đã chứng minh được tính phi mâu thuẫn của số hoc hình thức. l i ê u quan với lát cả những diêu dà ytióí Ư trêu, Hầy ra vẩn đề xây dựng lý thuyết cú pháp (tức là tiên đề hình thức của chính lôgic toán. Bằng cách chọn các hệ thống tiên đề khác nhau và các qui tộc suy luận khác nhau đi từ những công thức này đến những công thức khác, nói chung, ta sẽ được những lý thuyết lôgic cú pháp khác nhau. Mọi lý thuyết như thế thông thường gọi là hệ loàn loqic. Dưới đây ta sẽ trình bày vộn tột một trong những hệ toán lôgic đơn giản nhất, hệ toán lôgic này nằm trong nhiều hệ toán lôgic ịkhác như l ả một bộ pỉhận cấu thành — hệ toán dó gọi là hệ toán mệnh dê cồ điền, và ta cũng trình bày vộn tột một trong những hệ toán rộng rãi nhất và cũng thường dùng nhất trổng tòa li học ~~ đ ố l à hệ toán vị từ.. Đầu tiên ta chú ý một lần nữa là mọi lý thuyết cú pháp đặc trưng b ở i : 1) một bảng chữ cái, tức là một tập hợp các ký hiệu dùng đế xây dựng các công thức của lý thuyết, 2) một hệ thống tiên đè, tức là một tập hợp nào đó các công thức, được gọi là các tiên đè, ồ) những quy tộc suy luận cho phép từ những công t h ú c này nhặn được những công thức khác của ỈỶ • h u y ế t cú p h á p dang XỔI-
Si. NGÔN N*(r CỦA NỆ T O Á N MỆNH ĐẾ ( Á C TIÊN ĐÈ, CÁC QUI TẮC SUY LUẬN Trong m ỗ i lý thuyết iơáa học n g ư ờ i ta dùng những ký hiệu nào đó m à nói chung ta sẽ gọi là những chữ cái.'ĩ ừ những kí hiệu đã chọn trong lý thuyết đã cho ta lập nên các biền thức khác nhau và la gọi là các từ* Như vậy xuất hiện khái mộ IU ve ngôn ngừ của lý thuyết toán học đã cho n h ư một t r ư ờ n g hợp riêng cùa khái niệm tống quát vê ngôn ngũ' hình thức. 1.1° Ngôn ngữ hình thức: Dịu li nghĩa 1.1. Bảng chữ cái là một lập họ p hất ký các ký hiệu đôi một khác nhau a, 1), c, (Ì, chúng được gọi là các chữ cái của bảng chữ cái A : A = ị a, ì). €, cl, ... ị Chang hạn bảng chữ cái cua số học gom các ký híệti ( V I , '2,^3, 4, 5, 0, 7, 8, 9, = , Ị V —, X v : và- các (lẳu ngoặc * Định nghía 1.2. Từ trong bảng chừ cái À là một dâv hữu hạn tùy ý các chữ của bảng chữ cái D à y . Chẳng hạn abbac, đ b b a đ e líV nhưng l ừ trong bảng chữ cái À. : Ì 2 f 3 = ^ 7 , 0 X 2 = J2 là các l ừ trong bảng chữ cái của số học. Định nghía 1.3. Tập hợp SA tát cà các l ừ trong bàng chữ cải đã cho gọi là ngón ngừ hình thức xảv dựng írên bang chữ cái A. Khi xây dựng các lý Umyếl loàn họe HÚY hoạt;, khác, CÙUÍÍ v ớ i c á c k ý h i ệ u của mội bang c h ữ (.'ủi n à o d ó l a 159
cồn phải dùng l ớ i những ký hiệu dẻ biêu thị những sự hình t h à n h khác nhau Dầy sinh ra tử bảng chừ cái này. Các ký hiệu nhu- the gọi là mèta ki) hiệu, chúng tạo thành một tập hợp- gọi là lìứía bãỉUỊ chữ cái đ ố i v ớ i bảng chữ cái dang xét. Trong mê ta bảng chừ tái A VÃ) các ký h i ệ u A, , ị, ị đùng đề biêu thị bảng chừ cái này và ký h i ệ u SA biền thị tập hợp các tử trong bảng chữ cái A. Ta sẽ dùng các chữ cỏa bảng chữ oái Hy lạp (cổ thề d ù n g v ớ i các chi số) làm cảo méta ký hiệu biêu thị các t ừ trong, tập hợp SA : 0t » abbuc, p = dbbadc o o Thường là trong định nghĩa cỏa một k h á i n i ệ m nào đỏ ta thấy có sự tham gia cỏa các mê ta ký h i ệ u . Định nghía i.4. Bảng chừ cái A gọi là hảng chữ cái con cỏa bảng chữ cái B, và bảng chữ cái B là thác triền cỏa bảng chữ cái A, nếu láp hơp A chứa trong B : A c B. * Nếu bảng chữ cái tí là thác t r i ề n cỏa bảng chữ cái À thi ngôn ngữ Sfi gọi là thác triền cỏa ngôn ngữ S . A Định nghĩa 1.5. Độ (lài cỏa lù a là sỏ l à n các chù cái tham gia trong đó. Thí d ụ đ ộ dài cỏa l ử a 0 là 5, d ọ dài cỏa $ là 6. Q Định nghĩa 1.6. Hai từ a và p trong tập hợp SA gọi là bằng nhau « = p nêu nó có cùng mội đ ộ dài và ỏ n h ư n g vị trí giống nhau là các chữ cái giống nhau. Nếu la viết thêm vào phía phai một dầy chừ cái biêu thị từ ct 6 SA một d ã y chữ biêu Ihị l ử p £ S thỉ hỉnhA
líànii dược m ộ i t ử m ớ i , ký hiệu là a p và gọi là hụp •ủa các t ừ « và p. Chẳng hạn hợỊ) của các l ừ ot , p lả tử 0 0 á p = abỂacdbbadc 0 o Trong ngôn ngữ hình thức ta còn dưa vào từ irony, hiếu thị bỏng ký hiệu \, Ui định nghĩa đó là một. từ Mần theo đ i ề u k i ệ n Xa .== a À = Oi với bất kỳ ị ừ a nào và đ ộ d à i của n ỏ xem như bằng không. Định nghĩa 1.7; T ừ a J £ SA gọi là bộ phận hiì\ ỉu tử con của t ừ a £ SA (*I xuất hiện trong a) nếu cỏ.các từ ố €E SA v à T ệ SA (một trong chúng hay là-cả "hai"cỏ thê là trống) sao cho OI — Ạ Oil ĩ Chạng hạn n h ư l ừ a có một từ con lã «1 s á bi), T ừ 0 aỊ có the xuất h i ệ n trong từ a nhiều l ỏ n . Chẳng hạn tử b b xuất hiện trong từ a p hai l ầ n . ' . '0 o Theo t h ứ t ự kế t i ế p nhau (từ trái sang phải) la bải) lừ con oLi^xuất hiện lem thứ nhái, lần thử hai,..,, lần thử i trong *. 1-2°. Ngốn ngữ của hộ toán mệnh'đề. Ta láy tập hợp các ký hiệu sau đ â y làm bảng chữ cái của hệ toán mệnh đẽ (tên của các ký hiệu này hoàn loàn là ước l ệ và tạm t h ờ i chúng không chứa đựng một nội dung nào). 1. Một tập hợp đ ế m được các biến mệnh đệ, biêu Ihị bỏng những chữ la tinh. i n lo cùng với chỉ số hoặc không có chỉ số : À, li, c, . . . , Ả i , A2, ••• 0 2. Các ký hiệu của các phép toái) "ì. A> v< :>> tưưỉỉg ứng gụi lù phép phủ định, phép ìtội, phép tuyên, phép kẻo theo) Ì. - .,kf\I Ì-ỉ < ị 'VĩÌ 151
Ngoài các ký hiệu của bang chừ cái đã chọn, khi xây dựng hệ toán mệnh đề ta còn phải dùng đến các mêta ký hiệu. Chẳng hạn đó là các chữ Gôtic dùng đề ký hiệu các cồng thức của hệ toán mệnh đề, dấu SB dùng đề biêu diễn các công thức bằng'các mêta ký hiệu, v.v... Định nghĩa 1.8. Công thức của hệ toán mệnh đề là tất oả những từ, và chỉ những từ này, lụp thành từ các chữ cái của bảng chữ cái của hệ toán mệnh đề theo những qui tắc sau đây : 1. Mọi biến mệnh đề đều là cổng thức. 2. Nếu Gác từ A và B là các công thức thì cả các từ t ~) (À), (Á) V n (B)). (1.2) Mọi từ con của một công thức cũng là một công thức, được gọi là công thức con của công thức đã cho. Chẳng hạn các từ (1.1) là những công thức con của công thức (1.2). Hạng của một công thức cũng được định nghĩa giống như trong diêm 1.1.6. Việc sử dụng các dấu ngoặc đề ghi các công thức cho phép phân chia quá trình xây dựng công thức ra thành từng giai đoạn và trên mỗi giai đoạn có the nghiệm lại xem phần của từ nằm trong các dâu ngoặc cổ phải là một công thức hay không. Vì rằng số các 162
giai đ o ạ n n h ư thê là hữu hạn, nên vần đ ề tử dà cho cộ phải l à một công thức hay không là giải được. Khi viết các công thức n g ư ờ i ta cùng bỏ đi một số dấu ngoặc theo những qui ước tương ứng đã được "thừa nhận trong đ ạ i số mắnh đe (điềm 1.2.6°). Ngoài ra ta cũng ký hiắu từ ~Ị (A) bkĩìíẬ A và cùng * bỏ đi các dấu ngoáo, bào các hiến mắnh đè. hoặc các mêta ký hiắu biêu thị một cộng t h ứ c 1.3°. Các tiên đ ề của hệ toán mệnh dè. Ta lấy các công thức sau đ â y làm các tiên đề : a i . Ao (B } A ) ; * a 2. (A :> B) :> ((A ) (B > C)) D (Ả 'ẳ C) : * 3. A A B > A ; a ế. A A B > B ; a 5. ậ :> (B o AA B): a 6, A ) A Vfi; a 7. B ) A V B; * 8. (A :> C) ì ((B >e» :>jA V B ) C)) ; a 9. ( A o B) > ((A y B) :> A) ; a 10. x> A. 1.4. * Gác qui tác suy luận của hệ toán mệnh đe ; Trong hắ toán mắnh đ ề ta dùng hai qui tắc suv diễn. 1, Qui tác kẽl luận (modus ponens) Mp: từ các công thức A v à A > B suy ra được công thức B. Ta viết qui tắc đó một cách ngắn gọn n h ư sau: Mp(A, A } B) ^ B 2. Quì tắc thay thế s i từ công thức A la SUV ra dược b c ô n g thức B mà la nhận được tử A hằng cách thay thế" m
mối xuất hiện của các hiến mệnh dề Ải,..., À . íưưhí> k ứng bằng các công thức Bi,..., B : k ^ k (A ; Bi, ..., Bk) ~ B. Ợ dày các hiển mệnh đề A i , . . . , Ak vả các còng thức Bi, ... , B có thề chọn tùy ý. Đặc biệt nếu Ai, ... . A k k không xuãt hiện trong À, thì B -•_ A. 1.5°. Gác định lỹ của hệ toán mệnh dè. Khái niệm vè sự suy d i ê n . Đinh nghía 1.9. Công thức B gọi là chứng minh được (hay là là một định lý của hệ toán mệnh đề) nếu có một clăy hữu hạn các công thức* B i , . . . , Bị, (1.3) trong đó Bi• — B và mỗi một công thức Bi, í — 1,.,„ l hoặc là một tiên đè, hoặc là nhậu đước* từ những công thức nào ở phía trước của dãy (1.3) theo qui tắc suy luận. ì Như vậy, dãy công thức (1.3) gọi là phép chứng minh của công thức (hay là định lý) B, còn t gọi là độ dài của phép chứng minh. Tử định nghĩa này rõ ràng rằng mỗi một tiên đề của hệ toán mệnh đề là một định lý. Ngoài ra, nếu A và A > B là các định lý thỉ cả B cũng là một định lý, nếu A là một định lý và C i , . . . c là những k công thức bất kỳ thì S bA( A ; d , ..., c ) cũng là A k mót định lý. • • Ví T h i dụ : Dãy công thức Bi » (A ) B) ) ((A > ( B y Ó) > (A 3 C)), ft, » íA :> (B > À)) > ((A > Í(B > A) :> A)) :> . 2 (À 5 A))V 164
Ba (B :> A ) , B i == (A > ((B ;> A) :> A)) :> ( A D A ) , Bã - A :> ((B ;> A) :> A ) . Br, - A } A , B - A > A 7 là phép chứng minh công thức A ' O A trong đó A ìà một công thức bất kỳ. Thực vậy, Bi là tiến đề a,. B , nhận được từ B Ị theo qui tắc thay thế, cụ thê l à : B , == S ( B , ; B D A , A), B là tiên đề a i . B nhận b B C 3 4 được theo qui tắc kết luận từ.'các công thức B , BỊ, cụ 3 Iho l à : » T ư ơ n g í ự la có . B 5 = S b B B :> A) B(i = Mp ( B , 5 Bi), B 7 «S b A ( B - , A) 6 Như vậy, v ớ i bất kỳ công thức A , công thức A > A íả một định lý của hệ toán mệnh đe. Sau đây ta sẽ ký hiệu n ó là di. Việc giải quyết vấn đè mội công thức đã cho có phải là một định lý trong hệ toán mệnh đề hay không giúp cho ta đề ra khái niệm về sự suy diễn được của một công thức từ các tiện đề, 1 . 6 ° . K h á i n i ệ m về sự suy d i ễ n được c ủ a các c ô n g thức. Công thức B g i là suy diễn' được Đ ị n h n g h í a 1.10. l ử hệ thống công thức (liền đ ề ) . A|, ...» A
nếu có một dày hữu hạn công thức B Ị , ... , B t , trong đó B i B và m ồ i một công thức Bị (ì « Ì, ... I) hoặc là là một định lý, hoặc là là một tiền đề trong (1.4), hoặe là nhận được theo qui tắc Mp từ những công thức nào đó ở trước của (lầy (1.5). Như vậy chính d à y (1.5) gọi là phép suy điền của công thức B t ư hấ thống các tiết? đề (1.4), còn số í gọi là độ dài của p h é p suy d i ễ n này. Nếu công thức B suy diễn được từ các công thức (1.4) 1 thi ta v i ế t , * A i . ... , A s ị— B (j'.fi) Từ (lịnh nghĩa 1.10 ta thấy rồ rằng mỗi một tiên đề và m ỗ i một công thức trong (1.4) là suy diễn (lược từ hấ thống (1.4). Tập ỉiợp^tất cả các công thức suy diễn được từ hấ thống tieri ậề (1.4) được ky hiấu bằng 1 P ( A j , ... , A ) s l ĐỊNH LÝ 1.1. Công thức B là một định lý của hấ toán mấnh đề khi v à chỉ khi B là suy diễn được t ừ tập hợp trổng các tiền đ ề : Chứng minhiThụv vầy, nếu B là một định lý thì đ ố i với định lý n à y có thề xây dựng được một phép suy diễn có đ ộ dài là Ì từ một tập hợp trống các công thức. Phép suy diễn đó gồm duy nhất một công thức B . Ngược lại, nếu Bj,..., Bi là một phép suy d i ễ n của cổng thức B từ một tập hợp trống các t i ề n đề, thì bằng cách thay t h ế trong phép suy luận này m ỗ i một định lý bằng phép chứng minh
ỉa nó ta sỗ được phép chứng minh của cồng thức B. o đó B là một định lý. Tương ứng với ký hiệu (1.6), sau đây ta sẽ kỷ hiệu Ị - B (1.7) ê biêu thị B là một định lý. Chú ý rằng với phép suy diễn của một công thức, ta :hồng dùng được qui tắc thay thế. Tuy nhiên được phép lùng những định lý bựt kỳ. Vì rằng, khi áp dụng qui ắc thay thế cho một định lý, theo định nghĩa 1.9 ta lược một định lý, nên có thề nó i rằng, với phép suy l i ễ n ta chỉ được phép áp dụng qui tắc thay thế cho rác định lý. 1.7°. Các thí dụ của phép suy diễn và phép chứng minh. Ta sẽ đánh số các hệ thức suy diễn và các định lý đưa ra dưới đây của hệ toán mệnh đề theo thứ tự mả ta xét vẳ tương ứng ta sẽ kỷ hiệu bằng V k và đ k (trong đó k là số hiệu các hệ thức suy diễn hoặc là các đ ị n i t lý). Đê đơn giản cách viết với phép suy diễn hoặc phép chứng minh của công thức ta qui ước dùng các ký hiệu sau đây. Các công thức, tạo nên phép suy diễn hoặc lả phép chứng minh, sẽ viết thành cột và đánh số theo thứ tự mà ta xét tới chúng. Bên phải của một công thức ta viết trong dựu ngoặc gốc tích của n ó : éi ký hiệu giả thiết số i , «i ký hiệu tiên đề số i . Chẳng hạn cách viết (k, /, Mp) có nghĩa là công thức đã cho lập nên do việc áp ậụng qui tắc Mp.cho các công thức số k và /, cách viết S ^ (k, A) có nghĩa là cổng thức đã cho lập nên do b việc áp dụng qui tắc S cho công thức số k. b Ta xét các thí dụ về các hệ thức suy diễn. v i . A Ị— B } A, 167
P h é p suy d i ễ n (cồng thức B y A tử r ỗ n g thức A ) : 1. A (é,) 2. À > ( B :> A) ( A (1. 2. Mp) . V 2, A A B h ' A 1. A Ạ B (ôi) 2. ~A A B > A 3. A (12, Mo). T ư ơ n g l ự cỏ tho chứng tỏ rằng ta cỏ cáo hộ lỉiửe suy (liền sau đ â y : v3. A A B h~ fì : Vi. A K A V K: v5. B Ị - A V K: vft. I > A : v7. A y li I - H V A ; v8. A Ả B I - B Ạ A; v9. A, B I - A A Chẳng hạn ta chứng minh v9, tức là xây d ự n g phép suy d i ễ n cua công thirc A A R tử hệ thống- cong Ì lì ức A. B : ỉ. A (ói) 2. A > (B > A A B) 3. B > A A v> (h 2, Mp). L B (ố ), 2 3 M 5. A A H - 1.8°-. S(y đồ cụa các cong thức và 8©' đồ cua các liên đề. T ừ m ỗ i một công thức A, đ ù n g q u i tắc suy d i ễ n s b thụ* biện phép thay Ì trô Pốc biến mệnh đ ồ trong ràng,
thức này bằng những cống thức bất kỳ, ta cỏ thề nhận ặìĩạc một tập hợp v ổ hạn các cồng thức. Tập hợp công thức đ ỏ gọi là sơ đò'công tỉiức của A và biêu diễn bằng biêu thức nhận được bằng cách thay thế trong công thức À tất cẳ các biến mệnh đề A i , Ak tham gia trong đó bằng những mêta ký hiệu A i , Ak (hoặc là các chữ in đậm khác). Chẳng hạn tử công thức A ) B V c ta lập được sơ đồ công thức A ) B V c. (1.8) Đê nhận được tất cẳ các công thức thuộc váp sơ đồ công thức đã cho ta phẳi thay^hế các mêta ký hiệu tham gia trong sơ đò cồng thức ấy bằng những công thức bất ký của hệ toán mệnh đề. Chẳng hận sơ đồ cống ttựre (Ì.8) chứa cổng thức A V B ) ( B )-C)VD. Nếu trong một sơ đ ồ cồng thức ta thay thế tát cẳ hay chỉ một số trong những inêta ký hiệu bằng các sơ đồ công thức thì ta tạo ra được một sơ đồ công thức mới, trong đó những công thức thuộc vào sơ đồ này cũng thuộc vào sơ đồ công thức lúc đâu. Chẳng hạn khi thay t h ế trong sơ đồ cồng thức (1.8) mêta ký hiệu B bằng sơ đồ công thứe A ) B ta được sơ đồ còng thửe c \ y(A } B) V r 1.0) Công thức A V B } (A V B M A > B)) V (B ) A A 0 ) ; nhận được t ừ sơ đồ (Í.9) bằng phép thay thế A « A V B , B * A >B, c ~ B > A A n . •169
là thuộc vào sơ đ ồ công thức này. N h ư n g công thức đ ổ cũng cỏ thề nhận được t ừ sơ đồ (1.8) bằng phép thay the A « A V B, B r - . A V B ) ( A ) B ) , c ~ B ) A A D, Như vậy, rút cục phép thay thế các mêta ký hiệu trong một sơ đồ công thức bằng những sơ đ ồ công thức khác làm nay sinh ra những sơ đồ công thức m ớ i , làm tách ra những tập hựp con n à o đ ó các công thức t ừ tập hợp cồng thức thuộc vào sơ đ ồ lúc đầu. V ớ i các công thức là các tiên dề và các dinh lý, sơ đồ công thức lập n ê n t ừ đ ổ tương ứng gọi là sơ đò tiên đầ và sơ đò định lý. Các sơ đ ồ tiên đề l à : . 1- a i . A D (Đ } À); a2. (A D B) :> ((A D (B } C)) :> (A :> C); Ct3. À / \ B } A ; «4. A A B; «5. A ) (Bs Ả A B) ; aè. Ả ) A V B : *7, B > . A V B ; «8. (A :> C) 5 P ) C ) ) ( A V B ) C)); 0t9. (A ) B ) ) ((A :> B) :> A ) : »10. X :> A. Đắnh lý di là sơ đò A :> A. Sau n à y (đễ cho gọn), thay cho « s ơ đ ồ công thức >x, « s o đồ định lý)), ((Sơ đồ tiên đề)) ta sẽ nói là ((Còng thức)), ((đắnh lý)), ((tiên đề)). 1.9°. Những qui tắc suy diên phụ. Khái n i ệ m suy diễn được cỏ một loạt các tính chất, cho phép từ những í 70
hệ thức suy diễn n à y nhận được các hệ thức suy diễn khác mà không càn m ỗ i l ầ n đều phải v i ệ n tới phép suy diễn của những hệ thức trước. Ta ke ra đây những lính chất cơ bản n h ư thế. L Qui ỉ ác lập nần đầ: T , A h- A. 2. Qui tắc nhập tiên đế. Nếu T h A thỉ T, B ị- A. 3. Qui tắc tách Hên đề: nếu T, A h B và T h~ A thì T Ị - B. Đặc biện n ế u T, Ả ỉ - B và A là một đ ị n h lý Ihi T j ~ B . Như- vậy các định lý có the tách ra khỏi các tiền đề của một hệ thức suy diễn bất kỊ. • • mi - ị. Qui tắc tam đoạn luận: n ế u T ị— Ai, T Ị— A và Ai, A ị— B, thì T I— B. k K Đặc biệt nêu ị— Ai, Ằ và Ai, Ak ị— B, thì I — B k là một c ô n g t h ứ c suy d i ễ n đ ư ợ c từ các định l ý cũng là ỉ một định lý. ỉ, * " • '5. Quỉ lác > —nhập: nếu T; A |— B thì T Ị - A :> B. í, 6. Qui tắc > — tách: nêu T I - A :> B thì T. A I - B. 7. Qui tắc A -nhập: T, A, B ị - AẠB. 8. Qui tắc / \ — í ách: T, A / \ B I — A và T, A Ạ B I — B. 9. Qui tắc y~nhập: T, A Ị - A V B, T, B i - A y B , 171