Lập trình logic và ràng buộc

1Lập trình logic và ràng buộc(Logic Programming and Constraint)Ts. Lê Mạnh HảiKhoa CNTT, ĐH Kỹ thuật Công nghệ TP HCM2Mở đầuI Mục đích môn học:Giới thiệu một công cụ hỗ trợ nghiên cứu trí tuệ nhân tạo: ngôn ngữ lập trình SWI-Prolog. Một số ứng dụng trong xử lý ngôn ngữ tự nhiên. II. Thời gian và nội dung: 30 tiết lý thuyết + 15 tiết bài tập Tổng quan về Prolog(3 tiết)Kỹ thuật lập trình Prolog(9 tiết)Logic và CSDL(3 tiết)Logic và Hệ chuyên gia(3 tiết)Logic và ngữ pháp (6 tiết)Logic và lập trình ràng buộc (6 tiết)Bài tập và kiểm tra giữa kỳ (15 tiết)3III Giáo trình và tài liệu tham khảoBài giảng của Lê Mạnh Hải (Lưu hành nội bộ)James Lu, Jerud J. Mead. Prolog A Tutorial Introduction. Computer Science Department Bucknell University Ulf Nilsson and Jan Maluszynsky. LOGIC, PROGRAMMING AND PROLOG (2ED). John Wiley & Sons Ltd. 2000.Phan Huy Khánh. Lập trình logic trong Prolog. Nhà xuất bản ĐH QG Hà nội. 20044IV. Đánh giá:Điểm giữa kỳ (30%): Bài kiểm tra 60 phút trên PCThi kết thúc môn (70%): Bài kiểm tra 90 phútV. Giáo viên:Ts. Lê Mạnh Hải. Khoa CNTT HUTECH. email: lm.hai@hutech.edu.vnWebsite: giangvien.hutech.edu.vnBài 1: Giới thiệu về ngôn ngữ PrologMục tiêu:Lược sử Prolog và các dòng sản phẩmCài đặt SWI-Prolog và SWI-Prolog editorCác khái niệm cơ bản và ví dụ5Lược sử Prolog và các dòngTheo Wikipedia.org “Prolog là một ngôn ngữ lập trình. "lập trình theo lô gích". Xuất hiện từ năm 1972 , mục tiêu của Prolog là giúp người dùng mô tả lại bài toán trên ngôn ngữ của logic, dựa trên đó, máy tính sẽ tiến hành suy diễn tự động dựa vào những cơ chế suy diễn có sẵn (hợp nhất, quay lui và tìm kiếm theo chiều sâu) để tìm câu trả lời cho người dùng.Cú pháp và ngữ nghĩa của Prolog đơn giản và sáng sủa, nó được người Nhật coi là một trong những nền tảng để xây dựng máy tính thế hệ thứ năm mà ở đó, thay vì phải mô tả cách giải quyết một bài toán trên máy tính, con người chỉ cần mô tả bài toán và máy tính sẽ hỗ trợ họ nốt phần còn lại.6Ý tưởng mới trong các ứng dụng cũProlog được sử dụng nhiều trong các ứng dụng của trí tuệ nhân tạo (AI) và ngôn ngữ học trong khoa học máy tính (đặc biệt là trong ngành xử lý ngôn ngữ tự nhiên NLP vì đây là mục tiêu thiết kế ban đầu của nó).” Các lĩnh vực khác: theorem proving,[8] expert systems,[9] games, automated answering systems, ontologies and sophisticated control systems.Cơ sở của Prolog là hàm mệnh đề (propositional Function) và vị từ logic (logic predicate) . Xem thêm Toán rời rạc. 78Cơ sở lý thuyết của AIAI  Phát triển các chương trình có khả năng suy luận, dựa trên lý thuyết toán học mệnh đềSuy luận giúp chương trình AI biết được tính đúng/sai của một vấn đề nào đó. Không quan trọng vấn đề đó được thực hiện như thế nào.Phép toán vị từ được hiện thực bằng ngôn ngữ lập trình trên máy tính PROLOGSuy luận logic9Giáo sư môn logic học nhận ra mình bị mất kính. Ông bèn ngồi suy luận để xem đối tượng nào đã lấy kính của mình."Ai lấy cắp? Đương nhiên là kẻ cắp rồi. Và tên này có thể bị cận thị, có thể không. Có thể hắn đã có kính, có thể chưa có.Nhưng nếu chưa có làm sao hắn có thể trông thấy kính của mình? Điều này chứng tỏ hắn không bị cận thị. Mà không bị cận thị thì đâu cần tới kính.Từ những giả thuyết trên, có thể kết luận là không ai lấy kính của mình cả. Chắc chắn nó nằm ở đâu đây thôi.Nhưng mình đã nhìn khắp rồi, không thấy gì cả. Mà mình nhìn được như vậy có nghĩa là mình đang đeo kính. Ôi may quá!!!".Một anh chàng lập trình viên cùng người yêu đi du lịch nước ngoài. Trong đoàn còn có một cặp người Anh và một cặp người Mỹ nên họ nói với nhau bằng tiếng Anh.Một hôm cả đoàn ngồi ăn bữa sáng.Anh chồng người Anh nói với vợ:"Can you pass the honey, Honey?" (Đưa anh ít mật, em yêu)Anh chồng người Mỹ nói với vợ:"Do you mind passing the sugar, Sugar?" (Chuyển cho anh chút đường, em yêu)Chàng lập trình viên tỏ ra không thua kém:"Pass me the bacon, Pig!". (Lấy cho anh thịt lợn muối, Lợn!)10Mệnh đềBầu trời xanhLoan thích LongTâm yêu Tâm (!???)Mệnh đề không biểu diễn được biểu thức X=Y+3 vì X và Y chưa có giá trị, nên không thể kết luận đúng sai.Những sự tương đương sau không biểu diễn được bằng logic mệnh đề"Không phải tất cả bánh đều ăn được" và "Chỉ một số bánh ăn được“Ứng dụng phép tam đoạn luận: A v B, !A => BCó tôi với anh mà tôi mất đồng hồ, mà tôi thì không lấy của tôi rồi!11Logic vị từ (Predicate)Predicate là vị từ mô tả tính chất của những đối tượng, hoặc quan hệ giữa chúngPhát biểu x > 3 có 2 phần: Biến xTính chất của biến x (> 3), được gọi là vị từ (predicate)Ký hiệu phát biểu P(x)⇒ P(2), P(4) là mệnh đề. Mệnh đề đầu sai.12Tổng quátcác chương trình Prolog đều yêu cầu vị từ logic ở phần đầu của một mệnh đề Horn là một vị từ dương 13Các dòng PrologSWI – Prolog: Free but strong!ISO Prolog,Edinburgh PrologQuintusSICStusGNU PrologCiao prolog14SWI-PrologTất cả free trên ãy cài lên máy tính của bạn để thực hành15Ví dụ đầu tiên1 ?- atom(foot). true.2 ?- atom(3).false.3 ?- atom('foot').true.4 ?- atom("foot").false.5 ?- blue(sky).ERROR: toplevel: Undefined procedure: blue/1 (DWIM could not correct goal)16Các vị từ có sẵnatommember and so on6 ?- member(3,[1,2,3]).true.7 ?- member(X,[1,2,3]).X = 1 ;X = 2 ;X = 3.Làm sao tìm các hàm build-in ? Help - Manual1718Các quy ướcHằng số: 3.2 Hằng chuỗi: an, binh, ‘An’, ‘Binh’Hằng logic: true, false.Biến: bắt đầu bằng chữ hoa hoặc ‘_’. Biến nặc danh _ được dùng khi không cần truy cập1920Các mệnh đề của người sử dụng: chương trình prolog.8 ?- edit(file(vd)).Chép đoạn mã sau vào file vdlikes(mary,food). likes(mary,wine). likes(john,wine). likes(john,mary).Đóng file để lưu. Load file và query14 ?- [vd].% vd compiled 0.00 sec, 1 clausestrue.15 ?- likes(mary,food).true .16 ?- likes(mary,john).false.Ví dụ 2luong(an,300).luong(binh,400).luong(hai,500).luong(tuan,400).luong(long,450).luongcaohon(X,Y):-luong(X,Z),luong(Y,T),Z>T.luongbang(X,Y):- luong(X,Z),luong(Y,T),Z=T.25 ?- luongcaohon(X,tuan).X = hai ;X = long.21Ví dụ 3: tính giai thừafactorial(0,1). factorial(N,F) :- N>0, N1 is N-1, factorial(N1,F1), F is N * F1.31 ?- factorial(5,W).W = 120 .2223Bài tậpviết chương trình tính số fibonacciTìm hiểu vị từ setof Ý nghĩa?Ví dụ?Bài kế tiếpKỹ thuật lập trình PrologĐệ quy: tháp Hà nộiXử lý danh sách . Quicksort, MergesortBó mệnh đề.Ngữ nghĩa và thứ tựXử lý file.24