Results 1 to 6 of 6

Math Help - Logic-System Of Inference

  1. #1
    Member
    Joined
    Dec 2009
    Posts
    171

    Logic-System Of Inference

    I'll be delighted to get some help in the following:
    Let D be the following system of inference: The axioms are all the tautologies except the ones that \wedge is their main symbol and the only rule of inference if the rule:
     \frac{m,n}{m \wedge n} .
    A. Prove that D is entire in the weak meaning, but not entire (I've proved it).
    B. Let D' be the system of inference that derives from D by changing the rule by :
     \frac{m, m \to n}{n} . Prove that D' is entire.
    C. Sketch a proof tree for : P_1 \to (P_2 \vee P_3 ) from the set \{P_1 , P_2, P_3 \} .
    I've proved A... I realy need help in B and C.
    Here is what I know:
    in part B: if we can prove somehow that D' is entire in the weak meaning, we will be able to deduce what we need (because of the special rule of inference we have) ... But how can we prove it?
    In C-I know how to prove that P_2 \vee P_3 is true in D'... But can't figure out how to prove the full statement...
    Thanks !
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,551
    Thanks
    783
    By "entire", do you mean "complete"? If so, then, towards proving B, assume that P_1,\dots,P_n\models Q. Then P_1\to(P_2\to(\dots\to (P_n\to Q)\dots)) is a tautology and hence an axiom. By repeatedly using Modus Ponens, one can derive Q from P_1,\dots,P_n.

    For C, similarly, use the fact that P_2\to(P_1\to (P_2\lor P_3)) is a tautology.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Member
    Joined
    Dec 2009
    Posts
    171
    C is completely understandable..B isn't...I wrote my misunderstandings in a new reply...
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Member
    Joined
    Dec 2009
    Posts
    171
    Quote Originally Posted by emakarov View Post
    By "entire", do you mean "complete"? If so, then, towards proving B, assume that P_1,\dots,P_n\models Q. Then P_1\to(P_2\to(\dots\to (P_n\to Q)\dots)) is a tautology and hence an axiom. By repeatedly using Modus Ponens, one can derive Q from P_1,\dots,P_n.

    For C, similarly, use the fact that P_2\to(P_1\to (P_2\lor P_3)) is a tautology.
    Hey there...
    I couldn't understand from your guidance why:
    P_1\to(P_2\to(\dots\to (P_n\to Q)\dots)) is a tautology....If P_1,\dots,P_n\models Q then:
     (P_1 \wedge ...\wedge P_n)\to Q ...How can we deduce that P_1\to(P_2\to(\dots\to (P_n\to Q)\dots)) is a tautology?
    BTW- I meant Complete indeed...Sry

    Thanks !
    Follow Math Help Forum on Facebook and Google+

  5. #5
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,551
    Thanks
    783
    I remember that when I was listening to a lecture on logic as a fourth-year student and this subject came up, many students also did not understand this at first. However, using nested implications is very convenient.

    Let n = 2 for now. The formulas P1 -> (P2 -> Q)) and (P1 /\ P2) -> Q are logically equivalent. The first one says, "If P1, then if P2, then Q", which is the same as "If P1 and P2, then Q". Formally, their equivalence can be shown using truth tables.
    Last edited by emakarov; October 30th 2010 at 01:43 PM. Reason: Added parentheses around P1 /\ P2.
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Member
    Joined
    Dec 2009
    Posts
    171
    I think now I understand it...If I'll still have trouble with this, I'l reply here...

    Thanks a lot for your patience and help!
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Logic (L system)
    Posted in the Discrete Math Forum
    Replies: 4
    Last Post: October 8th 2010, 12:49 AM
  2. Proof in axiomatic system (Prop. logic)
    Posted in the Discrete Math Forum
    Replies: 3
    Last Post: October 3rd 2010, 11:12 AM
  3. Inference
    Posted in the Discrete Math Forum
    Replies: 13
    Last Post: September 17th 2010, 10:39 AM
  4. Proof System questions (Logic)
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: October 21st 2009, 07:50 PM
  5. HELP: Rules of Inference
    Posted in the Discrete Math Forum
    Replies: 3
    Last Post: September 8th 2009, 09:08 AM

Search Tags


/mathhelpforum @mathhelpforum