Jump to content
BrainDen.com - Brain Teasers
  • 0


superprismatic
 Share

Question

Let A, B, C, D, and E be statements. Consider the following

four statements made from these using the usual five sentential

connectives ~, ∨, &, →, and ↔ (explained below):


I: (((A&B)∨(B↔A))∨E)↔(((C↔(C∨B))&A)∨(E&A))
II: ((~((D∨((A&(D→B))∨((~C∨A)∨B)))∨E)∨E)&A)↔A
III: ((~A∨(C→A))&~C)→(B→(B→((((A∨B)&A)∨E)&A)))
IV: (A&(E→((E∨A)→E)))→((((E→A)↔D)↔(E↔C))∨E)
[/code] Which of the following statements are derivable from the above set of four statements, and which are not?
[code]
Statement 1: B∨(C∨(E&(D&(E∨((~E→A)&(A∨(E↔(C&B))))))))
Statement 2: (((((A↔D)↔(B→D))&D)↔(((C∨E)→D)∨B))∨A)↔B
Statement 3: (~(((C&B)∨A)&C)→A)∨(A&(E→(C∨(E→(B∨C)))))
Statement 4: B∨(E↔(A↔(~(B&((E∨((E∨A)→A))↔B))∨(A&D))))
Statement 5: A↔(((B↔C)&E)∨((D&B)&(D∨((A&D)&(E↔A)))))
Statement 6: (((((E∨~A)∨C)↔D)→((B↔D)↔D))∨A)&(E↔(E&A))
The five sentential connectives are: 1. ~ (not) ~X is true when X is false and ~X is false when X is true. 2. ∨ (or) X∨Y is true when at least one of X and Y is true, otherwise it is false. 3. & (and) X&Y is true when both X and Y are true; otherwise it is false. 4. → (implication) X→Y is true unless X is true and Y is false, in which case it is false. 5. ↔ (equivalence) X↔Y is true when X and Y have the same truth value, otherwise it is false. In case someone would rather have the RPN version of the statements, I include them below:

I: AB&BA↔∨E∨CCB∨↔A&EA&∨↔
II: DADB→&C~A∨B∨∨∨E∨~E∨A&A↔
III: A~CA→∨C~&BBAB∨A&E∨A&→→→
IV: AEEA∨E→→&EA→D↔EC↔↔E∨→
Statement 1: BCEDEE~A→AECB&↔∨&∨&&∨∨
Statement 2: AD↔BD→↔D&CE∨D→B∨↔A∨B↔
Statement 3: CB&A∨C&~A→AECEBC∨→∨→&∨
Statement 4: BEABEEA∨A→∨B↔&~AD&∨↔↔∨
Statement 5: ABC↔E&DB&DAD&EA↔&∨&∨↔
Statement 6: EA~∨C∨D↔BD↔D↔→A∨EEA&↔&
[/code]

Link to comment
Share on other sites

9 answers to this question

Recommended Posts

  • 0

I'm just a bit confused, so I guess I need to ask this first:

All the information in the OP points to propositional calculus.

When you say "derive" this makes me think of derivations from a set of axioms using a set of rules (e.g.modus ponens). If so, I take I, II, III, IV to be the axioms, but how about the rules? Which rules of inference do you accept for a syntactical derivation/proof?

On the other hand, when you say "~ (not) ~X is true when X is false and ~X is false when X is true." you interpret them as two-valued logic. In this case, the meaning implied is that of satisfiability / semantically implication. In this setting, one must show/disprove that for each truth-table in which I-IV are true, Statement X is true (X=1..6)

Just curios which of the 2 you meant - I know that they're equivalent for proposition calculus:

1)Syntactical - a proof by rules of inference OR a proof by showing contradiction arise if starting an inference from I-IV + Statement X

2)Semantical - a proof by exhaustive search over the truth-tables that make I-IV true OR a case where I-IV are true and X is not.

Edited by araver
Link to comment
Share on other sites

  • 0

I'm just a bit confused, so I guess I need to ask this first:

All the information in the OP points to propositional calculus.

When you say "derive" this makes me think of derivations from a set of axioms using a set of rules (e.g.modus ponens). If so, I take I, II, III, IV to be the axioms, but how about the rules? Which rules of inference do you accept for a syntactical derivation/proof?

On the other hand, when you say "~ (not) ~X is true when X is false and ~X is false when X is true." you interpret them as two-valued logic. In this case, the meaning implied is that of satisfiability / semantically implication. In this setting, one must show/disprove that for each truth-table in which I-IV are true, Statement X is true (X=1..6)

Just curios which of the 2 you meant - I know that they're equivalent for proposition calculus:

1)Syntactical - a proof by rules of inference OR a proof by showing contradiction arise if starting an inference from I-IV + Statement X

2)Semantical - a proof by exhaustive search over the truth-tables that make I-IV true OR a case where I-IV are true and X is not.

My intention was to allow solvers to do this in any way they wish. Since the 2 are equivalent for propositional

calculus, as you point out, I didn't want to hamstring anyone tackling this problem. I submitted this problem

to add to the variety of problems on this forum as well as to give something of a challenge to those who are

a bit shaky on their understanding of the methodology of sentential logic.

I purposely used the term "derivable" so as to allow any homemade rules of inference which don't allow false

statements to arise from true hypotheses. In short, this problem really wasn't intended for consumption of

those who find such things easy, although they are perfectly welcome to do so (in spoilers, I hope). I included

the RPN versions to aid solvers who wanted to write programs to solve this problem.

I hope this clears up my intentions. Thanks for your comments.

Link to comment
Share on other sites

  • 0

How does this work, if you get the answer you post it, of course, but is anything else reqired? Do you get some kind of credit for a correct answer?

and sometimes people get into a little friendly competition on problems. We all try to be civil and friendly. Sometimes there are differences of opinion, but people air their differing opinions with reasonable arguments.

Oh, and....

Yes, 3,4, and 6 are derivable but the others are not.

Link to comment
Share on other sites

  • 0

Thanks for the info, I've been reading the help file and not finding exactly what i was curious about. First, thanks for the puzzle, it was an enjoyable challenge, although I feel I may have taken the long way to figure it out. Second, if you don't mind answering, how do members advance from a NEWBIE?

Link to comment
Share on other sites

  • 0

Thanks for the info, I've been reading the help file and not finding exactly what i was curious about. First, thanks for the puzzle, it was an enjoyable challenge, although I feel I may have taken the long way to figure it out. Second, if you don't mind answering, how do members advance from a NEWBIE?

That rank is purely a reflection of the number of posts. So, it's really is a measure of activity. I wouldn't worry about it if I were you. I've seen NEWBIEs around here who are obviously PhDs in math related topics. I've also seen teenagers who are advanced members. Most of us just love math and logic problems. That's the main thing around these here parts, partner!

Link to comment
Share on other sites

Join the conversation

You can post now and register later. If you have an account, sign in now to post with your account.

Guest
Answer this question...

×   Pasted as rich text.   Paste as plain text instead

  Only 75 emoji are allowed.

×   Your link has been automatically embedded.   Display as a link instead

×   Your previous content has been restored.   Clear editor

×   You cannot paste images directly. Upload or insert images from URL.

Loading...
 Share

  • Recently Browsing   0 members

    • No registered users viewing this page.
×
×
  • Create New...