Drexel dragonThe Math ForumDonate to the Math Forum

Ask Dr. Math - Questions and Answers from our Archives
_____________________________________________
Associated Topics || Dr. Math Home || Search Dr. Math
_____________________________________________

Tautologies and Contradictions

Date: 02/19/2006 at 02:53:04
From: Timothy
Subject: Tautology and Contradiction

Hello Dr. Math,

I have a question on tautologies and contradictions.  On my upcoming
test time is limited.  In order for me to determine if a
well-formed-formula is a tautology or contradiction, I will have to
use a truth-table to see if it is all false or true.  I was wondering
if there is a faster way to determine that?



Date: 02/20/2006 at 14:56:43
From: Doctor Achilles
Subject: Re: Tautology and Contradiction

Hi Timothy,

To answer your question about how to tell if something is a tautology,
the fall-back is truth tables, and if you're comfortable with those,
then I would use them.  If you want another method, here's what I do.

NOTE: I will be teaching you a lot of new material.  If you master it,
then you will be able to very quickly figure out if something is a
tautology or a contradiction, but it will probably take some time to
get comfortable with this.  If all of this is too confusing, then you
may do better to just use truth tables.

First, let me introduce you to a term: "main connective".  The main
connective is the central logical operation in a logical expression.

I will use the word "connective" and "operation" interchangeably, they
mean the same thing.

The logical operations are:

  ~ : Not
  ^ : and
  v : or
  ->: if, then
 <->: if and only if or equivalence

The simplest logical expression is a single term:

  A

This is either true or false, but we don't know which.  One operation
we can apply is:

  ~A

The other operations all require two terms:

  (A ^ B)
  (A v B)
  (A -> B)
  (A <-> B)

We can build more complicated sentences.  To build a complicated
sentence just requires connecting the basic sentences with operations:

  ~(A ^ B)

This sentence is made by attaching the operator ~ to the sentence (A ^ B).

  ((A v B) ^ C)

I made this by connecting the sentence (A v B) and the sentence C with
the ^ operator.

  ((A -> B) -> A)

This sentence connects (A -> B) with A using ->.

  (((A ^ B) -> C) <-> C)

This connects ((A ^ B) -> C) to C using <->.  Notice that the -> is
not the main connective, even though it's in the middle.

  ~(A -> (~B v A))

Here the main operator is ~ and it applies to the sentence (A -> (~B v
A)).

Ok, so what does this have to do with figuring out if a sentence is a
tautology or a contradiction or neither?  Here's how I solve that kind
of problem:

  Step 1: Find the main connective.

  Step 2: Figure out if I can find any way to make the sentence true.

  Step 3: Figure out if I can find any way to make the sentence false.

If I cannot make it true, but I can make it false, then it is a
contradiction.  If I can make it true, but cannot make it false, then
it is a tautology.  If I can make it true and I can make it false,
then it is neither.

Step 1 requires some practice.  Once you get the hang of it, it won't
take long to find the main connective.

For step 2:

If the main connective is ~, then to make the sentence true, you need
to figure out a way to make the sentence inside false.

For example, I know that the sentence

  ~(A v B)

can be made true because I know I can make

  (A v B)

false.

If the main connective is v, then to make the sentence true, you need
to figure out a way to make EITHER of the sentences it connects true.

For example, I know that the sentence

  ((~A ^ A) v (~B ^ B))

must be a contradiction, because I cannot find a way to make either

  (~A ^ A)

or

  (~B ^ B)

true, no matter what I do.

If the main connective is ^, then to make the sentence true, you need
to figure out a way to make BOTH of the sentences it connects true at
the same time.

For example, I know that the sentence

  ((A v FALSE) ^ ~A)

is a contradiction, because I cannot make

  (A v FALSE)

true without making A true, which means

  ~A

will be false.

If the main connective is ->, then to make the sentence true you can
either figure out a way to make the part before the -> false, OR you
can make the part after the -> true.

For example, I know right away that the sentence:

  (A -> (((A ^ ~A) v (~B ^ B)) <-> (C ^ ~C)))

is not a contradiction, because if I make A false, then the sentence
will come out to be true.

If the main connective is <->, then you need to find a way to make
both parts true OR to make both parts false.

For example, I know that

  ((A ^ ~A) <-> B)

