Discrete Mathematics - 01 mathematical logic

brief introduction

1. Discrete Mathematics ： Mathematical logic , Set theory , Algebraic systems , graph theory
2. Mathematical logic ：$lifetopicLogicCompilation,PredicatewordLogicCompilation$
3. Propositional logic
   （1） The basic concept of propositional logic 、 Propositional logic connectives and truth tables , Tautology
   （2） The formalization of simple propositions （ The formalization of simple natural sentences ）
   （3） Equivalence theorem 、 Basic equivalence formula and equivalence calculus
   （4） The relationship between propositional formula and truth table 、 A complete set of connectives
   （5） Disjunctive normal form 、 Conjunctive paradigm 、 Principal disjunctive normal form and principal conjunctive normal form
   （6） Reasoning rules and reasoning calculus of propositional logic , Proof method of resolution reasoning
   （7） The concept of axiomatic system of propositional logic , The basic structure of axiomatic system
4. Predicate logic
   （1） The predicate 、 Basic concepts and expressions of quantifiers
   （2） The formalization of complex natural sentences
   （3） Negative equivalent 、 The equivalent of quantifier distribution
   （4） normal form 、 The toe in paradigm ,Skolem Standard shape
   （5） Basic reasoning formula and its proof method 

   （6） Reasoning rules and reasoning calculus of predicate logic , Reductive reasoning
5. The difference between predicate logic and propositional logic
   (1) Propositional logic regards simple propositions as the most basic unit , There is no connection in the category of propositional logic . Such as proposition ：“A It's the letters ”.
   (2) Predicate logic continues to split propositions , Divide the proposition into “A”、“… It's the letters ”、 These structures , You can get a proposition “π Is the set of real Numbers ” This proposition . among “… It's the letters ” It's called predicate . Predicate logic can describe richer forms of reasoning .

Propositional logic

Propositions and connectives

1. $lifetopic$： A statement that can tell true from false
   （1） Simple ( atom ) / Compound proposition , really / False proposition
   （2） Particular attention ： Variable , paradox , Non declarative sentences
2. $complexcloselifetopicUnitedjunctionword$： no ¬、 Syntaxis ∧（ And ）、 Disjunction ∨（ or ）、 implication →、 Equivalent
   （1） Incompatible or （ Repulsion or ）： Xiao Li is playing games tonight p Or play ball q：(p∧¬q)∨(¬p∧q)
   （2） implication ： If p be q; as long as p be q;p Only when the q; Unless q otherwise p; Only q I only p
   （3） Equivalent ：p If and only if q
   （4） Priority order ：¬,∧,∨,→,, Parenthesis priority

Propositional formula and its assignment

3. $closetypeMaletype(lifetopicMaletype)$： A string of symbols connecting propositions with connectives and parentheses according to a certain logical relationship
   （1） nature
     [1] Single propositional variable （ Or common items ） It's a formula
     [2] if A It's a formula , be （┐A） It's also a formula
     [3] if A,B It's a formula , be (A∧B),(A∨B),(A→B),(AB) It's also a formula
     [4] Limited applications (1)～(3) The resulting string of symbols is a compound formula
4. $canfullfoottypelifetopic$
   （1） set up A For a propositional formula
     [1] if A The value is true under various assignments , be A For tautology or eternal truth ;
     [2] if A The value is false under various assignments , be A It is contradictory or forever false ;
     [3] if A Not contradictory , said A Is satisfiable .
5. $reallyvaluesurface$
   （1） contain n(n≥1) A formula for the variables of a proposition A share 2ⁿ Assignments
   （2） notes ： Implication is false ： If and only if p It's true q For false .

Equivalent calculus

