of 4

Deducibility Theorems | Theorem | Mathematical Proof

9 views
All materials on our website are shared by users. If you have any questions about copyright issues, please report us to resolve them. We are always happy to assist you.
Share
Description
DEDUCIBILITY THEOREMS IN BOOLEAN LOGIC Florentin Smarandache University of New Mexico 200 College Road Gallup, NM 87301, USA E-mail: smarand@unm.edu ABSTRACT In this paper we give two theorems from the Propositional Calculus of the Boolean Logic with their consequences and applications and we prove them axiomatically. §1. THEOREMS, CONSEQUENCES In the beginning I shall put forward the axioms of the Propositional Calculus. A ⊃ (B ⊃ A) , I. a) b) ( A ⊃ ( B ⊃ C )) ⊃ (( A ⊃ B) ⊃ ( A ⊃ C)) . II. a)
Tags
Transcript
   1  DEDUCIBILITY THEOREMS IN BOOLEAN LOGIC Florentin SmarandacheUniversity of New Mexico200 College RoadGallup, NM 87301, USAE-mail: smarand@unm.edu   ABSTRACT In this paper we give two theorems from the Propositional Calculus of theBoolean Logic with their consequences and applications and we prove themaxiomatically. §1. THEOREMS, CONSEQUENCES In the beginning I shall put forward the axioms of the Propositional Calculus.I. a)     A ⊃ (  B ⊃ A ) , b)  ABCABAC  ⊃ ⊃ ⊃ ⊃ ⊃ ⊃  (())(()()) .II. a)     A ∧ B ⊃ A , b)     A ∧ B ⊃ B ,c)  (  A ⊃ B ) ⊃ ((  A ⊃ C  ) ⊃ (  A ⊃ B ∧ C  )) .III. a)     A ⊃ A ∨ B , b)     B ⊃ A ∨ B ,c) )  ACBCABC  ⊃ ⊃ ⊃ ⊃ ∨ ⊃  ((()()) .IV. a)  (  A ⊃ B ) ⊃ (  B ⊃ A ) , b)     A ⊃ A ,c)     A ⊃ A .. THEOREMS. If:       A ι ⊃ B i , i = 1, n , then1)     A 1 ∧ A 2 ∧ ... ∧ A n ⊃ B 1 ∧ B 2 ∧ ... ∧ B n ,2)  A 1 ∨ A 2 ∨ ... ∨ A n ⊃ B 1 ∨ B 2 ∨ ... ∨ B n .  Proof: It is made by complete induction. For  n = 1 :     A 1 ⊃ B 1 , which is true from thegiven hypothesis. For  n = 2 : hypotheses     A 1 ⊃ B 1 ,     A 2 ⊃ B 2 ; let’s show that     A 1 ∧ A 2 ⊃ B 1 ∧ B 2 . We use the axiom II, c) replacing  A → A 1 ∧ A 2 ,  B → B 1 , C  → B 2 ,it results:(1)  (  A 1 ∧ A 2 ⊃ B 1 ) ⊃ ((  A 1 ∧ A 2 ⊃ B 2 ) ⊃ (  A 1 ∧ A 2 ⊃ B 1 ∧ B 2 )) .We use the axiom II, a) replacing  A → A 1 ,  B → A 2 ; we have     A 1 ∧ A 2 ⊃ A 1 . But     A 1 ⊃ B 1 (hypothesis) applying the syllogism rule, it results     A 1 ∧ A 2 ⊃ B 1 .Analogously, using the axiom II, b), we have     A 1 ∧ A 2 ⊃ B 2 . We know that     A 1 ∧ A 2 ⊃ B i , i = 1,2 , are deducible, then applying in (I) inference rule twice, we have     A 1 ∧ A 2 ⊃ B 1 ∧ B 2 .   2 We suppose it’s true for  n ; let’s prove that for  n + 1 it is true. In     A 1 ∧ A 2 ⊃ B 1 ∧ B 2 replacing  A 1 → A 1 ∧ ... ∧ A n ,  A 2 → A n + 1 ,  B 1 → B 1 ∧ ... ∧ B n ,  B 2 → B n + 1 and using induction hypothesis it results     A 1 ∧ ... ∧ A n ∧ A n + 1 ⊃ B 1 ∧ ... ∧ B n ∧ B n + 1 and item 1) from the Theorem is proved.2) It is made by induction. For  n = 1 ; if      A 1 ⊃ B 1 , then of course     A 1 ⊃ B 1 . For  n = 2 : if      A 1 ⊃ B 1 and     A 2 ⊃ B 2 , then     A 1 ∨ A 2 ⊃ B 1 ∨ B 2 .We use axiom III, c) replacing  A → A 1 ,  B → A 2 , C  → B 1 ∨ B 2 we get(2) 1212212 )(()())  ABBABBAABB ⊃ ∨ ⊃ ⊃ ∨ ⊃ ∨ ⊃ ∨  121 ( .Let’s show that     A 1 ⊃ B 1 ∨ B 2 . We use the axiom III, a) replacing  A → B 1 ,  B → B 2 we get     B 1 ⊃ B 1 ∨ B 2 and we know from the hypothesis  A 1    B 1 . Applying thesyllogism we get     A 1 ⊃ B 1 ∨ B 2 .In the axiom III, b) replacing  A → B 1 ,  B → B 2 , we get     B 2 ⊃ B 1 ∨ B 2 . But     A 2 ⊃ B 2 (from the hypothesis), applying the syllogism we get     A 2 ⊃ B 1 ∨ B 2 . Applyingthe inference rule twice in (2) we get 212  AABB ∨ ⊃ ∨ 1  .Suppose it’s true for  n and let’s show that for  n + 1 it is true. Replace in 212  AABB ∨ ⊃ ∨  1 (true formula if      A 1 ⊃ B 1 and     A 2 ⊃ B 2 ) 1211121 ..., , ..., nnnn  AAAAABBBBB + + → ∨ ∨ → → ∨ ∨ → 1 . From induction hypothesis itresults     A 1 ∨ ... ∨ A n ∨ A n + 1 ⊃ B 1 ∨ ... ∨ B n ∨ B n + 1 and the theorem is proved. CONSEQUENCES. 1°) If      A ι ⊃ B , i = 1, n then     A 1 ∧ ... ∧ A n ⊃ B .2°) If      A ι ⊃ B , i = 1, n , then      A 1 ∨ ... ∨ A n ⊃ B .  Proof: 1°) Using 1) from the theorem, we get(3) 1 ...... n  AABB ∧ ∧ ⊃ ∧ ∧    ( n times).In axiom II, a) we replace  A → B ,  B → B ∧ ... ∧ B ( n − 1 times), and we get(4)     B ∧ ... ∧ B ⊃ B (n times).From (3) and (4) by means of the syllogism rule we get     A 1 ∧ ... ∧ A n ⊃ B .2°) Using 2) from theorem, we get     A 1 ∨ ... ∨ A n ⊃ B ∨ ... ∨ B ( n times). LEMMA.  ...  BBB ∨ ∨ ⊃    ( n times), n ≥ 1 .  Proof:  It is made by induction. For  n = 1 , obvious. For  n = 2 : in axiom III, c) we replace  A → B , C  → B and we get   (  B ⊃ B ) ⊃ ((  B ⊃ B ) ⊃ (  B ∨ B ⊃ B )) . Applying theinference rule twice we get  BBB ∨ ⊃    .Suppose for  n that the formula is deducible, let’s prove that is for  n + 1 .We proved that  B ⊃ B . In axiom III, c) we replace  A → B ∨ ... ∨ B ( n times), C  → B , and we get  (  B ∨ ... ∨ B ⊃ B ) ⊃ ((  B ⊃ B ) ⊃ (  B ∨ ... ∨ B ⊃ B )) ( n times).Applying two times the interference rule, we get     B ∨ ... ∨ B ⊃ B ( n + 1 times) solemma is proved.From     A 1 ∨ ... ∨ A n ⊃ B ∨ ... ∨ B ( n times) and applying the syllogism rule, fromlemma we get  Α 1 ∨ ... ∨ A n ⊃ B .   3 3°)     A ∧ ... ∧ A ⊃ A ( n times)4°)     A ∨ ... ∨ A ⊃ A ( n times).Previously we proved, replacing in Consequence 1°) and 2°),  B → A . Analogously, theconsequences are proven:5°) If      A ⊃ B i , i = 1, n , then     A ⊃ B 1 ∧ ... ∧ B n .6°) If      A ⊃ B i , i = 1, n , then     A ⊃ B 1 ∨ ... ∨ B n .Analogously,7°)     A ⊃ A ∧ ... ∧ A ( n times)8°)     A ⊃ A ∨ ... ∨ A ( n times)9°)     A 1 ∧ ... ∧ A n ⊃ A 1 ∨ ... ∨ A n .  Proof: Method I. It is initially proved by induction:     A 1 ∧ ... ∧ A n ⊃ A i , i = 1, n and 2) is appliedfrom the Theorem.Method II. It is proven by induction that:     A ι ⊃ A 1 ∧ ... ∧ A n , i = 1, n and then 1) isapplied from the Theorem.10°) If      A ι ⊃ B i , i = 1, n , then     A 1 ∧ ... ∧ A n ⊃ B 1 ∨ ... ∨ B n .  Proof: Method I. Using 1) from the Theorem, it results:(5)     A 1 ∧ ... ∧ A n ⊃ B 1 ∧ ... ∧ B n  We apply the Consequence 9°) where we replace  A i → B i , i = 1, n and results:(6)  B 1 ∧ ... ∧ B n ⊃ B 1 ∨ ... ∨ B n .From (5) and (6), applying the syllogism rule we get 10°).Method II. We firstly use the Consequence 9°) and then 2) from the Theorem and so weobtain the Consequence 10°). §2. APPLICATIONS AND REMARKS ON THEOREMS The theorems are used in order to prove the formulae of the shape:     A 1 ∧ ... ∧ A  p ⊃ B 1 ∧ ... ∧ B r        A 1 ∨ ... ∨ A  p ⊃ B 1 ∨ ... ∨ B r  , where  p , r  ∈ N ∗  It is proven that     A ι ⊃ B  j , i.e. ∀ i ∈ 1, p , ∃  j 0 ∈ 1, r  ,  j 0 = j 0 ( i ) ,     A ι ⊃ B  j 0  and ∀  j ∈ 1, r  , ∃ i 0 ∈ 1, p , i 0 = i 0 (  j ) ,     A ι 0 ⊃ B  j . EXAMPLES : The following formulas are deducible:(i)     A ⊃ (  A ∨ B ) ∧ (  B ⊃ A ) ,(ii)    (  A ∧ B ) ∨ C  ⊃ A ∨ B ∨ C  ,(iii)     A ∧ C  ⊃ A ∨ C  . Solution: (i)   We have     A ⊃ A ∨ B and     A ⊃ (  B ⊃ A ) (axiom III, a) and I, a)) andaccording to 1) from Theorem it results (i).   4 (ii)   From     A ⊃ (  B ⊃ A ) ,     A ∧ B ⊃ B , CC  ⊃  and Theorem 1), we have(ii).(iii)   Method I. From     A ∧ C  ⊃ A ,     A ∧ C  ⊃ C  and Theorem 2).Method II. From     A ⊃ A ∨ C  , CAC  ⊃ ∨    and using Theorem 1). REMARKS. 1) The reciprocals of Theorem 1) and 2) are not always true.a) Counter-example for Theorem 1). The formula     A ∧ B ⊃ A ∧ A is deduciblefrom axiom II, a),  AAA ∧ ⊃    (Consequence 7°) and the syllogism rule. But     A ⊃ A  for all A, that the formula  B ⊃ A is not deducible, so the reciprocal of the Theorem 1) isfalse.Counter-example for Theorem 2). The formula     A ∨ A ⊃ A ∨ B is deduciblefrom Lemma, axiom III, a) and applying the syllogism rule. But     A ⊃ A for all A, thatthe formula  A ⊃ B is not deducible, so the reciprocal of Theorem 2) is false.2) The reciprocals of Theorem 1) and 2) are not always true.Counter-examples:a)   for Theorem 1):     A ⊃ A and  BA ⊃/ results that     A ∧ B ⊃ A ∧ A so thereciprocal of Theorem 1) is false. b)   for Theorem 2):     A ⊃ A and  AB ⊃/ results that     A ∨ A ⊃ A ∨ B so thereciprocal of Theorem 2) is false. REFERENCES: [1] P. S. NOVOKOV. Elemente de logic ă matematic ă , Editura Ş tiin ţ ific ă ,Bucure ş ti, 1966.[2] H. FREUDENTHAL, Limbajul logicii matematice, Editura Tehnic ă ,Bucure ş ti, 1973.UNIVERSITATEA DIN CRAIOVA  Facultatea de Ş  tiinte Exacte 24.10.1979[Published in “An. Univ. Timi ş oara”, Seria Ş t. Matematice, Vol. XVII, Fasc. 2,1979, pp. 164-8.]
Related Search
We Need Your Support
Thank you for visiting our website and your interest in our free products and services. We are nonprofit website to share and download documents. To the running of this website, we need your help to support us.

Thanks to everyone for your continued support.

No, Thanks