Logical concepts – Tautology and contradiction

Definition: A formula of propositional logic is a tautology if the formula itself is always true regardless of which valuation is used for the propositional variables.

There are infinitely many tautologies.

Example
This formula has only 1 variable, A. To valuate this formula A, we must assign one of the truth values true or false, and assign ~A to the other truth value.

tautology

meaning

A

˅

~

A

 Tautology Law of excluded middle: for any proposition, either that proposition is true, or its negation is.

T

T

F

T

A or not A

F

T

T

F

not A or A

Verifying with tautologies
Why should we want to have tautologies? A tautology is a semantic way to verify that premises are true as well as their conclusion.

How do we determine whether a formula is a tautology? We 1st evaluate every variable and then the operand(s) for its possible valuations, till every part of the formula is mapped.  For every variable in a formula, we have 2 values, T and F. If a formula has n variables, then there are 2n possible valuations of the formula.

For example (A˅B) has 2 variables, then this statement has 22 (=2×2=4) possible valuations. When a statement has 3 variables, then it has 23 (=2x2x2=8) possible valuations.

Tautological implication
Suppose formula S is a label for formula (A˅(B˅~B)). If R implies S, when every valuation that causes R to be true also causes S to be true, then we have a tautology.

However, suppose formula S is a label for ((B˅~B)). Any valuation that makes A false, will make the formula S false, so that S is not a tautology.

Contradiction
Definition
: A contradiction is a statement that is false under all circumstances.

If R is false for all values of its variables, so that there is no truth valuation that causes R to be true, then R is a contradiction.
What happens when we have a contradiction?
For example, in R implies S, the outcome of RS for R=false, is always true, regardless of the truth or falsity of S. Say R is a label for a formula (~p), which is a contradiction; then R is always false.

contradiction

meaning

p

˄

~

p

 Contradiction

T

F

F

T

p and not p

F

F

T

F

not p and p

A contradiction does not eliminate anything, and therefore it implies everything. So a contradiction is useless for purposes of logic or evidence because it is always false, and anything can follow from it.

Advertenties

2 thoughts on “Logical concepts – Tautology and contradiction

  1. Timecoach Master your time schreef:

    Thank you for your thourough contribution to my day! remarks:- THe term U is not explained – there seems to be a mistake in the second proof “However, suppose formula S is a label for (A˄(B˅~B)). Any valuation that makes A false, will make the formula S false, so that S is not a tautology”Noticing that if S is false R-> S cannot be a tautology. It doesn’t matter to the total argument, that S is not a tautology. Actually it is a contradiction is R and S are held in R->S

    R = (A v (B v ~B)) -> S = (A ^ (B v ~B)) 0 1 1 1 0 0 0 0 1 1 0 0 1 0 1 1 0 0 0 0 1 1 0 1 1 1 0 0 0 0 1 1 0 0 1 0 1 1 0 0 0 0 1 1

    Date: Wed, 20 Mar 2013 04:59:09 +0000
    To: timecoach@hotmail.com

    • jacqlyne schreef:

      U=Universe, which is ~A. U and A together form the context. U makes A distinguishable from ~A.

      However, suppose formula S (but I mistakenly wrote R) is a label for (A˄(B˅~B)). Any valuation that makes A false (when evaluating per row), will make the formula S false, so that S is not a tautology (as a formula).
      R→S. S is a label for (A˄(B˅~B)), which is not a tautology |1100|. Then, if R is a tautology, then R→S is not a tautology |1100| (as a formula).
      (A ˄ (B ˅ ~ B))
      1 1 1 1 0 1 A=T, T˄T=T
      1 1 0 1 1 0 A=T, T˄T=T
      0 0 1 1 0 1 A=F, F˄T=F
      0 0 0 1 1 0 A=F, F˄T=F
      But if S is a label for (A˅ (B˅~B)), which is a tautology |1111|, then, if R is a tautology, then R→S is a tautology |1111| (as a formula).
      (A ˅ (B ˅ ~ B))
      1 1 1 1 0 1 A=T, T˅T=T
      1 1 0 1 1 0 A=T, T˅T=T
      0 1 1 1 0 1 A=F, F˅T=T
      0 1 0 1 1 0 A=F, F˅T=T

Thank you for your action!

Vul je gegevens in of klik op een icoon om in te loggen.

WordPress.com logo

Je reageert onder je WordPress.com account. Log uit / Bijwerken )

Twitter-afbeelding

Je reageert onder je Twitter account. Log uit / Bijwerken )

Facebook foto

Je reageert onder je Facebook account. Log uit / Bijwerken )

Google+ photo

Je reageert onder je Google+ account. Log uit / Bijwerken )

Verbinden met %s