6. $lifetopicOfetc.valuesex$： if AB It's tautology , said A And B Is equivalent , Write it down as A⇔B
   （1）AB Defined as ： A→B,B→A
   （2） Important equivalence
     [1] The law of double negation ：A⇔ ¬(¬A)
     [2] Equal power law ： A⇔A∨A; A⇔A∧A
     [3] Commutative law ： A∨B ⇔ B∨A; A∧B ⇔ B∧A
     [4] Associative law ： (A∨B)∨C ⇔ A∨(B∨C);(A∧B)∧C ⇔ A∧(B∧C)
     [5] Distributive law ： A∨(B∧C))⇔ (A∨B)∧(A∨C);A∧(B∨C) ⇔ (A∧B)∨(A∧C)
     [6] De Morgan law ： ¬(A∨B) ⇔ (¬A)∧(¬B);¬(A∧B) ⇔ (¬A)∨(¬B)
     [7] The law of absorption ： A∨(A∧B) ⇔ A;A∧(A∨B) ⇔A
     [8] Law of zero ： A∨1 ⇔1;A∧0 ⇔ 0
     [9] The same thing ： A∨ 0 ⇔A;A∧1 ⇔ A
     [10] The law of excluded middle ： A∨(¬A) ⇔ 1
     [11] Law of contradiction ： A∧(¬A) ⇔ 0
     [12] Implication equivalence ： A→B ⇔ (¬A)∨B
     [13] Equivalent equation ： AB ⇔ (A→B∧B→A)
     [14] Hypothetical translocation ： A→B ⇔ (¬B)→(¬A)
     [15] Equivalent negative equivalent ： AB ⇔ (¬A)(¬B)
     [16] To fallacy ： (A→B)∧(A→(¬B)) ⇔ (¬A)
   （3） Permutation theorem ： If A⇔B, be f（A）⇔ f（B）
     [1] function ： Verify that the two propositional formulas are equivalent ; Determine the type of propositional formula （ Tautology , Paradoxical , Satisfiability ）;

Disjunctive normal form and conjunctive normal form

7. $Janesingleclosetaketype/JanesingleAnalysistaketype$：
   （1） form : Propositional argument ( p) or Propositional argument negatives (¬ p) ;
   （2） Concept ： A limited number Propositional argument Or its Negative form The conjunctive form of composition / disjunction
   （3） written words ： Propositional symbols ( Represents a propositional variable or a propositional constant ) Or the negation of propositional symbols
   （4） Example :
     [1] Three Propositional argument Or its negative form The conjunctive form of composition ( p ∧ ¬q ∧ r ) / disjunction (p ∨ ¬q ∨ r)

8. $lifetopicMaletypeOfFantype$： Disjunction (∨) normal form and Syntaxis (∧) normal form Collectively referred to as paradigms
   （1） Disjunctive normal form ： A disjunctive form consisting of a finite number of simple conjunctions , Form like A1∨A2∨…∨An; (Ai Simple conjunctive )
   （2） Conjunctive paradigm ： A conjunctive form consisting of a finite number of simple disjunctions , Form like A1∧A2∧…∧An; (Ai Is a simple disjunctive )
9. $FantypeOfsetThe\; reason\; is$
   （1） Theorem 1
     [1] A simple disjunctive is the eternal truth , If and only if it contains a propositional symbol and its negation
     [2] A simple conjunction is a contradiction , If and only if it contains a propositional symbol and its negation .
   （2） Theorem 2：
     [1] A disjunctive paradigm is paradoxical , If and only if each of its simple conjunctions is contradictory .
     [2] A conjunctive paradigm is the eternal truth form , If and only if each of its simple disjunctions is an eternal truth .
   （3） Theorem 3：（ The existence theorem of normal form ） Any propositional formula has its equivalent disjunctive normal form and conjunctive normal form .
10. $FantypeOfcaseexample$
    （1） The steps to find the normal form of a formula are as follows ：
      [1] Eliminate the conjunction → and , Make the formula contain only connectives ¬、∧ and ∨： Using implication equivalence $(A\to B)\iff (\neg A\vee B)$ And equivalent equivalence $(AB)\iff (\neg A\vee B)\wedge (A\vee \neg B)$.
      [2] Using the law of double negation ¬¬A⇔A Eliminate the double negative word , De Morgan's law shifts negatives inward .
      [3] Using the law of distribution , Find disjunctive normal form ∧ Yes ∨ The law of distribution in the world , The conjunctive normal form uses ∨ Yes ∧ The law of distribution in the world .
    （2） seek (¬p→q)∧(p→r) Disjunctive normal form and conjunctive normal form
      [1] Disjunctive normal form : (¬p→q)∧(p→r)⇔(¬¬p∨q)∧(¬p∨r) ⇔(p∨q)∧(¬p∨r)⇔(p∧¬p)∨(p∧r)∨(q∧¬p)∨(q∧r)⇔(p∧r)∨(q∧¬p)∨(q∧r)
      [2] Conjunctive paradigm :(¬p→q)∧(p→r)⇔(p∨q)∧(¬p∨r)

