Giới thiệu.
Mục đích.
Các phần mới của môn toán rời rạc mặc dù được triển khai dưới dạng chương trình giảng dạy và hàng loạt bài giảng, vẫn chưa tồn tại dưới dạng chuyên khảo, ít nhất là bằng tiếng Nga, kể từ khi môn toán rời rạc dành cho các trường đại học kỹ thuật tập trung vào cái cũ bài toán ứng dụng, mà các kỹ sư đã phải giải quyết. Đặc biệt ở logic toán họcđó là sự giảm thiểu mạch logic, ngày nay đã mất đi sự liên quan.
Thật thú vị khi lưu ý rằng lý thuyết tổng hợp mạch logic, đã trải qua gần như một “chu trình sinh học” hoàn chỉnh trước mắt một thế hệ các nhà nghiên cứu, là một ví dụ rất mang tính hướng dẫn về việc các ngành công nghiệp rất dễ bị lỗi thời như thế nào. khoa học kỹ thuật, liên quan yếu đến khoa học cơ bản. 10 năm trước mọi chuyện tạp chí kỹ thuật chứa đầy các bài viết về tối thiểu hóa và tổng hợp các mạch logic. Hầu hết các phương pháp giảm thiểu do các nhà khoa học phát triển hiện đã bị lãng quên và không còn nhu cầu trong thực tế. Và những ý tưởng được coi là thuần túy lý thuyết vào thời điểm đó đã tìm thấy ứng dụng thực tế trong công nghệ hiện đại. Ví dụ, logic mờ, mạng Petri và lý thuyết thuật toán đã đứng vững trước thử thách của thời gian và được sử dụng rộng rãi trong khu vực khác nhauđiều khiển học và lập trình, chẳng hạn như lập trình hệ thống, độ phức tạp tính toán và trí tuệ nhân tạo.
Và lý thuyết về thuật toán đã trở thành phần trung tâm của toán học rời rạc. Tuy nhiên, không giống như hầu hết các chuyên khảo bằng tiếng Nga, trong quá trình giảng dạy, những vấn đề này được trình bày như một phương tiện để giải quyết các vấn đề thực tế, kỹ thuật.
Như đã biết, sau mỗi thập kỷ, cơ sở linh kiện của máy tính, hệ điều hành, phương tiện truy cập và bản thân các chương trình đang thay đổi hoàn toàn. Tuy nhiên, cấu trúc và thuật toán cơ bản của chúng vẫn không thay đổi trong thời gian dài hơn. Những nền tảng này bắt đầu được đặt ra từ hàng ngàn năm trước, khi logic hình thức được phát triển và các thuật toán đầu tiên được phát triển.
Logic toán học và lý thuyết thuật toán truyền thống thuộc về khoa học cơ bản và được coi là ít có liên quan thực tế và khó hiểu. Quả thực, khi J. Bull tạo ra bộ máy toán họcĐại số Boolean, anh ấy phải mất một thời gian dài mới tìm ra ứng dụng thực tế, tuy nhiên, vào thế kỷ 20, chính bộ máy toán học này đã giúp thiết kế tất cả các thành phần máy tính có thể thực hiện được. Do đó, thành kiến đầu tiên trong số này đã bị bác bỏ thành công bởi sự phát triển công nghệ máy tính.
Đối với thành kiến về sự khó hiểu của bộ môn này, phần lớn xuất phát từ việc các cuốn sách về logic toán học và lý thuyết thuật toán đều được các nhà toán học viết cho các nhà toán học.
Ngày nay, khi khả năng của công nghệ máy tính đã tăng lên gấp nhiều lần và máy tính cá nhân Có nhiều người biết cách sử dụng chúng một cách hiệu quả hơn rất nhiều, việc hiểu được những gì có thể và không thể làm được với công nghệ máy tính hiện đại là điều vô cùng quan trọng.
Chính xác lý thuyết tổng quát các thuật toán đã chỉ ra rằng có những vấn đề không thể giải quyết được cho dù sức mạnh tính toán có mạnh đến đâu và nhánh phát triển nhanh chóng của nó, lý thuyết về độ phức tạp tính toán, dần dần dẫn đến sự hiểu biết rằng có những vấn đề có thể giải quyết được, nhưng phức tạp về mặt khách quan, và sự phức tạp của chúng có thể trở thành tuyệt đối theo một nghĩa nào đó. thực tế không thể tiếp cận được với các máy tính hiện đại.
Khóa học này đặt ra các mục tiêu sau:
1. Trình bày tất cả các vấn đề đang được xem xét một cách đơn giản nhất có thể nhưng không đơn giản hơn yêu cầu đối với một chuyên gia có trình độ cao.
2. Vấn đề thực tế thiết kế và phân tích hệ thống thông tin là điểm khởi đầu và bộ máy chính thức là phương tiện giải pháp mang tính hệ thống những vấn đề này. Chúng tôi tin chắc rằng học sinh không phải là một chiếc bình cần được lấp đầy mà là một ngọn đuốc cần được thắp sáng.
3. Mỗi phần của khóa học đều có các câu hỏi tự kiểm tra. Để đồng hóa khóa học này học sinh phải trả lời tất cả những câu hỏi này.
Kết quả của việc nắm vững khóa học này, dựa trên sự hiểu biết rõ ràng về các phần lý thuyết có liên quan, sinh viên sẽ có thể:
Thực hiện hình thức đơn giản nhất chuyển đổi logic thông tin trong một cơ sở tùy ý của các chức năng logic;
Điểm nổi bật trong lập luận chứng cứ ngôn ngữ tự nhiên cấu trúc logic, xây dựng các sơ đồ chứng minh hình thức và kiểm tra tính đúng đắn của chúng.
1.2 Biểu diễn logic
Biểu diễn logic - mô tả hệ thống, quá trình, hiện tượng đang được nghiên cứu dưới dạng một tập hợp câu lệnh phức tạp tạo thành từ câu lệnh đơn giản (sơ cấp) Và kết nối logic
giữa họ. Các biểu diễn logic và các thành phần của chúng được đặc trưng bởi các thuộc tính nhất định và một tập hợp các phép biến đổi được phép đối với chúng (phép toán, quy tắc suy luận, v.v.), triển khai các biến đổi được phát triển dưới dạng hình thức (toán học) logic phương pháp đúng lý luận - quy luật logic.
Các phương pháp (quy tắc) trình bày chính thức các phát biểu, xây dựng các phát biểu mới từ những phát biểu hiện có bằng cách sử dụng các phép biến đổi chính xác về mặt logic, cũng như các phương pháp (phương pháp) xác lập tính đúng hay sai của các phát biểu được nghiên cứu trong logic toán học. Logic toán học hiện đại bao gồm hai phần chính: logic của phát biểu và che phủ nó logic vị từ(Hình 1.1), để xây dựng có hai cách tiếp cận (ngôn ngữ), tạo thành hai biến thể của logic hình thức: đại số logic Và phép tính logic. Có sự tương ứng một-một giữa các khái niệm cơ bản của các ngôn ngữ logic hình thức này. Tính đẳng cấu của chúng cuối cùng được đảm bảo bởi sự thống nhất của các phép biến đổi cơ bản có thể chấp nhận được.
Cơm. 1.1
Đối tượng chính của các nhánh logic truyền thống là các câu lệnh.
Tuyên bố - câu trần thuật (tuyên bố, phán đoán), o thật có ý nghĩa khi nói rằng nó ĐÚNG VẬY hoặc SAI. Tất cả kiến thức khoa học(các định luật và hiện tượng vật lý, hóa học, sinh học, v.v., các định lý toán học, v.v.), các sự kiện cuộc sống hàng ngày, các tình huống phát sinh trong quá trình kinh tế và quản lý được hình thành dưới dạng các phát biểu. Câu mệnh lệnh và câu hỏi không phải là câu khẳng định.
Ví dụ về các câu: “Hai lần hai là bốn”, “Chúng ta đang sống ở thế kỷ 21”, “Đồng rúp là tiền Nga”, “Alyosha là anh trai của Oleg”, “Các phép toán hợp, giao và cộng là các phép toán Boolean trên tập hợp ”, “Con người là phàm nhân”, “Sắp xếp lại vị trí của các số hạng không làm thay đổi tổng”, “Hôm nay là thứ Hai”, “Nếu trời đang mưa, bạn nên mang theo một chiếc ô."
Để tiếp tục hoạt động với những câu này dưới dạng các câu phát biểu, chúng ta phải biết từng câu đó là đúng hay sai, tức là. biết họ giá trị chân lý (sự thật). Lưu ý rằng trong một số trường hợp, tính đúng hay sai của một tuyên bố phụ thuộc vào thực tế cụ thể nào (hệ thống, quá trình, hiện tượng) mà chúng ta đang cố gắng mô tả với sự trợ giúp của nó. Trong trường hợp này, câu đã cho được cho là đúng (hoặc sai) theo cách giải thích (ngữ cảnh) nhất định. Chúng tôi tiếp tục giả định rằng bối cảnh đã được đưa ra và tuyên bố có một giá trị chân lý nhất định.
1.3 Lịch sử phát triển logic toán học
Logic như một khoa học được hình thành vào thế kỷ thứ 4. BC Nó được tạo ra bởi nhà khoa học Hy Lạp Aristotle.Từ "logic" xuất phát từ "logo" trong tiếng Hy Lạp, một mặt có nghĩa là "từ" hoặc "trình bày", mặt khác có nghĩa là suy nghĩ. TRONG từ điển giải thích Ozhegova S.I. Người ta nói: “Logic là khoa học về các quy luật tư duy và các hình thức của nó”. Vào thế kỷ 17 Nhà khoa học người Đức Leibniz đã lên kế hoạch tạo ra một ngành khoa học mới, đó sẽ là “nghệ thuật tính toán sự thật” . Theo logic này, theo Leibniz, mỗi câu lệnh sẽ có một ký hiệu tương ứng và lý luận sẽ có dạng tính toán. Ý tưởng này của Leibniz, chưa đáp ứng được sự hiểu biết của những người cùng thời với ông, đã không được lan truyền hay phát triển và vẫn là một phỏng đoán xuất sắc.
Chỉ vào giữa thế kỷ 19. Nhà toán học người Ireland George Boole là hiện thân của ý tưởng của Leibniz. Năm 1854, ông viết tác phẩm “Nghiên cứu các định luật tư duy”, đặt nền móng cho đại số của logic, trong đó các định luật tương tự như các định luật đại số thông thường được áp dụng, nhưng các chữ cái thì có. không biểu thị các con số, mà là các câu lệnh. Trong ngôn ngữ của đại số Boole, người ta có thể mô tả cách suy luận và “tính toán” kết quả của nó. Tuy nhiên, nó không bao hàm hết mọi lý luận mà chỉ một số kiểu của họ, Vì vậy, đại số Boole được coi là một phép tính mệnh đề.
Đại số của logic Boolean là phôi thai khoa học mới- logic toán học. Ngược lại, logic của Aristotle được gọi là logic hình thức truyền thống. Cái tên “logic toán học” phản ánh hai đặc điểm của môn khoa học này: thứ nhất, logic toán học là logic sử dụng ngôn ngữ và phương pháp của toán học; thứ hai, logic toán học được đưa vào cuộc sống bởi nhu cầu của toán học.
Vào cuối thế kỷ 19. Lý thuyết tập hợp do Georg Cantor tạo ra dường như là một nền tảng đáng tin cậy cho toàn bộ toán học, kể cả logic toán học, ít nhất là cho phép tính mệnh đề (đại số Boole), bởi vì Hóa ra đại số Cantor (lý thuyết tập hợp) là đẳng cấu với đại số Boole.
Bản thân logic toán học đã trở thành một nhánh của toán học mà thoạt đầu có vẻ rất trừu tượng và vô cùng xa vời. ứng dụng thực tế. Tuy nhiên, lĩnh vực này không còn là lãnh địa của các nhà toán học “thuần túy” được lâu nữa. Vào đầu thế kỷ 20. (1910) Nhà khoa học người Nga Ehrenfest P.S. đã chỉ ra khả năng sử dụng bộ máy đại số Boolean trong liên lạc qua điện thoại để mô tả các mạch chuyển mạch. Vào những năm 1938-1940, gần như đồng thời, các công trình của nhà khoa học Liên Xô V.I. Shestakov, nhà khoa học Mỹ Shannon và các nhà khoa học Nhật Bản Nakashima và Hakazawa đều xuất hiện về ứng dụng logic toán học trong công nghệ số. Chuyên khảo đầu tiên về việc sử dụng logic toán học trong thiết kế thiết bị kỹ thuật số được nhà khoa học Liên Xô M.A. Gavrilov xuất bản ở Liên Xô. vào năm 1950. Vai trò của logic toán học trong sự phát triển của công nghệ vi xử lý hiện đại là vô cùng quan trọng: nó được sử dụng trong thiết kế phần cứng máy tính, trong việc phát triển tất cả các ngôn ngữ lập trình và trong thiết kế các thiết bị tự động hóa rời rạc.
Các nhà khoa học có đóng góp to lớn cho sự phát triển của logic toán học các quốc gia khác nhau: Giáo sư của Đại học Kazan Poretsky P.S., de-Morgan, Pierce, Turing, Kolmogorov A.N., Heidel K. và cộng sự.
1.4 Câu hỏi tự kiểm tra.
1. Xây dựng mục tiêu khóa học
Gửi tác phẩm tốt của bạn tới cơ sở kiến thức thật dễ dàng. Sử dụng mẫu dưới đây
Các sinh viên, nghiên cứu sinh, các nhà khoa học trẻ sử dụng nền tảng kiến thức trong học tập và công việc sẽ rất biết ơn các bạn.
Chưa có phiên bản HTML của tác phẩm.
Bạn có thể tải xuống kho lưu trữ của tác phẩm bằng cách nhấp vào liên kết bên dưới.
Tài liệu tương tự
Các định nghĩa cơ bản về logic toán học, Boolean và các hàm tương đương. Khái niệm chungĐại số Boole. Đại số Zhegalkin: phát biểu và vị ngữ. Sự định nghĩa lý thuyết hình thức. Các yếu tố lý thuyết về thuật toán, hàm đệ quy, máy Turing.
khóa học, bổ sung ngày 08/08/2011
Các hình thức tư duy cơ bản: khái niệm, phán đoán, suy luận. Một bài luận của George Boole khám phá đại số logic một cách chi tiết. Giá trị đúng (tức là đúng hoặc sai) của một tuyên bố. Các phép toán logic đảo ngược (phủ định) và kết hợp.
trình bày, được thêm vào ngày 14/12/2016
Giải thích đồ họa của các tập hợp và các phép toán trên chúng. Logic toán học, đại số Boolean. Hình thức kết hợp hoàn hảo bình thường. Các công thức tương đương và cách chứng minh chúng. Tính hoàn chỉnh của hệ thống Hàm Boolean. Logic vị từ, lý thuyết đồ thị.
bài giảng, thêm vào 01/12/2009
Lịch sử xuất hiện của đại số Boolean, sự phát triển của hệ thống phép tính mệnh đề. Các phương pháp xác lập tính đúng hay sai của các phát biểu logic phức tạp bằng cách sử dụng phương pháp đại số. Phân tách, kết hợp và phủ định, bảng chân lý.
trình bày, thêm vào ngày 22/02/2014
Ma trận vuông và các yếu tố quyết định. Tọa độ không gian tuyến tính. Nghiên cứu hệ thống phương trình tuyến tính. Đại số của ma trận: phép cộng và phép nhân của chúng. Hình ảnh hình học số phức và họ dạng lượng giác. Định lý Laplace và cơ sở.
sổ tay đào tạo, bổ sung 02/03/2009
Khái niệm cơ bản của lý thuyết số dương (tự nhiên). Phát triển tốc ký cho các phép tính số học. Một ngôn ngữ tượng trưng cho sự phân chia. Tính chất và đại số của so sánh. Nâng cao sự so sánh về quyền lực. Bình phương lại. Định lý nhỏ Fermat.
trình bày, thêm vào ngày 04/06/2014
Hệ thống xử lý số thông tin. Khái niệm đại số Boole. Chỉ định các phép toán logic: phân tách, kết hợp, đảo ngược, hàm ý, tương đương. Các định luật và nhận dạng của đại số Boole. Khái niệm cơ bản về logic MÁY TÍNH. Chuyển đổi công thức cấu trúc.
trình bày, thêm vào ngày 11/10/2014
Cuốn sách được viết dựa trên tài liệu từ các bài giảng và hội thảo do tác giả thực hiện dành cho sinh viên năm cuối Khoa Cơ và Toán của Đại học quốc gia Moscow. Nó nói về các khái niệm cơ bản của logic toán học (logic mệnh đề, ngôn ngữ bậc nhất, khả năng diễn đạt, phép tính mệnh đề, lý thuyết có thể quyết định, định lý đầy đủ, nguyên tắc của lý thuyết mô hình). Buổi thuyết trình là dành cho sinh viên trường toán, sinh viên toán và mọi người quan tâm logic toán học. Cuốn sách bao gồm khoảng 200 vấn đề có độ khó khác nhau.
Logic của các phát biểu.
Lời nói và hoạt động
“Nếu số n là hữu tỉ thì n - số đại số. Nhưng nó không phải là đại số. Điều này có nghĩa là p không hợp lý.” Chúng ta không cần phải biết số n là gì, số nào được gọi là số hữu tỉ và số nào là số đại số, để nhận ra rằng lập luận này đúng theo nghĩa là kết luận thực sự xuất phát từ hai tiền đề đã nêu. Loại tình huống này - khi một tuyên bố nhất định là đúng bất kể ý nghĩa của các tuyên bố trong đó - tạo thành chủ đề của logic mệnh đề.
Sự khởi đầu này (đặc biệt khi coi khóa học logic là một phần trong chương trình của Khoa Triết học, nơi “logic biện chứng” cũng được nghiên cứu) là đáng báo động, nhưng trên thực tế, những xem xét của chúng ta sẽ có bản chất toán học hoàn toàn chính xác, mặc dù chúng ta sẽ bắt đầu với động lực không chính thức.
Mục lục
Lời nói đầu
1. Logic mệnh đề
1.1. Lời nói và hoạt động
1.2. Hệ thống dây chằng hoàn chỉnh
1.3. Sơ đồ các yếu tố chức năng
2. Phép tính mệnh đề
2.1. Phép tính mệnh đề (PC)
2.2. Chứng minh thứ hai của định lý đầy đủ
2.3. Tìm một phản ví dụ và phép tính dãy số
2.4. Logic mệnh đề trực quan
3. Ngôn ngữ bậc một
3.1. Công thức và giải thích
3.2. Định nghĩa sự thật
3.3. Vị ngữ biểu đạt
3.4. Tính biểu diễn trong số học
3.5. Vị từ không thể diễn đạt được: tự động cấu hình
3.6. Loại bỏ các bộ định lượng
3.7. Số học Presburger
3.8. Định lý Tarski-Seidenberg
3.9. Tương đương sơ cấp
3.10. trò chơi của Ehrenfeucht
3.11. Giảm điện năng
4. Phép tính vị ngữ
4.1. Công thức hợp lệ nói chung
4.2. Tiên đề và quy tắc suy luận
4.3. Tính đúng đắn của phép tính vị ngữ
4.4. Kết luận trong phép tính vị ngữ
4.5. Tính đầy đủ của phép tính vị từ
4.6. Đổi tên biến
4.7. Dạng chuẩn có tiền tố
4.8. Định lý Herbrand
4.9. Hàm Skolemov
5. Lý thuyết và mô hình
5.1. Tiên đề bình đẳng
5.2. Tăng sức mạnh
5.3. Lý thuyết hoàn chỉnh
5.4. Các lý thuyết không đầy đủ và không thể quyết định
5.5. Sơ đồ và phần mở rộng
5.6. Bộ siêu lọc và độ nén
5.7. Phân tích phi tiêu chuẩn
Văn học
chỉ mục chủ đề
Danh mục tên.
Tải xuống miễn phí sách điện tửở dạng thuận tiện, hãy xem và đọc:
- fileskachat.com, tải xuống nhanh chóng và miễn phí.
Tải xuống pdf
Dưới đây bạn có thể mua cuốn sách này với mức giá tốt nhất với mức giảm giá khi giao hàng trên khắp nước Nga. Mua cuốn sách này
Tải sách Các bài giảng về logic toán học và lý thuyết thuật toán, Phần 2, Ngôn ngữ và phép tính, Vereshchagin N.K., Shen A., 2012 - pdf - Depositfiles.
Đại học Volzhsky được đặt theo tên Tatishcheva.
Các bài giảng về logic toán học và lý thuyết thuật toán.
Biên soạn: Phó giáo sư S.V. Kaverin.
Chương I. Đại số logic.
§1.1. Định nghĩa hàm Boolean.
hàm Boolean y=f(x 1 ,x 2 ,…,x n)từ N biến x 1 , x 2 ,...,x n là bất kỳ hàm nào trong đó các đối số và hàm có thể nhận giá trị 0 hoặc 1, tức là. hàm Boolean là một quy tắc trong đó một tập hợp các số 0 và số 1 tùy ý
(x 1 ,x 2 ,...,x n) được gán cho giá trị 0 hoặc 1.
Hàm Boolean còn được gọi là hàm đại số logic, hàm nhị phân và hàm chuyển mạch.
Hàm Boolean từ N các biến có thể được chỉ định bởi một bảng chân lý trong đó các tập hợp giá trị đối số được sắp xếp theo thứ tự tăng dần của số lượng của chúng : lúc đầu tuyển dụng đang được tiến hành, biểu thị khai triển nhị phân của 0 (bộ này được đánh số 0); sau đó đến tập hợp, là khai triển nhị phân của 1, rồi 2, 3, v.v. Bộ cuối cùng bao gồm N đơn vị và là khai triển nhị phân của số 2 N-1 (thứ tự sắp xếp các tập hợp này sẽ được gọi là thứ tự từ điển). Xét rằng số đếm bắt đầu từ 0 và giá trị của hàm Boolean có thể là 0 hoặc N
1, chúng ta kết luận rằng chỉ có 22 hàm Boolean khác nhau của N các biến. Vì vậy, ví dụ, có 16 hàm Boolean hai biến, 256 hàm ba biến, v.v.
Ví dụ 1.1.1.(bỏ phiếu) . Hãy xem xét một thiết bị ghi lại việc thông qua một nghị quyết nhất định của “ủy ban ba người”. Mỗi thành viên ủy ban nhấn nút riêng của mình khi thông qua nghị quyết. Nếu đa số thành viên bỏ phiếu thuận thì nghị quyết được thông qua. Điều này được ghi lại bằng một thiết bị ghi âm. Như vậy, thiết bị thực hiện hàm f(x,y,z ) , bảng chân lý của nó có dạng
| x | 0 | 0 | 0 | 0 | 0 | 1 | 1 | 1 |
| y | 0 | 0 | 1 | 1 | 1 | 0 | 0 | 1 |
| z | 0 | 1 | 0 | 0 | 1 | 0 | 1 | 1 |
| f(x,y,z) | 0 | 0 | 0 | 0 | 1 | 0 | 1 | 1 |
Hàm Boolean cũng được chỉ định duy nhất bằng cách liệt kê tất cả các bộ dữ liệu mà nó nhận giá trị 0 hoặc bằng cách liệt kê tất cả các bộ dữ liệu mà nó nhận giá trị 1. Hàm thu được trong ví dụ f cũng có thể được xác định bằng hệ đẳng thức sau: f(0,0,0) = f(0,0,1) = f(0,1,0) = f(1,0,0) =0.
Một vectơ giá trị hàm Boolean y=f(x 1 ,x 2 ,…,x n) là tập hợp có thứ tự của tất cả các giá trị của hàm f, trong đó các giá trị được sắp xếp theo thứ tự từ điển. Ví dụ: cho một hàm ba biến f được xác định bởi một vectơ giá trị (0000 0010) và bạn cần tìm một tập hợp mà f lấy giá trị 1. Bởi vì 1 ở vị trí thứ 7 và đánh số vào thứ tự từ điển bắt đầu từ 0 thì chúng ta cần tìm khai triển nhị phân của 6. Do đó, hàm f lấy giá trị 1 trên tập hợp (110).
§1.2. Các hàm Boolean cơ bản.
Trong số các hàm Boolean, cái gọi là hàm Boolean cơ bản nổi bật, nhờ đó có thể mô tả bất kỳ hàm Boolean nào với số lượng biến bất kỳ.
1. Hàm Boolean f(x 1 ,x 2 ,…,x n) nhận giá trị 1 trên tất cả các tập hợp số 0 và số 1 được gọi là hằng số 1, hoặc đơn vị giống hệt nhau. chỉ định : 1 .
2. Hàm Boolean f(x 1 ,x 2 ,…,x n) nhận giá trị 0 trên tất cả các tập hợp số 0 và số 1 được gọi là hằng số 0, hoặc số 0 giống hệt nhau. chỉ định : 0 .
3. Từ chối là hàm Boolean của một biến được xác định bởi bảng chân trị sau
Tên khác : phép nhân logic (sản phẩm); hợp lý "và".
Chỉ định : x&y, xÿy, x⁄y, min(x,y).
5. Phân ly
Tên khác : hệ quả logic. Chỉ định : xØy, xfly, xy.
7. Tương đương là hàm Boolean của hai biến được xác định bởi bảng chân trị sau
Tên khác : phản tương đương. Chỉ định : x∆y, x+y.
9. Đột quỵ của Schaeffer là hàm Boolean của hai biến được xác định bởi bảng chân trị sau
Tên khác : sự phủ định của sự phân tách, hàm logic “không-hoặc”, Webb.
chỉ định : x∞y ; cho hàm Webb - x±y.
Bình luận. Các ký hiệu Ÿ, ⁄, ¤, Ø, ~, ∆, |, ∞ liên quan đến ký hiệu hàm cơ bản chúng tôi sẽ gọi chúng là kết nối hoặc hoạt động.
§1.3. Chỉ định các hàm Boolean bằng cách sử dụng các hàm cơ bản.
Nếu bạn thay thế một số hàm Boolean thành một hàm logic thay vì các biến thì kết quả là một hàm Boolean mới có tên là sự chồng chất hàm thay thế (hàm phức tạp). Sử dụng sự chồng chất, bạn có thể thu được các hàm phức tạp hơn có thể phụ thuộc vào bất kỳ số lượng biến nào. Chúng ta sẽ gọi cách viết hàm Boolean theo các hàm Boolean cơ bản công thức thực hiện chức năng này.
Ví dụ 1.3.1. Cho một hàm Boolean cơ bản x¤y. Chúng ta thay hàm x 1 ∞x 2 thay cho x. Ta thu được hàm ba biến (x 1 ∞x 2)¤y. Nếu thay vì biến y, chúng ta thay thế, ví dụ x 3 ∆x 4, thì chúng ta nhận được tính năng mới từ bốn biến: (x 1 ∞x 2)¤(x 3 ∆x 4). Rõ ràng, bằng cách này, chúng ta sẽ thu được các hàm Boolean, chúng sẽ được biểu diễn thông qua các hàm Boolean cơ bản.
Nhìn về phía trước, chúng tôi lưu ý rằng bất kì một hàm Boolean có thể được biểu diễn dưới dạng chồng chập của các hàm cơ bản.
Để ghi âm nhỏ gọn hơn hàm phức tạp hãy giới thiệu các quy ước sau : 1) dấu ngoặc ngoài được bỏ qua; 2) các phép toán trong ngoặc được thực hiện trước; 3) được coi là mức độ ưu tiên của các kết nối giảm theo thứ tự sau : Ÿ, ⁄, ¤, Ø, ~. Đối với các liên kết tương đương và các liên kết còn lại (∆,|,∞), bạn nên đặt dấu ngoặc đơn ngay bây giờ.
Ví dụ 1.3.2. Trong công thức x⁄y¤z, dấu ngoặc được đặt như sau: ((x⁄y)¤z), bởi vì hoạt động ⁄ mạnh hơn hoạt động ¤ theo thỏa thuận của chúng tôi.
1. Trong công thức x¤y~zØx, dấu ngoặc được đặt như sau: ((x¤y)~(zØx))
2. Trong công thức (x∆y)~zØxy¤Ÿz, các dấu ngoặc được đặt như sau: ((x∆y)~(zØ((xy)¤(Ÿz)))).
3. Công thức xØyØz, theo thỏa thuận của chúng ta, được viết không chính xác, bởi vì đặt dấu ngoặc dẫn đến hai kết quả chức năng khác nhau: ((xØy)Øz) và (xØ(yØz)).
§1.4. Các biến quan trọng và không quan trọng.
Hàm Boolean y=f(x 1 ,x 2 ,…,x n) phụ thuộc đáng kể từ biến x k nếu tồn tại một tập giá trị như vậy Một 1 ,Một 2 ,…,Một k - 1, Một k+1, Một k + 2 ,…, Một N cái đó (Một 1, một 2,…,a k-1 , 0 ,Một k+1,a k+2,…,a N) π f (Một 1, một 2,…,a k-1 , 1 ,Một k+1,a k+2,…,a N).
Trong trường hợp này x k được gọi là biến thiết yếu , V. nếu không thì x k được gọi là biến không đáng kể (giả) . Nói cách khác, một biến sẽ không có ý nghĩa nếu việc thay đổi nó không làm thay đổi giá trị của hàm.
Ví dụ 1.4.1. Giả sử các hàm Boolean f 1 (x 1 ,x 2) và f 2 (x 1 ,x 2) được xác định bởi bảng chân trị sau:
| x 1 | x 2 | f 1 (x 1 ,x 2) | f 2 (x 1 ,x 2) |
| 0 | 0 | 0 | 1 |
| 0 | 1 | 0 | 1 |
| 1 | 0 | 1 | 0 |
| 1 | 1 | 1 | 0 |
Đối với các hàm này, biến x 1 - là có ý nghĩa và biến x 2 không có ý nghĩa.
Rõ ràng, các hàm Boolean không thay đổi giá trị của chúng bằng cách đưa vào (hoặc loại bỏ) các biến không liên quan. Do đó, trong phần tiếp theo, các hàm Boolean được coi là các biến không quan trọng (trong ví dụ chúng ta có thể viết: f 1 (x 1 , x 2) = x 1 , f 2 (x 1 , x 2) = Ÿx 1 ).
§1.5. Các bảng sự thật. Chức năng tương đương.
Biết bảng chân trị của các hàm cơ bản, bạn có thể tính được bảng chân trị của hàm mà công thức này thực hiện.
Ví dụ 1.5.1. F1=x 1 ⁄x 2 ¤(x 1 ⁄Ÿx 2 ¤Ÿx 1 ⁄x 2)
Như vậy, công thức F1 thực hiện phép tách. Ví dụ 1.5.2. F2=x 1 ⁄x 2 Øx 1
Như vậy, công thức F3 thực hiện phép tách.
Các hàm Boolean f1 và f2 được gọi là tương đương, nếu trên mọi tập hợp ( Một 1 ,Một 2 ,…, MỘT) số không và số một, giá trị của các hàm trùng nhau. Ký hiệu cho các hàm tương đương như sau : f1=f2.
Theo các ví dụ đã cho 1-3, chúng ta có thể viết
X 1 ⁄x 2 ¤(x 1 ⁄Ÿx 2 ¤Ÿx 1 ⁄x 2)=x 1 ¤x 2 ;
X 1 ⁄x 2 Øx 1 =1;
((x 1 ⁄x 2)∆x 1)∆x 2 =x 1 ¤x 2.
§1.6. Sự tương đương cơ bản
Các giá trị tương đương đã cho thường hữu ích khi thao tác với các hàm Boolean.
Dưới H, H1, H2,... là viết tắt của một số hàm Boolean.
1. Định luật phủ định kép: H = H.
2. Sự bất lực
3. Tính giao hoán:
H1*H2=H2*H1, trong đó ký hiệu * có nghĩa là một trong các liên từ &, ¤, ∆,
4. Tính liên kết:
H1*(H2*H3)=(H1*H2)*H3, trong đó ký hiệu * có nghĩa là một trong các liên từ &, ¤, ∆, ~.
5. Tính phân phối:
H1&(H2¤H3)=(H1&H2)¤(H1&H3); H1¤(H2&H3)=(H1¤H2)&(H1¤H3); H1&(H2∆H3)=(H1&H2)∆(H1&H3).
6. Định luật De Morgan:
H1&H2 = H1 ∨ H2 , H1∨ H2 = H1 & H2 .
7. Nguyên tắc tiếp quản:
H1¤(H2&H3)=H1, H1&(H2¤H3)=H1
8. Định luật dán:
H1&H2 ∨ H1&H2 = H1, (H1∨ H2) & (H1∨ H2) = H1.
9. Định luật nghịch đảo: H ∨ H = 1, H & H = 0.
10. Quy tắc thực hiện các phép tính với hằng:
H¤1=1, H&1=H, H¤0=H, H&0=0.
Để kiểm tra tính đúng đắn của các đẳng thức trên, chỉ cần xây dựng các bảng chân trị tương ứng là đủ.
Lưu ý rằng thuộc tính kết hợp của một phép toán cho phép phép toán này được mở rộng cho bất kỳ số lượng biến nào. Vì vậy, ví dụ, ký hiệu x¤у¤z¤w là đúng, bởi vì bất kỳ sự sắp xếp nào của dấu ngoặc đơn đều dẫn đến cùng một chức năng. Bản chất giao hoán của một phép toán cho phép bạn hoán đổi các biến trong một công thức. Ví dụ: x⁄y⁄z⁄w=w⁄y⁄x⁄z.
§1.7. Sự hoàn thiện về chức năng.
Trong một máy tính kỹ thuật số hiện đại điển hình, các số là 0 và 1. Do đó, các lệnh mà bộ xử lý thực thi là các hàm Boolean. Dưới đây chúng tôi sẽ chỉ ra rằng bất kỳ hàm Boolean nào cũng được hiện thực hóa thông qua sự kết hợp, phân tách và phủ định. Do đó, có thể xây dựng bộ xử lý cần thiết, có sẵn các phần tử thực hiện kết hợp, phân tách và phủ định. Phần này được dành để trả lời câu hỏi: có (và nếu có) các hệ thống hàm Boolean khác có đặc tính mà chúng có thể được sử dụng để biểu diễn tất cả các hàm khác.
Hãy giới thiệu một số lớp hàm.
1. Lớp hàm bảo toàn hằng số 0, tức là chức năng như vậy
2. Lớp hàm bảo toàn hằng số 1, tức là chức năng như vậy
3. Lớp chức năng tự kép, tức là. các hàm số y=f(x 1 ,x 2 ,…,x n) sao cho f(x 1 , x 2 ,… , x n) = f(x 1 , x 2 ,… , x n) .
4. Lớp học hàm tuyến tính, tức là các hàm số y=f(x 1 ,x 2 ,…,x n), có thể được biểu diễn dưới dạng f(x 1 ,x 2 ,…,x n)=c 0 ∆c 1 x 1 ∆c 2 x 2 ∆… ∆ c n x n, trong đó c 0, c 1, c 2 ...các hệ số có thể nhận giá trị 0 hoặc 1.
5. Lớp học hàm đơn điệu. Trên tập các tập số 0 và số 1 Bn =((x 1 ,x 2 ,…,x n):x i œ(0,1),i=1,2,…,n) ta đưa ra một thứ tự từng phần như sau:
(Một 1 ,a 2 ,...,a n)§( b 1 ,b 2 ,...,b n) nếu và chỉ nếu Một 1 § b 1 , một 2 § b 2,…,a N § b N. Hàm f(x 1, x 2,..., x n) được gọi là đơn điệu nếu với hai phần tử bất kỳ thuộc B n sao cho
(Một 1 ,a 2 ,...,a n)§( b 1 ,b 2 ,...,b n) suy ra f( Một 1 ,a 2 ,...,a n)§f( b 1 ,b 2 ,...,b n).
Một hệ thống S của các hàm Boolean, sự chồng chất của chúng có thể biểu diễn bất kỳ hàm Boolean nào, được gọi là hoàn thiện về mặt chức năng . Họ nói nó có tác dụng hệ thống hoàn chỉnh Dạng hàm Boolean cơ sở trong không gian logic. Cơ sở S được gọi là tối thiểu , nếu việc loại bỏ bất kỳ chức năng nào khỏi nó sẽ khiến hệ thống này trở nên không hoàn chỉnh.
Tiêu chí đầy đủ (Định lý Post) . Một hệ S gồm các hàm Boolean là hoàn chỉnh khi và chỉ nếu nó bao gồm ít nhất một hàm: hằng số không bảo toàn 0, hằng số không bảo toàn 1, không tự đối ngẫu, phi tuyến tính và không đơn điệu.
Bảng 1.7 cho thấy các thuộc tính mà các hàm Boolean cơ bản có (ký hiệu * biểu thị thuộc tính mà hàm đã cho có).
Sử dụng định lý Post và bảng 1.7, bạn có thể xây dựng cơ sở từ các hàm cơ bản theo quy tắc tiếp theo. Bằng cách chọn bất kỳ hàm Boolean cơ bản nào và bổ sung nó, nếu cần, với các hàm khác sao cho tất cả chúng cùng thỏa mãn định lý về tính đầy đủ của hàm. Thông qua các chức năng của cơ sở này chúng ta có thể biểu diễn Tất cả các hàm Boolean khác.
Hãy xây dựng một số cơ sở được sử dụng thường xuyên trong các ứng dụng.
Bảng 1.7
| Tên | chỉ định | Không thể lưu trữ hằng số |
Không thể lưu trữ hằng số |
Samodvoys hiệu lực |
||
| Const.0 | 0 | * | * | |||
| Const.1 | 1 | * | * | |||
| Tiêu cực | Ÿ | * | * | * | ||
| Kongyun. | & | * | * | |||
| Phân ly. | ¤ | * | * | |||
| Ngụ ý. | Ø | * | * | * | * | |
| Tương đương. | ~ | * | * | * | ||
| Tổng theo mod_2 | ∆ | * | * | * | ||
| | | * | * | * | * | * | |
| Mũi tên của Pierce | ∞ | * | * | * | * | * |
1. Hệ hàm số S1=(Ÿ,⁄,¤) tạo thành một cơ sở. Để chuyển một hàm Boolean về dạng chỉ chứa các liên kết từ cơ sở S1, các giá trị tương đương sau đây có thể hữu ích: x → y = x ∨ y , x ↔ y = (x ∨ y)(x ∨ y) , x ⊕ y = xy ∨ xy , xy = x ∨ y , x ↓ y = x & y .
2. Hệ S2=(Ÿ,&) tạo thành một cơ sở. Hàm tùy ýđầu tiên có thể được rút gọn thành dạng chứa các liên kết từ S1 và sau đó
sử dụng quan hệ x ∨ y = x ⋅ y.
3. Hệ S3=(Ÿ,¤) tạo thành một cơ sở. Một hàm tùy ý trước tiên có thể được rút gọn về dạng chứa các liên kết từ S1 và sau đó
sử dụng quan hệ x ⋅ y = x ∨ y.
4. Hệ S4=(1,&,∆) tạo thành một cơ sở. Một hàm tùy ý trước tiên có thể được rút gọn về dạng chứa các liên kết từ S1, sau đó sử dụng các quan hệ x = 1⊕ x, x ∨ y = x ⊕ y ⊕ x ⋅ y.
5. Hệ S5=(|) tạo thành một cơ sở. Một hàm tùy ý trước tiên có thể được rút gọn về dạng chứa các liên kết từ S2, sau đó sử dụng các quan hệ x ⋅ y = x y , x = xx .
6. Hệ S6=(∞) tạo thành một cơ sở. Một hàm tùy ý trước tiên có thể được rút gọn thành dạng chứa các kết nối từ S3 và sau đó
sử dụng quan hệ x ∨ y = x ↓ y, x = x ↓ x.
7. Hệ S7=(Ø,0) tạo thành một cơ sở.
Ví dụ 1.7.1. Viết hàm x¨(y∆z) trên cơ sở S1=(Ÿ,⁄,¤). x ↔ (y ⊕ z) = (x ∨ y ⊕ z) ⋅(x ∨ (y ⊕ z)) = (x ∨ y ⋅ z ∨ y ⋅ z) ⋅(x ∨ y ⋅ z ∨ y ⋅ z)
Chương II. Đại số Boole.
Tập hợp tất cả các boolean trong cơ sở S1=( ÿ, &, ⁄} hình thức đại số Boole. Do đó, trong đại số Boolean, tất cả các công thức đều được viết bằng ba từ nối: Ÿ, &, ¤. Chúng ta đã xem xét một phần các tính chất của đại số này trong Chương I (ví dụ, xem các tương đương cơ bản). Chương này đề cập đến các thuộc tính cụ thể của đại số Boolean và do đó trong suốt chương này chúng ta sẽ chỉ đề cập đến ba hàm: ÿ, &, ⁄.
§2.1. Các hình thức bình thường.
Các dạng thông thường là một cách viết công thức rõ ràng về mặt cú pháp để thực hiện hàm đã cho.
Nếu x là biến logic và σœ(0,1) thì biểu thức x σ = x if if σσ == 10 hoặc x σ = 10 if if x x =≠σσ , x được gọi là một chữ cái . Các chữ x và Ÿx được gọi là trái nghĩa. Liên hợp rời rạc gọi là sự tách rời của các chữ cái. Ví dụ: các công thức x ⋅ y ⋅ z và x ⋅ y ⋅ x ⋅ x là các liên kết, các công thức x ∨ y ∨ z và x ∨ y ∨ x là các liên kết và công thức z vừa là liên kết vừa là liên kết.
Dạng chuẩn phân biệt (DNF)được gọi là sự phân tách của một số hữu hạn các liên kết .
Dạng thông thường liên hợp (CNF)được gọi là sự kết hợp của một số hữu hạn các mệnh đề .
Đơn giản hơn: DNF là tổng của các tích, còn CNF là tích của các tổng logic.
1. xÿy¤yÿz¤x là DNF (tổng sản phẩm).
2. (x ∨ y ∨ z)⋅(x ∨ y)⋅z là CNF (tích của các tổng).
3. x ∨ y ∨ z ∨ w là DNF và CNF (đồng thời).
4. x ⋅ y ⋅ z ⋅ w là DNF và CNF (đồng thời).
5. (x¤x¤y)·(y¤z¤x)·z là CNF.
6. x⋅y⋅z và x⋅y⋅x⋅x là DNF.
7. x ⋅(x ∨ yz)⋅ x ⋅ y ⋅ z không phải là dạng chuẩn (không phải DNF hoặc CNF).
Giả sử hàm f được viết trên cơ sở S1. Hàm này được chuyển về dạng bình thường như sau:
1) chúng tôi sử dụng định luật De Morgan để chuyển đổi công thức sang dạng trong đó dấu âm chỉ liên quan đến các biến riêng lẻ;
2) áp dụng quy tắc loại bỏ số âm kép: ŸŸx=x;
H1&(H2¤H3)=(H1&H2)¤(H1&H3) , và luật phân phối thứ hai để giảm xuống CNF. H1¤(H2&H3)=(H1¤H2)&(H1¤H3).
Bất kỳ hàm Boolean nào cũng có thể có vô số cách biểu diễn DNF và CNF. Ví dụ, bằng cách sử dụng bổ sung các định luật nghịch đảo và các quy tắc hoạt động với hằng số, có thể đảm bảo rằng trong mỗi liên kết hoặc rời rạc riêng lẻ, bất kỳ biến nào cũng xuất hiện không quá một lần (chính nó hoặc phủ định của nó).
Ví dụ 2.1.1.Để giảm xuống DNF, chúng tôi sử dụng luật phân phối thứ nhất.
x⋅y⋅x⋅y⋅z⋅(y∨z)=x⋅y⋅(x∨y∨z)⋅(y∨z)=(x⋅y⋅x∨x⋅y⋅y∨x⋅y ⋅z)⋅(y∨z)= là CNF
= (0∨ x⋅y∨ x⋅y⋅z)⋅(y∨ z) = (x⋅y∨ x⋅y⋅z)⋅(y∨ z) = - đây là một CNF khác
X ⋅ y⋅у ∨ x ⋅ y⋅z⋅ y ∨ x ⋅y⋅z ∨ x ⋅ y⋅z⋅z = 0∨ 0∨ x ⋅y⋅z ∨ x ⋅ y⋅z =
X ⋅ y ⋅ z ∨ x ⋅ y ⋅ z là DNF
Ví dụ 2.1.2. Để quy về CNF cần sử dụng định luật phân phối thứ hai.
x ∨ y ⋅ x ⋅ y ∨ z = x ∨ y ⋅ (x ⋅ y ⋅ z) = x ∨ y ⋅ (x ∨ y) ⋅ z =
X∨y⋅z⋅(x∨y)=(x∨y⋅z)⋅(x∨x∨y)=(x∨y)⋅(x∨z)⋅(1∨y)=
= (x ∨ y) ⋅ (x ∨ z) là CNF
§2.2. Hình thức bình thường hoàn hảo.
Nếu trong mỗi số hạng của dạng chuẩn tắc, tất cả các biến đều được biểu diễn (chính chúng hoặc phủ định của chúng), và trong mỗi liên kết hoặc phân tách riêng biệt, bất kỳ biến nào cũng xuất hiện đúng một lần (chính nó hoặc phủ định của nó), thì dạng này được gọi là dạng chuẩn hoàn hảo (SDNF hoặc SCNF). Ví dụ: Cho hàm ba biến f(x,y,z).
1. x ⋅ y ⋅ z ∨ x ⋅ y ⋅ z ∨ x ⋅ y ⋅ z là một DNF hoàn hảo.
2. (x ∨ y ∨ z)⋅(x ∨ y ∨ z)⋅(x ∨ y ∨ z) là một CNF hoàn hảo.
3. (x ∨ y) ⋅ (x ∨ z) không phải là một CNF hoàn hảo, bởi vì ví dụ: tổng đầu tiên không bao gồm biến z.
4. xÿyÿz là một DNF hoàn hảo. Định lý 2.2.1.
1. Bất kỳ hàm Boolean nào không bằng 0 đều chỉ có một SDNF, tùy theo vị trí của các số hạng.
2. Bất kỳ hàm Boolean nào không giống 1 đều chỉ có một SCNF, tùy theo vị trí của các số hạng.
Ta sẽ chứng minh định lý một cách xây dựng như là lời giải của bài toán sau: Sử dụng bảng chân lý này để xây dựng SDNF.
Hãy xem xét giải pháp bằng cách sử dụng ví dụ về hàm f(x,y,z) cho trong bảng (Bảng 2.2) với n=3.
Ví dụ 2.2.1. Sử dụng bảng chân lý này (Bảng 2.2), xây dựng SDNF.
Bảng 2.2
| x | y | z | nền tảng liên từ |
f(x,y,z) |
| 0 | 0 | 0 | x ⋅ y ⋅ z | 0 |
| 0 | 0 | 1 | x ⋅ y ⋅ z | 1 |
| 0 | 1 | 0 | x ⋅ y ⋅ z | 1 |
| 0 | 1 | 1 | x ⋅ y ⋅ z | 0 |
| 1 | 0 | 0 | x ⋅ y ⋅ z | 0 |
| 1 | 0 | 1 | x ⋅ y ⋅ z | 1 |
| 1 | 1 | 0 | x ⋅ y ⋅ z | 1 |
| 1 | 1 | 1 | x ⋅ y ⋅ z | 1 |
Liên từ cơ bản (hoặc thành phần_1) có trong bảng tương ứng với một tập hợp cụ thể các số 0 và các số lấy biến x, y, z. Các khu vực bầu cử đang được xây dựng_ 1 theo quy tắc sau: một biến được đưa vào chính tích nếu nó nhận giá trị 1 trên một tập hợp cho trước, nếu không thì phủ định của nó sẽ được đưa vào tích. Vì vậy, ví dụ, trên tập (0,0,1) các biến x,y lấy giá trị 0 và do đó các phủ định của chúng được đưa vào tích, còn biến z lấy giá trị 1 và do đó được đưa vào chính tích . Đối với một tập hợp nhất định (0,0,1), thành phần_1 bằng x ⋅ y ⋅ z .
Rõ ràng, liên hợp x ⋅ y ⋅ z chỉ bằng 1 trên tập hợp
(0,0,0) và x ⋅ y ⋅ z là 1 trên tập hợp (0,0,1), v.v. (xem bảng). Tiếp theo, lưu ý rằng phân của hai liên từ cơ bản bằng 1 trên đúng hai tập hợp tương ứng với các liên từ cơ bản này. Ví dụ: hàm x ⋅ y ⋅ z¤x ⋅ y ⋅ z chỉ bằng 1 trên hai bộ - (0,0,0) và (0,0,1), và trên tất cả các bộ khác, nó bằng 0. Tương tự, phân của ba liên từ cơ bản bằng 1 trên đúng ba tập hợp tương ứng với các liên từ cơ bản này, v.v.
Cái đó. chúng tôi nhận được quy tắc: để xây dựng SDNF bạn nên chọn các hàng trong đó hàm bằng 1, sau đó lấy phần tách của các liên từ chính tương ứng, chúng ta thu được SDNF mong muốn. Vì vậy, trong ví dụ của chúng ta, chúng ta có x ⋅ y ⋅ z ¤ x ⋅ y ⋅ z ¤ x ⋅ y ⋅ z ¤ x ⋅ y ⋅ z ¤ x ⋅ y ⋅ z .
Nhiệm vụ. Sử dụng bảng chân lý này để xây dựng SCNF.
Hiến pháp_0Đối với tập hợp các số 0 và số 1 (lấy các biến x,y,z) được xây dựng như sau: biến được đưa vào chính phép phân biệt nếu nó nhận giá trị trên tập hợp này 0 , nếu không thì công bao gồm sự phủ định của nó.
Quy tắc xây dựng SKNF: bạn nên chọn những dòng có hàm bằng 0 , sau đó lấy kết hợp của các thành phần tương ứng_0. Kết quả sẽ là SCNF mong muốn. Vì vậy, trong ví dụ của chúng ta, chúng ta có f = (x ∨ y∨ z)⋅(x ∨ y∨ z)⋅(x ∨ y∨ z) .
Bình luận. Để xây dựng một hàm CNF hoàn hảo f, việc xây dựng một DNF hoàn hảo cho hàm f là đủ, sau đó
Chúng ta hãy xây dựng SCNF cho ví dụ của chúng ta dựa trên nhận xét. 1. Chúng tôi xây dựng SDNF để phủ định.
x ⋅ y ⋅ z ∨ x ⋅ y ⋅ z ∨ x ⋅ y ⋅ z
2. Chúng ta sử dụng định luật de Morgan f = f = x ⋅ y⋅ z ∨ x ⋅ y⋅z ∨ x ⋅ y⋅ z = x ⋅ y⋅ z&x ⋅ y⋅z&x ⋅ y⋅ z == (x ∨ y ∨ z ) ⋅(x ∨ y ∨ z)⋅(x ∨ y ∨ z) .
Phương pháp tìm SDNF (và SCNF) được mô tả bằng bảng chân lý thường tốn nhiều công sức hơn thuật toán sau.
1. Để tìm SDNF công thức nàyĐầu tiên chúng tôi giảm xuống DNF.
2. Nếu kết hợp K nào đó (tức là K là tích của một số biến nhất định hoặc phủ định của chúng) không bao gồm biến y, thì chúng ta thay thế kết hợp này bằng công thức tương đương K&(y ∨ y) và áp dụng luật phân phối, chúng tôi trình bày công thức kết quả cho DNF; nếu thiếu một số biến, thì đối với mỗi biến đó, chúng ta thêm công thức tương ứng có dạng (y ∨ y) vào liên hợp.
3. Nếu DNF thu được chứa một số thành phần giống hệt nhau của đơn vị thì chúng ta chỉ để lại một trong số chúng. Kết quả là SDNF.
Bình luận: Để xây dựng một SCNF thành một mệnh đề không chứa một biến Tại chúng ta thêm một công thức có dạng y⋅ y, tức là Chúng tôi thay thế sự phân biệt này bằng công thức tương đương D ∨ y⋅ y và áp dụng định luật phân phối thứ 2.
Ví dụ 2. 2. 2. Xây dựng SDNF cho hàm f bằng cách sử dụng các phép biến đổi tương đương.
f = x ∨ y ⋅ z = x ⋅ (y ∨ y) ⋅ (z ∨ z) ∨ y ⋅ z ⋅ (x ∨ x) == x ⋅ y ⋅ z x ⋅ y ⋅ z x ⋅ y ⋅ z x ⋅ y ⋅ z y ⋅ z ⋅ x y ⋅ z ⋅ x =
RÚT LẠI.
Việc tính toán SDNF không chỉ mang tính lý thuyết mà còn có tầm quan trọng thực tiễn rất lớn. Ví dụ, ở nhiều chương trình hiện đại với giao diện đồ họa để soạn thảo phức tạp điều kiện logic một dạng trực quan dưới dạng bảng được sử dụng: các điều kiện được viết trong các ô và các ô của một cột được coi là được kết nối bằng một liên kết và các cột được coi là được kết nối bằng một sự phân tách, nghĩa là chúng tạo thành DNF (hoặc ngược lại, trong trường hợp này là thu được CNF). Đặc biệt, đây là cách thiết kế giao diện đồ họa QBE (Query-byExample), được sử dụng để hình thành các điều kiện logic khi truy vấn DBMS.
Thuật toán 2.2.1. Xây dựng SDNF
Cổng vào: vectơ X: mảng chuỗi - mã định danh biến, ma trận V: mảng 0..1 của tất cả các bộ giá trị biến khác nhau,
vector F: mảng 0..1 giá trị hàm tương ứng.
Ra: một chuỗi các ký hiệu tạo thành bản ghi công thức SDNF cho một hàm nhất định.
f:= SAI(dấu hiệu của sự có mặt của toán hạng bên trái của phép tách) vì Tôi từ 1ĐẾN 2 n LÀM
nếu như F[i] = 1 thì nếu f sau đó
năng suất"¤" (thêm dấu phân cách vào công thức; toán tử năng suất m in
ký hiệu m) khác f:= ĐÚNG VẬY
kết thúc nếu g:= SAI(dấu hiệu của sự có mặt của toán hạng bên trái của liên từ) vì j từ 1ĐẾN N làm nếu g sau đó
năng suất"⁄" (thêm dấu kết hợp vào công thức)
khác g: = đúng
kết thúc nếu nếu V (thêm mã định danh biến vào công thức
§2.3. Giảm thiểu DNF bằng phương pháp Quine.
Mỗi công thức có số cuối cùng sự xuất hiện của các biến. Sự xuất hiện của một biến đề cập đến vị trí mà biến đó chiếm giữ trong công thức. Nhiệm vụ là tìm, đối với một hàm Boolean f cho trước, một DNF đại diện cho hàm này và có số nhỏ nhất sự xuất hiện của các biến.
Nếu x là một biến logic và σœ(0,1) thì biểu thức x σ =xx if if σσ== 10 .
gọi điện thư . Liên hợp gọi là sự kết hợp của các chữ cái. Ví dụ: các công thức x ⋅ y ⋅ z và x ⋅ y ⋅ x ⋅ x là liên từ . Tích cơ bản là một kết hợp trong đó bất kỳ biến nào cũng xuất hiện không quá một lần (chính nó hoặc phủ định của nó).
Công thức f1 được gọi là người có liên quan công thức f , nếu f1 là tích cơ bản và f 1 ⁄ f = f 1, tức là nghĩa là, đối với các hàm tương ứng với các công thức, bất đẳng thức f 1 § f đúng. Hàm ý f1 của công thức f được gọi là đơn giản , nếu, sau khi loại bỏ bất kỳ chữ cái nào từ f1, không thu được công thức có liên quan đến công thức f.
Ví dụ 2.3.1 . Hãy tìm tất cả các hàm ý và hàm ý đơn giản cho công thức f=xØy . Có tổng cộng 8 sản phẩm cơ bản có biến X Và bạn. Dưới đây, để rõ ràng, bảng chân lý của họ được đưa ra:
| x | y | xØy | x ⋅ y | x ⋅ y | x ⋅ y | x ⋅ y | x | y | x | y | |||||||
| 0 | 0 | 1 | 1 | 0 | 0 | 0 | 1 | 1 | 0 | 0 | |||||||
| 0 | 1 | 1 | 0 | 1 | 0 | 0 | 1 | 0 | 0 | 1 | |||||||
| 1 | 0 | 0 | 0 | 0 | 1 | 0 | 0 | 1 | 1 | 0 | |||||||
| 1 | 1 | 1 | 0 | 0 | 0 | 1 | 0 | 0 | 1 | 1 | |||||||
Từ bảng chân trị ta kết luận rằng các công thức x ⋅ y , x ⋅ y , x ⋅ y , x ,y - tất cả các hàm ý của công thức xØy, và trong số các hàm ý này thì các công thức x và y đều đơn giản (ví dụ: công thức x ⋅ y không phải là hàm ý đơn giản, vì khi loại bỏ chữ y, chúng ta thu được hàm ý x).
DNF viết tắtđược gọi là sự phân tách của tất cả các hàm ý nguyên tố của một công thức (hàm) nhất định .
Định lý 2.3.1. Bất kỳ hàm Boolean nào không phải là hằng số 0 đều có thể được biểu diễn dưới dạng DNF tốc ký.
Trong ví dụ 2.3.1, hàm tương ứng với công thức xØy được biểu diễn bằng công thức x ∨ y, viết tắt là DNF.
DNF giảm có thể chứa các hàm ý bổ sung, việc loại bỏ chúng không làm thay đổi bảng chân lý. Nếu chúng tôi loại bỏ tất cả các yếu tố liên quan không cần thiết khỏi DNF đã giảm, chúng tôi sẽ thu được DNF được gọi là ngõ cụt.
Lưu ý rằng việc biểu diễn hàm dưới dạng DNF ngõ cụt trong trường hợp chung mơ hồ. Chọn từ tất cả các dạng ngõ cụt, dạng có số lần xuất hiện ít nhất của các biến sẽ cho DNF tối thiểu (MDNF).
Hãy xem xét phương pháp Quina,để tìm MDNF đại diện cho một hàm Boolean nhất định. Chúng tôi xác định ba hoạt động sau:
1. hoạt động liên kết đầy đủ : f ⋅ x ∨ f ⋅ x = f ⋅ (x ∨ x) = f ;
2. hoạt động dán một phần:
f ⋅ x ∨ f ⋅ x = f ⋅ (x ∨ x) ∨ f ⋅ x ∨ f ⋅ x = f ∨ f ⋅ x ∨ f ⋅ x ;
3. hoạt động hấp thụ sơ cấp f ⋅ x σ ∨ f = f , σ ∈ (0,1) .
Định lý 2.3.2(Định lý Quine). Nếu, dựa trên hàm SDNF, chúng ta thực hiện tất cả các hoạt động có thể có của quá trình dán không hoàn chỉnh và sau đó là sự hấp thụ cơ bản, thì kết quả sẽ là DNF giảm, tức là sự tách rời của tất cả các chất liên quan đơn giản.
Ví dụ 2.3.2. Giả sử hàm f(x,y,z) được cho bởi một DNF hoàn hảo f = x ⋅ y⋅ z ∨ x ⋅ y⋅z ∨ x ⋅ y⋅z ∨ x ⋅ y⋅ z ∨ x ⋅ y⋅z . Sau đó, thực hiện theo hai giai đoạn tất cả các hoạt động có thể có của việc dán không hoàn chỉnh và sau đó là sự hấp thụ cơ bản, chúng ta có
f 
Do đó, DNF rút gọn của hàm f là công thức y¤x·z.
Trong thực tế, khi thực hiện các thao tác dán không hoàn chỉnh ở mỗi giai đoạn, không thể viết các thuật ngữ liên quan đến các thao tác này mà chỉ viết kết quả của tất cả các thao tác dán và liên kết hoàn chỉnh có thể không liên quan đến bất kỳ thao tác dán nào.
Ví dụ 2. 3. 3. Giả sử hàm f(x,y,z) được cho bởi một DNF hoàn hảo f = x ⋅ y ⋅ z ∨ x ⋅ y ⋅ z ∨ x ⋅ y ⋅ z ∨ x ⋅ y ⋅ z .
Sau đó, thực hiện các thao tác dán và hấp thụ sơ cấp, chúng ta có
f = x ⋅ y ⋅(z ∨ z) ∨ y ⋅ z ⋅(x ∨ x) ∨ x ⋅ z ⋅(y ∨ y) = x ⋅ y ∨ y ⋅ z ∨ x ⋅ z
Để thu được DNF tối thiểu từ DNF đã giảm, ma trận Quine được sử dụng , được xây dựng như sau. Các tiêu đề cột của bảng chứa các thành phần của đơn vị DNF hoàn hảo và các tiêu đề hàng chứa các hàm ý đơn giản từ DNF được viết tắt thu được. Trong bảng, dấu hoa thị đánh dấu các giao điểm của hàng và cột mà liên kết trong tiêu đề hàng được bao gồm trong thành phần của đơn vị, là tiêu đề cột.
Ví dụ 2.3.3. Ma trận Quine có dạng
Trong DNF ngõ cụt, số lượng hàm ẩn đơn giản tối thiểu được chọn, sự phân tách của chúng bảo toàn tất cả các thành phần của đơn vị, tức là mỗi cột của ma trận Quine chứa một dấu hoa thị tại giao điểm với hàng tương ứng với một trong các những người liên quan được lựa chọn. DNF ngõ cụt có số lần xuất hiện biến nhỏ nhất được chọn làm DNF tối thiểu.
Trong Ví dụ 2.3.3, sử dụng ma trận Quine, chúng ta thấy DNF tối thiểu của một hàm đã cho là x ⋅ y ¤ x ⋅ z.
Bình luận.
sử dụng f = f và định luật De Morgan.
§ 2.4. Bản đồ Carnot.
Một cách khác để có được các công thức hàm ý đơn giản với một số ít biến số (và do đó tìm được DNF tối thiểu) là dựa trên việc sử dụng cái gọi là bản đồ Carnot.
Bản đồ Carnot là loại đặc biệt một bảng đơn giản hóa quá trình tìm các dạng tối thiểu và được sử dụng thành công khi số lượng biến không vượt quá sáu. Ánh xạ Karnaugh cho các hàm phụ thuộc vào n biến là một hình chữ nhật được chia thành 2 n ô. Mỗi ô của sơ đồ được liên kết với một tập nhị phân n chiều. Các giá trị của hàm f đã cho từ bảng chân lý được nhập vào các ô vuông cần thiết, nhưng nếu ô tương ứng với 0 thì ô đó thường trống.
Trong bảng 2.4.1. hiển thị ví dụ về đánh dấu bản đồ Karnaugh cho hàm phụ thuộc vào ba biến. Bốn ô dưới cùng của bản đồ tương ứng với các tập nhị phân trong đó biến x lấy giá trị 1, bốn ô trên cùng tương ứng với các tập hợp trong đó biến x nhận giá trị 0. Bốn ô tạo nên nửa bên phải của bản đồ tương ứng với các tập hợp trong đó biến y; lấy giá trị 1, v.v. Trong bảng 2.4.2. Việc đánh dấu bản đồ Karnaugh cho n=4 biến được hiển thị.
Để xây dựng một DNF tối thiểu, chúng tôi thực hiện quy trình dán "1". Các giá trị "1" dính vào nhau tương ứng với các ô lân cận, tức là. các ô chỉ khác nhau về giá trị của một biến (bằng biểu diễn đồ họa tách biệt theo chiều dọc hoặc đường ngang có tính đến sự gần gũi của các ô cực đối diện).
Quá trình dán số “1” bao gồm việc kết hợp các ô đơn lẻ của bản đồ Karnaugh thành các nhóm và phải tuân theo các quy tắc sau;
1. Số lượng ô trong một nhóm phải được biểu thị bằng bội số của 2, tức là. 2 m trong đó m=0,1,2,...
2. Mỗi ô thuộc một nhóm 2 m ô phải có m ô lân cận trong nhóm.
3. Mỗi ô phải thuộc ít nhất một nhóm.
4. Mỗi nhóm nên bao gồm số lượng tối đa tế bào, tức là không có nhóm nào được chứa trong một nhóm khác.
5. Số lượng nhóm nên ở mức tối thiểu.
Đọc chức năng f theo nhóm dán được thực hiện như sau: các biến tiết kiệm cùng giá trị trong các ô của nhóm dán, chúng kết hợp với nhau và các giá trị 1 tương ứng với chính các biến và giá trị 0 tương ứng với các phủ định của chúng.
Chúng tôi trình bày các mẫu giúp xây dựng phạm vi phủ sóng 1 (chúng tôi coi các biến là giống nhau, nhưng chúng tôi sẽ không viết chúng). Để đơn giản hóa ký hiệu, chúng ta sẽ không đánh dấu các biến, mặc dù chúng ta sẽ giữ nguyên tên gọi của chúng như trong bảng 2.4.1, 2.4.2.
| 1 | 1 |
| 1 | 1 |
| F=Ÿy&x | |
| 1 | 1 |
| 1 | 1 | 1 | 1 | 1 | 1 |
| 1 | 1 |
| 1 | 1 | 1 |
| 1 |
F=Ÿz&Ÿy f=Ÿx&y
| 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 |
| 1 | 1 | 1 | 1 | ||||
| 1 | 1 | 1 | 1 | ||||
| 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 |
F=Ÿx&z f=y&w F=Ÿx&Ÿy
| 1 | 1 | 1 | 1 | 1 | 1 |
| 1 | 1 | 1 | 1 | ||
| 1 | 1 |
F=Ÿy&Ÿw f=Ÿy&Ÿz F=Ÿz&Ÿx
| 1 | 1 | 1 | 1 | 1 | 1 |
| 1 | 1 | ||||
| 1 | 1 | 1 | 1 |
F=y&z&w f=Ÿy&Ÿz&Ÿw F=x&y&Ÿz
| 1 | ||
| 1 | ||
| 1 | 1 | 1 |
| 1 |
Ví dụ 2.4.1. Xây dựng MDNF.
Đầu tiên chúng ta xem có lớp phủ nào không_ 1 trong số 16 ô bao phủ ít nhất một ô không che phủ 1. Không có lớp phủ nào như vậy. Chúng tôi chuyển sang lớp phủ gồm 8 ô. Hãy xem liệu có 1 trong 8 ô che phủ ít nhất một ô không che 1. Không có bìa nào như vậy. Chúng tôi chuyển sang lớp phủ của 4 ô. Hãy xem có tấm che nào trong 4 ô che ít nhất một ô 1 không che. Có hai tấm che như vậy. Chúng tôi chuyển sang lớp phủ của 2 ô. Chỉ có một lớp phủ như vậy. Vì vậy, tất cả 1 đều được bảo hiểm. Tiếp theo, hãy xem liệu chúng ta có thể loại bỏ một số lớp phủ để tất cả các thiết bị vẫn được che phủ hay không. Cuối cùng, chúng tôi viết ra MDNF: f =x⋅z∨y⋅w∨y⋅z⋅w.
Bình luận.Để xây dựng CNF tối thiểu của hàm f, việc xây dựng DNF tối thiểu cho hàm f là đủ, sau đó
sử dụng f = f và định luật De Morgan.
Chương III. Đại số Zhegalkin.
Tập hợp các hàm Boolean được xác định trong cơ sở Zhegalkin S4=(∆,&,1) được gọi là đại số Zhegalkin.
Thuộc tính cơ bản.
1. tính giao hoán
H1∆H2=H2∆H1, H1&H2=H2
2. tính kết hợp
H1∆(H2∆H3)=(H1∆H2)∆H3, H1&(H2&H3)=(H1&H2)
3. tính phân phối
H1&(H2∆H3)=(H1&H2)∆(H1&H3);
4. tính chất của các hằng số H&1=H, H&0=0, H∆0=H;
5. H∆H=0, H&H=H.
Phát biểu 3.1.1. Tất cả các hàm Boolean khác có thể được biểu diễn thông qua các phép toán của đại số Zhegalkin:
Ÿx=1∆x, x¤y=x∆y∆xy, x~y=1∆x∆y, xØy=1∆x∆xy, x∞y=1∆x∆y∆xy, x|y= 1∆xy.
Sự định nghĩa.Đa thức Zhegalkin (đa thức modulo 2) của n biến x 1 ,x 2 ,…,x n là biểu thức có dạng c0∆с1x1∆c2x2∆…∆cnxn∆c12x1x2∆…∆c12…nx1x2…xn, trong đó các hằng số có k có thể nhận giá trị 0 hoặc 1.
Nếu đa thức Zhegalkin không chứa tích của các biến riêng lẻ thì nó được gọi là tuyến tính (hàm tuyến tính).
Ví dụ: f=x∆yz∆xyz và f1=1∆x∆y∆z là các đa thức, hàm thứ hai là hàm tuyến tính.
Định lý 3.1.1. Mỗi hàm Boolean được biểu diễn dưới dạng đa thức Zhegalkin theo một cách riêng.
Chúng ta hãy trình bày các phương pháp chính để xây dựng đa thức Zhegalkin từ một hàm đã cho.
1. Phương pháp hệ số không chắc chắn. Giả sử P(x 1 ,x 2 ,…,x n) là đa thức Zhegalkin mong muốn thực hiện hàm f(x 1 ,x 2 ,…,xn). Hãy viết nó dưới dạng
P= c 0 ∆c 1 x 1 ∆c 2 x 2 ∆…∆c n x n ∆c 12 x 1 x 2 ∆…∆c12… n x 1 x 2 …x n .
Hãy tìm các hệ số với k. Để làm được điều này, chúng ta gán tuần tự các giá trị x 1 , x 2 ,…, x n từ mỗi hàng của bảng chân lý. Kết quả là ta thu được hệ gồm 2 n phương trình với 2 n ẩn số, có giải pháp duy nhất. Giải xong ta tìm được các hệ số của đa thức P(x 1 ,x 2 ,…,xn).
2. Một phương pháp dựa trên việc chuyển đổi các công thức trên một tập hợp các từ nối ( ÿ,&}. Xây dựng công thức Ф nhất định trên tập hợp các liên kết (Ÿ,&), nhận ra hàm f(x 1 ,x 2 ,…,x n). Sau đó thay thế các công thức con ở mọi nơi của dạng A bằng A∆1, mở dấu ngoặc bằng cách sử dụng luật phân phối (xem thuộc tính 3), sau đó áp dụng thuộc tính 4 và 5.
Ví dụ 3.1.1. Xây dựng đa thức Zhegalkin cho hàm f(x,y)=xØy.
Giải pháp. 1 . (phương pháp hệ số không xác định). Hãy viết đa thức cần tìm dưới dạng
P(x,y)= c 0 ∆c 1 x∆c 2 y∆c 12 xy Sử dụng bảng chân lý
| x | 0 | 0 | 1 | 1 |
| y | 0 | 1 | 0 | 1 |
| xØy | 1 | 1 | 0 | 1 |
chúng ta thấy rằng f(0,0)=P(0,0)= c 0 =1, f(0,1)=P(0,1)= c 0 ∆ c 2 =1, f(1,0) =P(1,0)= c 0 ∆ c 1 =0, f(1,1)=P(1,1)= c 0 ∆c 1 ∆c 2 ∆c 12 =1
Từ đó chúng ta luôn tìm thấy, c 0 =1, c 1 =1, c 2 =0, c 12 =1. Do đó xØy=1∆x∆xy (so sánh với câu 3.1).
2.(Phương pháp chuyển đổi công thức.) Chúng tôi có
x → y = x ∨ y = x ⋅ y = (x ⋅ (y ⊕ 1)) ⊕ 1 = 1 ⊕ x ⊕ x ⋅ y .
Lưu ý rằng ưu điểm của đại số Zhegalkin (so với các đại số khác) là tính số học logic, giúp thực hiện các phép biến đổi các hàm Boolean khá đơn giản. Nhược điểm của nó so với đại số Boolean là sự cồng kềnh của các công thức.
Chương IV. Tuyên bố. Vị ngữ.
§4.1. Tuyên bố.
Khi xây dựng đại số logic, người ta đã sử dụng cách tiếp cận chức năng. Tuy nhiên, có thể xây dựng đại số này một cách xây dựng. Đầu tiên, xác định đối tượng nghiên cứu (các câu lệnh), giới thiệu các thao tác trên các đối tượng này và nghiên cứu tính chất của chúng. Hãy để chúng tôi đưa ra định nghĩa chính thức.
Bằng cách nói Chúng ta hãy gọi một câu khai báo liên quan đến câu mà người ta có thể nói rõ ràng liệu nó đúng (giá trị I hoặc 1) hay sai (giá trị L hoặc 0) tại một thời điểm cụ thể. Ví dụ: “5 là số nguyên tố”, “Nhấn phím Esc”, v.v. Sử dụng các từ nối “not”, “and”, “or”, “if,... then”, “if và only if” (tương ứng với các phép toán “Ÿ”, “&”, “¤”, “Ø” , “~” » tương ứng), có thể xây dựng các câu (câu) phức tạp hơn. Đây là cách đại số mệnh đề được xây dựng.
Để đơn giản hóa việc ghi lại các câu lệnh phức tạp, người ta đưa ra độ ưu tiên của các từ nối: “Ÿ”, “&”, “¤”, “Ø”, “~”, giúp loại bỏ các dấu ngoặc không cần thiết.
Chúng ta gọi các phát biểu đơn giản là các biến mệnh đề.
Hãy giới thiệu khái niệm về công thức.
1. Biến mệnh đề là công thức.
2. Nếu A, B là công thức thì các biểu thức ŸA, A⁄B, A¤B, AØB, A~B là công thức.
3. Công thức chỉ là những biểu thức được xây dựng theo khoản 1 và 2.
Công thức lấy giá trị AND cho mọi giá trị của biến mệnh đề được gọi là tautology (hoặc nói chung là hợp lệ), và một công thức lấy giá trị A cho mọi giá trị của biến mệnh đề được gọi là mâu thuẫn (hoặc không thể)
Việc mô tả các tính chất của đại số mệnh đề cũng tương tự như mô tả các hàm tương ứng trong đại số Boole và chúng ta bỏ qua chúng.
§4.2. Vị ngữ. Các phép toán logic trên vị ngữ.
Chủ đề nghiên cứu của chương này sẽ là các vị từ - ánh xạ các tập hợp tùy ý vào một tập hợp các mệnh đề. Trên thực tế, chúng tôi đang thực hiện chuyển đổi sang cấp độ mới sự trừu tượng hóa, một sự chuyển đổi kiểu đã được thực hiện ở trường - từ số học của số thực sang đại số của các hàm số.
Sự định nghĩa 2.1 Cho x 1 ,x 2 ,…,xn là ký hiệu của các biến có tính chất tùy ý. Chúng ta sẽ gọi những biến này là biến chủ đề. Cho các tập biến (x 1 ,x 2 ,…,x n) thuộc tập M=(M1,M2,…Mn), ta gọi là vùng chủ đề (tức là x i œM i, trong đó Mi gọi là miền định nghĩa của biến xi). Vị từ địa phương n (vị ngữ n-nơi) được xác định trên lĩnh vực chủ đề M, là hàm logic nhận giá trị AND hoặc giá trị L.
Ví dụ 4.2.1. D(x1,x2) = “Số tự nhiên x1 chia (không có dư) cho số tự nhiên x2.” - một vị từ hai vị trí được xác định trên một tập hợp các cặp số tự nhiên M=NäN. Hiển nhiên, D(4,2) = Và, D(3,5) = 0.
Ví dụ 4.2.2. Q(x) ==“x 2<-1, хœR» - одноместный предикат, определенный на множестве действительных чисел М=R. Ясно, что Q(1) = Л, Q(5) = Л, и вообще предикат Q(x) - тождественно ложен, т. е.
Q(x) = А với mọi xœR.
Ví dụ 4.2.3. B(x,y,z) = "x 2 +y 2 Vị từ P xác định trên M được gọi là đúng nếu nó nhận giá trị AND cho bất kỳ giá trị nào của biến chủ đề; Vị từ P được gọi là sai hoàn toàn nếu nó lấy giá trị A cho bất kỳ giá trị nào của biến chủ đề. Vị từ Q từ Ví dụ 4.2.2. là sai giống hệt nhau. Vì các vị từ là các hàm có các giá trị trong một tập hợp các câu lệnh trong đó các phép toán logic được đưa vào nên các phép toán này được xác định một cách tự nhiên cho các vị từ. Cho P và Q là các vị từ được xác định trên M. Sau đó 1. ÂP(x, x,…, x n) = P(x, x,…, x) ∧ 1 2 n 1 2 n ∧ 1 2 n 3. (P ∨ Q)(x 1 ,x 2 ,…,x n) = P(x 1 ,x 2 ,…,x n) ∨ Q(x 1 ,x 2 ,…,x n) 4. (P → Q)(x 1 ,x 2 ,…,x n) = P(x 1 ,x 2 ,…,x n) → Q(x 1 ,x 2 ,…,x n) Vị từ P và Q, được xác định trên M được gọi là tương đương (viết P=Q) nếu P(x 1 ,x 2 ,…,xn)=Q(x 1 ,x 2 ,…,xn) với mọi tập hợp (x 1 ,x 2 ,…, x n )
biến chủ đề từ M .
Định lý 4.2.1 Tập hợp các vị từ n-ary được xác định trên M tạo thành một đại số vị từ Boolean. Do đó, các tương đương cơ bản có giá trị đối với chúng (xem §1.6). Cho P(x 1 ,x 2 ,…,xn) là một vị từ n-ary được xác định trên M. Hãy sửa x i = Một. Chúng ta hãy định nghĩa vị từ (n-1)-ary Q(x 1 ,x 2 ,…,xk-1, xk+1,xn) như sau: Q(x 1 ,x 2 ,…,xk-1,xk +1, xn)=P(x 1 ,x 2 ,…,xk1, Một,xk+1,xn). Họ nói rằng vị từ Q(x 1 ,x 2 ,…,xk-1, xk+1,xn) được lấy từ vị từ P(x 1 ,x 2 ,…,xn) bằng cách cố định giá trị của i- biến thứ: x i = Một
. Sự định nghĩa
4.3.1
. Cho P(x) là một vị từ đơn nhất. Chúng ta hãy liên kết với nó một mệnh đề được ký hiệu là “xP(x) (đọc là “với mọi x P(x)”), mệnh đề này đúng khi và chỉ nếu P(x) là một vị từ đúng giống hệt. Mệnh đề “xP(x) được gọi là , nó thu được từ vị từ P bằng cách gắn một bộ định lượng phổ quát lên biến x. Định nghĩa 4.3.2. Cho P(x) là một vị từ đơn nhất. Chúng ta hãy liên kết nó với một mệnh đề được ký hiệu là $xP(x) (đọc “có x P(x)”), mệnh đề này sai khi và chỉ khi P(x) là một vị từ sai giống hệt nhau. Câu lệnh $xP(x) được cho là thu được từ vị từ P bằng cách gắn một bộ định lượng tồn tại vào biến x. Lưu ý 1. Các ký hiệu " và $ cho các từ định lượng lần lượt là các chữ cái La-tinh A và E đảo ngược, là các chữ cái đầu tiên trong các từ tiếng Anh Tất cả- Tất cả, Hiện hữu- hiện hữu. Lưu ý 2. Câu lệnh có thể được coi là vị ngữ không chứa biến, tức là vị ngữ 0 vị trí (hoặc vị ngữ của bất kỳ địa phương nào). Cho P(x 1 ,x 2 ,…,xn) là một vị từ n-ary được xác định trên M. Hãy cố định trong đó các giá trị của các biến x 1 ,x 2 ,…,x k-1 ,x k +1 ,x n . Chúng ta gắn một bộ định lượng (tồn tại) phổ quát vào vị từ đơn nhất Q(x k) thu được và thu được một phát biểu. Do đó, một tập hợp giá trị cố định của các biến x 1 ,x 2 ,…,x k-1 ,x k+1 ,x n được liên kết với một câu lệnh sử dụng định lượng của tính phổ quát (tồn tại). Vị từ (n-1)-ary này của các biến x 1 ,x 2 ,…,x k-1 ,x k+1 ,x n được cho là thu được từ vị từ gốc P(x 1 ,x 2 ,…, x n) bằng cách thêm một bộ định lượng phổ biến (tồn tại) vào biến thứ k. Vị từ này được ký hiệu là: “x to P(x 1 ,x 2 ,…,x n) ($x to P(x 1 ,x 2 ,…,x n)). họ nói rằng nó bị ràng buộc bởi định lượng của tính phổ quát (sự tồn tại). Ví dụ 4.3.1. Cho D(x1,x2) = “Số tự nhiên x1 chia hết (không có dư) cho số tự nhiên x2.” - vị ngữ hai vị trí. Chúng ta hãy lần lượt gán các bộ định lượng cho các biến của nó. Rõ ràng là vậy 1) "x1"x2D(x1,x2)=0 2) "x2"x1D(x1,x2)=0 3) $x1$x2D(x1,x2)=1 4) $x2$x1D(x1,x2)=1 5) "x1$x2D(x1,x2)=1 6) $x2"x1D(x1,x2)=1 7) $x1"x2D(x1,x2) =0 8) "x1$x2D(x1,x2)=1. Như vậy (bằng cách so sánh 7 và 8 trong ví dụ trước) chúng ta đã chứng minh được định lý: Thông thường, các từ nối và lượng hóa được sắp xếp theo mức độ ưu tiên như sau: Ÿ, ", $, &, ¤, Ø, ~. Định lý 4.3.1. Nói chung, các bộ định lượng trái ngược nhau không giao hoán. Định lý 4.3.2.(các tương đương cơ bản chứa các định lượng) Các tương đương sau đây diễn ra: 1. Định luật De Morgan ∀ xP (x) = ∃x P(x) , ∃xP (x) = ∀ x P(x) 2. Tính giao hoán ∀x∀yP(x,y) =∀y∀xP(x,y) , ∃x∃yP(x,y) =∃y∃xP(x,y) 3. Tính phân phối ∀x(P(x)&Q(x)) =∀xP(x)&Q(x) , ∃x(P(x)∨ Q(x))=∃xP(x)∨ Q(x) 4. Hạn chế trong hoạt động của bộ định lượng ∀x(P(x)∨Q(y))=∀xP(x)∨∀xQ(y) , ∃x(P(x)&Q(y) =∃xP(x)&∃xQ(y) 5. Đối với bất kỳ vị từ hai vị trí nào ∃y∀xP(x,y) →∀x∃yP(x,y) =1 Lý thuyết hình thức(hoặc phép tính)
Y- Cái này: 1. đặt MỘT
ký tự hình thành bảng chữ cái
;
1.
nhiều F
các từ trong bảng chữ cái A, F
à MỘT
được gọi là công thức
;
3. tập hợp con B
công thức, B
à F
,
được gọi là tiên đề; 4. nhiều mối quan hệ R
trên một tập hợp các công thức được gọi là quy tắc suy luận. Rất nhiều nhân vật MỘT
có thể là hữu hạn hoặc vô hạn. Thông thường, để tạo thành các ký hiệu, một tập hợp hữu hạn các chữ cái được sử dụng, nếu cần, các số tự nhiên sẽ được gán làm chỉ số. Rất nhiều công thức F
thường được đưa ra bằng định nghĩa quy nạp, ví dụ bằng ngữ pháp hình thức. Theo quy định, tập hợp này là vô hạn. bộ MỘT
Và F
cùng nhau xác định ngôn ngữ
,
hoặc chữ ký
,
lý thuyết hình thức. Nhiều tiên đề B
có thể là hữu hạn hoặc vô hạn. Nếu tập hợp các tiên đề là vô hạn thì theo quy tắc, nó được chỉ định bằng cách sử dụng một tập hợp hữu hạn các sơ đồ tiên đề và các quy tắc để tạo ra các tiên đề cụ thể từ sơ đồ tiên đề. Nhiều luật suy luận R
, như một quy luật, tất nhiên. Vì vậy, phép tính Y có bốn (A, F, B, R)
. Bằng đạo hàm trong giải tích Y là một chuỗi các công thức F 1 ,F 2 ,…,Fn sao cho với mọi k (1§k§n) công thức Fk hoặc là một tiên đề của phép tính Y hoặc là hệ quả trực tiếp của bất kỳ công thức nào trước đó thu được bằng quy tắc suy luận . Một công thức G được gọi là định lý của phép tính Y (dẫn xuất theo Y hoặc chứng minh được theo Y) nếu có kết luận F 1 ,F 2 ,…,F n ,G được gọi là dẫn xuất của công thức G hoặc chứng minh của định lý G. Điều này được viết như sau: F 1,F 2,…,F n + G. Giải tích Y gọi điện nhất quán, nếu không phải tất cả các công thức của nó đều có thể chứng minh được. Một định nghĩa khác về tính nhất quán có thể được đưa ra: Một phép tính được gọi là nhất quán nếu các công thức F và ŸF (phủ định của F) không được suy ra đồng thời trong đó. Giải tích Y gọi điện hoàn thành(hoặc thỏa đáng) nếu mỗi phát biểu đúng M tương ứng với một định lý của lý thuyết Y
. Lý thuyết hình thức Y gọi điện có thể quyết định được, nếu có một thuật toán, đối với bất kỳ công thức nào của lý thuyết, xác định liệu công thức này có phải là một định lý của lý thuyết hay không Y hay không. Sử dụng khái niệm phép tính hình thức, chúng ta định nghĩa phép tính mệnh đề (PS). Bảng chữ cái IW bao gồm 1. chữ cái A, B, Q, R, P và những thứ khác, có thể có chỉ mục (được gọi là biến mệnh đề), 2. ký hiệu logic(dây chằng) Ÿ, &, ¤, Ø, 3. phụ trợ nhân vật
(,). Rất nhiều công thức IV được xác định theo phương pháp quy nạp: 1. tất cả các biến mệnh đề đều là công thức IV; 2. Nếu A, B là công thức IV ,
toŸA, A⁄B, A¤B, AØB - công thứcIV ;
3. một biểu thức là công thức IV khi và chỉ khi điều này có thể được thiết lập bằng cách sử dụng các điểm "1" và Do đó, bất kỳ công thức IV nào cũng được xây dựng từ các biến mệnh đề sử dụng các từ nối Ÿ, ⁄, ¤, Ø. Trong tương lai, khi viết công thức, chúng ta sẽ lược bỏ một số dấu ngoặc đơn, sử dụng các quy ước tương tự như ở chương trước. tiên đề IV là các công thức sau (đối với mọi công thức A, B, C) 2. (AØB)Ø((AØ(BØC))Ø(AØC)); 5. (AØB)Ø((AØC)Ø(AØ(B⁄C))); 8. (AØC)Ø((BØC)Ø((A¤B)ØC)); 9. (AØB)Ø((AØŸB)ØŸA); Các công thức được chỉ ra được gọi là sơ đồ tiên đề IV .
Khi thay thế các công thức cụ thể vào bất kỳ sơ đồ nào, sẽ thu được trường hợp đặc biệt của sơ đồ tiên đề. Quy tắc suy luận trong IE có một quy tắc kết luận (modus ponens): nếu A và AØB là các công thức dẫn xuất được thì B cũng dẫn xuất được Một cách tượng trưng nó được viết như thế này: A, A B →
B
. Ví dụ: nếu các câu lệnh A⁄B và A⁄BØ(AØC) có thể suy diễn được thì câu lệnh AØC cũng có thể suy ra được theo quy tắc suy luận. Một công thức G được gọi là có thể suy ra từ các công thức F 1 ,F 2 ,…,F n (ký hiệu là F 1 ,F 2 ,…,F n +G) nếu tồn tại một dãy các công thức F 1 ,F 2 ,… ,F k ,G , trong đó bất kỳ công thức nào cũng là tiên đề hoặc thuộc danh sách các công thức F 1,F 2,...,F n (gọi là giả thuyết), hoặc thu được từ các công thức trước đó theo quy tắc suy luận. Khả năng suy ra của công thức G từ “ (ký hiệu là +G) tương đương với việc G là một định lý IV. Ví dụ 5.2.1. Hãy chứng minh rằng công thức AØA có thể suy ra được trong IV. Để làm điều này, chúng ta sẽ xây dựng đạo hàm của công thức này: 1) ở tiên đề 2, thay B bằng AØA, thay C bằng A. Chúng ta có được tiên đề (AØ(AØA))Ø((AØ((AØA)ØA))Ø(AØA)); 2) ở tiên đề 1 ta thay B bằng A. Ta thu được AØ(AØA); 3) từ 1 và 2 theo modus ponens chúng ta kết luận (AØ((AØA)ØA))Ø(AØA); 4) ở tiên đề 1 ta thay B bằng AØA. Chúng tôi nhận được AØ((AØA)ØA); 5) từ các đoạn văn. 3 và 4 theo quy tắc suy luận +AØA đúng. Định lý 5.2.1. 1. Nếu F 1 ,F 2 ,…,Fn,A,B là công thức IV, Г=(F 1 ,F 2 ,…,Fn), Г+A thì Г,B+A. (bạn có thể tăng số lượng giả thuyết). 2. Nếu và chỉ nếu F 1 ,F 2 ,…,F n +A, khi F 1 ⁄F 2 ⁄…⁄F n +A (rút gọn nhiều giả thuyết thành một giả thuyết). Định lý 5.3.1. (định lý suy diễn) Nếu Г,B+A thì Г+BØA, trong đó Г là tập hợp các công thức Г=(F 1 ,F 2 ,…,F n ). Hệ quả 5.3.1. Khi đó và chỉ khi F 1 ,F 2 ,…,F n +A, khi Bằng chứng. Giả sử F 1 ,F 2 ,…,F n +A. Khi đó, áp dụng định lý suy diễn, ta có F 1 ,F 2 ,…,F n-1 +F n ØA. Tương tự F 1 ,F 2 ,…,F n-2 +F n 1Ø(F n ØA), v.v. Tiếp tục quá trình với số lần yêu cầu, ta được F 1 Ø(F 2 Ø…Ø(F n-1 Ø(F n ØA))…) Để chứng minh tính đầy đủ, giả sử rằng +B, trong đó B=F 1 Ø(F 2 Ø…Ø(F n-1 Ø(F n ØA))…). Hãy sử dụng Định lý 5.2.1., mục 1: F 1 + B .
Theo quy tắc kết luận ta thu được F 1 + (F 2 Ø…Ø(F n-1 Ø(F n ØA))…), rồi sau n bước ta có F 1 ,F 2 ,…,F n +A . Như vậy, nhờ Hệ quả 5.3.1., việc kiểm tra tính suy diễn của công thức A từ các công thức F 1,F 2,…,Fn được rút gọn thành việc kiểm tra khả năng chứng minh của công thức F 1 Ø(F 2 Ø…Ø(F n-1 Ø(F n ØA))…). Hãy nhớ lại rằng công thức A được gọi là đúng hoàn toàn (hoặc tautology) nếu giá trị của công thức A bằng một đối với bất kỳ tập hợp giá trị nào của các biến mệnh đề. Định lý sau đây giảm việc xác minh khả năng chứng minh của một công thức thành việc xác minh tính đúng đắn của nó. Định lý 5.3.2. (về sự đầy đủ). Công thức A có thể chứng minh được khi và chỉ nếu A hoàn toàn đúng (tautology): +A ‹ A-tautology. Vì vậy, để xác định liệu một công thức có thể chứng minh được hay không, việc biên soạn bảng chân lý của nó là đủ. Như đã biết, có một thuật toán hiệu quả để xây dựng bảng chân lý, và do đó, IV tan. Ví dụ 5.3.1. Hãy chứng minh P+P. Theo định lý suy diễn thì điều này tương đương với +(PØP). Ngược lại, theo định lý về tính đầy đủ, chỉ cần chứng minh rằng (РØР) là một tautology là đủ. Biên soạn bảng chân lý cho công thức (РØР) ,
Chúng tôi tin rằng (РØР) hoàn toàn đúng và do đó có thể chứng minh được. Định lý 5.3.3. (về tính nhất quán). Tính toán IW là nhất quán. Bằng chứng. Theo định lý về tính đầy đủ, bất kỳ công thức nào không đúng hoàn toàn đều không thể chứng minh được trong IW. Ví dụ: công thức như vậy là công thức A⁄(ŸA). Tập hợp các công thức Г được gọi là gây tranh cãi
,
nếu Г+А⁄(ŸА) .
Nếu Г là một tập hợp các công thức mâu thuẫn nhau, chúng ta sẽ biểu thị điều này bằng Г+. Tuyên bố
5.3.1.
Công thức A được suy ra từ tập hợp các công thức Г khi và chỉ khi tập hợp Г»(ŸA) mâu thuẫn. Chứng minh định lý tự động là nền tảng của lập trình logic, trí tuệ nhân tạo và các xu hướng lập trình hiện đại khác. Nói chung, có thể không có một thuật toán nào mà qua đó, với một công thức A tùy ý, người ta có thể xác định trong một số hữu hạn các bước xem A có được suy ra trong phép tính Y hay không. Tuy nhiên, đối với một số lý thuyết hình thức đơn giản (ví dụ, phép tính mệnh đề) và một số lớp công thức đơn giản (ví dụ, phép tính vị từ ứng dụng với một vị từ đơn), các thuật toán chứng minh định lý tự động đã được biết đến. Dưới đây, bằng cách sử dụng ví dụ về phép tính mệnh đề, chúng tôi phác thảo những điều cơ bản của phương pháp giải - một phương pháp cổ điển và đồng thời phổ biến để tự động chứng minh các định lý. Hãy nhớ lại rằng nếu x là một biến logic và σœ(0,1) thì biểu thức x σ = xx nếu if σσ == 10 hoặc x σ = 10 nếu if x x =≠σσ , được gọi thư. Các chữ x và Ÿx được gọi là trái ngược.
Liên hợp gọi là sự kết hợp của các chữ cái. rời rạc gọi là sự tách rời của các chữ cái. Đặt D 1 = B 1 ∨ A, D 2 = B 2 ∨ A là các mệnh đề. Mệnh đề B 1 ¤B 2 được gọi là chất giải quyết mệnh đề D 1 và D 2 bằng chữ A và được ký hiệu là res A (D 1 ,D 2). Phép giải của mệnh đề D 1 và D 2 là phép giải bằng một chữ cái nào đó và được ký hiệu là res(D 1 ,D 2). Rõ ràng res(A,ŸA)=0. Thật vậy, bởi vì A=A¤0 và ŸA=ŸA¤0, thì res(A,ŸA)=0¤0=0. Nếu mệnh đề D 1 và D 2 không chứa các chữ cái đối lập nhau thì chúng không có giải pháp. Ví dụ 5.5.1. Nếu như D 1 =A¤B¤C, D 2 = A ∨ B ∨ Q thì res A (D 1 ,D 2)=B¤C¤ B ¤Q, res B (D 1 ,D 2)=A¤C¤A¤Q, resC(D 1 ,D 2) không tồn tại. Tuyên bố 5.5.1. Nếu res(D 1 ,D 2) tồn tại thì D 1 ,D 2 + res(D 1 ,D 2). Đặt S=(D 1 ,D 2 ,…,Dn) là tập hợp các mệnh đề. Một chuỗi các công thức F 1 ,F 2 ,…,F n được gọi là dẫn xuất tuyệt đối từ S nếu với mỗi công thức F k một trong các điều kiện được đáp ứng: 2. có j, k
Định lý 5.5.1.
(về tính đầy đủ của phương pháp giải quyết). Một tập hợp các mệnh đề S mâu thuẫn khi và chỉ khi có một kết luận dứt khoát từ S kết thúc bằng 0. Lưu ý rằng phương pháp giải có thể được sử dụng để kiểm tra khả năng suy ra của một công thức F từ một tập hợp các công thức F 1, F 2,…,F n đã cho. Thật vậy, điều kiện F 1 ,F 2 ,…,F n +F tương đương với điều kiện F 1 ,F 2 ,…,F n ,ŸF+ (nhiều công thức mâu thuẫn nhau), đến lượt nó tương đương với điều kiện Q+, trong đó Q=F 1 ⁄F 2 ⁄…⁄F n ⁄(ŸF). Hãy rút gọn công thức Q thành CNF: Q=D 1 ⁄D 2 ⁄...⁄Dm, sau đó Q+ ‹D 1 ⁄D 2 ⁄...⁄Dm+ ‹ D 1 ,D 2 ,...,D m + . Như vậy, nhiệm vụ kiểm tra tính suy diễn của F 1 ,F 2 ,...,F n +F phụ thuộc vào việc kiểm tra tính mâu thuẫn của tập hợp các mệnh đề S=(D 1 ,D 2 ,...,D m ) , tương đương với sự tồn tại của kết luận chắc chắn 0 từ S. Ví dụ 5.5.2. Kiểm tra tỷ lệ AØ(BØC), CDØE, ŸFØD&(Ÿ)E + AØ(BØF) bằng phương pháp phân giải. Theo phát biểu 5.3.1. cần kiểm tra nhiều công thức không nhất quán S = (AØ(BØC), CDØE, ŸFØD&(Ÿ)E, Ÿ(AØ(BØF))). Chúng tôi trình bày tất cả các công thức từ. S đến KNF: S = (A ∨ B ∨ C,C ⋅ D ∨ E, F ∨ D ⋅ E, A ∨ B ∨ F) == (A ∨ B ∨ C, C ∨ D ∨ E, (F ∨ D) ⋅ (F ∨ E), A ⋅ B ⋅ F) . Như vậy ta thu được tập mệnh đề S = (A ∨ B ∨ C, C ∨ D ∨ E,F ∨ D,F ∨ E,A,B, F) Hãy xây dựng một kết luận kiên quyết từ S kết thúc bằng 0: 1. res A (A ∨ B ∨ C,A) = B ∨ C ; 2. res B(B ∨ C,B) = C ; 3. độ phân giải D (C ∨ D ∨ E,F ∨ D) = C ∨ E ∨ F ; 4. res E (C ∨ E ∨ F,F ∨ E) = C ∨ F ; 5. độ phân giải C(C, C ∨ F) = F; 6. res(F, F) = 0 . Vì vậy, chúng ta kết luận rằng công thức AØ(BØF) được suy ra từ tập hợp các công thức AØ(BØC), CDØE, ŸFØD&(Ÿ)E. Lưu ý rằng phương pháp giải là đủ để khám phá khả năng thỏa mãn có thể có của một tập hợp các mệnh đề S. Để làm điều này, chúng ta hãy đưa vào tập S tất cả các mệnh đề thu được bằng cách dẫn xuất giải từ S. Từ định lý về tính đầy đủ của phương pháp giải nó theo sau Hệ quả 5.5.1. Nếu một tập hợp các mệnh đề S chứa các phần tử phân giải của tất cả các phần tử của nó thì S thỏa mãn khi và chỉ khi 0–S. Một đặc điểm đặc trưng của thời hiện đại là việc sử dụng rộng rãi máy tính để giải quyết các vấn đề (nhiệm vụ) trong các lĩnh vực hoạt động khác nhau của con người. Tuy nhiên, vấn đề trước tiên phải được giải quyết bằng thuật toán, tức là. phải đưa ra một đơn thuốc chính thức, theo đó người ta có thể thu được kết quả cuối cùng để giải quyết tất cả các vấn đề thuộc một loại nhất định (đây là một khái niệm trực quan, không nghiêm ngặt về thuật toán). Ví dụ: Thuật toán tìm ước chung lớn nhất của hai số tự nhiên một, b, trông như thế này: 1) mở rộng số lượng Một theo thừa số nguyên tố; 2) lặp lại bước 1 cho b
Và chuyển sang bước 3; 3) soạn tích của các thừa số nguyên tố chung từ khai triển MỘT Và b với các chỉ số bằng giá trị nhỏ nhất của các chỉ số đưa vào khai triển. Sau khi phân tích ví dụ này, chúng tôi lưu ý các tính năng (thuộc tính) quan trọng nhất của thuật toán: 1.
Nhân vật đại chúng- khả năng áp dụng thuật toán không phải cho một bài toán mà cho một lớp bài toán. 2.
sự rời rạc- phân tích rõ ràng thành các giai đoạn (bước) riêng lẻ của thuật toán. 3.
Chủ nghĩa quyết định- một cách tổ chức các giai đoạn thực hiện trong đó luôn rõ ràng cách thực hiện chuyển đổi từ giai đoạn này sang giai đoạn khác. 4.
Chân tay- Để thu được kết quả khi áp dụng một thuật toán để giải một bài toán cụ thể, người ta thực hiện một trình tự hữu hạn các bước của thuật toán: Lưu ý rằng nếu bản thân sự hiện diện của một thuật toán đóng vai trò là bằng chứng cho sự tồn tại của thuật toán, thì để chứng minh sự tồn tại của nó, cần phải có một định nghĩa toán học chặt chẽ về thuật toán. Những nỗ lực nhằm chính thức hóa khái niệm thuật toán đã dẫn đến việc tạo ra Máy Turing, như một thiết bị tưởng tượng nào đó thực hiện thuật toán. Một bước khác trong việc xác định khái niệm thuật toán là sự xuất hiện hàm đệ quy ,
là các hàm chính thức hóa khái niệm thuật toán và thực hiện khái niệm trực quan về khả năng tính toán. Người ta sớm phát hiện ra rằng tập hợp các hàm đệ quy trùng với tập hợp các hàm tính toán được trên máy Turing. Các khái niệm mới xuất hiện sau đó, tuyên bố giải thích khái niệm thuật toán, hóa ra tương đương với các hàm có thể tính toán được trên máy Turing và do đó tương đương với các hàm đệ quy. Kết quả của cuộc thảo luận đang diễn ra về thuật toán là gì là một tuyên bố mà ngày nay được gọi là luận điểm của Church. Luận án của Church. Khái niệm về thuật toán hoặc khả năng tính toán của một số thiết bị cơ khí trùng khớp với khái niệm về khả năng tính toán trên máy Turing (và do đó với khái niệm về hàm đệ quy). Nói cách khác, thuật toán là một quá trình có thể được biểu diễn bằng sơ đồ chức năng và được thực hiện bởi một số máy Turing. Máy Turing là một thiết bị (trừu tượng) bao gồm băng, thiết bị điều khiển và đầu đọc. Các băng được chia thành các tế bào. Mỗi ô chứa chính xác một ký tự từ bảng chữ cái bên ngoài
A=(
một số 0,
a 1,…,
MỘT ). Một số ký hiệu (chúng tôi sẽ biểu thị nó Ÿ
) của bảng chữ cái A được gọi là ô trống và bất kỳ ô nào hiện chứa ký tự trống được gọi là ô trống (tại thời điểm đó). Băng được coi là có khả năng không giới hạn ở cả hai hướng. Thiết bị điều khiển tại mỗi thời điểm đều ở trạng thái q j thuộc tập hợp Q=(q 0 , q 1 ,..., q m )(m=l). Tập Q được gọi là bảng chữ cái nội bộ
.
Một trong những điều kiện này (thường q 0) được gọi là cuối cùng và một số khác (thường là q 1) - ban đầu. Đầu đọc di chuyển dọc theo băng để tại bất kỳ thời điểm nào nó sẽ quét chính xác một ô của băng. Đầu có thể đọc nội dung của ô đang được theo dõi và ghi vào đó, thay vì ký hiệu được theo dõi, một số ký hiệu mới từ bảng chữ cái bên ngoài MỘT(có thể là giống nhau). Trong quá trình hoạt động, thiết bị điều khiển, tùy thuộc vào trạng thái của nó và biểu tượng mà người đứng đầu nhìn thấy, sẽ thay đổi trạng thái bên trong của nó q. Sau đó, nó ra lệnh cho đầu in một ký tự nhất định từ bảng chữ cái bên ngoài trong ô đang được theo dõi. MỘT, rồi ra lệnh cho đầu giữ nguyên vị trí hoặc di chuyển một ô sang phải hoặc di chuyển một ô sang trái. Khi ở trạng thái cuối cùng, máy sẽ ngừng hoạt động. Cấu hình trên băng (hoặc từ máy)được gọi là tập hợp được tạo bởi: 1) trình tự Một
tôi (1)
,Một
tôi (2)
,...,Một
là) ký tự từ bảng chữ cái bên ngoài MỘT, được ghi trong các ô băng, trong đó Một
Tôi
(1)
.- ký hiệu được viết ở ô đầu tiên bên trái, v.v. (bất kỳ trình tự nào như vậy được gọi là trong một từ), 2) trạng thái của bộ nhớ trong q r ; 3) số k tế bào được cảm nhận. Chúng ta sẽ viết cấu hình máy như sau: a ,a ,..., a a i(r) a ,a ,..., a i(1) i(2) i(r−1) q r i(r+1) i(r+2) i(s) Đây r- ô cảm nhận được đánh dấu dưới dạng phân số. Nếu máy đang ở trạng thái bên trong khí, chấp nhận một ô có ký hiệu bạn, ghi một ký hiệu vào ô này vào thời điểm tiếp theo một r, chuyển sang trạng thái bên trong qs và di chuyển dọc theo băng thì họ nói rằng máy đang thực hiện lệnh q tôi và bạn
Æ
qs a r S, trong đó ký hiệu S có thể nhận một trong các giá trị sau: -1 – dịch chuyển đầu sang trái; +1 - chuyển đầu sang phải; 0 – đầu vẫn giữ nguyên. Danh sách tất cả các lệnh (nhóm năm) xác định hoạt động của máy Turing được gọi là chương trình chiếc xe này. Chương trình máy thường được xác định dưới dạng bảng. Vì vậy, đối với tình huống được mô tả ở trên trong bảng tại giao lộ dòng Một
bạn và cột khí sẽ đứng qs a r S(xem bảng 6.2.1) Bảng 6.2.1. Nếu chương trình bao gồm ô tô cho cặp đôi (
q tôi, à bạn
)
năm bị thiếu, thì trong bảng ở giao điểm của dòng bạn và cột khí một dấu gạch ngang được thêm vào. Vì thế, Theo định nghĩa, máy Turing là, bộ M=(A,Q,P), Ở đâu MỘT- bảng chữ cái bên ngoài, Q- bảng chữ cái của các trạng thái nội bộ, P- chương trình. Nếu một chiếc máy, sau khi bắt đầu làm việc với một từ P nào đó được viết trên băng, đạt đến trạng thái cuối cùng thì nó được gọi là áp dụng cho từ này. Kết quả công việc của nó là từ được ghi trên băng ở trạng thái cuối cùng. Ngược lại, máy được cho là không thể áp dụng được cho từ R. Ví dụ 6.2.1. Hãy xây dựng một máy Turing cộng các số tự nhiên được viết bằng hệ thống số đơn phân (nghĩa là được viết bằng một ký hiệu |.
Ví dụ 5=|||||.). Giải pháp. Hãy xem xét bảng chữ cái MỘT
= {|, +, ⁄}. Máy được xác định theo chương trình sau: Chúng ta hãy viết ra các cấu hình phát sinh tuần tự trong quá trình hoạt động của chiếc máy này trên từ gốc ||+ ||| , tức là 2+3. Ở đây, khi ghi cấu hình, chúng ta sẽ sử dụng quy ước sau: trạng thái đặt máy được ghi trong ngoặc đơn ở bên phải phía sau chữ cái đang quan sát. Ví dụ 6.2.2. Xây dựng máy Turing nhân đôi số tự nhiên được viết bằng hệ thống số đơn phân. Giải pháp. Hãy xây dựng chiếc máy cần thiết theo bảng chữ cái A=(|, α, ⁄). Chương trình cho một chiếc máy như vậy có thể trông như thế này: Hãy áp dụng kết quả máy cho từ ||
. Giới thiệu chữ cái mới α và thay thế chữ cái ban đầu |
trên α cho phép người ta phân biệt được bản gốc |
và mới (được chỉ định) |
. Tình trạng q 1 cung cấp thay thế |
trên α ,
tình trạng q 2 cung cấp tìm kiếm cho α ,
dự định thay thế |
, và dừng máy trong trường hợp không phát hiện được α, q 3đảm bảo hoàn thành |
trong trường hợp khi α được thay thế bởi |.
Chúng ta hãy đồng ý rằng trong đoạn này 1. tập N số tự nhiên chứa 0 (không), tức là N=(0,1,2,3,...); 2. các hàm đang được xem xét f=f(x 1 ,x 2 ,…,x n) chỉ được xác định khi các biến lấy giá trị từ N, tức là. xiœN; 3. Phạm vi giá trị của hàm DŒN; 4. các hàm đang xét f=f(x 1 ,x 2 ,…,x n) có thể được xác định một phần, tức là. không được xác định cho tất cả các tập hợp số tự nhiên. Hãy giới thiệu vào xem xét chức năng đơn giản o(x)=0, s(x)=x+1,
Tôi là n (x 1 ,..., xn)
=
xm Các hàm này có thể được tính toán bằng thiết bị cơ khí thích hợp (ví dụ: máy Turing). Chúng ta hãy định nghĩa các toán tử xây dựng các hàm mới dựa trên một hoặc nhiều hàm đã cho. Toán tử chồng chất. Cho hàm f(x 1 ,x 2 ,…,x k) của k biến và k hàm f 1 (x 1 ,x 2 ,…,x n),…,f k (x 1 ,x 2 ,…,x n) là cho trước n biến. Sự chồng chất của các hàm f,f 1 ,…,f k là hàm j(x 1 ,x 2 ,…,x n)= f(f 1 (x 1 ,x 2 ,…,x n),…,f k (x 1 ,x 2 ,…,xn)) Chúng ta nói rằng hàm j có được bằng cách áp dụng toán tử xếp chồng S k+1 cho các hàm f,f 1 ,…,f k , và viết j=S k+1 (f,f 1 ,…,f k) Ví dụ: S 2 (s, o)=s(o(x)), tức là một hàm số giống hệt 1, và S 2 (s,s)=s(s(x)) là hàm y(x)=x+2. Toán tử đệ quy nguyên thủy. Cho các hàm g(x 1 ,x 2 ,…,x n) và h(x 1 ,x 2 ,…,x n+2). Hãy xây dựng hàm f(x 1 ,x 2 ,…,x n+1) Cho các giá trị x 1 ,x 2 ,…,x n cố định. Khi đó ta giả sử: f(x 1 ,x 2 ,…,x n ,0)= g(x 1 ,x 2 ,…,x n) f 1 (x 1 ,x 2 ,…,x n ,y+1)= h(x 1 ,x 2 ,…,x n ,y, f(x 1 ,x 2 ,…,x n ,y)) Những đẳng thức này xác định hàm f(x 1 ,x 2 ,…,x n+1) một cách duy nhất. Hàm f được gọi là hàm thu được bằng toán tử đệ quy nguyên thủy R. Ký hiệu f=R(g,h) được sử dụng. Định nghĩa quy nạp của một hàm (được thể hiện bằng toán tử đệ quy nguyên thủy) không phải là hiếm trong toán học. Ví dụ: 1) mức độ với số mũ tự nhiên được xác định theo phương pháp quy nạp: Một
0
=1, Một n+ 1
=a n
ÿ Một
; 2) giai thừa: 0!=1, (n+1)!= n!ÿ(n+1), v.v. Sự định nghĩa. Các hàm có thể thu được từ đơn giản nhất o(x)=0, s(x)=x+1, I m n (x 1 ,..., x n) = x m bằng cách áp dụng các toán tử xếp chồng và đệ quy nguyên thủy một số lần hữu hạn được gọi là nguyên thủy là đệ quy. Hãy kiểm tra xem hàm u(x,y)=x+y có phải là đệ quy nguyên thủy hay không. Thật vậy, chúng ta có: u(x,0)=0, u(x,y+1)=x+y+1=u(x,y)+1. Đây là một sơ đồ đệ quy nguyên thủy, vì x= I 1 1 (x), và u(x,y)+1=s(u(x,y))=S 2 (s,u). Ở đây g(x)= I 1 1 (x), và h(x,y,u)=s(u)=S 2 (s, I 3 3). Người ta cũng chứng minh tương tự rằng các hàm m(x,y)=xÿy, d(x,y)=x y (chúng ta giả sử theo định nghĩa 0 0 =1), Fact(x)=x! và nhiều thứ khác về cơ bản là đệ quy. Ghi chú; các hàm đệ quy nguyên thủy được xác định ở mọi nơi (nghĩa là được xác định cho tất cả các giá trị của đối số của chúng). Thật vậy, những hàm đơn giản nhất ồ, s, Tôi được xác định ở mọi nơi và việc áp dụng các toán tử chồng chất và đệ quy nguyên thủy cho các hàm được xác định ở mọi nơi cũng mang lại các hàm được xác định ở mọi nơi. Vì vậy, một chức năng như = x − y, nếu x ≥ y< y f(x,y) không tồn tại nếu x không thể đệ quy nguyên thủy. Chúng ta không có quyền xét hàm f(x,y)=x-y ở đây, vì các giá trị của hàm phải là số tự nhiên (do đó không âm). Tuy nhiên, có thể coi hàm ` y = 0x − y ifif x x<≥y.y Hãy kiểm tra xem nó có đệ quy nguyên thủy hay không. Trước tiên chúng ta hãy chứng minh rằng hàm j(x)=xπ1 là đệ quy nguyên thủy. Thật vậy, j(0)=0. j(y+1)=(y+1)π1=y, đóng vai trò là sơ đồ đệ quy nguyên thủy cho hàm xπ1. Cuối cùng, xπ0=x, xπ(y+1)=(xπy)π1=j(xπy) là sơ đồ đệ quy nguyên thủy cho xπy. Một lớp hàm rộng hơn đáng kể so với các hàm đệ quy nguyên thủy là lớp hàm đệ quy (xem định nghĩa bên dưới). Trong tài liệu, các chức năng này còn được gọi là đệ quy một phần .
Để xác định chúng, chúng tôi giới thiệu thêm một toán tử. Toán tử tối thiểu hóa. Cho hàm số f(x 1 ,x 2 ,… ,x n ,x n+1). Cố định một số giá trị x 1 ,x 2 ,… ,x n của n biến đầu tiên và tính f(x 1 ,x 2 ,… ,x n ,0), f(x 1 ,x 2 ,… ,x n ,1 ), f(x 1 ,x 2 ,… ,x n ,2) v.v. Nếu y là số tự nhiên nhỏ nhất thỏa mãn f(x 1 ,x 2 ,… X n ,y)=x n+1 (tức là các giá trị f(x 1 ,x 2 ,… ,x n ,0), f(x 1 ,x 2 ,… ,x n ,1),…,f( x 1, x 2,… X n ,y-1) đều tồn tại và không bằng xn +1) thì ta đặt g(x 1 ,x 2 ,… X n ,x n+1)=y. Do đó, g(x 1 ,x 2 ,… ,x n ,x n+1)=min(y|f(x 1 ,x 2 ,…,x n ,y)=x n+1). Nếu như vậy y không, khi đó chúng ta giả sử rằng f(x 1 ,x 2 ,… ,x n ,x n+1) không được xác định. Vì vậy, ba trường hợp có thể xảy ra: 1. f(x 1 ,x 2 ,… ,x n ,0), f(x 1 ,x 2 ,… ,x n ,1),…,f(x 1 ,x 2 ,… ,x n ,y-1) tồn tại và không bằng xn +1, và f(x 1 ,x 2 ,…,x n ,y)=x n+1 ; 2. f(x 1 ,x 2 ,… ,x n ,0), f(x 1 ,x 2 ,… ,x n ,1),…,f(x 1 ,x 2 ,… ,x n ,y-1) tồn tại và không bằng xn +1, nhưng f(x 1 ,x 2 ,…,x n ,y) không tồn tại; 3. f(x 1 ,x 2 ,… ,x n ,i) tồn tại với mọi iœN và khác xn +1. Nếu trường hợp thứ nhất xảy ra thì g(x 1 ,x 2 ,… ,x n ,x n+1)=y, và nếu trường hợp thứ 2 hoặc thứ 3 thì g(x 1 ,x 2 ,… ,x n , x n +1) không được xác định. Hàm g thu được theo cách này được gọi là thu được từ f bằng cách sử dụng toán tử cực tiểu hóa M. Chúng ta viết g= Mf. Toán tử tối thiểu hóa là một dạng tổng quát rõ ràng của toán tử hàm nghịch đảo. Sự khái quát hóa khá sâu sắc, vì hàm f không bắt buộc phải một-một (trong biến x n+1) Sự định nghĩa. Các hàm có thể được suy ra từ đơn giản nhất o(x)=0, s(x)=x+1,
Tôi là n (x 1 ,..., xn)
= xmáp dụng các toán tử xếp chồng, đệ quy nguyên thủy và toán tử giảm thiểu một số lần hữu hạn được gọi là đệ quy. Lớp hàm đệ quy rộng hơn lớp hàm đệ quy nguyên thủy, nếu chỉ vì nó không chỉ chứa các hàm được định nghĩa ở mọi nơi. Ví dụ, chúng ta hãy chứng minh rằng hàm = x − y, nếu x ≥ y< y f(x,y) không tồn tại nếu x là đệ quy. Thật vậy, f(x,y)=min(z| y+z=x), và trước đây người ta đã xác định rằng hàm u(x,y)=x+y về cơ bản là đệ quy. Hàm đệ quy phản ánh sự hiểu biết trực quan của chúng ta về các hàm mà một số thiết bị cơ khí có thể tính toán. Đặc biệt, chúng có thể tính toán được trên máy Turing (xem đoạn trước). Ngược lại, mọi hàm tính toán được trên máy Turing đều có tính đệ quy. Chúng tôi sẽ không kiểm tra thực tế này vì nó sẽ tốn quá nhiều thời gian và không gian. Ví dụ, có thể tìm thấy bằng chứng đầy đủ trong cuốn sách “Thuật toán và hàm đệ quy” của A.I. Lưu ý rằng không phải mọi hàm của các đối số tự nhiên đều có tính đệ quy, thậm chí không phải mọi hàm của một đối số duy nhất. Sự tồn tại của các hàm không đệ quy là “lý do toán học” cho sự tồn tại của các vấn đề không thể giải được bằng thuật toán. Trong các ngành toán học khác nhau, có những vấn đề không thể giải được bằng thuật toán, tức là. những vấn đề không có thuật toán giải, không phải vì nó chưa được phát minh mà vì về nguyên tắc là không thể. Tất nhiên, thuật toán phải được hiểu theo nghĩa máy Turing và hàm đệ quy. Chúng ta hãy xây dựng một trong những vấn đề này Vấn đề dừng máy Turing. Máy Turing là một đối tượng được xác định bởi một số hữu hạn các tham số. Tất cả các ánh xạ từng phần từ tập hữu hạn này sang tập hữu hạn khác có thể được đánh số lại một cách hiệu quả. Vì vậy, mỗi máy Turing có thể được gán một số (số tự nhiên). Giả sử T(n) là máy Turing có số n. Một số máy bắt đầu chạy trên băng tải trống cuối cùng sẽ dừng lại và một số máy chạy vô thời hạn. Bài toán đặt ra: Cho một số tự nhiên n, hãy xác định xem máy Turing T(n) chạy trên một băng trống có dừng lại hay không. Nhiệm vụ này không thể giải quyết được về mặt thuật toán. Tức là không có quy trình tự động ,
với mỗi n quyết định máy T(n) có dừng hay không. Điều này không ngăn cản chúng ta xác định xem nó có dừng hay không đối với bất kỳ máy cụ thể nào. Không có phương pháp nào giải quyết được vấn đề này cho tất cả các máy cùng một lúc .
Cho một bài toán, làm thế nào để tìm ra thuật toán hiệu quả để giải nó? Và nếu tìm ra một thuật toán thì làm sao có thể so sánh nó với các thuật toán khác giải quyết cùng một vấn đề? Làm thế nào để đánh giá chất lượng của nó? Những câu hỏi thuộc loại này được cả các lập trình viên và những người tham gia nghiên cứu lý thuyết về máy tính quan tâm. Có nhiều tiêu chí để đánh giá thuật toán. Thông thường, chúng ta sẽ quan tâm đến thứ tự tăng dần của thời gian và dung lượng bộ nhớ cần thiết để giải một bài toán khi dữ liệu đầu vào tăng lên. Chúng tôi muốn liên kết một số với từng nhiệm vụ cụ thể, được gọi là kích thước của nó ,
sẽ thể hiện thước đo lượng dữ liệu đầu vào. Ví dụ, kích thước của một bài toán nhân ma trận có thể là kích thước lớn nhất của ma trận nhân tử. Thời gian mà một thuật toán thực hiện như một hàm của kích thước bài toán được gọi là độ phức tạp thời gian thuật toán này. Hành vi phức tạp này trong giới hạn khi kích thước bài toán tăng lên được gọi là độ phức tạp thời gian tiệm cận
.
Tương tự chúng ta có thể định nghĩa độ phức tạp điện dung và độ phức tạp điện dung tiệm cận. Chính độ phức tạp tiệm cận của thuật toán cuối cùng sẽ xác định quy mô của các vấn đề có thể được giải quyết bằng thuật toán này. Nếu một thuật toán xử lý đầu vào có kích thước n trong thời gian cÿn 2 , trong đó c -
một số hằng số, thì họ nói rằng độ phức tạp về thời gian của thuật toán này là O(n 2) (đọc “thứ tự en bình phương”). Người ta sẽ nghĩ rằng sự gia tăng to lớn về tốc độ tính toán do thế hệ máy tính kỹ thuật số hiện nay mang lại sẽ làm giảm tầm quan trọng của các thuật toán hiệu quả. Tuy nhiên, điều ngược lại xảy ra. Khi máy tính ngày càng nhanh hơn và chúng ta có thể giải quyết các vấn đề lớn hơn, thì độ phức tạp của thuật toán sẽ quyết định mức độ tăng kích thước vấn đề có thể đạt được khi tốc độ máy tăng lên. Giả sử chúng ta có năm thuật toán A1,A2,…,A5 với độ phức tạp về thời gian như sau: Ở đây, độ phức tạp về thời gian là số đơn vị thời gian cần thiết để xử lý đầu vào có kích thước n. Đặt đơn vị thời gian là một mili giây (1 giây = 1000 mili giây). Sau đó, thuật toán A1 có thể xử lý đầu vào có kích thước 1000 trong một giây, trong khi A5 có thể xử lý đầu vào có kích thước không quá 9. Trong bảng. 6.5.1. Quy mô của các vấn đề có thể được giải quyết trong một giây, một phút và một giờ bằng mỗi thuật toán trong số năm thuật toán này được đưa ra. Bảng 6.5.3. Giả sử rằng thế hệ máy tính tiếp theo sẽ nhanh hơn thế hệ hiện tại 10 lần. Trong bảng 6.5.2. cho thấy quy mô của các vấn đề chúng ta có thể giải quyết nhờ sự gia tăng tốc độ này sẽ tăng lên như thế nào. Lưu ý rằng đối với thuật toán A5, tốc độ tăng gấp 10 lần sẽ làm tăng kích thước của bài toán có thể giải được chỉ bằng ba đơn vị (xem dòng cuối cùng trong Bảng 6.5.2.), trong khi đối với thuật toán A3, kích thước của bài toán lớn hơn gấp ba lần . Bảng 6.5.4. Thay vì tác động của việc tăng tốc độ, bây giờ chúng ta hãy xem xét tác động của việc sử dụng thuật toán hiệu quả hơn. Trở lại bảng 6.5.1. Nếu lấy 1 phút làm cơ sở để so sánh thì bằng cách thay thuật toán A4 bằng thuật toán A3, chúng ta có thể giải được bài toán lớn gấp 6 lần và thay A4 bằng A2 ,
bạn có thể giải một bài toán lớn hơn 125 lần. Những kết quả này ấn tượng hơn nhiều so với mức cải thiện gấp 2 lần đạt được nhờ tốc độ gấp 10 lần. Nếu lấy 1 giờ làm cơ sở so sánh thì sự khác biệt càng trở nên rõ ràng hơn. Từ đó, chúng tôi kết luận rằng độ phức tạp tiệm cận của thuật toán đóng vai trò là thước đo quan trọng về chất lượng của thuật toán và là thước đo hứa hẹn sẽ trở nên quan trọng hơn nữa khi tốc độ tính toán tăng lên sau đó. Mặc dù thực tế là sự chú ý chính ở đây được dành cho thứ tự tăng dần của số lượng, nhưng người ta phải hiểu rằng thứ tự tăng trưởng lớn về độ phức tạp của thuật toán có thể có hằng số nhân nhỏ hơn (hằng số c trong định nghĩa của O(f(x))), hơn là mức tăng nhỏ về độ phức tạp của thuật toán khác. Trong trường hợp này, một thuật toán có độ phức tạp tăng nhanh có thể thích hợp hơn cho các bài toán nhỏ - thậm chí có thể cho tất cả các bài toán mà chúng ta quan tâm. Ví dụ: giả sử độ phức tạp về thời gian của thuật toán A1, A2, A3, A4, A5 thực tế lần lượt là 1000n, 100nÿlog(n), 10n2, n3 và 2. n Khi đó A5 sẽ là tốt nhất cho các bài toán có kích thước 2§n§9, A2 - cho các bài toán có kích thước 10§n§58, A1 - tại 59§n§1024, và A1- với n>1024.- 1. F.A Novikov. Toán rời rạc cho lập trình viên./ St. Petersburg: Peter, 2001, 304С. 2. S.V. Sudoplatov, E.V. Các yếu tố của toán học rời rạc./ M., INFRA-M, Novosibirsk, Nhà xuất bản NSTU, 3. Y.M.Erusalimsky. Toán rời rạc / M., “Sách đại học”, 2001, 279 trang. 4. A. Aho, J. Hopcroft, J. Ullman. Xây dựng và phân tích các thuật toán tính toán. / M., Mir, 1979, 536C. 5. V.N.Nefedov, V.A.Osipova Khóa học về toán rời rạc./ M., Nhà xuất bản MAI, 1992, 264P.§4.3. Định lượng và tính chất của chúng.
Chương V. Các lý thuyết hình thức.
§5.1. Định nghĩa lý thuyết hình thức
§5.2. Phép tính mệnh đề.
§5.3. Định lý suy diễn. Tính đầy đủ của IV.
§5.4. Tự động chứng minh các định lý.
§5.5. Phương pháp phân giải trong IW.
Chương VI. Các yếu tố của lý thuyết thuật toán.
§6.1. Định nghĩa thuật toán.
§6.2. Máy Turing.
q 0
…
khí
…
q m
…
bạn
q
S
Một
rS
…
§6.3. Hàm đệ quy
§6.4. Các vấn đề không thể giải quyết được về mặt thuật toán.
§6.5. Các thuật toán và độ phức tạp của chúng.
VĂN HỌC.