Formal Proof

[Gorion]

Is anyone able to solve this one?

[ATTACH=CONFIG]2956[/ATTACH]

If you click on the image, it will be bigger.

[suicidal_monkey]

If you click on the image, it will be bigger.

Bigger? ...yes
Clearer? ...no
:-)

[Gorion]

Discrete maths, it's a formal proof problem.

Need to prove it both ways so that the left side results in the right side and vice-versa.  And, I'm stuck.

[albert]

Brain just exploded and now is pulp. I have a mathematics honors btw

Sent from my LG-F320 using Tapatalk

[Penfold]

To be honest I struggle with the kids' algebra homework.......... they're 11. :sad:

[smilodon]

I understood that the two ⊢ shapes in the middle meant that the equation stated that the left side could be derived from the right and vice versa. Maybe you could break it up and look at ∃x:X and whether it is the same as ¬∀x:X ? i.e. does ∃ = ¬∀ ? Doesn't ∃ mean that there is at least one true case, whereas ∀ means that all cases are true. Therefore ¬∀ would mean all cases are not true. So the two contradict each other.

The statement P∨Q is true if either P and Q or both are true. The statement P∧Q is true only if P and Q are both true. ¬P is true only if P is false and ¬Q is true only if Q is false. So ¬P∧¬Q is only true if P and Q are false. This is about the point my head starts to hurt.

I'm guessing that ¬∀x:X contradicts ∃x:X and that P∨Q contradicts ¬P∧¬Q. So on the principle that the two contradictions cancel each other out I'm guessing the equation is true. But I'm not at all sure any of that makes proper mathematical sense certain that it's not even close to being the formal proof you need.

Sorry :sad:

[BrotherTobious]

No one else has said it so I will 42?

Sent from my Nexus 5

[Gorion]

Around 26-30 lines actually.

@Smilo, that's the logic of it yeah.  But then comes the proof part of it where you have to break it down and prove that the LHS and RHS mean the same thing.

[Chaosphere]

May I point you in this direction...

http://mymathforum.com/math/


or something similar

I imagine this level of maths is beyond most lurking here!

[TeaLeaf]

I haven't done this type of math for a while, but isn't it :

¬∀x:X.P ∨ Q ⊣⊢ ∃x:X.¬P ∧ ¬Q

LHS:
For all x, ¬ P ∨ Q is true where P or Q are false.
Truth table for P ∨ Q:
P..Q..Output
T..T..True
T..F..True
F..T..True
F..F..False

Thus showing that for ¬ P ∨ Q to be true (i.e. P ∨ Q false) then both P and Q must be false.

RHS:
There exists a value for x where ¬P ∧ ¬Q is true.
For  P ∧ Q to be true then both P and Q must be true.
For ¬P ∧ ¬Q to be true, then both P and Q must be false.

therefore ¬∀x:X.P ∨ Q ⊣⊢ ∃x:X.¬P ∧ ¬Q


....or should I go and start looking for my math books!

[Gorion]

I attached the answer. Excuse the handwriting..

[ATTACH=CONFIG]2958[/ATTACH][ATTACH=CONFIG]2959[/ATTACH]

[smilodon]

Well at least we laymen were vaguely on the right track, if still miles away from an actual answer to your question.

[Gorion]

It's the thought that counts