4/The Matrix Test of Equivalence
3/THE MATRIX TEST OF EQUIVALENCE YolaFile-15.1126
s15. INTERDEFINITIONS OF TRUTH-FUNCTIONS
15a. Negation and Conjunction. P=(--p) by the Principle of Double Negation. Negating -–p will give us –p and by the Principle of Triple Negation, we have –p=-(--p)
Matrix:
1 2 3
p |-p = -(--p)
--|------
1 |0 1 0 1
0 |1 1 1 0
For conjunction, the expression p.q assumes the truth of both statements since neither one of them is negated. But to say that both p and q are true is to deny that either one of them is false.
To deny that either one is false is to assert the truth of both statements. Hence,p.q)= -(-pv-q).
Example: Boole is both beautiful and kind
Interpretation : it is false: -
that Boole is not beautiful: -p
or : v
Boole is not kind: -q Hence, -( -p v -q)
Df. = conjunction is logically equivalent to the negation of the disjunction of false statements.
Matrix: Guide Col. 1 2 3
p q : p.q -pv-q -(-pv-q)
------
1 1 : 1 0 1
1 0 : 0 1 0
0 1 : 0 1 0
0 0 : 0 1 0
15b. Disjunction and Implication. pvq is a disjunction of true statements. In its inclusive sense, any disjunction of true statements asserts that at least one of the disjuncts is true or possibly both. Since the truth rather than the falsity of both disjunction may be asserted a disjunction denies that neither one nor the other is false -> (-p.-q). To deny that both are false is to assert that either one is true and possibly both. Hence, (pvq)=-(-p.-q)
Example: Either John Venn is lazy or sleepy
Interpretation: it is false: -
that Venn is not lazy: -p
and : .
that Venn is not sleepy: -q Hence,-(-p.-q)
Df.= disjunction is logically equivalent of the negation of the conjunction of false statements.
-2-
Matrix: 1 2 3
p q : pvq -p.-q -(-p.-q)
------
1 1 : 1 0 1 0
1 0 : 1 0 1 0
0 1 : 1 0 1 0
0 0 : 0 1 0 1
The implication, `if p, then q' asserts that if p is true, then q is equally true. Because an implication is false if the antecedent is true and the consequent is false, we deny that the antecedent is true, but the consequent is false.
Example: if Pierre de Fermat's last theorem is correct, then he was a great mathematician.
Interpretation: It is not the case: -
that de Fermat’s last theorem is correct: p
but : .
that he was not a great mathematician: -q Hence, (p>q)= -(p.-q)
Matrix: 1 2 3
p q : p>q p.-q -(p.-q)
------
1 1 : 1 0 1 0
1 0 : 0 1 0 1
0 1 : 1 0 1 0
0 0 : 1 0 1 0
`if p, then q’ also have a disjunctive equivalent.
Example: if Boole wrote the Laws of Thought, then he was a great logician.
Interpretation: either
Boole did not write the book: -p
Or: v
that he was a great logician: q Hence, (p>q) = (-pvq)
Matrix: 1 2 3
p q : p>q -pvq (p>q)=(-pvq)
------
1 1 : 1 1 1
1 0 : 0 0 1
0 1 : 1 1 1
0 0 : 1 1 1
15c. Biconditional. (p:q)= [(p>q).(q>p)]. This is in accordance with the idea that both statements materially imply each other.
Another way of analyzing the biconditional is to take into account the truth values of the variables as shown in the matrix for biconditional, i.e.
-3-
either
both p and q are true: p.q
or : v
both p and q are false: -p.-q Hence, (p:q)=[(p.q)v(-p.-q)]
Matrix: 1 2 3 4
p q : p:q = [(p.q)v(-p.-q)]
------
1 1 : 1 1 1 1 0
1 0 : 0 1 0 0 0
0 1 : 0 1 0 0 0
0 1 : 1 1 0 1 1
or
1 2 3 4
p q : p:q p.q -p.-q (p.q)v(-p.-q)
------
1 1 : 1 1 0 1
1 0 : 0 0 0 0
0 1 : 0 0 0 0
0 0 : 1 0 1 1
s16. DE MORGAN TRANSFORMATION. Of theoretical importance among the various logical equivalences are the so-called De Morgan's Laws, two of which, we have so far discussed: 3rd (pvq)=-(-p.-q) and 4th (p.q)=-(-pv-q).
The 1st and 2nd DM Laws are:
r1. The negation of disjunction (of true statements) is logically equivalent to the conjunction of negated (or false) statements. -> -(pvq)=(-p.-q).
r2. The negation of conjunction (of true statements) is logically equivalent to the disjunction of negated (or false) statements. -> -(p.q)=(-pv-q).
Matrix: 1 2 3 4
p q : pvq (-p.-q) -(pvq)=(-p.-q)
------
1 1 : 1 0 0 1
1 0 : 1 0 0 1
0 1 : 1 0 0 1
0 0 : 0 1 1 1
In the same way, the negation of conjunction can be transformed into its disjunctive equivalent.
With these rules it is easy to find the logical equivalence of any of these: a.-(p.-q)
b.-(-p.q) c.-(-pvq) d.-(pv-q)and even such expressions as -(p>q),
-(-p>q), -(p>-q) assuming that we know the disjunctive equivalence of the conditionals.
In the transformation of a given expression, two steps should be observed: 1. Negate the variables. 2. For the negation of dis- junction, change the wedge to the dot symbol. For the negation of conjunction, change the dot to the wedge symbol.
-4-
The De Morgan's Theorems are not limited to only two variables. These rules can be extended to more complicated expressions involving many distinct variables. For instance, the expression
-[(pvq).r] is logically equivalent to (-p.-q)v-r by r2. Its matrix is as follows:
p q r : -[(pvq). r] = [(-p.-q) v -r]
------
1 1 1 : 0 1 1 1 1 0 0 0
1 1 0 : 1 1 0 0 1 0 1 1
1 0 1 : 0 1 1 1 1 0 0 0
1 0 0 : 1 1 0 0 1 0 1 1
0 1 1 : 0 1 1 1 1 0 0 0
0 1 0 : 1 1 0 0 1 0 1 1
0 0 1 : 1 0 0 1 1 1 1 0
0 0 0 : 1 0 0 0 1 1 1 1
-:-
s17. STATEMENT FORMS. a. Tautology. Any truth-functional expression whose truth values remain true regardless of the truth conditions of its component variable. Hence, any logically equivalent statement expressed as a true biconditional is a tautology.
Example: 1st and 2nd laws of tautology: p:(pvp) and p:(p.p)
Matrix: p pvp p:(p:p) p p.p p:(p.p)
------
1 1 1 1 1 1
0 0 1 0 0 1
always true always true
These laws both express/imply the Principle of Identity (p=p) which states that everything is equal to itself.
Example: "either p or not p" and "not both p and not p" Either I am honest or I am not.
It is not true that I am both here and not here.
These are always true, especially the second which implies that no one can be in two places at the same time.
Hence, pv-p and -(p.-p) respectively
Matrix: p -p : pv-p p -p : -(p.-p)
------
1 0 : 1 1 0 : 1 0
0 1 : 1 0 1 : 1 0
always true always true
These are the simplest forms of tautologies. The 1st expresses the Law of Excluded Middle: a statement is true or false, but not both true and false. The 2nd expresses the Law of Non-Contradiction: no statements can both be true and false at the same time.
The last two examples show that not all tautologies are true biconditional.
-5-
Other tautologies: [(p>q).-q]>-p, [(pvq).-p]>q, -[p.(qvr)]>[-pv(-q.-r)]
b. Self-Contradiction: any statement whose truth values are always false regardless of the truth conditions of its component parts.
Example: Today is Monday and today is not Monday. I am here and I am not also here.
These are the statements of the form `p and not p' (p.-p), which is a conjunction of true and false statements. It asserts that p is true and false at the same time, which is self-contradictory.
Matrix: p -p : p.-p
------
1 0 : 0
0 1 : 0 -> always false
c. Contingency: any statement that contains a combination of true and false values in the final column of its matrix.
Example: p, p.q, pvq, p>q, and p:q A more complicated contingent expression is shown in the following matrix:
p q : [(p.q)=-p] > q
------
1 1 : 0 1 1
1 0 : 1 0 0
0 1 : 0 1 1
0 0 : 0 1 0
--> some 1 and some 0
Review Questions
1. State in words the De Morgan's Theorems.
2. Define the following terms: tautology/s-contradictory/contingency.
3. Define each of the truth-functions as interpreted in this chapter.
4. Do contingent statement forms always have a true value? Why?
5. What are the principles of identity/non-contradiction/excluded middle?
s15/s17 EXERCISES I. By using De Morgan’s Theorems determine the logical equivalence of the following expressions.
1. -(pv-q) 5. -[(pvq).-p] 2. -(-q.p) 6. (-p>q)
3. -(p:q) 7. -[(p.q).p] 4. -[(-pvq).-r] 8. (p.-q)
Determine by matrix which of the ff. statement are tautologies, s-contradictories, contingent forms
1.(-pvq)>q 2.(pvq)= p 3.[(p.-q)v p 4.(p.q)>(p>-q)
5.[(pvq).-p)]-q
III. Determine by matrix which of the following biconditional are tautologies.
1. p:(pvq) 2.(-p>q):(pv-q) 3.(-p>-q):(--pv-q)
4. p.(qvr)]:[(pvq).(pvr)] 5. [p>(q>r)]:[(p.q)v r]