11. $extremelySmallterm$: yes A kind of Simple conjunction , True assignment
    （1） Concept ： Satisfying the following three points is the minimum term , The first i A minimal term , be called m _i .
      [1] contain n A simple conjunctive of words
      [2] If every propositional sign does not exist at same time as its negation , One of the two must occur and only once
      [3] The first i A propositional argument or negation appears on the left i A place （ If argument of the a proposition has no subscript , Then arrange them in dictionary order )
    （2） Number of minimal terms ：n individual Propositional arguments produce 2ⁿ individual minterm
    （3） Not equal to each other ： 2ⁿ individual The minimum terms are not equivalent to each other
    （4） Minimum item table
    
12. $extremelyBigterm$: yes A kind of Simple disjunctive , False assignment
    （1） Concept ： Satisfying the following three points is the largest item , The first i A very large item , be called M _i .
      [1] contain n A simple disjunctive of words
      [2] If every propositional sign does not exist at same time as its negation , One of the two must occur and only once
      [3] The first i A propositional argument or negation appears on the left i A place （ If argument of the a proposition has no subscript , Then arrange them in dictionary order )
    （2） The number of maximal terms ：n individual Propositional arguments produce 2ⁿ individual minterm
    （3） Not equal to each other ： 2ⁿ individual The maximal terms are not equivalent to each other
    （4） Maximum term table
    
    （5） The maximal term M _i And minima m _i The relationship between :
      [1] ¬ m _i * M _i
      [2] ¬ M _i * m _i

13.$LordAnalysistakeFantype$: All simple conjunctions are disjunctive normal forms of minimal terms
(1) Theorem ： Any propositional formula has a unique equivalent principal disjunctive normal form
(2) Find the propositional formula A The main disjunctive normal form step of
  [1] seek A A disjunctive normal form of
  [2] For example, a simple conjunctive of the disjunction B It contains no argument of a certain proposition $p$, It doesn't contain $\neg p$, Then the simple conjunctive becomes ：（B ∧ $p$）∨ （B ∧ $\neg p$）
  [3] Eliminate repeated propositional arguments or negations , Paradoxical and recurring minima , And arrange the propositional arguments or negations of each minimal term in subscript order or dictionary order .
(3) Case study ：(¬p→q)∧(p→r)
  [1] adopt 10 have to (¬p→q)∧(p→r) A disjunctive normal form of is (p∧r)∨(q∧¬p)∨(q∧r)
  [2] Each simple conjunctive is expanded to disjunction of the minimal terms containing all propositional arguments :
     (p∧r)：(p∧q∧r)∨(p∧¬q∧r),(q∧¬p)：(¬p∧q∧r)∨(¬p∧q∧¬r),(q∧r)：(p∧q∧r)∨(¬p∧q∧r)
  [3] Eliminate duplicate ：(p∧q∧r)∨(p∧¬q∧r)∨(¬p∧q∧r)∨(¬p∧q∧¬r)
  [4] Rearrange according to the size of the binary number corresponding to the minimum term ：(¬p∧q∧¬r)∨(¬p∧q∧r)∨(p∧¬q∧r)∨(p∧q∧r)

14.$LordclosetakeFantype$: All simple disjunctions are conjunctive normal forms of maximal terms
(1) Theorem ： Any propositional formula has a unique equivalent principal conjunctive normal form
(2) Find the propositional formula A The main disjunctive normal form step of
  [1] seek A The conjunctive paradigm of A ’
  [2] Such as A ’ A simple disjunctive of B It contains no argument of a certain proposition $p$, It doesn't contain $\neg p$, Then the simple conjunctive becomes ：B⇔B∨0⇔B∨(p∧┐p)⇔(B∨p)∧(B∨p)
  [3] Eliminate repeated propositional arguments or negations , Paradoxical and recurring minima , And arrange the propositional arguments or negations of each minimal term in subscript order or dictionary order .
