# Proofs by induction on immediate predecessors (well-formed formula complexity)

• StopWatch
In summary: Physics ForumIn summary, the conversation discusses a proof by induction on immediate predecessors to show that no well-formed formula (wff) using only the letters P, Q and the connectives ^,v is a tautology. The speaker defines key terms, breaks down the three steps of the proof, and explains how to use the principle of mathematical induction to conclude that all wffs have the property of not being a tautology. They also offer encouragement and well wishes for the proof.
StopWatch
Hi physics forum,

As far as I know the general pattern for this sort of proof is,

1) All atomic well-formed formulas (wffs) have some property P
2) From the assumption that immediate predecessors of any non-atomic wff A have P, so too does A.
3) Every wff A has P

and I have to:

Prove by induction on immediate predecessors (wff complexity) that
no wff using only the letters P, Q and the connectives ^,v is a tautology.

Any suggestions would be much appreciated.

Stopwatch

Hi Stopwatch,

First, let's define the terms we are dealing with. A well-formed formula (wff) is a string of symbols that follows the rules of a given formal language, in this case using the letters P, Q, and the connectives ^ (conjunction) and v (disjunction). A tautology is a wff that is always true, regardless of the truth values assigned to its atomic components.

Now, for the proof by induction. We will use the three steps you mentioned in your post, but let's break them down further for clarity:

1) All atomic wffs have the property of not being a tautology. This is true by definition, since atomic wffs consist of a single letter (P or Q) and cannot be both true and false at the same time.

2) From the assumption that immediate predecessors of any non-atomic wff A have the property of not being a tautology, we can show that A also has this property. This is because the truth value of A is determined by the truth values of its immediate predecessors, and if those predecessors are not tautologies, then A cannot be a tautology either.

3) By using the principle of mathematical induction, we can conclude that all wffs have the property of not being a tautology. This is because we have shown that all atomic wffs have this property, and that any non-atomic wff A will also have this property if its immediate predecessors have it.

In conclusion, we can prove that no wff using only the letters P, Q and the connectives ^,v is a tautology by showing that each step in the induction process holds true. I hope this helps you get started on your proof.

Best of luck,

## What is a well-formed formula?

A well-formed formula is a mathematical expression that is constructed according to certain rules and symbols. It must be syntactically correct and unambiguous in order to be considered a valid formula.

## What is the principle of mathematical induction?

The principle of mathematical induction is a method of proving mathematical statements or theorems. It states that if a statement is true for a base case, and if it can be shown that the statement is true for the n+1th case assuming it is true for the nth case, then it can be concluded that the statement is true for all cases.

## How do you use proof by induction on immediate predecessors?

To use proof by induction on immediate predecessors, you must first identify the base case and prove that the statement is true for it. Then, you must show that if the statement is true for the nth case, it is also true for the n+1th case. Finally, you can conclude that the statement is true for all cases.

## What is the complexity of a well-formed formula?

The complexity of a well-formed formula refers to the number of symbols or operations used to construct it. This can include variables, constants, and logical operators. The complexity can vary depending on the length and structure of the formula.

## What are the benefits of using proofs by induction on immediate predecessors?

Proofs by induction on immediate predecessors can be useful for proving statements about recursive structures, such as well-formed formulas. It allows for a systematic and efficient way of proving statements for all cases, rather than having to prove each case individually.

• Set Theory, Logic, Probability, Statistics
Replies
1
Views
2K
• Set Theory, Logic, Probability, Statistics
Replies
40
Views
7K
• Calculus and Beyond Homework Help
Replies
4
Views
1K
• Quantum Physics
Replies
210
Views
15K
• Calculus
Replies
8
Views
602
• Calculus and Beyond Homework Help
Replies
1
Views
1K
• Set Theory, Logic, Probability, Statistics
Replies
1
Views
1K
• Calculus and Beyond Homework Help
Replies
2
Views
2K
• Calculus
Replies
3
Views
409
• Set Theory, Logic, Probability, Statistics
Replies
2
Views
2K