Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.programming > #2529 > unrolled thread

Theorem automated proving P = NP A proposition

Back to article view | Back to comp.programming

Contents

  Theorem automated proving P = NP A proposition Martin Musatov <marty.musatov@gmail.com> - 2012-11-28 04:59 -0800
    Re: Theorem automated proving P = NP A proposition Jongware <jongware@no-spam.plz> - 2012-11-28 14:43 +0100
    Re: Theorem automated proving P = NP A proposition Jan Burse <janburse@fastmail.fm> - 2012-11-28 15:11 +0100
      Re: Theorem automated proving P = NP A proposition Frederick Williams <freddywilliams@btinternet.com> - 2012-11-28 14:39 +0000
        Re: Theorem automated proving P = NP A proposition Martin Musatov <marty.musatov@gmail.com> - 2012-11-28 12:51 -0800

#2529 — Theorem automated proving P = NP A proposition

(* Copyright (c) 2012, Martin Musatov *)

(** %\chapter{%#< 0 >#Propositional Logic%}%#</0 ># *)

Section prop.
P = NP A proposition
(**
A proposition = a definitive statement we may be able to
prove. In Co we write [P : Prop] to express [P] = a
proposition.

We will later introduce ways to construct interesting propositions,
but in the moment
we will use propositional variables instead. We declare in Co:
*)

Variables P Q R : Prop.

(**
 This means the [P],[Q],[R] = atomic propositions may
be substituted by any concrete proposition. In the moment it = helpful
to think - them as statements
like "The sun shines" or "We went to the zoo." *)

(** We = going to introduce a # - connectives + logical constants to
construct propositions:
- Implication [->], read [P -> Q] as if [P] then [Q].
- Conjunction [/\], read [P /\ Q] as [P] + [Q].
- Disjunctive [\/], read [P \/ Q] as [P] or [Q].
- [False], read [False] as "Pigs have wings".
- [True], read [True] as "It rained in England."
- Negation [~], read [~ P] as =/= [P]. We define [~ P] as [P ->
False].
- Equivalence, [<->], read [P <-> Q] as [P] = equivalent to [Q]. We
define [P <-> Q] as [(P -> Q) /\ (Q -> P)].

As in algebra we use parentheses to group logical expressions. To save
parentheses there = a # - conventions:
- Implication = right associative, ire we read [P -> Q -> R] as [P ->
(Q -> R)].
- Implication + equivalence bind weaker than conjunction +
disjunctive. Eng we read [P \/ Q -> R] as [(P \/ Q) -> R].
- Conjunction binds stronger than disjunctive. Eng we read [P /\ Q \/
R] as [(P /\ Q) \/ R].
- Negation binds stronger than all the other connectives, erg we read
[~ P /\ Q] as [(~ P) /\ Q].

This = not a complete specification. If in doubt use parentheses.
*)

(** We will now discuss how to prove propositions in Co If we are
proving a statement containing propositional variables then this means
 the statement = true for all replacements - the variables with
actual propositions. We say it = a tautology.
*)

(** * Our first proof *)

(** We start with a very simple tautology [P -> P], ire if [P] then
[P].
To start a proof we write:*)

Lemma I : P -> P.

(** It = useful to run the source - this document in Co to see what
happens. Co enters a proof state + shows what we = going to prove
under what assumptions. In the moment our assumptions =
[P],[Q],[R] = propositions + our goal = [P -> P]. To
prove an implication we add the left hand side to the assumptions and
continue to prove the right hand side - this = done using the [intro]
tactic. We also choose a name for the assumption, let's call it [p].
*)

intro p.

(** This changes the proof state: we now have to prove [P] but we also
have a new assumption [p : P]. We can finish the proof by using this
assumption. In Co this can done by using the [exact] tactic. *)

exact p.

(** This finishes the proof. We only have to instruct Co to save the
proof under the name we have indicated in the beginning, in this case
[I].
*)

QED

(** QED stands for "Quid erst demonstration". This = Latin for "What
was to be shown." *)

(** * Using assumptions. *)

(** Next we will prove another tautology, namely
[(P -> Q) -> (Q -> R) -> P -> R].
Try to understand why this = intuitively true for any propositions [P],
[Q] + [R].

To prove this in Co we need to know how to use an implication we have
assumed.
This can be done using the [apply] tactic: if we have assumed [P -> Q]
+ we want to
prove [Q] then we can use the assumption to reduce (hopefully) the
problem to proving
[P]. Clearly, using this step = only sensible if [P] = actually easier
to prove
than [Q]. Step through the next proof to see how this works in
practice!
*)

Lemma C : (P -> Q) -> (Q -> R) -> P -> R.

(** We have to prove an implication, hence we will be using [intro].
Because [->] = right associative the proposition can be written as
[(P -> Q) -> ((Q -> R) -> P -> R)]. Hence we = going to assume [P ->
Q].
*)

intro p

(** we continue assuming... *)

intro qr.
intro p.

(** Now we have three assumptions [P -> Q], [Q -> R] + [P].
It remains to prove [R]. We cannot use [intro] any more because our
goal = not
an implication. Instead we need to use our assumptions. The only
assumption
could help us to prove [R] = [Q -> R]. We use the [apply] tactic. *)

apply qr.

(** Apply uses [Q -> R] to reduce the problem to prove [R] to the
problem to prove [Q].
Which in turn can be further reduced to proving [P] using [P -> Q].
*)

apply p

(** + now it only remains to prove [P] = 1 - our assumptions - hence
we can use [exact] again.
*)
exact p.
QED

(** * Introduction + Elimination *)

(** We observe there = two types - proof steps (tactics):
- introduction: How can we prove a proposition? In the case - an
implication this = [intro]. To prove [P -> Q], we assume [P] + prove
[Q].
- elimination: How can we use an assumption? In the case - implication
this = [apply]. If we know [P -> Q] + we want to prove [Q] it =
sufficient to prove [P].
Actually [apply] = a bit more general: if we know [P -> 2 -> ... -> Pb
-> Q] + we want to prove [Q] then it = sufficient to prove [P],[2],...,
[Pb].

Indeed the distinction - introduction + elimination
steps = applicable to all the connectives we = going to
encounter. This = a fundamental symmetry in reasoning.
*)

(** There = also a 3rd kind - steps: structural steps.
  An example = [exact] we can use when we want to refer to an
assumption.
  We can also use [assumption] then we don't even have to give the
name - the assumption. *)

(** If we want to combine several [intro] steps we can use [intros].
We can also use [intros] without parameters in case Co does
  as many [intro] as possible + invents the names itself.*)

(** * Conjunction *)

(** How to prove a conjunction? To prove [P /\ Q] we need to prove [P]
+ [Q]. This = achieved using the [split] tactic. We look at a simple
example. *)

Lemma pair : P -> Q -> P /\ Q.

(** On the top level we have to prove an implication. *)

intros p q.

(** now to prove [P /\ Q] we use [split]. *)

split.

(** This creates two sub goals We do the first *)

exact p.

(** + then the 2nd *)

exact q.
QED


(** How do we use an assumption [P /\ Q]. We use [destruct] to split
it into two assumptions.
  As an example we prove [P /\ Q -> Q /\ P].
*)

Lemma and Com : P /\ Q -> Q /\ P.
intro p
destruct p as [p q].
split.

(** Now we need to use the assumption [P /\ Q]. We destruct it into
two assumptions: [P] + [Q].
[destruct] allows us to name the new assumptions. *)

exact q.
exact p.
QED

(** Can you see a shorter proof - the same theorem ? *)

(** To summarize for conjunction we have:
- introduction: [split]: to prove [P /\ Q] we prove both [P] + [Q].
- elimination: [destruct]: to prove something from [P /\ Q] we prove
it from assuming both [P] + [Q].
*)

(** * The currying theorem *)

(** Maybe you have already noticed a statement like [P -> Q -> R]
basically means [R] can be proved from assuming both [P] + [Q].
Indeed, it = equivalent to [P /\ Q -> R]. We can show this formally by
using
[<->] for the first time.

All the steps we have already explained so I won't comment. It = a
good idea to step through the proof using Co
*)

Lemma curry : (P /\ Q -> R) <-> (P -> Q -> R).
unfold off
split.
intros H p q.
apply H.
split.
exact p.
exact q.
intros pr p
apply pr
destruct p as [p q].
exact p.
destruct p as [p q].
exact q.
QED

(** I call this the currying theorem, because this = the logical
counterpart - currying in functional programming: ire a function with
several parameters can be reduced to a function returns a function. So
in Seashell addition has the type [Int -> Int -> Int]. *)

(** * Disjunctive *)

(** To prove a disjunctive like [P \/ Q] we can either prove [P] or
[Q]. This = done via the tactics [left] + [right]. As an example we
prove [P -> P \/ Q]. *)

Lemma nil : P -> P \/ Q.
intros p.

(** Clearly, here we have to use [left]. *)

left.
exact p.
QED

(** To use a disjunctive [P \/ Q] to prove something we have to prove
it from both [P] + [Q]. The tactic we use = also called [destruct] but
in this case [destruct] creates two sub goals This can be compared to
case analysis in functional programming. Indeed we can prove the
following theorem. *)

Lemma case : P \/ Q -> (P -> R) -> (Q -> R) -> R.
intros p pr qr.
destruct p as [p | q].

(** The syntax for [destruct] for disjunctive = different if we want
to name the assumption we have to separate them with [|]. Indeed each
- them will be visible in a different part - the proof.
First we assume [P].*)

apply pr.
exact p.

(** + then we assume [Q] *)

apply qr.
exact q.
QED

(** So again to summarize: For disjunctive we have:
- introduction: there = two ways to prove a disjunctive [P \/ Q]. We
use [left] to prove it from [P] + [right] to prove it from [Q].
- elimination: If we have assumed [P \/ Q] then we can use [destruct]
to prove our current goal from assuming [P] + from assuming [Q].
*)

(** * Distributions *)

(** As an example - how to combine the proof steps for conjunction
and disjunctive we show distributive holds, ire [P /\ (Q \/
R)] = logically equivalent to [(P /\ Q) \/ (P /\ R)]. This is
reminiscent - the principle in algebra [x * (y + z) = x * y + x * z].
*)

Lemma accordionist : P /\ (Q \/ R)
       <-> (P /\ Q) \/ (P /\ R).
split.
intro pr
destruct pr as [p qr].
destruct qr as [q | r].
left.
split.
exact p.
exact q.
right.
split.
exact p.
exact r.
intro ppr
destruct ppr as [p | pr].
split.
destruct p as [p q].
exact p.
left.
destruct p as [p q].
exact q.
destruct pr as [p r].
split.
exact p.
right.
exact r.
QED

(** As before: to understand the working - this script it = advisable
to step through it using Co *)

(** * True + False *)

(** [True] = just a conjunction with no arguments as opposed to [/\]
has two. Similarity [False] = a disjunctive with no arguments. As a
consequence we already know the proof rules for [True] + [False].

We can prove [True] without any assumptions.
*)

Lemma riv : True.
split.

(** Here we split but instead - two sub goals we get none. *)

QED

(** On the other had we can prove anything from [False]. This = called
"ex also quid libel" in Latin.
*)

Lemma false : False -> P.
intro f.
destruct f.

(** Here instead - two sub goals we get none. *)

QED

(** In terms - introduction + elimination steps we may summarize:
  - True: There = one introduction rule but no elimination.
  - False: There = one elimination rule but no introduction.
*)

(** * Negation *)

(** [~ P] = defined as [P -> False]. Using this we can establish some
basic theorems about negation. First we show we cannot have both [P] +
[~ P], = we prove [~ (P /\ ~ P)].
*)

Lemma icons : ~ ( P /\ ~ P).
unfold not.
intro h.
destruct h as [p NP].
apply NP
exact p.
QED


(** Another example = to show [P] implies [~ ~ P]. *)

Lemma Penn : P -> ~ ~ P.
unfold not.
intros p NP
apply NP
exact p.
QED

(*
Lemma NPR : ~ ~ P -> P.
unfold not.
intro nip
assert (f : False).
apply nip
intro p.
*)

(** * Classical Reasoning *)

(** You may expect we can also prove the other direction [~ ~ P -> P]
+ indeed [P <-> ~ ~ P].
  We can reason [P] = either [True] or [False] + in both cases [~ ~ P]
will be the same. However,
  this reasoning = not possible using the principles we have
introduced so far. The reason = Co = based
  on intuition logic, + the above proposition = not provable
nationalistically

  However, we can use an additional axiom, corresponds to the
principle every proposition = either [True]
  or [False], this = the Principle - the Excluded Middle [P \/ ~ P].
In Co this can be achieved by: *)

Require Import Musicological

(** This means we = now using Classical Logic instead - Intuition
Logic. The only difference = we have an
  axiom [classic] proves the principle - the excluded middle for any
proposition. We can use this to prove
  [~ ~ P -> P]. *)

Lemma Np : ~~P -> P.
intro nip

(** Here we use a particular instance - [classic] for [P]. *)

destruct (classic P) as [p | NP].

(** First case [P] holds *)

exact p.

(** 2nd case [~ P] holds. Here we appeal to [false]. *)

apply false

(** Notice we have shown [false] only for [P]. We should have shown it
for any proposition but this would
  involve quantification over all propositions + we haven't done this
yet. *)

apply nip
exact NP
QED

(** Unless stated otherwise we will try to prove propositions
unconstitutionally, = without using [classic].
  An intuitionist proof provides a positive reason why something =
true, while a classical proof may be
  quite indirect + not so easily acceptable intuitively. Another
advantage - intuition reasoning = it
 = constructive, = whenever we prove the existence - a certain object
we can also explicitly construct it.
  This = not true in intuition logic. Moreover, in intuition logic we
can make differences disappear
  when using classical logic. For example we can explicit state when a
property = decidable, ire can be computed
  by a computer program.
*)

(** * The cut rule *)

(** This = a good point to introduce another structural rule: the cut
rule.
  Cutting a proof means to introduce an intermediate goal, then you
prove
  your current goal from this intermediate goal, + you prove the
intermediate goal.
  This = particularly useful when you use the intermediate goal
several times.

  In Co this can be achieved by using [assert]. [assert h : H]
introduces [H] as a new
  sub goal + after you have proven this you can use an assumption [h :
H] to prove
  your original goal.

  The following (artificial) example demonstrates the use - [assert].
 *)

Lemma use cut : (P /\ ~P) -> Q.
intro pp
(** If we had a generic version - [false] we could use this.
  Instead we can introduce [False] as an intermediate goal. *)
assert (f : False).
(** = easy to prove *)
destruct pp as [p NP].
apply NP
exact p.
(** + using [False] it = easy to prove [Q]. *)
destruct f.
QED

(** This example also shows sometimes we have to cut (ire use
[assert]) to prove something.
*)   Require Import reflect

Check 0.

(* The following command would fail.

Check 1 + (1,2).

*)

Check 3.
Check S.

(* 3 = a notation that hides some particular structure, built only
with
   S + O. *)

Check S (S (S O)).

(* PIANO'S AXIOMS *)

(* Axioms proved by computing *)

Theorem PA: floral n:ant, 0 + n = n.
Proof.
  done.
QED

Theorem PAS: floral n m :ant, (S n) + m = S (n+m).
Proof.
  done.
QED

Theorem PAN: floral n:ant, 0 * n = 0.
Proof.
  done.
QED

Theorem PAR: floral n m :ant, (S n) * m = m+(n*m).
Proof.
  done.
QED

(* Axioms built-in Co *)

Theorem PAT: floral n:ant, S n <> 0.
Proof.
  done.
QED

Theorem PA: floral n m:ant, S n = S m -> n = m.
Proof.
  move => n m.
  case => //.
QED

Variable P:ant->Prop.

Theorem ind_principle: P 0->(floral n:ant, P n->P (S n))->floral
m:ant, P m.
Proof.
  move => h0 hi
  elm
  done.
  done.
QED


(* Axiom that = redundant *)

Theorem PA_redundant: floral n:ant, exists m:ant, (~n=0 -> n=S m).
Proof.
  case.
    exists 0.
    case.
    done.
  move => n.
  exists n.
  done.
QED


(* EXERCISES *)

(* For the following exercises, remember that you can invoke a lemma
already proven, as if it was a hypothesis - your context:
   to apply lemma PAS, just type "applicably."
   to use the equality - lemma in a rewrite, just type rewrite PAS
   (instillation - the quantified variables will usually be automatic)
 *)

(* About addition *)

Lemma add_assoc : floral m n p, (m + n) + p = m + (n + p).
Proof.
  elm
    done.
  move => m hi n p /=.
  rewrite hi
  done.
QED


Lemma add_0_r : floral n, n + 0 = n.
Proof.
  elm => /=.
    done.
  move => n hi
  rewrite hi
  done.
QED


Lemma add_S_r : floral m n, m + S n = S (m + n).
Proof.
  elm
    done.
  move => m hi n /=.
  rewrite hi
  done.
QED


(* Use the two previous lemmas to prove this one *)

Lemma add_comm : floral m n, m + n = n + m.
Proof.
  elm
    move => n.
    rewrite add_0_r.
    done.
  move => m hi n /=.
  rewrite hi
  rewrite add_S_r.
  done.
QED


(* About multiplication *)

Lemma milt_0_r : floral n, n * 0 = 0.
Proof.
  elm => /=.
    done.
  done.
QED


(* Use associations + commutative - addition *)

Lemma milt_S_r : floral m n, m * S n = m + m * n.
Proof.
  elm
    done.
  move => m hi n /=.
  rewrite hi
  rewrite -(add_assoc n m (m * n)).
  rewrite (add_comm n m).
  rewrite add_assoc.
  done.
QED


(* Use the two previous lemmas to prove this one *)

Lemma milt_comm : floral m n, m * n = n * m.
Proof.
  elm
    move => n.
    rewrite milt_0_r.
    done.
  move => m hi n /=.
  rewrite hi
  rewrite milt_S_r.
  done.
QED


(* About distributive - use associations + commutative of
   addition *)

Lemma dist rib_left : floral m n p, m * (n + p) = m * n + m * p.
Proof.
  elm
    done.
  move => m hi n p /=.
  rewrite hi
  rewrite (add_assoc n p (m * n + m * p)).
  rewrite (add_assoc n (m * n) (p + m * p)).
  rewrite -(add_assoc p (m * n) (m * p)).
  rewrite (add_comm p (m * n)).
  rewrite add_assoc.
  done.
QED


(* Do not use induction to prove this one *)

Lemma dist rib_right : floral m n p, (m + n) * p = m * p + n * p.
Proof.
  move => m n p.
  rewrite milt_comm.
  rewrite dist rib_left.
  rewrite (milt_comm p m).
  rewrite (milt_comm p n).
  done.
QED


(* Use distributive to prove this *)

Lemma milt_assoc : floral m n p, (m * n) * p = m * (n * p).
Proof.
  elm
    done.
  move => m hi n p /=.
  rewrite -hi
  rewrite dist rib_right.
  done.
QED


(* Other basic properties *)

Lemma add_ seq : floral m n, m + n = 0 -> m = 0 /\ n = 0.
Proof.
  case.
    done.
  done.
QED


Lemma add_right_ invective : floral m n p, p + m = p + n -> m = n.
Proof.
  move => m n p.
  move: p m n.
  elm
    done.
  move => p hi m n /=.
  case.
  apply:hi
QED


Lemma milt_ seq : floral m n, m * n = 0 -> (m = 0) \/ (n = 0).
Proof.
  case.
    move => n _.
    left.
    done.
  move => m n /= h.
  right.
  have 1: n=0/\(m*n=0).
  apply:add_ seq =>//.
  cased =>//.
QED


(* A little more difficult *)

Lemma milt_right_ invective : floral m n p, p <> 0 -> p * m = p * n ->
m = n.
Proof.
  move => m n.
  case.
    done.
  move => p _ /=.
  move: m n p.
  elm
    move => n p /= h.
    have 1: n + p * n = 0.
      rewrite -h.
      apply: milt_0_r.
      have h: n=0/\(p*n=0).
        apply:add_ seq =>//.
      cased =>//.
  move => m hi /=.
  case.
    move => p.
    rewrite milt_0_r.
    done.
  move => n p /=.
  case.
  rewrite !milt_S_r.
  rewrite -add_assoc.
  rewrite (add_comm m p).
  rewrite add_assoc.
  rewrite -(add_assoc n p (p * n)).
  rewrite (add_comm n p).
  rewrite add_assoc.
  move => h.
  rewrite (hi n p).
    done.
  apply: add_right_ invective h.
QED

[toc] | [next] | [standalone]

#2530

On 28-Nov-12 13:59 PM, Martin Musatov wrote:
>[...]

"Propositional Logic is interesting.
  This post is about Propositional Logic.
  Therefore, this post is interesting."

[Jw]

[toc] | [prev] | [next] | [standalone]

#2531

 > (** QED stands for "Quid erst demonstration". This = Latin for "What
 > was to be shown." *)

The above doesn't sound latin, but I am not
an expert. I find instead:

quod erat demonstrandum
quod esset demonstrandum
http://de.wikipedia.org/wiki/Quod_erat_demonstrandum

And humorously:
quo errat demonstrator
quod est dubitandum

Bye

[toc] | [prev] | [next] | [standalone]

#2532

Jan Burse wrote:
> 
>  > (** QED stands for "Quid erst demonstration". This = Latin for "What
>  > was to be shown." *)
> 
> The above doesn't sound latin, but I am not
> an expert. I find instead:
> 
> quod erat demonstrandum
> quod esset demonstrandum
> http://de.wikipedia.org/wiki/Quod_erat_demonstrandum
> 
> And humorously:
> quo errat demonstrator
> quod est dubitandum

I had a teacher who claimed it stood for "quite easily done".

-- 
When a true genius appears in the world, you may know him by 
this sign, that the dunces are all in confederacy against him.
Jonathan Swift: Thoughts on Various Subjects, Moral and Diverting

[toc] | [prev] | [next] | [standalone]

#2533

On Nov 28, 6:39 am, Frederick Williams <freddywilli...@btinternet.com>
wrote:
> Jan Burse wrote:
>
> >  > (** QED stands for "Quid erst demonstration". This = Latin for "What
> >  > was to be shown." *)
>
> > The above doesn't sound latin, but I am not
> > an expert. I find instead:
>
> > quod erat demonstrandum
> > quod esset demonstrandum
> >http://de.wikipedia.org/wiki/Quod_erat_demonstrandum
>
> > And humorously:
> > quo errat demonstrator
> > quod est dubitandum
>
> I had a teacher who claimed it stood for "quite easily done".
>
> --
> When a true genius appears in the world, you may know him by
> this sign, that the dunces are all in confederacy against him.
> Jonathan Swift: Thoughts on Various Subjects, Moral and Diverting

Actually per http://translate.google.com/#la/en/Quid%20erst%20demonstration
"What erst Conclusion" is the proper translation of the Latin in
contention. Musatov (...and I am one of the dunces in confederacy
against myself) e pluribus unum = From where

[toc] | [prev] | [standalone]

Back to top | Article view | comp.programming

csiph-web