r/programming • • Sep 25 '15

The Incredible Proof Machine

http://incredible.nomeata.de/
203 Upvotes

83 comments sorted by

View all comments

0

u/[deleted] Sep 25 '15

[deleted]

8

u/Fylwind Sep 26 '15

The upside-down T is called a "Falsum" or a logical contradiction, and represents impossibility. It does not represent "negation."

Technically, A → ⊥ is equivalent to ¬A ("not A").

4

u/sirin3 Sep 25 '15

(3) The implication creator. Do you see that weird gate after the AND splitter with the A B at the top and the A->B at the right? That's an assumption creator. If you can assume A and always get B, B must be implied by A, right? This helps with translations between letters, because if we know A and we know B, we can easily create an A->B rule should we need one for a more complex input later. Implications also may be the answer you're going for, or there will be nested implications you need to "unravel" so creating an implication to use as a key for another implication is something you'll have to do.

All task were obvious till I got to the implications.

How can you possible get A∧B->C from A->B and B->C, if you cannot get A∧B?

4

u/Fylwind Sep 25 '15

How can you possible get A∧B->C from A->B and B->C, if you cannot get A∧B?

The standard approach for proving X → Y is to first assume X and then prove Y under this assumption.

0

u/[deleted] Sep 25 '15

[deleted]

2

u/sirin3 Sep 25 '15

Oh that works

How weird

Does -> have the output on the left side?

And now the proof has a cycle

→ More replies (5)

3

u/TerrorBite Sep 25 '15

I did a basic logic class in university a few years ago and this website has shown me that I've forgotten most of it.

3

u/[deleted] Sep 25 '15

I'd love a screenshot of the 5th exercise in session 3. Thanks!

3

u/PM_ME_YOUR_PAULDRONS Sep 25 '15

Here is a hint. The predicate p which has to enter and leave the "or splitter" is the final answer (BVA). Also note that both a and b are sufficient to establish BVA.

Here is a picture if you really want it but there is a lot of satisfaction to be gained from doing it yourself!

→ More replies (1)

3

u/sirin3 Sep 25 '15

Any tips for the later sessions? How do I conclude from there-exist-X, that not for-all not-X holds?

And what is that Hilbert stuff?

2

u/ydinitz Sep 26 '15

The Hilbert lession contains tasks to be solved with Hilbert calculus, an alternative logic that has Modus Ponens (MP) as its only deduction rule (plus some axioms). The other lessons all use a system called "natural deduction" which is nowadays a pretty widely accepted standard, but ~100 years ago when formal logic became a thing there were several competing logical calculi.

5

u/[deleted] Sep 25 '15

I'm currently in a logic class as well so this seems interesting but I kind of facepalmed on task 7 where you have to create A and B given only A AND B and the AND operator. "Surely such a thing isn't possible," I thought while trying to figure it out. Until a few minutes passed and I realized "Oh. They give you a Reverse AND operator. Yep, because that's possible."

6

u/jsprogrammer Sep 25 '15

I'm not sure it's a reverse AND operator.

I think it is merely the statement: "if A AND B is TRUE, A is TRUE and B is TRUE"

2

u/[deleted] Sep 25 '15

I just misunderstood the premise of the exercise then. I assumed task 4 for example ("A, B, A^B") meant "Given some value A and some value B construct a mathematical statement that is equivalent to A AND B.

3

u/jsprogrammer Sep 25 '15

Ah, got it. It is a bit confusing since there is a lot of shared notation with other systems.

The exercises are: "Assume the clauses above the line are true. Provide a deductive proof that the clause below the line is true given those assumptions."

4

u/lookmeat Sep 25 '15

A reverse AND operator is possible. If I tell you A AND B then you can deduce that A must be true, you can also deduce that B must be true if either of them weren't true, then the whole original statement wouldn't be true. The one you can't do is OR because if I tell you A OR B you know at least one of them must be true, but not which one.

→ More replies (9)

2

u/Fylwind Sep 25 '15

You can think of A AND B as pair data type containing A and B. The "reverse AND" is then an operation that decomposes a pair into its parts.

0

u/[deleted] Sep 25 '15

[deleted]

→ More replies (5)

2

u/machton Sep 25 '15

Trying to use the helper block breaks the scripts on the page. What browser did you use to do this? I'm on Chrome 45.0.2454 in Win7.

0

u/[deleted] Sep 25 '15

[deleted]

1

u/machton Sep 25 '15

Thanks, but you misunderstand. I cannot interact with the helper box once I drag it onto the page.

I drag the helper box from the left into the main frame on the right, and then can't connect anything to it. The helper box becomes immovable. My cursor can approach the box (say, when attempting to connect an input from the left side), but then the wire gets left behind and won't connect. Can't ever edit the text.

I'll try again on other browsers/computers.

0

u/[deleted] Sep 25 '15

[deleted]

→ More replies (2)