A formula provable without is a tautology

  • Thread starter antonio85
  • Start date
  • Tags
    Formula
In summary, the conversation discusses methods for proving that a formula is a tautology without using certain axioms and rules. One suggested approach is to use induction, starting with a base case and then showing that the proof holds for all cases. Another question is posed about how to proceed for a proof with more than one step.
  • #1
antonio85
5
0
How can I prove that:

If a formula [tex]A[/tex] is provable without use of substitution axioms, nonlogical axioms, equality and identity axioms, and the [tex]\exists[/tex]-introduction rule, than [tex]A[/tex] is a tautology.

I try to act this way: consider a tautology A and show that using propositional axioms I get another tautology, and that if the hypothesis of a rule are tautologies then also the conclusion is a tautology. But I don't know wether it is the correct way or not.
Anyone can help me?
 
Physics news on Phys.org
  • #2
A good way to start might be by induction

If your proof is one step then what can A possibly be?

Then if it's true for all proofs of less than or equal to n steps... for an n+1 step proof how would you proceed?
 

1. What is a tautology?

A tautology is a statement that is always true, regardless of the truth values of its components. In other words, it is a statement that is true by definition.

2. How is a formula provable without axioms?

A formula can be proven without axioms by using logical deductions and reasoning. This means that the proof relies solely on the structure of the formula itself, rather than any external assumptions or premises.

3. What does it mean for a formula to be provable?

When a formula is provable, it means that it can be logically derived from a set of axioms or assumptions. This means that the formula is true based on the rules and principles of logic.

4. Can a formula be provable without being a tautology?

Yes, a formula can be provable without being a tautology. This means that the formula can be logically derived from axioms or assumptions, but it may not be true by definition.

5. What are some examples of formulas that are provable without being tautologies?

Some examples of formulas that are provable without being tautologies include mathematical equations, scientific hypotheses, and logical arguments. These formulas can be proven based on logical deductions and reasoning, but they may not be true by definition.

Similar threads

I Are existence proofs outlawed in multi-valued logics?
    • Set Theory, Logic, Probability, Statistics
Replies
19
Views
2K
B What is the role of tautology in an axiomatic system and proof?
    • General Math
Replies
2
Views
1K
Arguments in sentential logic and contradictions/tautologies.
    • Set Theory, Logic, Probability, Statistics
Replies
7
Views
6K
A A "Proof Formula" for all maths or formal logic?
    • Set Theory, Logic, Probability, Statistics
Replies
3
Views
2K
Is it possible to prove (P→Q)↔[(P ∨ Q)↔Q] without using truth tables?
    • Precalculus Mathematics Homework Help
Replies
1
Views
1K
Logic- How to show something is NOT provable?
    • Calculus and Beyond Homework Help
Replies
5
Views
2K
Equivalence classes of proper classes
    • Set Theory, Logic, Probability, Statistics
Replies
10
Views
4K
MHB How Can I Understand and Use the Stars and Bars Selection Formula?
    • Set Theory, Logic, Probability, Statistics
Replies
7
Views
1K
A The Blessings of Dimensionality and Hilbert's 6th Problem
    • Set Theory, Logic, Probability, Statistics
Replies
4
Views
1K
Is Alan Turing given too much credit when it comes to computers?
    • Programming and Computer Science
Replies
29
Views
3K

Hot Threads

Recent Insights

Back
Top