Page 1 of 2 12 LastLast
Results 1 to 15 of 18

Math Help - NEW QUESTION about Fitch

  1. #1
    Newbie
    Joined
    Oct 2012
    From
    Bangladesh
    Posts
    9

    NEW QUESTION about Fitch

    i'm at a loss with this one.....can anyone give me a hint to solve it with Fitch system:
    Given (p ⇒ q) and (r ⇒ s), use the Fitch System to prove (p ∨ r ⇒ q ∨ s).
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Newbie
    Joined
    Oct 2012
    From
    Bangladesh
    Posts
    9

    Re: Abstract reasoning/natural deduction with Fitch

    Given (p ∨ q), use the Fitch System to prove (p ∧ q).
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Newbie
    Joined
    Oct 2012
    From
    Bangladesh
    Posts
    9

    Re: Abstract reasoning/natural deduction with Fitch

    Given (p ⇒ q) and (r ⇒ s), use the Fitch System to prove (p ∨ r ⇒ q ∨ s).
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Newbie
    Joined
    Oct 2012
    From
    Bangladesh
    Posts
    9

    Re: Abstract reasoning/natural deduction with Fitch

    Starting from the premise (p ⇒ q), use the Fitch System to prove the conclusion (q ⇒ p).
    Follow Math Help Forum on Facebook and Google+

  5. #5
    MHF Contributor

    Joined
    Apr 2005
    Posts
    15,721
    Thanks
    1476

    Re: NEW QUESTION about Fitch

    You might get some response if, instead of just listing more problems, you explained what the "Fitch system" is!
    Follow Math Help Forum on Facebook and Google+

  6. #6
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,537
    Thanks
    778

    Re: Abstract reasoning/natural deduction with Fitch

    I'll describe the derivation with words and let you translate it to the Fitch form.
    Quote Originally Posted by rai009 View Post
    Given (p ⇒ q) and (r ⇒ s), use the Fitch System to prove (p ∨ r ⇒ q ∨ s).
    Assume p ∨ r. Use disjunction elimination. If p, then p ⇒ q gives q and therefore q ∨ s. Similarly, if r, then
    r ⇒ s gives s and therefore q ∨ s. In both cases, we get q ∨ s, which concludes the disjunction elimination rule.

    Quote Originally Posted by rai009 View Post
    Given (p ∨ q), use the Fitch System to prove (p ∧ q).
    Use disjunction elimination on p ∨ q. Suppose p. Assume p ∧ q, derive p. Together with p this gives a contradiction; therefore, (p ∧ q). Derive (p ∧ q) in a similar way if q.

    Quote Originally Posted by rai009 View Post
    Starting from the premise (p ⇒ q), use the Fitch System to prove the conclusion (q ⇒ p).
    Assume q and p. Then p together with p ⇒ q this gives q, and q with q gives a contradiction. Therefore, p.
    Follow Math Help Forum on Facebook and Google+

  7. #7
    MHF Contributor

    Joined
    Apr 2005
    Posts
    15,721
    Thanks
    1476

    Re: NEW QUESTION about Fitch

    Yes, that is how I would have done it. But what does that have to do with "the Fitch system"?
    Follow Math Help Forum on Facebook and Google+

  8. #8
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,537
    Thanks
    778

    Re: NEW QUESTION about Fitch

    Fitch calculus, or flag notation, is a notation for derivations in natural deduction (ND). In my English description, I used only inference rules available in ND. For example, deriving B from an assumption A in order to derive A -> B is an ND rule, but De Morgan's law is not.
    Follow Math Help Forum on Facebook and Google+

  9. #9
    Newbie
    Joined
    Oct 2012
    From
    Bangladesh
    Posts
    9

    Re: NEW QUESTION about Fitch

    Can't i solve the De Morgan's law without using the contradiction introduction tool?
    only using the "implication introduction", "implication elimination", "and introduction", and elimination", or introduction, or elimination, negation introduction, negation elimination & biconditional introduction & elimination......
    what do i do if i have to use this tools only to prove it with Fitch....
    Last edited by rai009; October 16th 2012 at 07:25 PM.
    Follow Math Help Forum on Facebook and Google+

  10. #10
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,537
    Thanks
    778

    Re: NEW QUESTION about Fitch

    Could you write the exact version of the De Morgan's law you are talking about? Also, please write all rules in your system dealing with contradiction and negation. I am asking this because different sources give different names to such rules. In particular, sometimes negation elimination is called contradiction introduction. Unlike for other connectives, it would be more correct to have only the elimination rule for contradiction, which derives any formula from contradiction. Dually, if there is a connective denoting truth, it should have only the introduction rule.

    A couple of remarks about the terminology. De Morgan's law can be derived, or deduced, or proved, but not solved. Also, implication introduction and similar things may be called tools in a particular computer program, but in logic they are called inference rules.
    Follow Math Help Forum on Facebook and Google+

  11. #11
    Newbie
    Joined
    Oct 2012
    From
    Bangladesh
    Posts
    9

    Re: NEW QUESTION about Fitch

    the version of De Morgan's law i am talking about is: Given (p ∨ q), use the Fitch System to prove (p ∧ q).
    and the 'negation elimination' in this case does not mean contradiction introduction.....it only eliminates double negations such as: ~~p by negation elimination we get p.
    negation introduction does something like this: when i find p&q=>q ,p&q=>~q then by negation introduction i get ~(p&q)....i reached to this conclusion but i have a dependence line in my program.....that's why it's saying the proof is incomplete........and when i try to use it on p, ~p it doesn't do anything....so i am not sure whether NI can be called contradiction intro in this case.......
    and there is no contradiction tool in my program to use....that's why i can't use contradiction introduction rule....
    implication introduction and elimination rules are what they're supposed to do...........though i'm not sure about biconditional introduction and elimination because i don't understand them well enough.......
    i'm still new to the use of inference rules in propositional logic.
    Follow Math Help Forum on Facebook and Google+

  12. #12
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,537
    Thanks
    778

    Re: NEW QUESTION about Fitch

    What about the following derivation?

    Code:
     1.   ~p \/ ~q		Assumption
     2.     ~p		Assumption
     3.       p /\ q	Assumption
     4.       p		3, /\E
     5.     p /\ q -> p	3-4, ->I
     6.       p /\ q	Assumption
     7.       ~p		2
     8.     p /\ q -> ~p	6-7, ->I
     9.     ~(p /\ q)	5, 8, ~I
    10.     ~q		Assumption
    11.	  p /\ q	Assumption
    12.       q		11, /\E
    13.	p /\ q -> q	11-12, ->I
    14.       p /\ q	Assumption
    15.       ~q		10
    16.     p /\ q -> ~q	14-15, ->I
    17.     ~(p /\ q)	13, 16, ~I
    18.   ~(p /\ q)		1, 2-9, 10-17, \/E
    19. ~p \/ ~q -> ~(p /\ q) 1-18, ->I
    Follow Math Help Forum on Facebook and Google+

  13. #13
    Newbie
    Joined
    Oct 2012
    From
    Bangladesh
    Posts
    9

    Re: NEW QUESTION about Fitch

    yes it works..........but how do we prove ~p|~q from the given ~(p&q)
    Follow Math Help Forum on Facebook and Google+

  14. #14
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,537
    Thanks
    778

    Re: NEW QUESTION about Fitch

    By | in ~p|~q do you mean disjunction? Why not use the same notation as in the previous posts?
    Follow Math Help Forum on Facebook and Google+

  15. #15
    Newbie
    Joined
    Oct 2012
    From
    Bangladesh
    Posts
    9

    Re: NEW QUESTION about Fitch

    oh yes ..........sorry for that.
    Given (p∧q), use the Fitch system to prove (p∨q)
    Follow Math Help Forum on Facebook and Google+

Page 1 of 2 12 LastLast

Similar Math Help Forum Discussions

  1. Replies: 9
    Last Post: December 10th 2011, 01:23 PM
  2. Derivation using Fitch
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: October 23rd 2011, 03:07 AM
  3. Abstract reasoning/natural deduction with Fitch
    Posted in the Discrete Math Forum
    Replies: 10
    Last Post: October 19th 2011, 12:37 PM
  4. How to convert with Fitch ~A v B to A -> B ?
    Posted in the Discrete Math Forum
    Replies: 7
    Last Post: June 30th 2010, 03:45 AM
  5. Formal proof (using Fitch Format) with an OR
    Posted in the Discrete Math Forum
    Replies: 5
    Last Post: June 29th 2010, 02:06 AM

Search Tags


/mathhelpforum @mathhelpforum