Artificial Intelligence - Propositional Logic PDF

Artificial Intelligence A Course About Foundations Artificial Intelligence 2024-2025 Propositional Logic  Prologue: Boolean Algebra(s) Artificial Intelligence 2024-2025 Propositional Logic B...

Artificial Intelligence A Course About Foundations Artificial Intelligence 2024-2025 Propositional Logic  Prologue: Boolean Algebra(s) Artificial Intelligence 2024-2025 Propositional Logic Boolean algebras by examples W  W W = {a} W = {a, b} W = {a, b, c}  {a} {b} {a, b} {a, c} {b, c}...  {a} {b} {c} {a, b} Each arrow represents  (Hasse diagrams) set inclusion {a} {a}  {a, b}  W W, 2W Artificial Intelligence 2024-2025 Propositional Logic Boolean algebras by examples W  W W = {a} W = {a, b} W = {a, b, c}  {a} {b} {a, b} {a, c} {b, c}...  {a} {b} {c}   W (the complement of A with respect to W ) W W  Artificial Intelligence 2024-2025 Propositional Logic Boolean algebras by examples W  W W = {a} W = {a, b} W = {a, b, c}  {a} {b} {a, b} {a, c} {b, c}...  {a} {b} {c}  De Morgan’s laws (A  B)c = Ac  Bc (A  B) c = Ac  Bc A = {b} A = {b} B = {b, c} B = {b, c} A  B = {b, c} A  B = {b} (A  B) c = {a} (A  B) c = {a, c} These sets Ac = {a, c} These sets Ac = {a, c} are identical are identical Bc = {a} Bc = {a} Ac  Bc = {a} Ac  Bc = {a, c} Artificial Intelligence 2024-2025 Propositional Logic Which Boolean algebra for logic?  := {W, } {nothing, everything} {false, true} {, } or {0, 1} ▪ < {0,1}, OR, AND, NOT > ▪ f : {0, 1}n {0, 1} AND OR NOT A B OR A B AND A NOT 0 0 0 0 0 0 0 1 0 1 1 0 1 0 1 0 1 0 1 1 0 0 1 1 1 1 1 1 Artificial Intelligence 2024-2025 Propositional Logic Composite functions These columns are identical A B NOT A NOT B A OR B NOT(A OR B) NOT A AND NOT B 0 0 1 1 0 1 1 0 1 1 0 1 0 0 1 0 0 1 1 0 0 1 1 0 0 1 0 0 These columns De Morgan’s laws are identical A B NOT A NOT B A AND B NOT(A AND B) NOT A OR NOT B 0 0 1 1 0 1 1 0 1 1 0 0 1 1 1 0 0 1 0 1 1 1 1 0 0 1 0 0 Artificial Intelligence 2024-2025 Propositional Logic Adequate basis ▪ A1 A2... An f(A1, A2,..., An) 0 0... 0 f1 2n rows 0 0... 1 f2.............................. 1 1... 1 f2n OR AND NOT j fj = 1 AND n Ai i 1 NOT Ai i 0 OR Artificial Intelligence 2024-2025 Propositional Logic Other adequate bases {OR, NOT} {AND, NOT} NOR NAND A B A NOR B A B A NAND B 0 0 1 0 0 1 0 1 0 0 1 1 1 0 0 1 0 1 1 1 0 1 1 0 ▪ A B A IMP B A B A EQU B 0 0 1 0 0 1 0 1 1 0 1 0 1 0 0 1 0 0 1 1 1 1 1 1 A IMP B = (NOT A) OR B A EQU B = (A IMP B) AND (B IMP A) {IMP, NOT} Artificial Intelligence 2024-2025 Propositional Logic  Language and Semantics, Possible Worlds Artificial Intelligence 2024-2025 Propositional Logic Propositional logic: the project ▪ ▪ ▪ Artificial Intelligence 2024-2025 Propositional Logic The class of propositional semantic structures {0,1}  v  {0,1}   A B C D ...  {0,1} v Artificial Intelligence 2024-2025 Propositional Logic Formal language ▪ LP   = {A, B, C,...} , , ,  (, ) ▪ LP wff(LP) A    A  wff(LP)   wff(LP)  ()  wff(LP) ,   wff(LP)  ( )  wff(LP) ,   wff(LP)  (  )  wff(LP) ,   wff(LP)  (  )  wff(LP) ,   wff(LP)  (  )  wff(LP) Artificial Intelligence 2024-2025 Propositional Logic Formal semantics: interpretations ▪ wff v :  {0,1} v() = NOT(v()) v(  ) = AND(v(), v()) v(  ) = OR(v(), v()) v( ) = OR(NOT(v()), v()) IMP(v(), v()) v(  ) = AND(OR(NOT(v()), v()), OR(NOT(v()), v())) ▪ v   wff(LP) v : wff(LP) {0,1} v LP wff   Artificial Intelligence 2024-2025 Propositional Logic An Aside: object language and metalanguage ▪ LP , , , , , , (, ), wff ▪      wff       Artificial Intelligence 2024-2025 Propositional Logic  Entailment Artificial Intelligence 2024-2025 Propositional Logic About formulae and their hidden relations ▪ 1 = B  D  (A  C) 2 = B  C 3 = A  D 4 = B Is there any logical relation between hypothesis and thesis? ▪ =D And among the propositions in the hypothesis? Artificial Intelligence 2024-2025 Propositional Logic Entailment A B C D 1 2 3 4  0 0 0 0 1 0 0 1 0 0 0 0 1 1 0 1 1 1 wff 0 0 1 0 1 1 0 1 0 1 = B  D  (A  C) 0 0 1 1 1 1 1 1 1 2 = B  C 0 1 0 0 1 1 0 0 0 3 = A  D 0 1 0 1 1 1 1 0 1 4 = B ____________________ 0 1 1 0 1 1 0 0 0 =D 0 1 1 1 1 1 1 0 1 1 0 0 0 1 0 1 1 0 1 0 0 1 1 0 1 1 1 Notation! 1 0 1 0 0 1 1 1 0 1 0 1 1 1 1 1 1 1 1 1 0 0 1 1 1 0 0 {1, 2, 3, 4}   1 1 0 1 1 1 1 0 1 1 1 1 0 1 1 1 0 0 1 1 1 1 1 1 1 0 1 {1, 2, 3, 4}  Artificial Intelligence 2024-2025 Propositional Logic  wff wff  There is entailment iff every world that satisfies  also satisfies  Artificial Intelligence 2024-2025 Propositional Logic Satisfaction, models ▪ A B C AB (A  B)  C  = (A  B)  C 0 0 0 0 0 0 0 1 0 0 0 1 0 1 0 0 1 1 1 1 1 0 0 1 0   wff(LP) 1 0 1 1 1 1 1 0 1 0 1 1 1 1 1  v() = 1    w  wff  = {1, 2,... , n} w wff 1, 2,... , n Artificial Intelligence 2024-2025 Propositional Logic Tautologies, contradictions ▪ A A  A A  A wff 0 0 1 1 0 1 A B (A  B)  (B  A) wff    0 0 1 0 1 1 ▪ 1 0 1 1 1 1 wff A B ((A  B)  (B  A)) wff    0 0 0 0 1 0 1 0 0 1 1 0 ▪ wff ▪   Artificial Intelligence 2024-2025 Propositional Logic Formulae and subsets ▪ W wff  LP W  {w : w  }  W  The set of all possible worlds W Artificial Intelligence 2024-2025 Propositional Logic Formulae and subsets ▪ W wff  LP W  {w : w  }  W  The set of all “ is a tautology” possible worlds “any possible world in W W is a model of ”  “ is valid” Furthermore: “ is satisfiable” “ is not falsifiable” Artificial Intelligence 2024-2025 Propositional Logic Formulae and subsets ▪ W wff  LP W  {w : w  }  W  The set of all “ is a contradiction” possible worlds “none of the possible worlds in W W is a model of ” “ is not valid” Furthermore: “ is not satisfiable” “ is falsifiable” Artificial Intelligence 2024-2025 Propositional Logic Formulae and subsets ▪ W wff  LP W  {w : w  }  W  “ is neither a contradiction The set of all nor a tautology” possible worlds “some possible worlds in W W are model of , others are not” “ is not (logically) valid”  Furthermore: “ is satisfiable” “ is falsifiable” Artificial Intelligence 2024-2025 Propositional Logic Formulae, subsets and entailment All possible worlds W  “All possible worlds that are models of ” Artificial Intelligence 2024-2025 Propositional Logic Formulae, subsets and entailment W  1 “All possible worlds that are models of 1” { 1}   because the set of models for { 1} is not contained in the set of models of  Artificial Intelligence 2024-2025 Propositional Logic Formulae, subsets and entailment W  2 1 “All possible worlds that are models of 2” { 1, 2}   because the set of models of { 1, 2} (i.e. the intersection of the two subsets) is not contained in the set of models of  Artificial Intelligence 2024-2025 Propositional Logic Formulae, subsets and entailment W  2 1 3 “All possible worlds that are models of 3” { 1, 2 , 3}   because the set of models of { 1, 2 , 3} is not contained in the set of models of  Artificial Intelligence 2024-2025 Propositional Logic Formulae, subsets and entailment W 4  2 1 3 “All possible worlds that are models of 4” { 1, 2 , 3 , 4}   Because the set of models for { 1, 2 , 3 , 4} is contained in the set of models of  Artificial Intelligence 2024-2025 Propositional Logic Formulae, subsets and entailment W 4  2 1 3 “All possible worlds that are models for { 1, 2 , 3 , 4}” { 1, 2 , 3 , 4}   In the case of the example, all the wff 1, 2 , 3 , 4 Because the set of models for { 1, 2 , 3 , 4} are needed for the relation is contained in the set of models of  of entailment to hold Artificial Intelligence 2024-2025 Propositional Logic  wff wff  There is entailment iff every world that satisfies  also satisfies  Artificial Intelligence 2024-2025 Propositional Logic  Further Properties Artificial Intelligence 2024-2025 Propositional Logic Symmetric entailment = logical equivalence ▪   wff       wff    ▪ wff wff { 1, 2 , 3 , 4}   1 = B  D  (A  C) 1 = B  D  (A C) 2 = B  C 2 = B  C 3 = A  D 3 = A D 4 = B 4 = B =D =D Artificial Intelligence 2024-2025 Propositional Logic Implication and Inference Schemas wff {, } 1 = C (B (A D)) 1 = B  D  (A  C) 2 = B C 2 = B  C 3 = A D 3 = A  D 4 = B 4 = B =D =D ▪    ______   ,     ,    Artificial Intelligence 2024-2025 Propositional Logic Modern formal logic: fundamentals ▪ wff ▪ wff {1, 0} ▪ wff wff 1 wff wff wff Artificial Intelligence 2024-2025 Propositional Logic Properties of entailment (classical logic) ▪ wff      ▪        ▪           ▪     wff Artificial Intelligence 2024-2025 Propositional Logic  What we have seen so far language   semantics semantics entailment meaning v() v() Artificial Intelligence 2024-2025 Propositional Logic