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

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

Thêm vào BST

Báo xấu

114
lượt xem 25
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 1 Tài liệu gồm nội dung chương 1 - Đại số mệnh đề và chương 2 - Đại số 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 các bạn cùng tham khảo nội dung chi tiết Tài liệu này.

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 1

MỞ DẦU T o á n học là m ộ t khoa học trong đ ó m ọ i c h â n Jý đ ê u được c h ử n g m i n h b ằ n g suy l u ậ n . Vì the đ ố i v ớ i toán học, các ty t h u y ế t v ề ỉogic — p h ư ơ n g t i ệ n đề xây d ự n g các k i ế n thức t o á n học — c ó giá t r ị l ở n . T r o n g các lý thuyết logic n g ư ờ i ta m ô tả các q u á trình suy l u ậ n v à các q u i luật của sự suy nghĩ c h ơ p h é p t ụ t i n h c h â n t h ự c của m ộ t p h á n đ o á n n à y đ ư a ra nhụm> k ế t l u â n v ề tính đ ú n g đ ắ n h o á c sai lam của c á c phán đ o á n k h á c m à chỉ d ự a t r ê n d ạ n g của các p h á n íÌGán n à y c h ứ k h ô n g l ệ thuộc vào nội dung cụ the cửa các p h ú n đoản đ ó . Chang h ạ n n h ư qui l u ậ t tam đ o ạ n luận, mà c h ú n g la rát hay dụpg k h ẳ n g đ ị n h r ằ n g : « T ụ tính c h â n ỉliựe của các phái? đ o á n « À là c )) v à «'B là c)) suy r a í inh đù nơ đắn í-ủa pỉián đ o á n « A ỉà c » m à khôn?;' phụ thuộc v à o các c h ữ A , B v à c b i ê u ti)ị các đ ố i t ư ợ n g n à o ) ) . Do mức đ ộ t r ụ u t ư ợ n g x á c đ ị n h của m ì n h , m ỗ i lý thuyết khoa học cần p h ả i sản sinh ra m ộ t h ệ thống ký h i ệ u r i ê n g đ ẽ biêu thị các k h á i n i ệ m và ghi nhận các k ế t - l u ậ n l ô n g q u á i của n ó . T r o n g logic c ư n g c â n c ó m ộ i hệ thống ký h i ệ u nhu vậy. Việc á p d ụ n g trong logic n h ữ n g k ý h i ệ u riêng (hi cho p h é p h ì n h thức hóa cá í/ qui luật c ù a n ó d ư ớ i dạng chung n h á t v à đ ã sản sinh ra n h ữ n g tiền đề đê ứng dụng trong logic nhữỉi£> p h ư ơ n g p h á p toàn học, V ;e đ ó
đ ã d ẫ n t ớ i m ộ t sự đ i ề u c h ỉ n h c ă n b á n t r o n g c á c l ý t h u y ế t logic v à l à m nay sinh r a m ộ t l ĩ n h v ự c m ớ i của toán. hoe, đ ó là m ồ n ( d o m e t o á n ) ) . " i N g ư ờ i đ a u liên t r o n g lịch sử b ầ y tò Ý (lịnh x ả y d ự n g logic d ự a t r ê n CƯ sở của t o á n học l à G.v. L e p n i t ở c u ố i the kỷ 'thạ X V I I . Ô n g đ a đ ặ t c ơ sở cho v i ệ c đ ạ i số h ó a logic và v i ệ c x â y d ự n g c á c bệ l o à n logic. ( ( C h ú n g ta sử d ụ n g c á c ký h i ệ u k h ô n g p h a i chỉ là đ ễ d i ễ n đ ạ t sạ suy nghĩ của ta cho n g ư ờ i k h á c m à cả là đ ề đ ơ n g i ả n h ó a c h í n h q u á ( r ì n h suy n g h ĩ của c h ú n g ta )) ( L e p n i l ) . N h ữ n g t h à n h q u ả t i ế p theo t r o n g sự p h á t t r i ề n của logic t o á n gắn l i ề n v ớ i t ê n t u ổ i của Đ ơ m o o c g a n (1806— '1871), Bùn (1815 - Í864), Freghe (1841 - 1902), P o r e x k i (4846 - 19Q7), Preg (1848 - 1925), P i ê e s ơ (1839 - 1914), P ê a n o ( 1 8 5 $ - 1932). L â n đ ầ u tiên logic'(.oán đ ư ơ c g i ớ i t h i ệ u n h ư l à m ộ t l ĩ n h v ự c m ớ i của t o á n học ơ t r o n g c ô n g t r ì n h cơ sở của Oaithit v à R a i x e n xi N g u y ê n l ý t o á n học )). V i ệ c ạ n g dụng, l o à n học v à o logic đ à cho la n h ữ n g p h ư ơ n g t i ệ n b ô t r ợ r ấ t t h u ậ n l ợ i (lề t r ì n h b à y các lý t h u y ế t logic v à c ũ n g cho la m ộ t c ồ n g cụ t í n h t o á n đ ẽ ' g i ả i c á c b à i - t o á n q u á k h ó . N g ư ờ i la đ ã x á c đ ị n h đ ư ợ c T n h ữ n g n g u y ê n l ý x â y d ự n g c á c l ý l h u j ế t logic cho p h é p phát. h i ệ n r a n h ữ n g v ấ n đ ề logic m ớ i v à q u a n t r ò n g , v à n g ư ờ i la c ũ n g đ à m ở r ộ n g l ì n h vực n g h i ê n c ạ u v ẽ logic. Sự p h á t t r i ể n của logic t o á n đ ư ợ c đ ặ t ra d ó c h í n h y ê u c â u của sự p h á t I r i ễ n của t o á n học. T r ê n cơ sở của logic t o á n , sự p h á t t r i ề n của các l ý t h u y ế t t o á n họe c ó t h ề x e m n h ư l à lý t h u y ế t của sự ; suy d i ễ n . tạc l à x e m n h ư c á c l ý Ì h u y ế t l i ê n đ ề c ù n g v ớ i A a
những p h ư ơ n g tiện logic đã được xác định một cách nghiêm ngặt. Nhờ logic toán n g u ô i ta đà giải quyết được nhiều vấn đẽ vè lính chất lỗng quái của các JỶ thuyết toán học (thí d ụ các vấn đề v ề tính phi mâu thuẫn,, tỉnh đay đủ, tính íịiki được v.v...). Trong việc x â y dạng logic toán n h ư là một khoa học càn thiết cho sạ phát t r i ề n của toán học, các công trình của Hinbe, G ơ đ e n , Pôxt, Chơơc, Genxen, C ô n m ô g ô r ô p , Nôvicôp, Maccốp v.v... đã có nhiều đóng góp l ớ n . T r ê n ranh giới giữa đ ạ i số và logic toán đ ã nay sinh ra một lý thuyết t o á n học m ớ i — đ ó là lý thuyết m ô hình mả sạ phát t r i ề n của n ó gắn l i ề n v ớ i tên tuổi của Tarxkĩ, Manxep, R o b i n s ơ n . Trong lý thuyết m ô b ì n h , các v á n đ ề quan trọng liên quan đ ế n các hệ thống đ ạ i số tát nhiên sẽ đ ư ợ c p h á t biêu hếpq n g ô n n g ừ của logic toán v à Cling đ ư ợ c giải q u y ế t Dằng n h ữ n g p h ư ơ n g ' t i ệ n của ÌOỊịic t o á n . Nhiều định lý được chứng minh trong các lĩnh vạc khác nhau của đ ạ i số tỏ ra là những t r ư ờ n g hợp riêng của những định lý tông quát h ơ n trong lý thuyết mô hình hoặc là được suy ra t ừ chúng. Giải thích toán học, hình h ọ c tỏpô học trở t h à n h lĩnh vạc ứng dụng của các p h ư ơ n g p h á p của lý thuyết mô h ì n h . Đừng v ề tính bồ ích, về hiệu lạc và tẳn) quan trọng của các phát minh, về giá trị đ ố i v ớ i m ọ i ngành toán học, logic toán đã chiếm một trong những vị trí quan trọng' trong khoa học toán học hiện đ ạ i . Logic toán hiện đ ạ i (.'ó ứng dụng rộng rãi vào nhiều lĩnh vạc khác nhau của các nghiên cửu khoa học, diêu » • 7 Ó • mà logic hình thức cổ t r u y ề n c h ư a hề biết đ ế n . Logic toán và lý thuyết thuật toán đ ạ t được nhiều o %/ mỉ • • • hànỉi tạu to l ớ n trong l ý thuyết c á c so đ ồ . công tắc r>
rớle và trong lý thuyết tự dộng hóa. trong ngón ngừ học, trong các nghiên cứu thuộc lĩnh vực kinh tế, trong sinh lý học sọ não và tâm lý học. Logic toán rát quan trọng đ ố i v ớ i các thày giáo dạy toán. Nó tạo cho n g ư ờ i thày khả năng đi sâu vào bản chất của khái niệm về sự chứng minh, giải thích rồ ý nghĩa của khái niệm về phép kéo theo logic, thiết lập nên những tương quan giữa các đụnh lý thuộc các loại khác nhau (đảo nhau và phản nhau). H ệ thống ký hiệu của logic toán cho phép thực hiện việc ghi chép ngắn gọn và chính xác các đụnh nghĩa của các khái niệm toán học, ghi chép các đụnh lý v à các chứng minh của chúng. Nó tạo cho n g ư ờ i thày nhưng phương tiện mới đê rèn luyện cho học sinh thói quen suy nghĩ chính xác. Về phương diện lụch sử, lógic toán hình thành n h ư là một lý thuyết đ ạ i số, trong đó mối quan hệ giữa các khái lụệm logic khác nhau được biêu diễn bằng các phép toán! Việc xây dựng logic toán như thể về sau này gọi là đ ạ i số mệnh đề và đ ạ i số vụ''từ, trong đó đ ạ i số mệnh đề xem như một phần trong đ ạ i số vụ từ. Nó còn gọi là sự xây dựng thuộc về nội dung (ngữ nghĩa) của ỉogic toán và đôi khi n g ư ờ i ta kết thú c ở đây việc trình bầy về logic toán, đểu đó cũng đã cỏ thê lập và giải những bài toán rất quan trọng. Bên cạnh việc xây dựng theo nội dung của logic toán ta thấy cần xây dựng logic toán như là một lý thuyết tiên đề hình thức (thuộc về cú pháp), v ớ i lý thuyết này đ ạ i số vụ từ là một trong những minh họa có thề có được. Trên cơ sử những điều đã chỉ dẫn, ta thấy rồ v i sao trong giáo trình này bắt đầu bằng việc trình bày đ ạ i số ựiệnh đề (chương ì), xem n h ư phần chuần bụ đề trình bày vồ đại sổ vụ từ (chương l i ) và cả hai phàn ỈV
đ ó Jà liền đề cho hệ (oán mệnh đề và hệ toán vị l ừ (chương HI). Trong mọi mục còn chia ra các diêm. Các định nghĩa, các định lý, các hệ thức và các công thức được đánh số liên tiếp trong từng mục một. Việc đánh sỗ thề hiện bằng một cặp số, số đầu chỉ số mục, còn số thứ bai chỉ sổ t h ứ l ự . Khi phải dổn ra trong một chương khác ta thêm vào ử bên trái mỗi cặp số tương ứng một chữ số nữa đề chỉ sổ chương. Chẳng hạn cách ghi « định nghĩa 2.3.1 * có nghĩa là dổn ra định nghĩa thứ nhất trong §3 thuộc chương l i . Tác giả thấy càn phải tổ lòng biết ơn đối với ông M.M. Ghekhôp, biên tập viên; đa dành nhiều công đễ ohuần bị bản thảo cho việc xuất bản, và cũng xin gửi lời cảm ơn trước đối với các độc giả cho biết những ĩìhận xét của mình về nội dung cuốn sách. TẢO GIẢ 7
CHƯƠNG ì ĐẠI S Ổ M Ệ N H ĐỀ §1. KHÁI NIỆM VỀ M Ệ N H ĐỀ V À V Ị TÙ* •» 1.1°. Trong đ ạ i số mệnh đề n g ư ờ i ta nghiên cứu các mệnh đè và các phép toán trên chúng, ở đây ta hiếu mệnh đề là mọi điều khẳng định mà ta có the nối rồ được một cách xác định và khách quan là nó đúng hay sai. 4 •' ' , Chẳng hạn ta xét các mệnh đề sau đ â y : 1) Hình binh hành cớ bốn đ ĩ n h ; '2) 25 chia hết cho 5; 3) Ngà y mùa đông ngắn hơn ngày mùa hạ ; 4) Số 2 lán han số 5; 5) Đường chéo của một hình vuông thông ước v ớ i cạnh của nớ. Các mệnh đề Ì, 2, 3 là đúng, còn 4 và 5 là sai. Trong dại số mệnh đề n g ư ờ i ta không chú V l ớ i n ộ i dung cụ the của mệnh đề mà chỉ quan tâm tới vấn đ ề : ; mệnh đề đó là đúng hay sai. Khi nói đến một trong những khả năng đúng hay sai của một mệnh đề n g ư ờ i ta nói đến giá trị chân lý của mệnh đề đã cho: «Giá trị chân lý của mệnh đè A là đúng » hoặc là « giá trị chân lý của mệnh đề A là S M » . ị
Như vậy, thực chát là ta có một ánh xạ tư tập hợp tất ca các mệnh đề lên tập Hợp B gồm hai phan lử,- một trong chúng mang tên là đúng, còn phần tử kia mang tên là sai. Nếu từ đúng biêu thị bằng số một và từ sai biêu thị bằng số không thì ta có thê nó** rằng giá trị chân lý của mệnh đề A bằng một hoặc bằng không.- 1 Trong đại số, các ghổ có the biêu thị hoặc là một sỗ xác định nào đó hoặc là một số bất kỳ trong một tập hợp số nạo đổ. Trong đại số mệnh đề cũng cầỊì phải dùng các chổ đê biêu thị một mệnh đề xác định cũng như biêu thị một mệnh đề bất kỳ. Trong trường hạp đầu ta dùng các chừ hoa đầu trong bảng chổ cái la tinh A, B, c, ... (có thề dùng với các chỉ số), trong trường hợp sau ta dùng các chổ hoa cuối của bảng chổ cái la tinh X, Y, z, ... (có thê dùng với các chỉ số). Mỗi chổ" dùng đề biêu thị một mệnh đề bất kỳ (biến đôi) sẽ gọi là một «biến mệnh đ ề » . Chú ý rằng biến mệnh đề không pjiai là mọt mệnh đề, vá nếu nối rằng giá trị của một biển mệnh đề X bằng một hoặc bằpg không (X lấỳ giá trị đúng hoặc sai) thì là nói về một mệnh đố cụ thề A nào đó thế vào X. ị.2°. Trong mồi mệnh đê có chả ngữ và vị nqữ (hoặc chả từ và vị từ). ĐỆ hiểu được cách ghi chép bằng kỷ hiệu các mệnh đề bằng cách tách chủ ngổ và vị ngổ của chúng ra, ta hãy định nghĩa khái niệm vị từ. Ta hãy xét các thí dự. 1. Giả sử N = Ị Ì, 2, 3, ...ị là tập họp các số tự nhiên và chổ p biên thị tính chất một số tự nhiên là số nguyên số. Khi đó mệnh đề (í số tự nhiên a là một số nguyên lổ)) có thề viểl dưới dạng P(a), và trong cách ghi chép* này ký hiệu a biêu thị chủ từ còn ký hiệu p biêu thị vị lừ, mà ta gọi là vị từ của số nguyên tố. Mệnh đè này l à đúng hay sai (tức là lấy giá trị một hoặc không) tùy 9
t h e o a. Chẳng hạn P(2).= P(3) = 1; P(l) = P(4) = ọ. Thực chất vị t ừ p là một ánh xạ t ừ tập hợp N vào tập hợp gồm hai phần t ử B = ịo, l ị . 2. Giả sử z = ịo, ± Ì, ± 2, ...Ị là tập họp các sộ ' nguyên và c là tính chất cặp sỏ nguyên a, b đồng dấu. * K h i đó mệnh đề « c á c sỏ nguyên a v à b có cùng dấu » ^được viết d ư ớ i dạng C(a, b) v à n ó sẽ là đúng hoác sai tùy theo a và b c (o, a) v à c (a, theo qui ước cỏ thề xem là bằng một v ớ i bất kỳ a). Vị t ừ c là vị từ t r ê n tập hợp z. N ổ kjiông còn phụ thuộc v à o một sỏ n h ư trong thí dụ Ì m à phụ thuộc vào một cặp sỏ. Vị t ừ G là m ộ t á n h xạ của tập hợp tất cả các cặp sỏ nguyên vảo tập hợp gồm hai phần tủ*B = (0, l ị . Bây giờ ta chuyên sang định nghĩa tong quát khái 3D lỏm vị t ừ . Định nghĩa 1.1. Tập hợp các hệ thỏng sắp t h ứ t ự (a x> &2, — a )r có thề có được của các phần t ử của một tập n hợp M gọi là lập hợp Đêcac bậc n của M và ký hiệu n M = ị(a lf a, 2 a ) r ai 6 M, i = ì, n 2 , n Ị . . ĐịnẾÍ nghía 1.2. Giả sử l i là m ộ t sỏ t ự nhiên bất kỳ. 3Chi đ ó ta gọi vị từ n—nguyên (hoặc ri —ngôi) xác định trên tập hợp M là một á n h xạ đ ơ n trị p của tập hợp Đêcac bậc n của M v à o tập hợp gồm hai giả trị B = = |0, l ị . Nói một cách v ắ n t ắ t : n p :M B. N h ư vậy vị t ừ n—nguyên p trêu lặp họp M là một l i à m n ngồi xác định t r ê n M và l ấ y các giá trị trong tập hớp B == ị ó , l ị . Vì thế, cũng tihu v ớ i h à m so, ta d ù n g :'fcỷ h i ệ u P(Xj, Xỉ, # n ) » Q ( ^ 1 » 3*2» '^n) V . V . . to
đễ chỉ vị từ li—nguyên. Trọng trường hợp muốn nhấn n mạnh rang vị từ p là n—nguyên thì ta viểt p( ) thay cho p. Nếu qua ảnh xạ p, ảnh của hệ thống (aj, a2, ...» a ) là n một thì ta viết \ P(ai, a , 2 a) = 1 n và nó i rĐng giá trị của vị từ p ứng với hệ thống (ai, aj, a ) là đúng. Còn nếu ảnh của hệ thống (ai, a , n 2 a ) qua ánh xạ p là không thì ta viết n m: P(a!, a 2 a) = 0 n và nối rĐng giá trị của vị từ P ứng với hệ thống (aj, 3-2» •••» 3-n) là. Sãi. Vị từ n—nguyên v ớ i n = Ì gọi là đơn nguyên, với n = 2 gọi là nhỉ nguyên và với n = 3 gọi là tam nguyên. Đễ cho tống quát ta còn đưa ra khái niệm YỈ từ 0—nguyên. Cụ thề là, vị từ 0 —nguyên là một mệnh đề đúng hoặc sai bất kỳ. Các thỉ d ụ : Giả sử N là tập hợp các số tự nhiên 1. Vị từ đồng nhát E : N B: 2 E(a a ) = Ì khi và chỉ khi ai = a . lf t 8 2 2. Vị từ thứ tự Q : N - > B : Q(ai, a ) = Ì khi và chỉ khi ai =s a . 2 2 a 3. Vị từ chia hét D : N B: D(ai, a ) = Ì khi và chỉ khi a Ị chia hết cho a 8 2 4. Vị từ lấy tông s : N B: 3 S(ai, a , a ) = Ì khi và chỉ khi' ai - f a = a . 2 5 3 3 3 5. Vị từ lẫy.tích P : N - > B : P(ai, a , ag) = Ì khi và chỉ khi ai a = a . s f a lí
Định nghía 1.3. Mỗi lập con A của tập hợp M° gọi là một quan hệ li —nguyên xác định trên tập hơp M Vội n — Ì, 2, 3, quan hệ n—nguyên gọi là đơn nguyên, nhị nguyên, tam nguyên. Nếu (ai, a ) £5 A thì ta noi rằng các phần tử ai,. n ạ, 2 a của lập hợp M có quan hệ A. n Đối chiểu các định nghĩa 1.2 và 1.3 la dễ dàng phát hiện rà mối quan hệ giữa các khái niệm Vị từ li—nguyên* và khại niệm quan hệ n—nguyên xác định trên cùng một tập hợp M. . Quạ vậy, giạ sử A £ M . Nếu v ớ i mỗi hệ thống (ai, n n a, 2 a ) £ M ta đặt P(£i, a , n a )•= Ì khi và ch! 2 n khi (ai, a ) £ A thì ta được một vị từ li—nguyên n trên tập hợp M. Ngược l ạ i nếu p là một vị từ n—nguyên trên M thì bằng cách đặt (ai, a ) £ Ả khi và chỉ khi' n n P(ai, a ) = Ì ta được một tập hợp con Ạ trong M . n Như vậy mỗi vị từ li—nguyên p trên tập hợp M xác định duy nhất một quan Kệ n-^nguyên trên tập hợp M và ngược l ạ i mỗi quan hệ n—nguyên A trên tập hợp M xác định duy nhất một vị l ừ lì—nguyên p trên tập hợp M. Các thi d ụ : Các vị từ đã xét trong các thí dụ ở trên xác định: trên tập hợp các số tự n h i ê n : 1. Vị từ E xác định quan hệ bằng nhau A i : (ai, a ) £ A j klii và chỉ khi E (ai, a ) = 1. 2 2 2. Vị từ Q xác định quan hệ thứ tự A : 2 (ai, a ) ^ A khi và chỉ khi Q (ai, a ) = 1. 2 2 s 3. Vị từ D xác định quan hệ chia hết A : 3 à ( i> a ) € A khi và. chỉ khi D (ai, a ) = 1. 2 3 2 ị. Vị t ừ s xác định quan hệ A : 4 (ai, a , a ) ^ A khi và chỉ khi s (ai, a , a ) — 1 . 9 3 4 2 3 12
5. Vị lừ p xác định quan hệ A : 5 (ai, a , a ) £ A khi và chỉ. khi P (ai, a . a ) = 2 3 5 2 3 1. Định nghía 1.4. Phép toán lĩ—nguyên xác định trên tập bợp M là một ánh xạ đơn trị a từ tập hợp Đêcac bậc n của tập hợp M v à o lập hợp M : n a : M -> M. Với n — Ì, 2, 3 phép toán n —nguyên gọi là đơn nguyên, nhị nauụên và lam nguyên, T ừ định nghĩa 1.4 ta thấy rõ rằng nếu a là một phép toán n—nguyên trên tập hợp M thì với mỗi một hệ n thống c ó thứ 'tự (ai, a ) M c ó m ộ i phắn tử duy n nhất I) €z M sao cho: ==: ót ( B Ị , 8. ) n b. Có the lẫy các thí dụ quen biết về phép toán nhị n g u y ê n trên tập hợp eác sỗ nguyên z là cắc phép tính cộng, tính trừ và tính nhân. P h é p toán đơn nguyên a trên tập có thề lấy ỉa ÍC phép toán l á y số đối)): a :a —a. Với mỗi phép toán li nguyên a trên tập hợp M c ỏ thề xác định một vị tử n-h Ì—nguyên P bằng cách đặt a P (ai, tt a , a +i) == Ì khi và chỉ khi a ( a i , a „ ) = a +if n n n Viết một cách vắn tắt: P (aj, B a , a i ) =: Ì n n + a(ai, a ) — a n n + í . Chú ý rằng t ư ơ n g ứng vừa chỉ ra giữa các phép toán , và vị íừ là không một—một. Cụ thê là không phải mỗi vị từ li-f Ì— nguyên p có thề cho ứng với một phép toán n—nguyên oe sao chơ p = p . Việc đ ó c ó thê và chỉ c ổ o J - ót • thề làm đirợc trong trường hợp khi vị từ p có tính chất sau đ â y : với mỗi phắn tử (a ... a ) trong M có duy Jr f n nhất một phán íử b £E Xỉ sao cho: 1 3
Nếu Xu 'Xu là các b i ế n m à m i ề n giá trị của c h ú n g là tập hợp M, còn p là một vị t ừ n—nguyên xác định t r ê n tập hợp M thì. đê biêu thị vị t ừ n à y ta dùng b i ế u thức P(Xu Xn), biêu thức n à y chỉ trở t h à n h một mệnh đề,khi-tất cả các b i ế n Xu x trong đó đã được thay n thế bằng các phần t ử của tập hợp M. Do đ ó P(x u r > n gọi là dạng mệnh đầ. Bằng cách thay trong dạng mệnh đề P(Xị, .... x ) một n vài biến bằng nhạng phần t ử bất kỳ n à o đ ó của tập h ọ p M ta sẽ được nhạng vị t ừ mới và nhạng dạng mệnh đ ệ m ớ i . Đôi k h i một dạng mệnh đề có thê suy biên t h à n h một mệnh đề h o à n t o à n xác định. Chẳng hạn, D(a?i, Xi) là một dạng, mệnh đ ề , n h ư n g D(6, 2) là một mệnh đ è , giá trị của n ó là đ ú n g trong khi giá trị của mệnh d ề D(5, 2) là sai. D(ar, 2) cưng là một dạng mệnh đề vì rằng các giá trị chân lý của nó còn phụ thuộc v à o việc thay số t ự n h i ê n n à o cho ký hiệu .r. N h ư n g D^(a, 1) — Ì v ớ i bất kỳ p h à n t ử a n à o thuộc N (bất kỳ số t ự nhiên n à o cũng chia hết cho đ ơ n vị),, do v đ ó D(x, 1) là một mệnh đ è . Trong các mệnh đ ề toán học chủ y ế u là ta 21.ói t ớ i tỉnh đ ú n g hoặc sai của các vị t ừ xác định t r ẽ n n h ạ n g tập hợp khác nhau. BÀI TẬP I . Hãy chỉ ra trong số những câu sau đ à y , câm nào là mệnh đ ề : a) Trong mặt phang qua mỗi d i ê m đã cho có t h ề kè đ u ợ c ít nhát một tiếp tuvẽn v ớ i một v ò n g tròn cho t r ư ỏ c ; b) Có các tam giác v u ô n g g ó c ; c) Tam giác đà cho l à v u ô n g góc ; d) Sồng Vonga chảy v à o Hắc h ả i ; đ) Chơi cờ đồminò đ i ! 14
2. Hãy xét xem trong sô những mệnh đe vừa ke trên, mệnh' đề nào đúng, mệnh đề nào sai. 3. Có thê xác định được bao nhiêu vị từ n —nguyên khác nhau trẽn một tập hợp hữu hạn M chứaj k phần t ử ? §2. CÁC PHÉP TOÁN TRÊN MỆNH ĐỀ 2. 1° Nếu cỏ nhiều mệnh đề t h i t ừ chúng có t h ề lập* được những mệnh đê m ớ i nhờ những liên hệ g ọ i là liên kết logic, như các từ nối « v à » , Khoác là)), từ phủ định « không », các t ừ « nếu..., thì...», « khi và chỉ khi...» Chẳng hạn câu phát biêu v ề tính chất bắc càu của sầ chìa hết của các số n g u y ê n : « nếu a chia hết cho và b chia hết cho c thì a chia hét cho c » cổ thề lập nên được từ ba mệnh đề D(a, b), D(b.e). D(a, c) (2.1) trong đó D là vị t ừ chia hết đ ã đ ư a ra ờ diêm 1.2°. Có nghĩa là tính chất bắc cầu của s ư chia hết có t h ề v i ế t dưới d ạ n j cân: « nếu D(a, b) và D(b, c), thì D(a, c)'» (2.2) T ừ các dạng mệnh đề (2.1) cũng có thề lập được câu : « D(a, b) hoặc D(b, c)» (2.3) - Với những giá trị cụ thề của a. b, c, các câu (2.2) và (2.3) là những mệnh đ ề . Giá trị chân lý của chúng phụ thuộc vào các g i á 4 r ị của a, b, c và việc dùng Hên kết nào đễ lập n ê n chúng. Trong đ ạ i số mệnh đề, các liê n kết đóng vai trò n h ư các phép t o á n , gọi là các p h é p toán logic, hay là các phép toán mệnh đề. 2.2°. P h é p toán p h ả định. Ta xét mệnh đẽ Ả. Phú định của A là m ộ i mệnh đề, kỷ hiệu là A (và đọc là >), nó ãímf.ĩ khi A .sai và sai khi À.đúng.
P h é p t o á n n à y đ ư ợ c xác định bằng m ộ t bảng, g ọ i là bảng chán lý: A ! A P h é p t o á n phủ đ ị n h t ư ợ n g ứ n g v ớ i l i ê n k ế t logic ((không)). Chẳng h ạ n n ế u A b i ể u 0 Ì t h ị m ệ n h đồ D (a, b) thì À b i ê u thị câu Ì 0 « s ố t ự n h i ê n a k h ô n g chia hết cho sỉ t ự n h i ê n b)). 2.3°. Phép toán hội*: Hội của các m ệ n h đ ề A và B là .một m ệ n h đ ề , k ý h i ệ u là A Ạ B (đọc là « x \ v à B))) mà 'Các giá trị của nó được xác định bằng bảng sau d ầ y : Ã B A Ạ B M ệ n h đề Ả /\B đ ủ n g k h i và chỉ k h i cả hai m ệ n h đ ề A và lì là 0 0 0 đún£>". T r o n g tất cả các trưởng •ri' hợp ktĩảc n ộ là sai. P h é p h ộ i 1 0 thực h i ệ n v a i t r ò của t ừ n ỉ i « và)). 0 1 0 Chẳng hạn câu D(a, b) / \ D(a, c) u 1 1 t r o n g đó D b i ê u t h ị vị t ừ chia hết c ó nghĩa l à : « số ni)"uyên a chia h ế t cho sỗ n g u y ê n b v à sỗ n g u y ê n a chia hết cho D 4 l à số n g u y ê n Ó). |Thí d ụ n h ư D(6, 5) A (G< ) mị m ệ n h đ ề sai, D(6. 2) A D(6, 4) cũng là một mệnh đ i •sai, c ò n D(6, 2) Ạ D(6, 3) l à một m ệ n h đề đúng. . í 2.4° Phép toan tuyền*: Tuyên của các m ệ n h éc-A và B là m ộ t m ệ n h đ ề , k ý h i ệ u là A V B ( đ ọ c - l à C( Ả hoặc B » ) , m à giá trị của nó được xác định bằng bặỉỊg M ệ n h đ ề A V B sai k h i v à chỉ k h i c á hai mệnh đ ề A và B đ ề u sai."-Phép t u y ê n thực h i ệ n v a i t r ò của t ừ * T ừ l a tinh là conjunctio, có nghĩa là liên kết, l i ê n h ộ . , * T ừ l a tinh l à disjuntio c ó nghĩa l à sự khảo nhau.
A B A V B nỗi « h o ặ c » . Chang hạn câu ccD(a, b) V D (a, c ) » theo ngôn 0 0 0 ngữ thông thường có nghĩa l à : (CSỐ n g u y ê n a chia hết cho số 1 0 1 nguyên b hoặc số nguyên ó * . 0 1 1 Vi t h ế C( D (6, 5) V (6, 4)» là mệnh 1 1 í đ ề sai, còn các mệnh đề (í D (6, 2) V D(6, 4)» và «0(6, 2) V D (6. 3 » là đúng. 2.5°. Phép toán k é o theo**. Phép kéo theo của các mệnh đề A và B là một mệnh đề, ký hiệu là A ) B ( đ ọ c l à : C( A kéo theo Bp), mà các g i á trị của nó được xác định bằng b ả n g : Mệnh đè A :> B chỉ sai khi A A B A } B đ ú n g m à B sai. N ế u A và B liên hệ v ớ i nhau 0 0 1 theo nghĩa này thì p h é p kéo theo 1 0 0 t ư ơ n g íậig v ớ i liên hệ logic tí nếu..., thi... )),qua đ ó hình thành 0' 1 1 n é n mệnh đề gọi là mệnh đề điều 1 1 1 k i ệ n
thì định đề về đường thẳng song song trong hình học ơclit không chứng minh dược» và từ tinh đúng đắn của tiền đề của nỏ ta suy rá điều khẳng định chắc chắn sau đây: ccĐịnh dề về đường thẳng song song là không the chứng minh được từ tất cả các tiên đề còn lại của hint học ơclit)). Theo định nghĩa Qua phép kéo theo, các mệnh đề: nếu « 2 là một số nguyên tố )) thì «trong tam giác câr các góc ớ đáy bằng nhau hoặc là nếu « 4 là một se nguyên tố » thì «trong tam giác cân các góc ớ đáy bằn£ nhau*), lả hoàn toàn đúng, mặc dâu rằng tiền đề và lú quả trong các mệnh đề này không liền hệ gì với nhai vệ mặt nội dung. * ìí 2.6° Phép toán tương đương. Phép tương đương củi các mệnh đề A và B là một mệnh đè, ký hiệu là A - ì đọc là^A tương đương với B) mà giả trị của nó đượ< Kấc định bằng bảng Ai B Mệnh đệ A ^ B lấy giá trị đun! chỉ trong trường hợp cồ hai mèn] 0 0 1 đề Ả và B đều đúng hoặc đềi sai. Nếu A và B liên hệ với nhai 1 0 0 theo nghĩa này thì phép lươn, ti .1 0' đương tương ứng với liên h 1 1 1 logic «...khi và chỉ khi.*.». Khái niệm tương đương đón Tai trò quan trọng trọng toán học. T a sẽ dùng tới phê này khi nói tới các mệnh đề A và B sao cho từ A đùn suy ra B đúng và từ B đúng suy ra A đúng, Thí dụ ĩ í Giả sử A và B là như sau: A là mệnh đề ( í s ố 3n ] chẵn » còn B là « s ố n là chẵn ». Phép tương đương củ 18
f & B trong trường hợp này có nghĩa l à : ((số 3n là Ifh khi vả chỉ khi số n là chẵn ». ĩphẻỹ t ư ơ n g đ ư ơ n g có nhiều cách phát biêu bằng lời ihẳc nhau. V ớ i thí d ụ đ ã nêu, các cách phát biêu đó l à : ù T ừ n là số chẵn suy ra rằng 3n cũng là số chẵn %ị ngược l ạ i ; '* 2. Điều kiện n là số chẵn là cần và đủ đê cho 3n là l ổ chẵn; 3. Điều kiện 3n là số chằn là cằn và đủ đề cho n là #6, chẵn; 4. Các điều k i ệ n 3n là số chẵn và n là số ếhẵn là Hiêng đương; 5. Số 3n là chẵn khi và chỉ khi n là số chẵn. ý.2.7°. Khái niệm về công thức. Giả sử cho các biến llêrih đề Xi , x . n (2. 4). ậỊjfr các biến mệnh đ ề này, mà ta gọi là các biến mệnh M gốc, níiờ các phép toán mệnh đề có thề lập được ỊỆC biêu thức khác phau, chẳng hạn I (X, V Xa) :> Xa, ((X, V Xà) :> Xs) Ạ ( X i V x ) v.v... 4 Các biêu thức nhận được n h ư v ậ y gọi ĩà công thức xây l ự n g t r ê n các biến mệnh đề gốc. ; Nhờ các đẩu ngoặc ta xác định được t h ứ t ự thực hiện lác p h é p toán khi lập công thức. ^ I Trong trường hợp tông quát ta viết công thức lập n ê n l i các biến mệnh đề («2. 4) d ư ớ i dạng A(Xj, x ). n lặc b i ệ t ' *A(Xu Xa, Xa) = ((X, V x ) :> x ) A ( X i V x ). « (2. 5) 2 3 8 |dấu bằng thay thế cho từ ((CỘ nghĩa Jà»). Giả sử M là tạp hợp tất cả ứác công thức xây dựng tược t ừ hệ thống (2. 4). Khi đ ổ v ớ i bất kỳ hai công thức A(Xt, X ) , B(Xj, n X ) ^ M, n 19
(Ạ), (A) V (BX (A) A (B). (2. 6) ( A ) :> (B), (A) - (BO cũng thuộc M. Các công thức A và B gọi là bộ phận hav công thức con của các công thức (2. 6). Cả điêu ngược l ạ i cũng đúng. Với mỗi công thức c ^ M thì c hoặc là một trong những biến mệnh đề (2, 4) hoặc là có các công thức A, ỉ* £ M sao cho c trùng với một trong các công thức ( Ã ) , (A) V (B), (A) A > (B), (A) ~ ( B ) . (B), CA) Nói một cách khác, tập hợp M là đóng kín đ ố i với tất cả các phép toán mệnh đề, hay là nói rẳng, đ ố i với các phép toán này, M là một đại số — đó là đại số các công thức. Ta hây định nghĩa lùột đặc trưng bẳng số đ ố i v ớ i các công thức. Định nghía 2.1. Ta gọi hạng r (A) của còng thức A là SỐ tất cả các phép toán mệnh đe mà qua đó lập nên công tụức Ả từ hệ thống gốc của các biến mệnh ctè, trong đó ta đặt r (X) = 0 klii X là một biến mạnh đẽ. Chẳng hạn, với cồi|g thức A = ( X V Y) > (X y Y) ta cỏ r (A) = 4. Đễ giảm bớt số lượng các dấu ngoặc khi viết các công thức ta đưa ra qui tắc coi phép toán / \ được thực hiện trước phép toán V và cả hai phép toán này l ạ i thực hiện trước các p h é p toán 2> và Công thúc (2.5) cỏ thê viểt như sau: A = (Xi V x > x ) A ( X i V x ) s 3 3 (sau này thường ta không liệt kê các biên mệnh đè gốc trong các đấu ngoặc viết sau A nữa). Còn trong công thức B - ( X O x ) A (X, > Xí) 3 20
•MỊ" í thì không thê bỏ đi một cặp dấu ngoặc nào. Những câu trong toán học có thề biêu thị bạng các lông thức, trong đỏ các vị từ tương ứng dược coi là các biên mệnh đề gốc. Chang hạn như câu (2.2) cố the viết dưới dạng cổng thức Dfa,b)AD(b,c))D(a,c), Câu ((nếu mỗi số hạng cửa một tòng các số nguyên chia hết cho một số nào đó thì cả tổng đó cũng chia Siết cho số đ ó ) ) được viết bằng công thức S(a, b, c) A D(a, d) A D(b, d) :> D(c, d) trong đó s biêu thị vị tử lẩy tong. . 2 . 7 ° . Các giá trị chân lý cửa công thức A(Xj,...,X ) n àượe xác định từ các giá trị chân lý cửa X!,...,x n . Vì tằng các giá trị chân ly cửa X i là các phàn tử cửa tập l ợ p B = ị 0; Ì ị nên công thức A có the xem như một n |bàm số, ịiay là một ảnh xạ cửa tập hợp B vào B . Nó, Igọi là hàm chân lý. Các giả trị cửa hàm này cho bằng Ibảng chân lý. Ta háy lập bâng chân lý cho công thức B = ( X o Xa) A x 3 Xi x 2 Xa Xi :> X , B 0 0 0 1 0 0 0 1 1 1 0 1 0 1 0 0 í 1 1 1 í 0 0 0 0 1 0 1 0 0 1 1 0 1 0 1 1 1 1 1 Tám hàng cửa ba cột thứ nhất chứa tất cả các hệ nhông có the có được cửa các giá trị cửa các biến mênh 21