(3) Case study ：(p→¬q)→r
  [1] Find conjunctive normal form ：(p∨r)∧(q∨r)
  [2] take (p∨r) To The main conjunctive paradigm :
     (p∨r) * (p∨0∨r) * (p∨(q∧¬q)∨r) * ((p∨r)∨(q∧¬q)) * (p∨r∨q)∧(p∨r∨¬q) * (p∨q∨r)∧(p∨¬q∨r)
  [3] according to Maximal term formula Write the corresponding serial number : (p∨q∨r): False assignment 000, The maximal term M₀; (p∨¬q∨r): False assignment 010, Is a maximal term M₂ ;
  [4] (p∨r) Corresponding The principal conjunctive paradigm is :(p∨q∨r)∧(p∨¬q∨r)    *   M₀ ∧ M₂
  [5] take (q∨r) To The main conjunctive paradigm : ( p∨q∨r)∧(¬p∨q∨r)    *    M₀ ∧ M₄
  [6] (p∨r)∧(q∨r) * M₀ ∧ M₂ ∧ M₄

15. $reallyvaluesurfaceseekLordAnalysistakeFantypeandLordclosetakeFantype$
    （1） Conditions : A = ( p → ¬ q ) → r
    

16. $lifetopicLogicCompilationOfPUSHThe\; reason\; isThe\; reason\; isOn$
    (1) Reasoning : From Premise Introduction Conclusion The process of thinking
      [1] Premise ： The known propositional formula
      [2] Conclusion ： A proposition formula derived from the application of inference rules was proposed
    （2） Premise and The conclusions are as follows 4 Kind of ：
      [1] A₁ ∧ … ∧ A_k by 0,B by 0;
      [2] A₁ ∧ … ∧ A_k by 0,B by 1;
      [3] A₁ ∧ … ∧ A_k by 1,B by 0;
      [4] A₁ ∧ … ∧ A_k by 1,B by 1;
    As long as it doesn't show up [3], Reasoning is right .
    （3）A ⇒ B Express “A → B” It's tautology .B Is the logical conclusion / Valid conclusion .
    （4） Case study ：
      [1] {p, p → q}
      [2] {p, q → p}
      [3] Reasoning [1] There was no The phenomenon 【3】, The reasoning is correct
      [4] Reasoning [2] appear The phenomenon 【3】, Wrong reasoning
    
17. $heavywantOfPUSHThe\; reason\; issetLaw$
    (1) The laws of
      [1] Additional law ：A⇒(A∨B)
      [2] The law of simplification ：(A∧B)⇒A,(A∧B)⇒B
      [3] Hypothetical reasoning ：(A→B)∧A⇒B
      [4] Reject ：(A→B)∧¬B⇒¬A
      [5] Disjunctive syllogism ：(A∨B)∧¬B⇒A
      [6] Hypothetical syllogism ：(A→B)∧(B→C)⇒(A→C)
      [7] Equivalent syllogism ：(AB)∧(BC)⇒(AC)
      [8] Structural dilemma ：(A→B)∧(C→D)∧(A∨C)⇒(B∨D)
    (2) Case study ：((p∨q)∧¬p)→q
      [1] Equivalent calculus is used to judge whether the above formula is tautological ((p∨q)∧¬p)→q⇔((p∧¬p)∨(q∧¬p))→q⇔(q∧¬p)→q
    ⇔¬(q∧¬p)∨q⇔¬q∨p∨q⇔1
      [2] The above form is tautological , So the reasoning is correct
18. $PUSHThe\; reason\; isgaugebe$
    （1）A₁ , … , A_k |- B, Express B yes A₁ , … , A_k The logical conclusion of .
    （2） In the sequence of proofs , If you have any A₁ , … , A_k, Then we can introduce B.

Predicate logic （ First order logic ）

1. $Janesinglelifetopic$： It can be divided into two parts: individual words and predicates .
   （1） Individual words ： An individual that can exist independently , It can be concrete things , Can represent abstract concepts
   （2） The predicate ： Describe the nature of individual words and the relationship between individual words
   （3） Predicate element ： The number of individuals associated with the predicate
   （4） Individual items ： An individual word that denotes a specific or specific individual , Generally lower case letters a,b,… Express
   （5） Individual variables ： An individual word that represents an abstract or general reference , commonly x,y,… Express
   （6） Individual domain （ Domain ）： The value range of the individual variable , Can and poor collection , It can also be an infinite set , Commonly used D Express
   （7） Total individual domain ： The individual domain of all things
   （8） function / Letter item ： Predicate logic can introduce functions that map individuals to individuals / Letter item , Such as F(x): x Is odd
