Logic-System Of Inference

Printable View

October 30th 2010, 10:54 AM
WannaBe

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:

Quote:

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 !
October 30th 2010, 12:35 PM
emakarov

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.
October 30th 2010, 01:26 PM
WannaBe

C is completely understandable..B isn't...I wrote my misunderstandings in a new reply...
October 30th 2010, 01:31 PM
WannaBe

Quote:

Originally Posted by emakarov

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 !
October 30th 2010, 01:42 PM
emakarov

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.
October 30th 2010, 01:44 PM
WannaBe

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!