Propositional Calculus Proofs (4)

Th17) ⊢ ¬T ⇒ (T ⇒ U)
1.) ⊢ (¬U ⇒ ¬T) ⇒ (T ⇒ U)                                  Lk3                               
2.) ⊢ ¬T ⇒ [(¬U ⇒ ¬T) ⇒ (T ⇒ U)]                   Th1
3.) ⊢ [¬T ⇒ (¬U ⇒ ¬T)] ⇒ [¬T ⇒ (T ⇒ U)]     Th2
4.) ⊢ ¬T ⇒ (¬U ⇒ ¬T)                                          Lk1
5.) ⊢ ¬T ⇒ (T ⇒ U)                                                MP 3,4

CIC Proofs (5)

Th12) ⊢ (P ⇒ Q) ⇒ [(Q ⇒ R) ⇒ (P ⇒ R)]
1.) (P ⇒ Q) ⇒ [(Q ⇒ R) ⇒ (P ⇒ Q)]                                    Lk1
2.) ⊢ (Q ⇒ R) ⇒ [(P ⇒ Q) ⇒ (P ⇒ R)]                                Th11
3.) ⊢ (P ⇒ Q) ⇒ {(Q ⇒ R) ⇒ [(P ⇒ Q) ⇒ (P ⇒ R)]}         Th1
4.) ⊢ (P ⇒ Q) ⇒ [(Q ⇒ R) ⇒ (P ⇒ R)]                                 Th9

Th13) A ⇒ (B ⇒ C), (D ⇒ B) ⊢ A ⇒ (D ⇒ C)

1.) ⊢ D ⇒ B                                                            Hyp
2.) ⊢ (D ⇒ B) ⇒ [(B ⇒ C) ⇒ (D ⇒ C)]              Th12

3.) ⊢ (B ⇒ C) ⇒ (D ⇒ C)                                     MP 1,2

4.) ⊢ A ⇒ (B ⇒ C)                                                Hyp

5.) ⊢ A ⇒ (D ⇒ C)                                                Th5

Th14) O ⇒ (U ⇒ V), (V ⇒ W) ⊢ O ⇒ (U ⇒ W)
 1.) ⊢ V ⇒ W                                                          Hyp
2.) ⊢ (V ⇒ W) ⇒ [(U ⇒ V) ⇒ (U ⇒ W)]           Th11
3.) ⊢ (U ⇒ V) ⇒ (U ⇒ W)                                   MP 1,2
4.) ⊢ O ⇒ (U ⇒ V)                                                Hyp
5.) ⊢ O ⇒ (U ⇒ W)                                               Th5

Th15) ⊢ [G ⇒ (H ⇒ J)] ⇒ [H ⇒ (G ⇒ J)]       Law of Commutation
1.) ⊢ [G ⇒ (H ⇒ J)] ⇒ [(G ⇒ H) ⇒ (G ⇒ J)]    Lk2
2.) ⊢ H ⇒ (G ⇒ H)                                              Lk1
3.) ⊢ [G ⇒ (H ⇒ J)] ⇒ [H ⇒ (G ⇒ J)]               Th13

Th16) ⊢ A ⇒ [(A ⇒ B) ⇒ B]                                Law of Assertion
1.) ⊢ (A ⇒ B) ⇒ (A ⇒ B)                                        Th3
2.) ⊢ [(A ⇒ B) ⇒ A] ⇒ [(A ⇒ B) ⇒ B]                 Th2
3.) ⊢ A ⇒ [(A ⇒ B) ⇒ A ]                                       Lk1
4.) ⊢ A ⇒  [(A ⇒ B) ⇒ B]                                       Th5

Cube

Formula Synthesis (Examples)

Assume D = [●,○,●,○] is the set of desired truth values for an unknown formula D. Since, D has four values, D must have two atomic components. Allow A and B to be atomic components of D. If A = [○,○,●,●] and B = [○,●,○,●], then the minterms of A and B are (A ∧ B) = [○,●,●,●] , (A ∧ ¬B) = [●,○,●,●] , (¬A ∧ B) = [●,●,○,●] , (¬A ∧ ¬B) = [●,●,●,○]. Consequently, (A ∧ ¬B) and (¬A ∧ ¬B) are the proper minterms to choose. When combined into a disjunction [(A ∧ ¬B) ∨ (¬A ∧ ¬B)] = [●,○,●,○] = D.

Assume C is an unknown formula and C = [○,●,●,●,●,●,●,●]. C must have three atomic components because there are eight truth values in C. If E, F, and G are the atomic components of formula C, then [(E ∧ F) ∧ G] = [○,●,●,●,●,●,●,●] is the only minterm needed because C has only one true truth value. C is what is called a "consensus" formula because E, F, and G must all be true in order for C to be true.

Back To Basics (5) Formula Synthesis

