ppt/theme/theme1.xml
ppt/theme/theme2.xml
ppt/notesMasters/notesMaster1.xml
ppt/notesMasters/_rels/notesMaster1.xml.rels
ppt/notesSlides/notesSlide1.xml
ppt/notesSlides/_rels/notesSlide1.xml.rels
ppt/notesSlides/notesSlide2.xml
ppt/notesSlides/_rels/notesSlide2.xml.rels
ppt/notesSlides/notesSlide3.xml
ppt/notesSlides/_rels/notesSlide3.xml.rels
ppt/notesSlides/notesSlide4.xml
ppt/notesSlides/_rels/notesSlide4.xml.rels
ppt/notesSlides/notesSlide5.xml
ppt/notesSlides/_rels/notesSlide5.xml.rels
ppt/notesSlides/notesSlide6.xml
ppt/notesSlides/_rels/notesSlide6.xml.rels
ppt/notesSlides/notesSlide7.xml
ppt/notesSlides/_rels/notesSlide7.xml.rels
ppt/notesSlides/notesSlide8.xml
ppt/notesSlides/_rels/notesSlide8.xml.rels
ppt/notesSlides/notesSlide9.xml
ppt/notesSlides/_rels/notesSlide9.xml.rels
ppt/notesSlides/notesSlide10.xml
ppt/notesSlides/_rels/notesSlide10.xml.rels
ppt/notesSlides/notesSlide11.xml
ppt/notesSlides/_rels/notesSlide11.xml.rels
ppt/notesSlides/notesSlide12.xml
ppt/notesSlides/_rels/notesSlide12.xml.rels
ppt/notesSlides/notesSlide13.xml
ppt/notesSlides/_rels/notesSlide13.xml.rels
ppt/notesSlides/notesSlide14.xml
ppt/notesSlides/_rels/notesSlide14.xml.rels
ppt/notesSlides/notesSlide15.xml
ppt/notesSlides/_rels/notesSlide15.xml.rels
ppt/notesSlides/notesSlide16.xml
ppt/notesSlides/_rels/notesSlide16.xml.rels
ppt/notesSlides/notesSlide17.xml
ppt/notesSlides/_rels/notesSlide17.xml.rels
ppt/notesSlides/notesSlide18.xml
ppt/notesSlides/_rels/notesSlide18.xml.rels
ppt/notesSlides/notesSlide19.xml
ppt/notesSlides/_rels/notesSlide19.xml.rels
ppt/notesSlides/notesSlide20.xml
ppt/notesSlides/_rels/notesSlide20.xml.rels
ppt/notesSlides/notesSlide21.xml
ppt/notesSlides/_rels/notesSlide21.xml.rels
ppt/notesSlides/notesSlide22.xml
ppt/notesSlides/_rels/notesSlide22.xml.rels
ppt/notesSlides/notesSlide23.xml
ppt/notesSlides/_rels/notesSlide23.xml.rels
ppt/notesSlides/notesSlide24.xml
ppt/notesSlides/_rels/notesSlide24.xml.rels
ppt/notesSlides/notesSlide25.xml
ppt/notesSlides/_rels/notesSlide25.xml.rels
ppt/notesSlides/notesSlide26.xml
ppt/notesSlides/_rels/notesSlide26.xml.rels
ppt/notesSlides/notesSlide27.xml
ppt/notesSlides/_rels/notesSlide27.xml.rels
ppt/notesSlides/notesSlide28.xml
ppt/notesSlides/_rels/notesSlide28.xml.rels
ppt/notesSlides/notesSlide29.xml
ppt/notesSlides/_rels/notesSlide29.xml.rels
ppt/notesSlides/notesSlide30.xml
ppt/notesSlides/_rels/notesSlide30.xml.rels
ppt/notesSlides/notesSlide31.xml
ppt/notesSlides/_rels/notesSlide31.xml.rels
ppt/notesSlides/notesSlide32.xml
ppt/notesSlides/_rels/notesSlide32.xml.rels
ppt/notesSlides/notesSlide33.xml
ppt/notesSlides/_rels/notesSlide33.xml.rels
ppt/notesSlides/notesSlide34.xml
ppt/notesSlides/_rels/notesSlide34.xml.rels
ppt/notesSlides/notesSlide35.xml
ppt/notesSlides/_rels/notesSlide35.xml.rels
ppt/notesSlides/notesSlide36.xml
ppt/notesSlides/_rels/notesSlide36.xml.rels
ppt/notesSlides/notesSlide37.xml
ppt/notesSlides/_rels/notesSlide37.xml.rels
ppt/notesSlides/notesSlide38.xml
ppt/notesSlides/_rels/notesSlide38.xml.rels
ppt/notesSlides/notesSlide39.xml
ppt/notesSlides/_rels/notesSlide39.xml.rels
ppt/notesSlides/notesSlide40.xml
ppt/notesSlides/_rels/notesSlide40.xml.rels
ppt/notesSlides/notesSlide41.xml
ppt/notesSlides/_rels/notesSlide41.xml.rels
ppt/notesSlides/notesSlide42.xml
ppt/notesSlides/_rels/notesSlide42.xml.rels
ppt/notesSlides/notesSlide43.xml
ppt/notesSlides/_rels/notesSlide43.xml.rels
ppt/notesSlides/notesSlide44.xml
ppt/notesSlides/_rels/notesSlide44.xml.rels
ppt/notesSlides/notesSlide45.xml
ppt/notesSlides/_rels/notesSlide45.xml.rels
ppt/notesSlides/notesSlide46.xml
ppt/notesSlides/_rels/notesSlide46.xml.rels
ppt/notesSlides/notesSlide47.xml
ppt/notesSlides/_rels/notesSlide47.xml.rels
ppt/notesSlides/notesSlide48.xml
ppt/notesSlides/_rels/notesSlide48.xml.rels
ppt/notesSlides/notesSlide49.xml
ppt/notesSlides/_rels/notesSlide49.xml.rels
ppt/notesSlides/notesSlide50.xml
ppt/notesSlides/_rels/notesSlide50.xml.rels
ppt/notesSlides/notesSlide51.xml
ppt/notesSlides/_rels/notesSlide51.xml.rels
ppt/notesSlides/notesSlide52.xml
ppt/notesSlides/_rels/notesSlide52.xml.rels
ppt/notesSlides/notesSlide53.xml
ppt/notesSlides/_rels/notesSlide53.xml.rels
ppt/notesSlides/notesSlide54.xml
ppt/notesSlides/_rels/notesSlide54.xml.rels
ppt/notesSlides/notesSlide55.xml
ppt/notesSlides/_rels/notesSlide55.xml.rels
ppt/notesSlides/notesSlide56.xml
ppt/notesSlides/_rels/notesSlide56.xml.rels
ppt/notesSlides/notesSlide57.xml
ppt/notesSlides/_rels/notesSlide57.xml.rels
ppt/notesSlides/notesSlide58.xml
ppt/notesSlides/_rels/notesSlide58.xml.rels
ppt/notesSlides/notesSlide59.xml
ppt/notesSlides/_rels/notesSlide59.xml.rels
ppt/notesSlides/notesSlide60.xml
ppt/notesSlides/_rels/notesSlide60.xml.rels
ppt/notesSlides/notesSlide61.xml
ppt/notesSlides/_rels/notesSlide61.xml.rels
ppt/notesSlides/notesSlide62.xml
ppt/notesSlides/_rels/notesSlide62.xml.rels
ppt/notesSlides/notesSlide63.xml
ppt/notesSlides/_rels/notesSlide63.xml.rels
ppt/notesSlides/notesSlide64.xml
ppt/notesSlides/_rels/notesSlide64.xml.rels
ppt/notesSlides/notesSlide65.xml
ppt/notesSlides/_rels/notesSlide65.xml.rels
ppt/notesSlides/notesSlide66.xml
ppt/notesSlides/_rels/notesSlide66.xml.rels
ppt/notesSlides/notesSlide67.xml
ppt/notesSlides/_rels/notesSlide67.xml.rels
ppt/notesSlides/notesSlide68.xml
ppt/notesSlides/_rels/notesSlide68.xml.rels
ppt/notesSlides/notesSlide69.xml
ppt/notesSlides/_rels/notesSlide69.xml.rels
ppt/notesSlides/notesSlide70.xml
ppt/notesSlides/_rels/notesSlide70.xml.rels
ppt/notesSlides/notesSlide71.xml
ppt/notesSlides/_rels/notesSlide71.xml.rels
ppt/notesSlides/notesSlide72.xml
ppt/notesSlides/_rels/notesSlide72.xml.rels
ppt/notesSlides/notesSlide73.xml
ppt/notesSlides/_rels/notesSlide73.xml.rels
ppt/notesSlides/notesSlide74.xml
ppt/notesSlides/_rels/notesSlide74.xml.rels
ppt/notesSlides/notesSlide75.xml
ppt/notesSlides/_rels/notesSlide75.xml.rels
ppt/notesSlides/notesSlide76.xml
ppt/notesSlides/_rels/notesSlide76.xml.rels
ppt/notesSlides/notesSlide77.xml
ppt/notesSlides/_rels/notesSlide77.xml.rels
ppt/notesSlides/notesSlide78.xml
ppt/notesSlides/_rels/notesSlide78.xml.rels
ppt/notesSlides/notesSlide79.xml
ppt/notesSlides/_rels/notesSlide79.xml.rels
ppt/notesSlides/notesSlide80.xml
ppt/notesSlides/_rels/notesSlide80.xml.rels
ppt/notesSlides/notesSlide81.xml
ppt/notesSlides/_rels/notesSlide81.xml.rels
ppt/notesSlides/notesSlide82.xml
ppt/notesSlides/_rels/notesSlide82.xml.rels
ppt/notesSlides/notesSlide83.xml
ppt/notesSlides/_rels/notesSlide83.xml.rels
ppt/notesSlides/notesSlide84.xml
ppt/notesSlides/_rels/notesSlide84.xml.rels
ppt/notesSlides/notesSlide85.xml
ppt/notesSlides/_rels/notesSlide85.xml.rels
ppt/notesSlides/notesSlide86.xml
ppt/notesSlides/_rels/notesSlide86.xml.rels
ppt/notesSlides/notesSlide87.xml
ppt/notesSlides/_rels/notesSlide87.xml.rels
ppt/slideLayouts/slideLayout1.xml
ppt/slideLayouts/_rels/slideLayout1.xml.rels
ppt/slideLayouts/slideLayout2.xml
ppt/slideLayouts/_rels/slideLayout2.xml.rels
ppt/slideLayouts/slideLayout3.xml
ppt/slideLayouts/_rels/slideLayout3.xml.rels
ppt/slideLayouts/slideLayout4.xml
ppt/slideLayouts/_rels/slideLayout4.xml.rels
ppt/slideLayouts/slideLayout5.xml
ppt/slideLayouts/_rels/slideLayout5.xml.rels
ppt/slideLayouts/slideLayout6.xml
ppt/slideLayouts/_rels/slideLayout6.xml.rels
ppt/slideLayouts/slideLayout7.xml
ppt/slideLayouts/_rels/slideLayout7.xml.rels
ppt/slideLayouts/slideLayout8.xml
ppt/slideLayouts/_rels/slideLayout8.xml.rels
ppt/slideLayouts/slideLayout9.xml
ppt/slideLayouts/_rels/slideLayout9.xml.rels
ppt/slideLayouts/slideLayout10.xml
ppt/slideLayouts/_rels/slideLayout10.xml.rels
ppt/slideLayouts/slideLayout11.xml
ppt/slideLayouts/_rels/slideLayout11.xml.rels
ppt/slideLayouts/slideLayout12.xml
ppt/slideLayouts/_rels/slideLayout12.xml.rels
ppt/slideLayouts/slideLayout13.xml
ppt/slideLayouts/_rels/slideLayout13.xml.rels
ppt/slideLayouts/slideLayout14.xml
ppt/slideLayouts/_rels/slideLayout14.xml.rels
ppt/slideLayouts/slideLayout15.xml
ppt/slideLayouts/_rels/slideLayout15.xml.rels
ppt/slideLayouts/slideLayout16.xml
ppt/slideLayouts/_rels/slideLayout16.xml.rels
ppt/slideLayouts/slideLayout17.xml
ppt/slideLayouts/_rels/slideLayout17.xml.rels
ppt/slideLayouts/slideLayout18.xml
ppt/slideLayouts/_rels/slideLayout18.xml.rels
ppt/slideLayouts/slideLayout19.xml
ppt/slideLayouts/_rels/slideLayout19.xml.rels
ppt/slideMasters/slideMaster1.xml
ppt/slideMasters/_rels/slideMaster1.xml.rels
ppt/slides/slide1.xml
ppt/slides/_rels/slide1.xml.rels
ppt/slides/slide2.xml
ppt/slides/_rels/slide2.xml.rels
ppt/slides/slide3.xml
ppt/slides/_rels/slide3.xml.rels
ppt/slides/slide4.xml
ppt/slides/_rels/slide4.xml.rels
ppt/slides/slide5.xml
ppt/slides/_rels/slide5.xml.rels
ppt/slides/slide6.xml
ppt/slides/_rels/slide6.xml.rels
ppt/slides/slide7.xml
ppt/slides/_rels/slide7.xml.rels
ppt/slides/slide8.xml
ppt/slides/_rels/slide8.xml.rels
ppt/slides/slide9.xml
ppt/slides/_rels/slide9.xml.rels
ppt/slides/slide10.xml
ppt/slides/_rels/slide10.xml.rels
ppt/slides/slide11.xml
ppt/slides/_rels/slide11.xml.rels
ppt/slides/slide12.xml
ppt/slides/_rels/slide12.xml.rels
ppt/slides/slide13.xml
ppt/slides/_rels/slide13.xml.rels
ppt/slides/slide14.xml
ppt/slides/_rels/slide14.xml.rels
ppt/slides/slide15.xml
ppt/slides/_rels/slide15.xml.rels
ppt/slides/slide16.xml
ppt/slides/_rels/slide16.xml.rels
ppt/slides/slide17.xml
ppt/slides/_rels/slide17.xml.rels
ppt/slides/slide18.xml
ppt/slides/_rels/slide18.xml.rels
ppt/slides/slide19.xml
ppt/slides/_rels/slide19.xml.rels
ppt/slides/slide20.xml
ppt/slides/_rels/slide20.xml.rels
ppt/slides/slide21.xml
ppt/slides/_rels/slide21.xml.rels
ppt/slides/slide22.xml
ppt/slides/_rels/slide22.xml.rels
ppt/slides/slide23.xml
ppt/slides/_rels/slide23.xml.rels
ppt/slides/slide24.xml
ppt/slides/_rels/slide24.xml.rels
ppt/slides/slide25.xml
ppt/slides/_rels/slide25.xml.rels
ppt/slides/slide26.xml
ppt/slides/_rels/slide26.xml.rels
ppt/slides/slide27.xml
ppt/slides/_rels/slide27.xml.rels
ppt/slides/slide28.xml
ppt/slides/_rels/slide28.xml.rels
ppt/slides/slide29.xml
ppt/slides/_rels/slide29.xml.rels
ppt/slides/slide30.xml
ppt/slides/_rels/slide30.xml.rels
ppt/slides/slide31.xml
ppt/slides/_rels/slide31.xml.rels
ppt/slides/slide32.xml
ppt/slides/_rels/slide32.xml.rels
ppt/slides/slide33.xml
ppt/slides/_rels/slide33.xml.rels
ppt/slides/slide34.xml
ppt/slides/_rels/slide34.xml.rels
ppt/slides/slide35.xml
ppt/slides/_rels/slide35.xml.rels
ppt/slides/slide36.xml
ppt/slides/_rels/slide36.xml.rels
ppt/slides/slide37.xml
ppt/slides/_rels/slide37.xml.rels
ppt/slides/slide38.xml
ppt/slides/_rels/slide38.xml.rels
ppt/slides/slide39.xml
ppt/slides/_rels/slide39.xml.rels
ppt/slides/slide40.xml
ppt/slides/_rels/slide40.xml.rels
ppt/slides/slide41.xml
ppt/slides/_rels/slide41.xml.rels
ppt/slides/slide42.xml
ppt/slides/_rels/slide42.xml.rels
ppt/slides/slide43.xml
ppt/slides/_rels/slide43.xml.rels
ppt/slides/slide44.xml
ppt/slides/_rels/slide44.xml.rels
ppt/slides/slide45.xml
ppt/slides/_rels/slide45.xml.rels
ppt/slides/slide46.xml
ppt/slides/_rels/slide46.xml.rels
ppt/slides/slide47.xml
ppt/slides/_rels/slide47.xml.rels
ppt/slides/slide48.xml
ppt/slides/_rels/slide48.xml.rels
ppt/slides/slide49.xml
ppt/slides/_rels/slide49.xml.rels
ppt/slides/slide50.xml
ppt/slides/_rels/slide50.xml.rels
ppt/slides/slide51.xml
ppt/slides/_rels/slide51.xml.rels
ppt/slides/slide52.xml
ppt/slides/_rels/slide52.xml.rels
ppt/slides/slide53.xml
ppt/slides/_rels/slide53.xml.rels
ppt/slides/slide54.xml
ppt/slides/_rels/slide54.xml.rels
ppt/slides/slide55.xml
ppt/slides/_rels/slide55.xml.rels
ppt/slides/slide56.xml
ppt/slides/_rels/slide56.xml.rels
ppt/slides/slide57.xml
ppt/slides/_rels/slide57.xml.rels
ppt/slides/slide58.xml
ppt/slides/_rels/slide58.xml.rels
ppt/slides/slide59.xml
ppt/slides/_rels/slide59.xml.rels
ppt/slides/slide60.xml
ppt/slides/_rels/slide60.xml.rels
ppt/slides/slide61.xml
ppt/slides/_rels/slide61.xml.rels
ppt/slides/slide62.xml
ppt/slides/_rels/slide62.xml.rels
ppt/slides/slide63.xml
ppt/slides/_rels/slide63.xml.rels
ppt/slides/slide64.xml
ppt/slides/_rels/slide64.xml.rels
ppt/slides/slide65.xml
ppt/slides/_rels/slide65.xml.rels
ppt/slides/slide66.xml
ppt/slides/_rels/slide66.xml.rels
ppt/slides/slide67.xml
ppt/slides/_rels/slide67.xml.rels
ppt/slides/slide68.xml
ppt/slides/_rels/slide68.xml.rels
ppt/slides/slide69.xml
ppt/slides/_rels/slide69.xml.rels
ppt/slides/slide70.xml
ppt/slides/_rels/slide70.xml.rels
ppt/slides/slide71.xml
ppt/slides/_rels/slide71.xml.rels
ppt/slides/slide72.xml
ppt/slides/_rels/slide72.xml.rels
ppt/slides/slide73.xml
ppt/slides/_rels/slide73.xml.rels
ppt/slides/slide74.xml
ppt/slides/_rels/slide74.xml.rels
ppt/slides/slide75.xml
ppt/slides/_rels/slide75.xml.rels
ppt/slides/slide76.xml
ppt/slides/_rels/slide76.xml.rels
ppt/slides/slide77.xml
ppt/slides/_rels/slide77.xml.rels
ppt/slides/slide78.xml
ppt/slides/_rels/slide78.xml.rels
ppt/slides/slide79.xml
ppt/slides/_rels/slide79.xml.rels
ppt/slides/slide80.xml
ppt/slides/_rels/slide80.xml.rels
ppt/slides/slide81.xml
ppt/slides/_rels/slide81.xml.rels
ppt/slides/slide82.xml
ppt/slides/_rels/slide82.xml.rels
ppt/slides/slide83.xml
ppt/slides/_rels/slide83.xml.rels
ppt/slides/slide84.xml
ppt/slides/_rels/slide84.xml.rels
ppt/slides/slide85.xml
ppt/slides/_rels/slide85.xml.rels
ppt/slides/slide86.xml
ppt/slides/_rels/slide86.xml.rels
ppt/slides/slide87.xml
ppt/slides/_rels/slide87.xml.rels
ppt/presProps.xml
ppt/tableStyles.xml
ppt/presentation.xml
ppt/_rels/presentation.xml.rels
_rels/.rels
ppt/media/image3.jpg
ppt/media/image39.png
ppt/media/image64.png
ppt/media/image56.png
ppt/media/image81.png
ppt/media/image13.png
ppt/media/image8.png
ppt/media/image51.jpg
ppt/media/image20.png
ppt/media/image63.png
ppt/media/image72.png
ppt/media/image22.png
ppt/media/image82.png
ppt/media/image46.png
ppt/media/image38.png
ppt/media/image78.jpg
ppt/media/image65.png
ppt/media/image29.png
ppt/media/image55.png
ppt/media/image12.png
ppt/media/image73.png
ppt/fonts/Ubuntu-boldItalic.fntdata
ppt/media/image30.png
ppt/media/image47.png
ppt/media/image21.png
ppt/media/image40.png
ppt/media/image10.png
ppt/media/image83.png
ppt/media/image70.png
ppt/fonts/Ubuntu-regular.fntdata
ppt/media/image53.png
ppt/media/image6.png
ppt/media/image24.png
ppt/media/image67.png
ppt/media/image11.png
ppt/media/image37.png
ppt/media/image19.png
ppt/media/image5.png
ppt/media/image54.png
ppt/media/image41.png
ppt/media/image36.png
ppt/media/image1.jpg
ppt/media/image66.png
ppt/media/image79.png
ppt/media/image84.png
ppt/media/image23.png
ppt/fonts/Ubuntu-bold.fntdata
ppt/media/image49.png
ppt/fonts/Ubuntu-italic.fntdata
ppt/media/image26.png
ppt/media/image4.png
ppt/media/image17.png
ppt/media/image42.png
ppt/media/image69.png
ppt/media/image85.png
ppt/media/image18.png
ppt/media/image50.png
ppt/media/image35.png
ppt/media/image48.jpg
ppt/media/image52.png
ppt/media/image33.png
ppt/media/image68.png
ppt/media/image16.png
ppt/media/image43.png
ppt/fonts/Comfortaa-regular.fntdata
ppt/media/image2.png
ppt/media/image25.png
ppt/media/image77.png
ppt/media/image34.png
ppt/media/image60.png
ppt/media/image58.png
ppt/media/image45.png
ppt/media/image28.png
ppt/media/image15.png
ppt/media/image61.png
ppt/media/image31.png
ppt/media/image59.png
ppt/media/image74.png
ppt/media/image27.png
ppt/media/image76.png
ppt/media/image7.gif
ppt/media/image57.png
ppt/media/image44.png
ppt/media/image14.png
ppt/media/image80.png
ppt/media/image9.png
ppt/media/image71.jpg
ppt/media/image32.png
ppt/media/image62.png
ppt/fonts/Comfortaa-bold.fntdata
ppt/media/image75.png
[Content_Types].xml
‹#›
*
*
*
*
*
‹#›
‹#›
*
*
*
*
*
‹#›
‹#›
*
‹#›
*
‹#›
*
*
*
‹#›
‹#›
*
‹#›
‹#›
*
*
*
*
*
‹#›
*
‹#›
‹#›
*
‹#›
‹#›
‹#›
‹#›
‹#›
*
‹#›
‹#›
‹#›
‹#›
‹#›
‹#›
‹#›
‹#›
‹#›
xx% ‹#›
‹#›
‹#›
‹#›
Knowledge Representation: Logic [ AIMA 4G ] Chapter 7 ( Optional: 7.6-7.7) COSC1127/1125 Artificial Intelligence Semester 2, 2021 Prof. Sebastian Sardina * Many slides are based on those from Hector Levesque and Ron Branchman, those of James Harland, and those of Pascal Poupart.
— Wominjeka! Welcome! I acknowledge, and invite you all to acknowledge, the Traditional Owners (Wurundjeri people of the Kulin Nations) of the land on which we will conduct this session for AI21. I recognise their continuing connection to land, waters and culture, as well as the challenges and injustices that continue up to our times, unfortunately.
IMPORTANT DISCLAIMER These pack of slides are NOT core study material . The core & main material is the book or any specific resources given for the week. The slides in this presentations were prepared only for supporting the instructor during the lectorial and only some of them have been used in the session as needed. These pack of slides do not represent the complete material of the week , but only a few bits here and there around what was discussed in lectorials. Most of the week content will NOT show up in this pack of slides. Please refer to the book (and any resources specifically given) for a comprehensive coverage of the week material.
I have Pacman dreams…
Overview for … Book-keeping info & news. Project 0 & Project 1 Project 2: team formation Questions? Representing knowledge and reasoning. Propositional Syntax & Semantics. Propositional Resolution.
From Project 1 to 2 Project 1 is finished, we will be marking it soon… Time to start Project 2 – Adversarial Search First thing is to register your team! See #100 Deadline for teams: Wed Aug 11 After that, I will assign teams randomly – no changes then. Teams of 3 as a default. Teams of 2 if: You want to do Project Contest in a group of 4. Send me an email to discuss. You have just 1 team-mate so far. GitHub Template coming soon… For ONLY when you have a team!
Project 0 + 1 lessons.. P0 t o make “cheap” errors now and avoid them later for the “real” projects! Double check tag and certification: Is my tag in the GitHub remote repo? Have I received my certification email receipt? And before and above all: style.visibility
style.visibility style.visibility style.visibility
style.visibility style.visibility style.visibility style.visibility
Ownership matters! style.visibility style.visibility
Remember drop-in lab + consultation Pacman drop-in labs on Fridays No booking, in CU Monday 4pm-5pm Consultation Time via booking in MT
90%+ said YES!
Some feedback… “Assignment was more interactive than other subject assignments” “ Heuristic is hard to write” “ Very nice assignment. I quite enjoyed implementing the different algorithms. I wish I could have completed the heuristic questions 100% though very tricky especially Q7.” “ pretty brutal for those of us who havent used python much. shoudld be worth more than 7% considering how much time i put into this” “It is a very engaging project.” “ While it was indeed a fun project, I feel the amount of work involved should be represented as more than just 7% of the course. Regardless, it was very interesting and I very much appreciated the inclusion of the autograder giving direct on the spot feedback.” “Autograder is very helpful in gauging progress.” “Overall I’d say a tough but fair task.” Projects 1 & 2 are the “foundations” for the main contest project. So, consider them as stepping stones, a checkpoint to the final main project. I recognize they are quick & challenging, including catching up with Python. That’s partly why it is “just” 7%! (used to be 5%!) style.visibility style.visibility style.visibility style.visibility style.visibility style.visibility style.visibility style.visibility style.visibility
Some feedback (cont.) … “Very nice assignment. I quite enjoyed implementing the different algorithms. I wish I could have completed the heuristic questions 100% though very tricky especially Q7.” “While it’s only 7% and that in some cases may have alleviated stress, I found the comments about how important this assignment was for upcoming ones extremely unhelpful. It did not serve as motivation to me and only stressed me out when I got stuck due to fearing falling behind in later assignments. What I did complete, however, I learned a great deal from and felt accomplished for finishing.” “Was a great assignment. Would have loved a small session to briefly explain the codebase but I guess its fine as its part of the learning experience. Great work from teaching team to make learning fun.” “Nothing against the assessment. I did however underestimate the work required to complete it and I hold myself accountable at all costs. Will be working harder on the future assessments.” Ownership! style.visibility style.visibility style.visibility style.visibility style.visibility
On Q7 – Heuristic “It is difficult to get a good heuristic function applying to Q7 to find the shortest path in a second. I always end up with time out with various methodologies. If possible, would you please give a hint on Q7 during the lectorial? Really want to make it work. Thanks.” Indeed, it is one of the challenging ones. At the top level of Bloom’s hierarchy. It is OK to struggle on that. Aim is to have a first exposure . We will discuss ideas and tips for this question in THIS Friday drop-in session on Friday, join us!
What? No “rough” emails or posts? Of course yes, there were, but a minority. Most were: Thankful. Respectful of our work & effort. Appreciative. Well & carefully written. Assuming own mistakes and limitations, and challenges. Appreciating of the learning journey. So, THANKS! style.visibility style.visibility style.visibility style.visibility style.visibility style.visibility style.visibility style.visibility style.visibility style.visibility
Remember drop-in lab + consultation Pacman drop-in labs on Fridays No booking, in CU Monday 4pm-5pm Consultation Time via booking in MT
Questions?
Where is search today? IDS? style.visibility ppt_y
Weeks 4 and 5: KR&R
Knowledge Representation & Reasoning Chapter 7 : Provides a useful motivation for logic, and an introduction to some basic ideas. Also introduces propositional logic, which is a good background for first-order logic. Much covered in Discrete Structures In our AI course we want to focus on : Logic as a knowledge representation formalism. syntax vs semantics Logic to infer implicit conclusions: reasoning propositional AND first-order resolution
Why logic in CS & AI? Again? Why!? It is part of the curriculum to get you degree. It is fun! Logic is fun! Logical thinking is useful in life: think straight. Logic is the foundation of maths. Logic is the foundation of CS! Logic is the foundations of AI! style.visibility style.visibility style.visibility style.visibility style.visibility style.visibility
CS & AI style.visibility style.visibility style.visibility
“Computational Thinking”… ‹#› What is “computation”? What does it have to do with (human) “thinking”? “Computation is the process of taking symbolic structures , breaking them apart, comparing them, and reassembling them according to a precise recipe called a procedure . The symbols at the start of the procedure are called the inputs . The symbols at the end of the procedure are called the outputs . The procedure is called on the inputs and returns the outputs. It is important to keep track of where you are and to follow the instructions in the procedure exactly . (You may not be able to figure out why you are doing the steps involved. No matter.)” – Computation as Thinking , H. Levesque style.visibility style.visibility style.visibility style.visibility style.visibility style.visibility
Why KR&R in AI? A bit of history… We have been interested in understanding the phenomenon of rational thinking/argument/reasoning for long long time…. Aristotele 4th BC Gottfried Leibniz 17th Century Syllogisms Premise A Premise B —————— Conclusion C Ideas , (objects of ordinary thought) are like numbers . It will be sufficient to manipulate symbols standing for them according to certain rules. One will be able to go from one idea to the next idea just by doing symbolic manipulation according to certain unambiguous rules. George Boole 19th Century … but also those universal laws of thought which are the basis of all reasoning, and which, whatever they may be as to their essence, are at least mathematical as to their form . Gottlob Frege 19th Century First-order logic: variables, for all x , some x . “logicism” : arithmetic can be reduced to logic, no intuition needed Ada Lovelace 19th Century Computation beyond pure calculations… style.visibility style.visibility style.visibility style.visibility style.visibility style.visibility style.visibility style.visibility style.visibility style.visibility style.visibility style.visibility style.visibility style.visibility style.visibility style.visibility style.visibility
History of thinking, logic, CS and AI. Aristotele 4th century BC Gottfried Leibniz 17th Century George Boole 19th Century Gottlob Frege 19th Century Ada Lovelace 19th Century Bertrand Russell 20 th Century David Hilbert 19th Century Kurt Godel 20th Century Alan Turing 20th Century John McCarthy 20th Century style.visibility style.visibility style.visibility style.visibility style.visibility style.visibility style.visibility style.visibility style.visibility style.visibility style.visibility style.visibility
What is knowledge? Easier question: how do we talk about it? We say “John knows that …” and fill the blank with a proposition: – can be true / false, right / wrong Contrast: “John fears that …” – same content, different attitude Other forms of knowledge: • know how, who, what, when, … • sensorimotor: typing, riding a bicycle • affective: deep understanding The main idea: Taking the world to be one way and not another. style.visibility
Why Knowledge for AI? For sufficiently complex systems, it is sometimes useful to describe systems in terms of beliefs , goals, fears, intentions. e.g. in a game-playing program: “because it believed its queen was in danger, but wanted to still control the center of the board.” more useful than description about actual techniques used for deciding how to move: “because evaluation procedure P using minimax returned a value of +7 for this position” = taking an intentional stance ( Dan Dennett ) • sometimes anthropomorphizing is inappropriate e.g. thermostats
What is representation? Symbols standing for things in the world: First aid Women “John” John “John loves Mary” The proposition that John loves Mary Knowledge representation: symbolic encoding of propositions believed (by some agent)
What is reasoning? Manipulation of symbols encoding propositions to produce representations of new propositions. Analogy: arithmetic “1011” + “10” ===> “1101” eleven two thirteen “John is Mary’s father” “John is an adult male” style.visibility
Why bother? Why not “compile out” knowledge into specialized procedures? distribute KB to procedures that need it almost always achieves better performance No need to think. Just do it! riding a bike driving a car playing chess? doing math? staying alive?? Skills (Hubert Dreyfus): novices think; experts react But, why don’t we “compile out” databases into the specialized software? style.visibility
Reporting Colours of Things… EXAMPLE 1: printColour(snow) :- !, write(“It’s white.”). printColour(grass) :- !, write(“It’s green.”). printColour(sky) :- !, write(“It’s yellow.”). printColour(X) :- write(“Beats me.”). EXAMPLE 2: printColour(X) :- colour(X,Y), !, write(“It’s “), write(Y), write(“.”). printColour(X) :- write(“Beats me.”). colour(snow,white). colour(sky,yellow). colour(X,Y) :- madeof(X,Z), colour(Z,Y). madeof(grass,vegetation). colour(vegetation,green). Knowledge compiled out into specialized procedures Separate collection of symbolic structure a la KR: knowledge-base style.visibility style.visibility style.visibility style.visibility style.visibility
Advantages of KB Systems Knowledge-based system most suitable for open-ended tasks. can structurally isolate reasons for particular behaviour Good for: Explanation and justification “Because grass is a form of vegetation.” Informability: debugging the KB “No the sky is not yellow. It’s blue.” Extensibility: new relations “Canaries are yellow.” Extensibility: new applications returning a list of all the white things painting pictures Knowledge-bases kind of “fancy” databases. 🙂 style.visibility
Logic, Proofs, Databases & AI KRR
Logic, Proofs, Databases & AI KRR QUERY: Is ɸ true? ɸ 1 , ɸ n , …, ɸ n , style.visibility
Why reasoning? Want knowledge to affect action: not do action A if sentence P is in KB. but do action A if world believed in satisfies P. Difference: P may not be explicitly represented. Need to apply what is known in general to the particulars of a given situation. Example: “Patient x is allergic to medication m.” “Anybody allergic to medication m is also allergic to m’.” Is it OK to prescribe m’ for x ? Usually need more than just DB-style retrieval of facts in the KB.
Entailment Sentences P 1 , P 2 , …, P n entail sentence P iff the truth of P is implicit in the truth of P 1 , P 2 , …, P n . If the world is such that it satisfies the P i ‘s then it must also satisfy P. Inference : the process of calculating entailments sound: get only entailments complete: get all entailments Logic : study of entailment relations languages truth rules of inference First-order logic (FOL) or predicate calculus
Knowledge + Reasoning Intelligent systems = a knowledge base + inference engine Knowledge base (KB) —> domain-dependent “Dogs are mammals’’ ===> ∀x Dog(x) →Mammal(x) “Fido is a dog” ===> Dog(fido) Inference engine —> domain-independent ` If A and A → B are true, then B is true’
Propositional Logic (very quickly!) Check xkcd comics!
Logic for reasoning Logic is all about (implicit) consequences `If I assume KB, I can conclude ɸ query : KB ╞ ɸ query `Whenever KB is true, ɸ query must be true’ Entailment relation A logic (propositional, FOL, etc) has three components : Syntax: how to write ideas. Semantics : meaning of syntax. Inference methods: derive/extract implicit ideas. style.visibility
Propositional Logic in 1 slide Sentences/statements built from ( SYNTAX ): basic propositions: P, Q, R, … sentences and logical connectives: ¬, ∧, ∨, ⇒, ⇔ ¬P (negation), P ∧ Q (conjunction), P ∨ Q (disjunction), P ⇒ Q (implication) is the same as (¬P ∨ Q) P ⇔ Q (biconditional) is the same as (P ⇒ Q) ∧(Q ⇒ P) An interpretation is a truth valuation ( SEMANTICS ) “one way the world could turn out to be” each basic proposition is True (T) or False (F) complex formulas valuations from simpler formulas + specific meaning of logical connectives. Truth-tables: express all interpretations. Inference rules/methods: De Morgan’s laws (distribute negation) Modus ponens (deductive reasoning) Resolution refutation . style.visibility style.visibility style.visibility style.visibility style.visibility style.visibility style.visibility style.visibility style.visibility style.visibility style.visibility style.visibility style.visibility style.visibility style.visibility
Example: Model 4-Queens problem {4135191E-EBDB-4B39-89FD-899264298190} 1 2 3 4 1 2 3 4 Q ij = “there is a queen in (i, j)” What if we have 80×80 board? At least one queen in row 1: Q 11 ∨ Q 12 ∨ Q 13 ∨ Q 14 At most one queen in row 1: Q 11 → ¬Q 12 ∧ ¬Q 13 ∧ ¬Q 14 Q 12 → ¬Q 11 ∧ ¬Q 13 ∧ ¬Q 14 Q 13 → ¬Q 11 ∧ ¬Q 12 ∧ ¬Q 14 Q 14 → ¬Q 11 ∧ ¬Q 12 ∧ ¬Q 13 style.visibility
Conditionals (implies): P —> Q Q = “I will be in your city” P = “You want to hang out” P —> Q “If P, then Q” what if ¬P? Q or ¬Q? style.visibility style.visibility style.visibility style.visibility style.visibility style.visibility style.visibility
Implies as OR P→Q means: “ if P is true, then Q is true” P→Q false if and only if P is true and Q is false P→Q false iff P∧¬Q is true P→Q true iff P∧¬Q is false P→Q true iff ¬(P∧¬Q) is true P→Q true iff ¬P∨Q is true P→Q true if and only if ¬P∨Q is true P→Q↔(¬P∨Q) is true style.visibility style.visibility style.visibility style.visibility style.visibility style.visibility style.visibility style.visibility
Knowledge Base (KB) Knowledge base Encode problem description and any knowledge that could help solve the problem. Database of facts and constraints. Possible language: propositional logic . Entailment What can we derive/conclude from KB? KB |= α formula α “ follows ” from KB
Semantics: What is truth?
Solving t he Zebra/Einstein Puzzle The Englishman lives in the Red house The Spaniard has a Dog The Japanese is a Painter The Italian drinks Tea The Violinist drinks Fruit juice The Sculptor breeds Snails The Diplomat lives in the Yellow house The Green house is on the right of the White house The owner of the Green house drinks Coffee The owner of the middle house drinks Milk The Norwegian lives next door to the Blue house The Norwegian lives in the first house on the left The Fox is in the house next to the Doctor’s The Horse is next to the Diplomat’s 1 2 3 4 5 Who owns the Zebra? Who drinks Water? style.visibility
Reasoning about Zebra Domain We want to check whether KB zebra ╞ ɸ query ? where: KB zebra is the knowledge base of the Zebra puzzle domain. Set of all propositional formulas expressing each piece of information (e.g., “The Spaniard has a Dog” ) ɸ query is the query formula: Is the Zebra in house 3? ɸ query = A 3zebra Does the Italian own the Zebra? ɸ query = (O 1italian ∧ A 1zebra ) ∨ ….. ∨ (O 5italian ∧ A 5zebra ) All models of KB zebra are models of ɸ query style.visibility
Semantics: Models ‹#› KB zebra ╞ ɸ query : all models of KB are models of ɸ query A model of a formula S is an interpretation in which S is true. ???? An interpretation is “one way the world could turn out to be”. In propositional logic, each possible truth assignment/row. {4135191E-EBDB-4B39-89FD-899264298190} P Q ¬ P P ∧ Q P ∨ Q P → Q P ↔ Q F F T F F T T F T T F T T F T F F F T F F T T F T T T T style.visibility style.visibility style.visibility
Satisfaction A formula ɸ is: valid or a tautology : it is true in every interpretation satisfiable : there is an interpretation that makes it true unsatisfiable or contradiction : it is false in every inter. Two formulae ɸ 1 and ɸ 2 are logically equivalent (same truth table) iff formula ɸ 1 ↔ ɸ 2 is a tautology In propositional logic, ɸ 1 and ɸ 1 have the same truth value in every interpretation.
From Entailment to Satisfiability KB ╞ ɸ iff all models of KB are models of ɸ (every interpretation where KB is true, makes ɸ true) iff Formula (KB→ɸ) is valid (a tautology) (i.e., true in all interpretations: TRUE ╞ KB → ɸ ) iff (KB ∧ ¬ɸ) is unsatisfiable (a contradiction) (i.e., the formula KB ∧ ¬ɸ is false in all interpretations) style.visibility style.visibility style.visibility style.visibility style.visibility style.visibility style.visibility style.visibility style.visibility style.visibility
From Entailment to Satisfiability (P ∨ Q) ∧ ¬(P ∧ ¬ Q) ╞ ¬ R → Q iff all models of (P ∨ Q) ∧ ¬(P ∧ ¬Q) are models of ¬ R → Q iff Formula [(P ∨ Q) ∧ ¬(P ∧ ¬Q)]→( ¬ R → Q) is valid (i.e., true in all interpretations: TRUE ╞ KB → ɸ ) iff [(P ∨ Q) ∧ ¬(P ∧ ¬Q)] ∧ ¬( ¬ R → Q) is unsatisfiable (i.e., the formula is false in all interpretations) style.visibility style.visibility style.visibility style.visibility style.visibility style.visibility style.visibility style.visibility style.visibility style.visibility
Inference Methods How do we check that KB ╞ ɸ applies? Suppose we want to check whether: (P ∨ Q) ∧ ¬(P ∧ ¬ Q) ╞ ¬ R → Q Automatic p rocess of verifying the truth of a formula. Simple inference algorithm: First, b uild a truth table that enumerates all models . Then, v erify that formula ɸ is true in all models where KB is true . style.visibility
Methods of Inference KB ┣ M ɸ means: `We can show KB implies ɸ by algorithmic method M’ M is sound if when KB ┣ M ɸ , it is the case that KB ╞ ɸ M is complete when KB ╞ ɸ , it is the case that KB ┣ M ɸ There are many such methods M: building a truth table: Hopeless! exponential number of interpretations/rows to check resolution (with lots of variants), natural deduction, sequent calculi, tableaux systems, Hilbert-type systems, … style.visibility style.visibility
Let’s do a 10’ break…
Formal Proofs by Resolution style.visibility
Inference Process of verifying the truth of a formula. How do we check that KB ╞ a holds? Simple inference algorithm: Build a truth table that enumerates all models Verify that formula is true in all models where KB is true. Suppose we want to check if (P ∧ Q) ╞ (R ∨ Q) ?
Check (P ∧ Q) ╞ (R ∨ Q) ? {4135191E-EBDB-4B39-89FD-899264298190} P Q R P ∧ Q R ∨ Q (P ∧ Q) ⇒ (R ∨ Q) T T T T T T T T F T T T T F T F T T T F F F F T F T T F T T F T F F T T F F T F T T F F F F F T
Entailment as Satisfiability Building a truth table is very inefficient, hopeless! exponential in the number of variables. Alternatives: backtracking (Prolog), resolution , etc. Rewrite “KB |= ɸ” as KB’ = (KB ∧ ¬ ɸ) Put KB’ in a convenient “style” (CNF) (but equivalent!) CNF = Conjunctive Normal Form Prove that KB’ is not satisfiable (i.e., unsatisfiable) there is no model for which KB is true, but ɸ is false So, if KB is true, a must be true as well!
CNF: Syntax Convenience KB may contain any formula that follows the syntax of our simple logic. Inconvenient: too many possible formula Can we simplify syntax? YES! Conjunctive normal form (CNF) Only use ∧, ∨, ¬ Conjunction of clauses, where each clause is a disjunction of (possibly negated) literals Example: (P ∨ Q ∨ R) ∧ (¬P ∨ S) ∧ (¬Q ∨ R)
CNF: Conjunctive Normal Form Conjunctions of disjunctions of literals Propositional atoms: P , Q , R, etc. are all atoms Literal: an atom or negated atom P , Q , ¬P , ¬Q are all literals Clause: a disjunction of literals (¬P ∨ Q ∨ ¬R) is a clause P and ¬R are also legal clauses CNF Formula: a conjunction of clauses (¬P ∨ Q ∨ ¬R) is a CNF (¬P ∨ Q ∨ ¬R) ∧ (R) ∧ (P ∨ ¬Q) is a CNF (¬R ∧ (P ∨ ¬Q)) → (P ∨ ¬Q) is NOT a CNF! style.visibility style.visibility style.visibility style.visibility style.visibility style.visibility style.visibility style.visibility style.visibility style.visibility style.visibility style.visibility
CNF: Conjunctive Normal Form
From any formula to CNF formulas Can we transform any formula or KB into CNF? YES! Logical equivalence rules ¬(¬A) ≡ A (A → B) ≡ ¬A ∨ B (A ↔ B) ≡ (A → B) ∧ (B → A) ¬(A ∨ B) ≡ (¬A ∧ ¬B) ¬(A ∧ B) ≡ (¬A ∨ ¬B) (A ∨ (B ∧ C)) ≡ ((A ∨ B) ∧ (A ∨ C)) Can every KB be transformed in CNF in polynomial time and space? No: last rule may yield exponentially many clauses
From formula to CNF: Example Take the following non-CNF formula: (P ∨ Q) ∧ ¬(P ∧ ¬ Q) ∧ ¬(¬ R → Q) (P ∨ Q) ∧ ¬(P ∧ ¬Q) ∧ ¬(¬¬R ∨ Q) [(A → B) ≡ ¬A ∨ B] (P ∨ Q) ∧ ¬(P ∧ ¬Q) ∧ ¬(R ∨ Q) ¬(¬A) ≡ A (P ∨ Q) ∧ ¬(P ∧ ¬Q) ∧ ¬R ∧ ¬Q ¬(A ∨ B) ≡ (¬A ∧ ¬B) (P ∨ Q) ∧ (¬P ∨ ¬¬Q) ∧ ¬R ∧ ¬Q ¬(A ∧ B) ≡ (¬A ∨ ¬B) (P ∨ Q) ∧ (¬P ∨ Q) ∧ (¬R) ∧ (¬Q) ¬(¬A) ≡ A DONE! Obtained a CNF with 4 clauses: { (P ∨ Q), (¬P ∨ Q), (¬R), (¬Q) } { {P, Q}, {¬P, Q}, {¬R}, {¬Q} } CNF as a set! style.visibility style.visibility style.visibility style.visibility style.visibility style.visibility style.visibility style.visibility style.visibility style.visibility style.visibility style.visibility style.visibility
Main resolution step : Resolvent Consider clauses ( P ∨ Q) and ( ¬ P ∨ R) are true : If P is true, (P ∨ Q) is true and (¬ P ∨ R) is just R If P is false, (¬ P ∨ R) is true and (P ∨ Q) is just Q Resolution Step: reduce ( P ∨ Q) and ( ¬ P ∨ R) to clause (R ∨ Q) (then (P ∨ Q) ∧ (¬P ∨ R) ╞ (R ∨ Q)) (consider P and ( ¬ P ∨ R) , and (P ∨ Q) and ¬ P ) Clause (R ∨ Q) is the resolvent of (P ∨ Q) and (¬ P ∨ R) The resolvent was “implicit” knowledge style.visibility
Resolution as a Graph Resolution Step: reduce (P ∨ Q) and (¬ P ∨ R) to clause ( R ∨ Q) Clause (R ∨ Q) is the resolvent of (P ∨ Q) and (¬ P ∨ R) (P ∨ Q) ( ¬ P ∨ R) (R ∨ Q)
Resolution as a Graph ( P ∨ Q ∨ ¬W ) ( ¬W ∨ ¬ P ∨ R) (Q ∨ ¬W ∨ R) ( ¬W ∨ R) ( ¬ Q) (W) Unit resolution Resolution step ( ¬ R) () Derive empty clause! (FALSE!)= (R) KB (green boxes) yields FALSE! ∴ The KB has no model! style.visibility style.visibility style.visibility style.visibility style.visibility style.visibility style.visibility style.visibility style.visibility style.visibility style.visibility style.visibility style.visibility style.visibility style.visibility style.visibility
Resolution Inference Method Idea: generate new sentences by implications Unit resolution: A ∧ (A → B) |= B General resolution: (A → B) ∧ (B → C) |= (A → C) How do we do this with KB in CNF? Unit resolution: A ∧ (¬A ∨ B) |= B General resolution: (¬A ∨ B) ∧ (¬B ∨ C) |= (¬A ∨ C) Algorithm: apply resolution to every possible pair of clauses until: Empty clause is generated: false set of formulas! No more clauses can be generated: all generated clauses are entailed
Resolution: An Example Want to prove (P ∨ Q) ∧ ( ¬ P ∨ Q) ╞ (R ∨ Q) Prove (P ∨ Q) ∧ ( ¬ P ∨ Q) ∧ ¬ (R ∨ Q) is unsatisfiable. Prove (P ∨ Q) ∧ ( ¬ P ∨ Q) ∧ ( ¬ R) ∧ ( ¬ Q) is unsatisfiable Preform resolution: (P ∨ Q) ( ¬ R) ( ¬ Q) ( ¬ P ∨ Q) (Q) () Contradiction!! style.visibility style.visibility style.visibility style.visibility style.visibility style.visibility style.visibility style.visibility style.visibility style.visibility style.visibility style.visibility style.visibility style.visibility
Resolution: Another Example Prove: (P ∨ R) ∧ (R → Q) ∧ ¬ Q ∧ (T → S) ∧ (P -> T) ╞ S Then, prove that (P ∨ R) ∧ ( ¬ R ∨ Q) ∧ ¬ Q ∧ ( ¬ T ∨ S) ∧( ¬ P ∨ T) ∧ ¬ S is unsat ! (P, R) ( ¬ S) ( ¬ Q) ( ¬ R , Q) (P ∨ Q) (P) (T, ¬ P) (S, ¬ T) (S, ¬ P) ( ¬ P) () (Q,S) style.visibility style.visibility style.visibility style.visibility style.visibility style.visibility style.visibility style.visibility style.visibility style.visibility style.visibility style.visibility style.visibility style.visibility style.visibility style.visibility style.visibility style.visibility style.visibility style.visibility style.visibility style.visibility style.visibility style.visibility style.visibility
Exercise… Prove that (¬Q → ¬P) ∧ (M → S) ╞ (P ∨ M → Q ∨ S)
Entailment as Un-satisfiability KB ╞ ɸ iff all models of KB are models of ɸ iff Formula (KB→ɸ) is valid (a tautology) (i.e., true in all interpretations: TRUE ╞ KB → ɸ ) iff (KB ∧ ¬ɸ) is unsatisfiable (a contradiction) (i.e., the formula KB ∧ ¬ɸ is false in all interpretations) RESOLUTION
A simple example from…. style.visibility style.visibility
KB Example (Brachman & Levesque’05) KB: FirstGrade FirstGrade→ Child Child ∧Male → Boy AtKinder → Child Child ∧ Female → Girl Prove: KB |= Female → Girl KB to CNF: (FirstGrade) (¬FirstGrade ∨ Child) (¬(Child∧Male) ∨ Boy) (¬AtKinder ∨ Child) (¬(Child ∧ Female) ∨ Girl) Prove (in CNF): KB |= ¬Female ∨ Girl style.visibility
Resolution Example KB in CNF: (FirstGrade) (¬FirstGrade ∨ Child) (¬(Child∧Male) ∨ Boy) (¬AtKinder ∨ Child) (¬(Child ∧ Female) ∨ Girl) Prove: KB |= ¬Female ∨ Girl KB in CNF: (FirstGrade) (¬FirstGrade ∨ Child) (¬Child∨¬Male ∨ Boy) (¬AtKinder ∨ Child) (¬Child ∨ ¬Female ∨ Girl) Prove: KB |= ¬Female ∨ Girl style.visibility
Entailment as Un-satisfiability KB ╞ ( ¬Female ∨ Girl) iff all models of KB are models of (¬Female ∨ Girl) iff Formula KB → (¬Female ∨ Girl) is valid (a tautology) (i.e., true in all interpretations: TRUE ╞ KB → ¬Female ∨ Girl ) iff (KB ∧ ¬(¬Female ∨ Girl) ) is unsatisfiable (i.e., formula KB ∧ ¬ (¬Female ∨ Girl) is false in all inter.) RESOLUTION
Resolution Example KB in CNF: (FirstGrade) (¬FirstGrade ∨ Child) (¬Child∨¬Male ∨ Boy) (¬AtKinder ∨ Child) (¬Child ∨ ¬Female ∨ Girl) Prove: KB |= ¬Female ∨ Girl KB in CNF: (FirstGrade) (¬FirstGrade ∨ Child) (¬Child∨¬Male ∨ Boy) (¬AtKinder ∨ Child) (¬Child ∨ ¬Female ∨ Girl) Prove: KB ∧ ¬(¬Female ∨ Girl) is unsatisfiable/contradiction style.visibility
Resolution Example KB in CNF: (FirstGrade) (¬FirstGrade ∨ Child) (¬Child∨¬Male ∨ Boy) (¬AtKinder ∨ Child) (¬Child ∨ ¬Female ∨ Girl) Prove: KB ∧ ¬(¬Female ∨ Girl) is unsatisfiable/contradiction KB in CNF: (FirstGrade) (¬FirstGrade ∨ Child) (¬Child∨¬Male ∨ Boy) (¬AtKinder ∨ Child) (¬Child ∨ ¬Female ∨ Girl) Prove: KB ∧ Female ∧ ¬Girl is unsatisfiable/contradiction style.visibility
Resolution Example KB in CNF: (FirstGrade) (¬FirstGrade ∨ Child) (¬Child∨¬Male ∨ Boy) (¬AtKinder ∨ Child) (¬Child ∨ ¬Female ∨ Girl) Prove: KB ∧ Female ∧ ¬Girl is unsatisfiable/contradiction FirstGrade (¬FirstGrade ∨ Child) Child (¬Child ∨ ¬Female ∨ Girl) (¬Female ∨ Girl) Female (Girl) ¬ Girl () contradiction, so KB|= ¬(Female ∧ ¬Girl) style.visibility style.visibility style.visibility style.visibility style.visibility style.visibility style.visibility style.visibility style.visibility style.visibility style.visibility style.visibility style.visibility style.visibility style.visibility style.visibility style.visibility style.visibility style.visibility style.visibility style.visibility
Resolution Example KB: FirstGrade FirstGrade→ Child Child ∧Male → Boy AtKinder → Child Child ∧ Female → Girl Prove: KB |= Female → Girl So KB ∧ Female ∧ ¬Girl is unsatisfiable – contradiction! But we know that KB is true! So, if you have KB, you have to have ¬(Female ∧ ¬Girl)! That is: KB |= ¬(Female ∧ ¬Girl) So, KB |=(¬Female ∨ Girl) So, KB |=(Female → Girl) style.visibility style.visibility style.visibility style.visibility style.visibility style.visibility style.visibility style.visibility style.visibility style.visibility style.visibility style.visibility
SAT Competition: who can prove faster?
Too c oncise Language? Propositional logic provides a general language to encode deterministic domain knowledge. While the encoding is precise and well defined it is often tedious or complicated. Simple English sentences often lead to long logical formula. Can we make propositional logic more concise and more natural?
Conclusion Logic to model reasoning. no intuition needed. Knowledge Representation Make knowledge important! Decouple it from procedures. Open-ended uses. Propositional Logic simplest KR formalism. syntax, semantics, entailment Resolution : mechanic way for doing inference. implement entailment. KB ╞ a