Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Every first-order logic formula which has a tautological shape in propositional logic is a valid formula. Will it be possible to give a formal proof for the above ? Thanks and Regards.

share|improve this question
    
Yes it is indeed possible to give a formal proof. And it is proved in many textbooks. Which have you looked at? –  Peter Smith Nov 6 '12 at 17:42
    
i hav not looked at any textbooks as yet.can you please give any reference.so far i have been sticking to my notes only. –  heboy Nov 6 '12 at 17:47
    
I know not the tastes of others, but I learned my set theory from Bourbaki.Hope you like it. –  awllower Nov 6 '12 at 17:56
2  
You might want to take a look at Enderton, H. B. (2002) A Mathematical Introduction to Logic, Harcourt/Academic Press, ISBN 0-12-238452-0. Note that in first order logic, such tautologies (or formulas which have "tautological shape in propositional logic) are a proper subset of logically valid formulas, which I presume you know. –  amWhy Nov 6 '12 at 18:05

1 Answer 1

You might want to have a look at any proper proof of Herbrand's Theorem. There, $\forall \vec{y}\exists \vec{x}\phi_{qf}(\vec{x},\vec{y})$ sentences are transformed into a finite quantifier-free disjunction $\phi_{qf}(\vec{c_x},\vec{t_{1}})\vee\dots\vee\phi_{qf}(\vec{c_x},\vec{t_{n}})$; this disjunction, interpreted as a formula in propositional logic (!), is a tautology if and only if the original sentence was already valid.

The proof of this will contain some justification about the part where the quantifier-free disjunction is interpreted as a propositional formula. Basically, this should be straightforward. You define an injective mapping which assigns propositional variables to atoms such that exactly thos atoms which are syntactically equivalent are assigned the same variables. Then you do some argumentation based on the semantics of first-order and propositional logic; basically, these semantics should coincide for the "propositional" part of first-order logic.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.