A logical formula possessing only one occurrence of ○ in its truth table is called a minterm.

The above examples can be used to construct logical formulae for any desired pattern of truth values given it has two components. Assume R is the desired yet unknown formula with two true and two false values and in the order. (Blogger is being stupid right now. I will have to put the truth values in row vector form... For some reason it won't let me upload another photo)

So, R = [○,○,●,●] and C1 = [○,●,●,●] C2 = [●,○,●,●] where C1 C2 are component formula. According to the above table C1 is the third column from the left and C2 is the fourth column from the left. Once the formulae are identified use a disjunction between the two component formula. C1 ∨ C2 or R ⇔ (A ∧ B) ∨ (¬A ∧ B). The formula is in what is called disjunctive normal form. It is a sequence of conjunctions divided by disjunctions.

Back to Basics (4) Proof by Contradiction

The method of proof by contradiction establishes a statement as true by showing that its negation leads to two mutually exclusive results. This method is made possible by the fact that in Boolean Algebraic logic a proposition is either true or false and no where in between. 

For every contradiction N and every proposition ᵹ the formula ᵹ ⇔ ( ¬ᵹ ⇒ N) is a tautology. If ¬ᵹ ⇒ N is true, then ᵹ is true by contraposition. N can also be represented by (ᴔ ∧ ¬ᴔ) where ᴔ is a proposition. If it can be shown that ¬ᵹ ⇒ ᴔ and ¬ᵹ ⇒ ¬ᴔ, then [¬ᵹ ⇒ (ᴔ ∧ ¬ᴔ)] ⇔ ( ¬ᵹ ⇒ N). Since, the proposition ¬ᵹ ⇒ (ᴔ ∧ ¬ᴔ) can be constructed (is true) the only possibility is that ¬ᵹ must be false.

Assume P and Q are propositions, P ⇒ Q, and (P ⇒ Q) ⇔ ᵹ. (P ⇒ Q) ⇔ ¬(P ∧ ¬Q). So, ¬ᵹ ⇔ (P ∧ ¬Q). In order to prove ¬ᵹ ⇒ (ᴔ ∧ ¬ᴔ), if P ⇒ ᴔ and ¬Q ⇒ ¬ᴔ, then ¬ᵹ ⇒ (ᴔ ∧ ¬ᴔ) since [(P ⇒ ᴔ) ∧ (¬Q ⇒ ¬ᴔ)] ⇒ [(P ∧ ¬Q) ⇒ (ᴔ ∧ ¬ᴔ)]. Therefore P ⇒ Q is true according to the method of proof by contradiction.

Back To Basics (3) Proof by Tautology

Tautologies can be used to prove new propositions or justify old ones. The transitive property of both ⇒ and ⇔ allow this to be done. Start with truth tables to demonstrate their transitivity, then use proof by tautology. (Tautologies listed on pages tab at the top right corner of the Home page)

Proof by Tautology 1

1.) A ∧ B                                         Assume

2.) ¬[¬(A ∧ B)]                             t8

3.) ¬[(¬A ∨ ¬B)]                           De Morgan's First Law

 ∴ (A ∧ B) ⇔ ¬[(¬A ∨ ¬B)]        Conclusion

Each line in this proof is equivalent to the next. The transitive property allows for the "detachment" and/or "addition" of propositions. Since each line from the first is a tautology built from line one, each proposition must therefore be equivalent to the first.

Proof by Tautology 2

1.) ¬A ∧ ¬B                             Assume

2.) ¬{[¬(¬A)] ∨ ¬(¬B)]}       Proof by Tautology 1

3.) ¬{A ∨ B}                            Complete Law of Double Negation

∴ ¬A ∧ ¬B ⇔ ¬{A ∨ B}        Conclusion

Tetrahedron

Back to Basics (2) Tautologies and Contradictions

A formula is a tautology iff it is true for all possible truth values of its components. To find out if a propositional form is a tautology a truth table is a sufficient means of proof. Here is a list of five important tautological formulae:

1.) A ∨ ¬A                                                         Law of Excluded Middle
2.) ¬(¬A ) ⇔ A                                                 Complete Law of Double Negation
3.) (A ⇒ B) ⇔ (¬B ⇒ ¬A)                               Complete Law of Contraposition
4.) (A ⇒ (B ⇒ C) ⇒ [(A ⇒ B) ⇒ (A ⇒ C)]     Transitivity of Logical Implication
5.) (A ∧¬A) ⇒ B                                               A Contradiction Implies Every Consequent

A and B are logical formulae and logically equivalent iff A ⇔ B is a tautology.

A formula is a contradiction iff it is false for all possible truth values of its components. To find out if a propositional form is a contradiction again a truth table can be used. Here are a couple examples of contradictions:

1.) A ∧¬A
2.) (A ∧ B) ∧ (¬A ∧ ¬B)