2. $The\; amountword$： A word that expresses quantity in a proposition , Full name quantifier , There are quantifiers
   （1） Full name quantifier : “ everything ”、“ all ”、“ arbitrarily ” etc. , use “∀” Express ,∀xF(x) Indicates that all individuals in the individual domain have properties F.
     [1] ∀xP(x) It's true , If and only if for all individuals in the universe x There are P(x) It's true
     [2] Translated into →
   （2） There are quantifiers : “ There is ”、“ There is one ”、“ At least one ” etc. , use “∃” Express ,∃xF(x) Indicates that the individual in the individual domain has the property F.
     [1] ∃xP(x) It's true , If and only if there is at least one individual in the universe x₀ send F(x₀) It's true
     [2] Translated into ∧
   

3. $OnerankLogicCompilationetc.valuetype$
   （1） set up A、B Is a first-order logic formula , if AB It's Yongzhen style , said A And B Is equivalent , Write it down as A⇔B , call A⇔B Is the equivalent of . for example ：∃xF(x)⇔∃xF(x)∧∃xF(x),∀xF(x)∧¬∀xF(x)⇔0,∃xF(x)∨¬∃xF(x) ⇔1;
   （2） Equivalent calculus method 1： Eliminate quantifier equivalents
     [1] ∀x A(x)⇔ A(a₁) ∧ A(a₂) ∧…∧ A(a_n)
     [2] ∃x A(x)⇔ A(a₁) ∨ A(a₂) ∨…∨ A(a_n)
   （3） Equivalent calculus method 2： The quantifier negates the equivalent
     [1] ¬∀ x A(x)⇔∃x ¬A(x)
     [2] ¬∃x A(x)⇔ ∀x ¬A(x)
   （4） Equivalent calculus method 3： The equivalent of quantifier distribution
     [1] ∀x (A(x)∧B(x))⇔∀ xA(x)∧∀x B(x)
     [2] ∃x (A(x)∨B(x))⇔∃ xA(x)∨∃x B(x)
   (5) Case study
     [1] ¬∀x (F(x)→G(x))⇔¬∀x (¬F( x )∨G(x))
   ⇔∃x ¬(¬F(x)∨G(x)) ⇔∃x(F(x)∧¬G(x))
     [2] ¬∀x∀y (F(x)∧G(y)→H(x,y)) ⇔ ∃x∃y ¬(F(x)∧G(y)→H(x,y))⇔∃x∃y ¬(¬(F(x)∧G(y))∨H(x,y))⇔∃x∃y (F(x)∧G(y)∧¬H(x,y))

4. $frontbeamFantype$
   （1） set up A Is a first-order logic formula , if A It has the following form Q₁ x₁ … Q_nx_n B, said A Is the toe in paradigm .
     [1] among Q i yes ∀ / ∃,i =1, …, n, B It's a formula for non content words , example ∀x∀y∃z (P(x,y)→H(x,z)) and ∃x∃y∃zP(x,y,z)
   （2） Theorem ： For any order logic formula, there is a bundle normal form equivalent to it （ But the form is not unique ）
   （3） Case study
     [1] ∀xF(x)∧¬∃xG(x)⇔∀xF(x)∧∀x¬G(x) The quantifier negates the equivalent
       ⇔∀x(F(x) ∧¬G(x)) The equivalent of quantifier distribution
     [2] ∀xF(x) ∨¬∃xG(x)⇔∀xF(x)∨∀x¬G(x) The quantifier negates the equivalent
       ⇔∀yF(y)∨∀x¬G(x) Constraint variable renaming rule
       ⇔∀y∀x (F(y) ∨¬G(x)) Quantifier contraction expansion equivalence
       ⇔∀y∀x (G(x)→F(y))
5. . $OnerankLogicCompilationOfPUSHThe\; reason\; is$
   (1) Socrates' syllogism
   Explain ： Take the total individual field , set up F(x):x Is the person , G(x):x It's going to die , a: Socrates .
   Premise : ∀x (F(x)→G(x)), F(a);
   Conclusion : G(a)
   prove : Introduction premise ∀x (F(x)→G(x)), Eliminate the whole quantifier F(a)→G(a),
       Introduction premise F(a), Come to the conclusion : G(a), That is to say : ( ∀x (F(x)→G(x)) )∧F(a) → G(a)