2

I was reading the following proof and am having trouble following the propositional logic underpinning the proof:

http://www.mathcs.emory.edu/~cheung/Courses/323/Syllabus/Graph/DAG.html

To simplify, it looks to me like the propositional logic is as follows:

Prove (P IFF Q)
1. Prove (if P, then Q)
a. (if P, then Q) = (~P or Q).
b. Prove (~P or Q) by contradiction: Assume ~(~P or Q) is true, i.e. assume (P and ~Q) is true.
c. Assuming ~Q contradicts P, therefore Q must be true.

1.c. is the step which I don't understand.

In the DAG proof, the author simply claims that assuming ~Q contradicts a given P. But where was P given? This proof doesn't proceed by assuming P and showing Q logically follows, so I don't know how the author makes the claim that P must be true thereby creating a contradiction.

Thanks!

BeginnersMindTruly
  • 101
  • 8

1 Answers1

2

You cannot prove $P \leftrightarrow Q$ "alone", and you cannot prove $P \rightarrow Q$ alone.

There must be some other assumption missing !

This is the reason why (in this you are right !) you cannot understand the claim that :

"not-Q contradicts a given P".

Referring to your attachment, I assume that you are interested to the following proof :

Proposition 13.21 (Goodrich) : A directed graph G has a topological ordering if and only if G is acyclic.

Proof of : if a directed graph G has a topological ordering, then G is acyclic (by contradiction).

Rewrite the statement to be proved in a semi-formal way as :

if Topological-ordered(G), then Acyclic(G),

i.e. : $Top(G) \rightarrow Acy(G)$.

Assume :

(1) $Top(G)$

and assume :

(2) $\lnot Acy(G)$;

if G is cyclic (i.e. not-acyclic), then there exists a cycle : $v_1, \ldots, v_n$ such that :

(3) $v_1=v_n$;

by known properties of topological we have that :

(4) $Top(G) \rightarrow (v_1 < v_n)$.

Thus, by (3) and (4) :

(5) $\exists v (v < v)$;

this is impossible : contradiction !

Therefore, the assumption $\lnot Acy(G)$ is false: and we conclude with $Acy(G)$.

I.e.

$Top(G) \rightarrow Acy(G)$.

Mauro ALLEGRANZA
  • 94,169