is not a contradiction, because (A ^ ~A) is always false, but if I
make B false as well, then the sentence will be true.

For step 3:

Alright, now we've figured out if our sentence can ever be true, now
we need to figure out if it ever can be false.

If the main connective is ~, then we need to make the sentence inside
true.

For example, I know that

  ~(A -> (A v B))

is not a tautology, because I can make

  (A -> (A v B))

true.

If the main connective is ^, then you need to make either of the parts
false.

For example, I know that

  (A ^ ((B -> C) v (C -> B)))

is not a tautology because I can make it false if A is false.

If the main connective is v, then you need to make BOTH of the parts
false.

For example, I know that

  (B v (B -> ~B))

is a tautology because if I make B false, then

  (B -> ~B)

comes out true.

If the main connective is ->, then you need to make the first part
true AND the second part false.

For example, I know that

  (C -> (C ^ D))

is not a tautology because I can make C true and still make

  (C ^ D)

false.

If the main connective is <->, then you need to make the two parts
have different truth values.

For example, I know that

  ((A ^ ~A) <-> B)

is not a tautology because when I make B true, the two sides have
different truth values.


Ok, let me work through some examples:

  1.  (~(A v B) ^ B)

Step 1, the main connective is ^, it connects

  ~(A v B)

to

  B.

Step 2, I cannot make the sentence true.  When I try, I have to make B
true.  But when B is true, then (A v B) MUST BE true, so ~(A v B) is
false.

Therefore, I know that this is a contradiction.

  2.  ((B -> C) v C)

Step 1, the main connective is v, it connects:

  (B -> C)

to

  C.

Step 2, I can make the sentence true.  All I need to do is make C true.

Step 3, I can make the sentence false.  To do that I need to make C
false, and I need to make (B -> C) false.  I can do that when C is
false and B is true.

Therefore, this is neither a contradiction nor a tautology.

  3.  ~((A -> B) ^ ~A)

Step 1, the main connective is ~, it governs:

  ((A -> B) ^ ~A)

Step 2, I can make the sentence true.  To do it, I need to make A
true.  When A is true, ~A is false, so the sentence ((A -> B) ^ ~A)
will be false, so the negation of that (which was our original
sentence) is true.

Step 3, I can make the sentence false.  To do that I need to make A
false.  When A is false, ~A is true AND (A -> B) is also necessarily
true.  Therefore, when A is false ((A -> B) ^ ~A) is true and so the
negation is false.

Therefore, the sentence is neither a contradiction nor a tautology.

  4.  ((~A ^ C) -> (B v C))

Step 1, the main connective is ->, it connects

  (~A ^ C)

to

  (B v C).

Step 2, I can make the sentence true.  All I need to do is make A true
(or make C false), either way (~A ^ C) comes out false, so the whole
sentence comes out true.

Step 3, I cannot make the sentence false.  To make the first part
true, I need to make A false and C true.  If I do that, then the
second part MUST also be true.

Therefore, the sentence must be a tautology.

  5.  ((A v ~B) <-> (~A ^ B))

Step 1, the main connective is <->, it connects

  (A v ~B)

to

  (~A ^ B).

Step 2, I cannot make the sentence true.  Here's what I try:

  a)  Make the first part true by making A true.
      When I do that, the second part ends up false.

  b)  Make the first part true by making B false.
      When I do that, the second part ends up false.

  c)  Make the first part false by making A false and B true.
      When I do that, the second part ends up true.

So there is no way to get the two sides to have the same truth value.

Therefore, the sentence is a contradiction.


I hope all of this helps.  If you have other questions or you'd like
to talk about this some more, please write back.

- Doctor Achilles, The Math Forum
  http://mathforum.org/dr.math/ 
Associated Topics:
High School Logic

Search the Dr. Math Library:


Find items containing (put spaces between keywords):
 
Click only once for faster results:

[ Choose "whole words" when searching for a word like age.]

all keywords, in any order at least one, that exact phrase
parts of words whole words

Submit your own question to Dr. Math

[Privacy Policy] [Terms of Use]

_____________________________________
Math Forum Home || Math Library || Quick Reference || Math Forum Search
_____________________________________

Ask Dr. MathTM
© 1994-2013 The Math Forum
http://mathforum.org/dr.math/