02-Boolean-HO.pdf

Knowledge Representation and Reasoning Boolean Algebra and Propositional Logic Rafael Peñaloza Milano, 2024-2025 Università di Milano-Bicocca Boolean Algebra Boolean algebra is a formalism for manipulating...

Knowledge Representation and Reasoning Boolean Algebra and Propositional Logic Rafael Peñaloza Milano, 2024-2025 Università di Milano-Bicocca Boolean Algebra Boolean algebra is a formalism for manipulating truth values (logical operations) We consider only two truth values: true (1) false (0) and three Boolean operators: conjunction, disjunction, negation KRR 2024-2025 1 Boolean Operators I: Conjunction Conjunction is the logical “AND” (∧) A conjunction of (two) truth values is true if and only if (iff) both values are true Truth table: ∧ 0 1 0∧0=0 0 0 0 0∧1=0 1 0 1 1∧0=0 1∧1=1 (Hint: min) KRR 2024-2025 2 Boolean Operators II: Disjunction Disjunction is the logical “OR” (∨) A disjunction of truth values is true iff at least one value is true ∨ 0 1 0 0 1 1 1 1 (Hint: max) KRR 2024-2025 3 Boolean Operators III: Negation Negation is the logical “NOT” (¬) The negation of a truth value is true iff the value is false ¬ 0 1 1 0 (Hint: duality) KRR 2024-2025 4 Boolean Operators IV: Many other options exist Exercise Build a table for the XOR operator which is true iff exactly one value is true KRR 2024-2025 5 Complex Expressions The operations allow us to compute the value of a complex expression (¬(1 ∨ 0)) ∧ (1 ∨ (1 ∧ 0)) | {z } 0 Kind of boring if we only have constants (0/1) what if we use variables instead? KRR 2024-2025 6 Propositional Logic Propositional logic is a formalism for combining propositions (sentences, statements) to make conclusions about their truth value Atomic propositions state one specific fact or property mammals are vertebrate vertebrates are vegetarians cars have umbrellas it’s Slay x Formulas combine propositions to make complex statements KRR 2024-2025 7 Sidenote Remember that a logic is just a language We must specify: which expressions are allowed (syntax) what do they mean (semantics) KRR 2024-2025 8 Syntax of Propositional Logic Take an arbitrary set of propositional variables (atomic propositions) The class of propositional formulas is defined by: every propositional variable is a formula if φ and ψ are formulas, then so are: – ¬φ – φ∧ψ – φ∨ψ Operator precedence: ¬, ∧, ∨ KRR 2024-2025 9 Example: Some formulas w x y z ¬w ¬w ∧ z ≡ (¬w ) ∧ z x ∨y ¬(x ∨ y ) ¬(x ∨ y ) ∧ (¬w ∧ z)... Anything that is “well formed” in the intuitive sense KRR 2024-2025 10 Intuition of the Semantics Recall that atomic propositions may be true or false What about formulas? Depends on the truth status of its components (subformulas) Must specify the value of each variable the rest is fully characterised KRR 2024-2025 11 Semantics of Propositional Logic A valuation is an assignment of a truth value to each variable Formally, a function V : P → {0, 1} Example: the valuation V: w x y z V(w ) = 0 0 1 1 0 V(x) = 1 V(y ) = 1 V(z) = 0 w , z are false x, y are true KRR 2024-2025 12 Semantics of Propositional Logic II The assignment of a valuation is extended to formulas: V(¬φ) = ¬V(φ) careful with the meaning! V(¬φ) = 1 iff V(φ) = 0 V(φ ∧ ψ) = V(φ) ∧ V(ψ) V(φ ∧ ψ) = 1 iff V(φ) = 1 and V(ψ) = 1 V(φ ∨ ψ) = V(φ) ∨ V(ψ) V(φ ∨ ψ) = 1 iff V(φ) = 1 or V(ψ) = 1 KRR 2024-2025 13 Example of the Semantics w x y z ¬w ¬w ∧ z x ∨y ¬(x ∨ y ) ¬(x ∨ y ) ∧ (¬w ∧ z) 0 1 1 0 1 0 1 0 0 0 0 0 1 1 1 0 1 1 u ¬u ¬u ∨ u ¬u ∧ u 0 1 1 0 1 0 1 0 KRR 2024-2025 14 Three Kinds of Formulas There are three types of propositional formulas: tautologies are always evaluated to 1 (true) regardless of the valuation contradictions are always evaluated to 0 (false) regardless of the valuation (non-tautological) satisfiable formulas are all others KRR 2024-2025 15 Formulas as Functions A formula takes a valuation and returns a truth value A formula with n variables is a function a mapping from n truth values to one truth value Example x y x XOR y 0 0 0 0 1 1 1 0 1 1 1 0 KRR 2024-2025 16 Equivalence What characterises a formula is its behaviour as a function Two formulas are equivalent iff they have the same truth table (syntactically different expressions with the same meaning) Example: x ∧ y and (x ∧ y ) ∧ (x ∨ y ) are equivalent x ∧ y ≡ (x ∧ y ) ∧ (x ∨ y ) KRR 2024-2025 17 Variable Accumulation When comparing formulas with different variables, implicitly extend the arity of the functions Example: x ∨ y ̸≡ x ∨ z Exercise: verify that x ∧ y ≡ x ∧ y ∧ (z ∨ ¬z) KRR 2024-2025 18 Special Formulas Important: all tautologies are equivalent, and all contradictions are equivalent ⊤ (top) and ⊥ (bottom) stand for arbitrary tautologies, contradictions, respectively Properties: φ∧⊤≡φ φ∨⊤≡⊤ φ∨⊥≡φ φ∧⊥≡⊥ KRR 2024-2025 19 Other Operators We can imagine other binary operators (how many?) NAND not both true implication x → y if x then y... KRR 2024-2025 20 Completeness of Operators They can all be expressed via ¬, ∧, ∨ x XOR y ≡ (x ∨ y ) ∧ ¬(x ∧ y ) x → y ≡ ¬x ∨ y Exercise: find an equivalent representation for NAND KRR 2024-2025 21 Completeness of Operators II The operators ¬, ∧, ∨ suffice to express ANY formula regardless of the number of variables Example x y z φ 0 0 0 0 0 0 1 0 0 1 0 0 (¬x ∧ y ∧ z) ∨ 0 1 1 1 (x ∧ ¬y ∧ z) ∨ 1 0 0 0 (x ∧ y ∧ ¬z) 1 0 1 1 1 1 0 1 1 1 1 0 KRR 2024-2025 22 Fundamental Equivalences DeMorgan ¬(x ∧ y ) ≡ ¬x ∨ ¬y ¬(x ∨ y ) ≡ ¬x ∧ ¬y Distributivity x ∧ (y ∨ z) ≡ (x ∧ y ) ∨ (x ∧ z) x ∨ (y ∧ z) ≡ (x ∨ y ) ∧ (x ∨ z) Involution ¬¬x ≡ x KRR 2024-2025 23 OK But Why? What has this to do with KR? Knowledge Bases are sets of formulas which constraint the relevant interpretations Reasoning corresponds to analysing formulas under these constraints We will start with an even simpler language KRR 2024-2025 24 [email protected]