file is: logic.mem --- will be discussed in class version 1.2 April 1998 Elliott CSC357 / CSC457 Fall 1997 ======================================================================= Rewrite rules: 1. ~~P ==> P 2. P -> Q ==> ~P or Q 3. P or P ==> P 4. P and Q ==> P Q 5. ~(P and Q) ==> ~P or ~Q [DeMorgan's Law] 6. ~(P or Q) ==> ~P and ~Q ==> ~P [DeMorgan's Law] ~Q ======================================================================= Conjunctive Normal Form (CNF) 1. TermA or TermB or TermC... Conjunt One AND 2. TermA' or TermB'... Conjunct Two AND... Where a Term is a distinct (for each conjunct) proposition of the form, p, or ~p. Note that there are no implications (->), conjunctive connectives, or repeated terms in any of the conjuncts (numbered statemetns). Read each conjunct as, for example, It is a TRUE statement that TermA is true, or TermB is true, or TermC is true (...). Each of (1), (2), and so forth are true statements and can be used independently of any other conjuncts. Read the entire database (the "world") as "It is a TRUE statement that conjunct One is a true statement and conjunct Two is a true statement and conjunct Three is a true statement... By writing the conjuncts down in a database, we are stating that, for our logical purposes, we are assuming that each statement is true. Sometimes it is convenient, using the "Closed World Assumption," that we assume everything not known to be true is false. ------------------------------------------------------------------- Example: 1. p or q or ~s 2. ~p "It is a true statement that p is true, or q is true, or s is false." "It is a true statement that p is false." "It is a true statement that line (1) is true, and that line (2) is true. Using the rewrite rules it is possible to put any propositional logic database into conjunctive normal form. ======================================================================= PROOF BY CONTRADICTION ======================================================================== The idea: suppose that we want to show that when given a "world" that we assume to be true, it must follow that some new thing (our theorem) in that world is true. Now suppose we added the opposite of our theorem (the "dark side of our theorem") to the world and we ended up with an impossible situation. Since the world was fine before, what had to be the cause of the problem? Right -- the "dark side of our theorem." We can now reason that since the "dark side of our theorem" leads to an impossible situation then it must in turn be impossible, and our original theorem must be so. In short: Negate the theorem. Add to a consistent database. Show that the database becomes inconsistent. ======================================================================== Examples: ======================================================================== Goal: Prove the theorem that Al is in the room. Facts: Al is in the room. Negation of theorem: Al is NOT in the room. 1. Al is in the room Fact 2. Al is not in the room Negation of theorem 3. [] From 2,1 QED ================================================= ================================================= Goal: Prove the theorem that Al is in the room. Facts: Al is with Jean Jean is in the room. Al with Jean and Jean in room -> Al in room Negation of theorem: Al is NOT in the room. Change to conjunctive normal form (CNF): (Al with Jean AND Jean in room) --> Al in room fact ~(Al with Jean AND Jean in room) OR Al in room implication rewrite ~(Al with Jean) OR ~(Jean in room) OR Al in room DeMorgan's Law 1. Al is with Jean fact 2. Jean is in room fact 3 ~(Al with Jean) OR ~(Jean in room) OR Al in room fact, rewrite, above. 4. Al is not in the room Negation of theorem 5. ~(Jean in room) OR Al in room 3,1 6. Al in room 5,2 7. [] 6,4 QED ======================================================================== ======================================================================== Removing implication: Representation: E.g. If you meet Frankenstein then you're dead. Meet-F ==> You-are-dead ~Meet-F or You-are-dead ======================================================================== ======================================================================== Propositional logic and First order predicate logic: FOPC allows us to use variables. This is a good thing since instead of saying a is green b is green c is green... for all 4,060 items in our "green world," we can instead say: All things are green. Forall(x) is-green(x). Or... There does not exist anything that is not green. ~Exists(x) ~is-green(x). And, instead of saying a is tall, or b is tall, or c is tall,... for all 4,060 items in our "green world," we can instead say: There is at least one thing that is tall. Exists(x) tall(x). ================================================================== Limitations of the FOPC FOPC, like all logic systems, have limitations that humans do not: Time, for example, is a particularly difficult concept to capture. ------------------------------------------------------------------- THE YALE SHOOTING PROBLEM: Temporal projection, and the frame problem: (1) If a live human is shot in the head with a loaded gun they die immediately. (2) Unless circumstances are abnormal, if a gun is loaded at time t then unless it is fired it will still be loaded at time t+2. (Frame axiom one) (3) Unless the circumstances are abnormal, a thing that is alive at time t will continue to be alive at time t+2. (Frame axiom two) Freda is alive when the assassin loads the gun at time t. The gun is not fired for two minutes. The assassin steps out of concealment, grips Freda by the hair, and pulls the trigger at point blank range. Is Freda dead? Well a logic system can conclude that either: (2) holds so Freda is dead, and (3) is to be overridden, or... (3) holds so Freda is alive, and (2) is to be overridden (the gun was unloaded at time t+1). ------------------------------------------------------------------- The general idea is that to avoid having to keep track of, and restate, every fact in our world at each new time, t+n, we use frame axioms to specify various subsets of: (Universal frame axiom) Everything that is true at time t is true at time t+1. Since a world where nothing ever changes is not very interesting we will sooner or later be forced to manually tweak gray areas arising from our general frame axioms. ========================================================================== Resolution. Examples: 1. p or q 2. ~p 3. q by resolution, 2,1 1. p or q 2. ~q or s 3. p or s by resolution, 2,1 Case 1: q then s Case 2: ~q then p The maid said that she saw the butler in the living room. The living room adjoins the kitchen. The shot was fired in the kitchen, and could be heard in all adjoining rooms. The butler, who has good hearing, said he did not hear the shot. Using resolution, prove: If the maid told the truth, the butler lied. p = the maid told the truth q = the butler was in the living room r = the butler was near the kitchen s = the butler heard the shot u = the butler told the truth 1. ~p or q if the maid told the truth, the butler was in the L.R. 2. ~q or r if the butler was in the L.R, he was near the kitchen 3. ~r or s if he was near the kitchen, he heard the shot 4. ~u or ~s if he told the truth, he did not hear the shot Theorem: ~p or ~u if the maid told the truth, the butler did not. Negated theorem: ~(~p or ~u) 5. u 6. p By resolution: 7. ~p or r 2, 1 8. ~p or s 3, 7 9. ~p or ~u 8, 4 10. ~u 9, 6 11. [] 10, 5 Since it is not possible for it to NOT be a true statement that if the maid told the truth the butler did not, then it MUST be a true statement that if the maid told the truth, then the butler did not. QED.