Logique Mathématique - Chapitre 2 - Propositional Logic - PDF
Document Details
Uploaded by Deleted User
Université Constantine 2
Pr ZEGHIB Nadia
Tags
Summary
This document presents lectures on mathematical logic, specifically propositional logic, including semantic analysis and normal forms. It covers the plan and examples of conversion to various forms. This document is from the University Constantine 2.
Full Transcript
Logique Mathématique – Course 4 – Chapiter 2 : Propositional Logic Sémantics (2/3) Pr ZEGHIB Nadia...
Logique Mathématique – Course 4 – Chapiter 2 : Propositional Logic Sémantics (2/3) Pr ZEGHIB Nadia Faculté des Nouvelles Technologies de l’Information et de la Communication Département Mathématique & Informatique (MI) Email: [email protected] Université Constantine 2 2020/2021. Semestre 3 Plan 1-Introduction 2- Valuation (assignment, value system) 3- Interpretation 4- Semantic analysis (Truth analysis) of a formula 5- Synonym/equivalent propositional formulas 6- Normal forms of a propositional formula 7- Satisfied/valid formula 8- Model 9- Compatibility 10- Logical consequence (tautological consequence) Université Constantine 2 © Zeghib Nadia 2 Normal forms of a propositional formula In Computer Science, and in particular in some proof methods, it is required that the Formula (to be treated) is in a special form. For instance: must contain only the connectors must contain only the connectors …etc. We will define the most known normal forms. We show how we can put a formula in a given normal form. Université Constantine 2 © Zeghib Nadia 3 Normal forms of a propositional formula Definitions Atom: We call an atom a Propositional Variable Literal: A literal is an atom or the negation of an atom Elementary Conjunction : is a literal or a conjunction of literals Examples: ABCAD , (AB)C , B, B are elem.conj AB , (AB), (AvB)(BC) are not elem.conj Elementary disjunction : is a littéral or a disjunction de literals Université Constantine 2 © Zeghib Nadia 4 Normal forms of a propositional formula 1 Negative Normal Form (NNF) Definition A formula is in negative normal form (under FNN) if and only if : is built with only connectors and The connector appears only in front of PV ( does not govern a , one or another ) Examples AB v C , (AB)v (AC) A , A(BvC) under NNF AB, A B vC , A (AvB) not under NNF Université Constantine 2 © Zeghib Nadia 5 Normal forms of a propositional formula 1 Negative Normal Form (NNF) Lemma: Any propositional formula is synonym with a propositional formula under NNF Method to put under NNF (Conversion to NNF) 1- Remove all and by replacing 12 by 1v2 12 by (1v2) (1 v2) 2-Use Morgan’s identities to push the negations towards the inside (12)=1v2 (1v2)=12 3- Replace the sub-formulas by Université Constantine 2 © Zeghib Nadia 6 Normal forms of a propositional formula 1 Negative Normal Form (NNF) Example of conversion to NNF = ( (AB) C) ( (AB) C) = (AB) v C Step 1 = (A vB) vC Step 2 = (A v B) v C Step 3 Université Constantine 2 © Zeghib Nadia 7 Normal forms of a propositional formula 2 Conjunctive Normal Form (CNF) Definition A formula is in Conjunctive normal form (under CNF) if and only if : is an elementary disjunction or is a conjunction of elementary disjunctions Examples (AvB)(AvBv C) (Av Cv D) ( Av D) AvB A are under CNF Université Constantine 2 © Zeghib Nadia 8 Normal forms of a propositional formula 2 Conjunctive Normal Form (CNF) Lemma: Any propositional formula is synonym with a propositional formula under CNF Method to put under CNF (Conversion to CNF) (1) Put under NNF Replace all sub-formulaes 1v(23) by (1v2)(1v3) distributivity left of v by (23)v1 by (2v1) (3v1) distributivity right of v by Université Constantine 2 © Zeghib Nadia 9 Normal forms of a propositional formula 2 Conjunctive Normal Form (CNF) Example of Conversion to CNF =A( BC ) =Av(B C) NNF =(AvB)(AvC) distributivity left of v by CNF Université Constantine 2 © Zeghib Nadia 10 Normal forms of a propositional formula 2 Conjunctive Normal Form (CNF) Method to put under CNF (conversion to CNF) (2) ( Using the truth table) CNF = (AvBvC) (AvBvC) (AvBvC) Université Constantine 2 © Zeghib Nadia 11 Normal forms of a propositional formula 3 Disjunctive Normal Form (DNF) Definition A formula is in Disjunctive normal form (under DNF) if and only if : is an elementary conjunction or is a disjunction of elementary conjunctions Examples (AB)v(A B C) (A C D) v ( A D) A B A are under DNF Université Constantine 2 © Zeghib Nadia 12 Normal forms of a propositional formula 3 Disjunctive Normal Form (DNF) Lemma: Any propositional formula is synonym with a propositional formula under DNF Method to put under DNF (Conversion to DNF) (1) Put under NNF Replace all sub-formulaes 1 (2v3) par (1 2) v(1 3) distributivity left of by v (2v3) 1 par (2 1) v(3 1) distributivity right of by v Université Constantine 2 © Zeghib Nadia 13 Normal forms of a propositional formula 3 Disjunctive Normal Form (DNF) Example of Conversion to DNF = (A( BC ) ) = ( Av (B C) ) = A (B C) ) = A ( B v C) ) = A ( B v C) ) NNF =(A B) v (A C) distributivity left of by v DNF Université Constantine 2 © Zeghib Nadia 14 Normal forms of a propositional formula 3 Disjunctive Normal Form (DNF) Method to put under DNF (Conversion to DNF) (2) ( Using the truth table) DNF= (A B C) v (A BC) v (ABC) v (ABC) v (ABC) Université Constantine 2 © Zeghib Nadia 15 Plan 1-Introduction 2- Valuation (assignment, value system) 3- Interpretation 4- Semantic analysis (Truth analysis) of a formula 5- Synonym/equivalent propositional formulas 6- Normal forms of a propositional formula 7- Satisfied/valid formula 8- Model 9- Compatibility 10- Logical consequence (tautological consequence) Université Constantine 2 © Zeghib Nadia 16 Satisfied/valid formula 1 Satisfied formula A formula is satisfied iff is true for at least one valuation V of variables []V=1 satisfied V []V=1 A satisfied formula is True at least once A formula is not satisfied iff it is false for each valuation V of variables not satisfied V []V=0 A not satisified formula is always False Example: AVB satisfied AA not satisfied Université Constantine 2 © Zeghib Nadia 17 Satisfied/valid formula 2 Valid Formula A formula is valid iff for each valuation V of variables we have []V=1 valid V []V=1 A formula is valid iff it is always true A formula is not valid iff it is False for at least one valuation not valid V []V=0 A formula is not valid iff it is False at least once Examples: AvA valid AvB not valid Université Constantine 2 © Zeghib Nadia 18 Satisfied/valid formula 3 Tautology A tautology is a formula that is always True A tautology is a valid formula tautology V []V=1 4 Antilogy An antilogy is a formula that is always False An antilogy is a not-satisfied formula antilogy V []V=0 Université Constantine 2 © Zeghib Nadia 19 Satisfied/valid formula There are therefore 3 categories of formulas: Valid formulas (always true) i.e tautologies Satisfied not valid formulas Not satisfied formulas (always false) i.e les antilogies. Université Constantine 2 © Zeghib Nadia 20 Satisfied/valid formula Examples Université Constantine 2 © Zeghib Nadia 21 Satisfied/valid formula Valid Formulas Ex: Av A (Tautologies) Ex: (A vB)C Satisfied ¬ valid Formulas Not Satisfied Formulas Knowledge Base Ex: AA (Antilogies) Université Constantine 2 © Nom et prénom 22
