Logic: Structural Induction and Tree-method problem

In summary, the conversation discusses two questions related to proposition formulas and the use of a recursive definition and structural induction to prove a function. The first question involves a function h that counts the number of parentheses in a formula, and the second question involves using the tree method to determine the truth or falsity of certain meta-allegations. The conversation also touches on the use of logical operators and the semantic tableau in solving these problems.
  • #1
A.Dasher
2
0
I have this challenge to do but can't seem to be able to understand it completely! I also have test right now and can't concentrate. Please help this poor soul! It will be appreciated!
The first question is:Let F ∈ PROP. Let (h)F be defined by the number of parentheses in the formula F.
a): Give a recursive definition of the function h: PROP -> N (natural numbers) for the number of parentheses in the formula: F= ¬(p1 v (¬p2->p1)) or in this case h(F)=4; Feel free to change the formula if you'd like.
b): Prove with structural induction, using the definition you gave in question a and the function props, that for all proposition formulas F∈ PROP:
1/2 * h(F)+1= props (F);

And the second one is a tree method:
Let A,B,C ∈PROP. Check if these meta-allegations are true or false. Use the tree-method to show if there are counterexamples for these allegations. If there are counterexamples give at least 1 valuation.
a): A->B, ¬B->C |=A->C;
b): A<->(¬B v ¬C), ¬(A -> ¬ C) |= ¬B
Thank you before hand! I really, REALLY appreciate it!
 
Physics news on Phys.org
  • #2
A.Dasher said:
The first question is:Let F ∈ PROP. Let (h)F be defined by the number of parentheses in the formula F.
a): Give a recursive definition of the function h: PROP -> N (natural numbers) for the number of parentheses in the formula: F= ¬(p1 v (¬p2->p1)) or in this case h(F)=4; Feel free to change the formula if you'd like.
b): Prove with structural induction, using the definition you gave in question a and the function props, that for all proposition formulas F∈ PROP:
1/2 * h(F)+1= props (F);
What is the function props?

What is your definition of formulas? It should be inductive and go something like this:
if x is a variable, then x is a formula.
if x and y are formulas, then ¬(y) and (y -> z) are formulas.​
And so on for whatever logical operators you have. You could start from the outermost and leftmost formula, identify what kind of formula it is (atomic, negation, implication, etc), add the corresponding number of parentheses to your counter, remove them and the operator, and repeat. Follow a branch until it contains only what kind of formulas?

And the second one is a tree method:
Let A,B,C ∈PROP. Check if these meta-allegations are true or false. Use the tree-method to show if there are counterexamples for these allegations. If there are counterexamples give at least 1 valuation.
a): A->B, ¬B->C |=A->C;
b): A<->(¬B v ¬C), ¬(A -> ¬ C) |= ¬B
Thank you before hand! I really, REALLY appreciate it!
I'll assume the tree method is the semantic tableau. It's been a while, but I can try. Where do you get stuck? Do you know how to set it up? You want to prove that you cannot satisfy both the premises and the negation of the conclusion. So start with
(A->B)&(¬B->C)&(¬(A->C))​
What can you get from there? (Save the disjunctions for last so you'll need fewer nodes.)
 
  • #3


I am sorry to hear that you are struggling with this challenge and also have a test to focus on. I will try to explain the concepts of structural induction and tree-method in a simple way to help you understand them better.

Structural induction is a method used to prove statements about recursively defined objects, such as the number of parentheses in a formula. It involves breaking down the object into smaller parts and proving the statement for each of those parts, and then using those proofs to prove the statement for the entire object.

For the first question, we are asked to define a function h that counts the number of parentheses in a formula F. The function is recursive, meaning it can be defined in terms of itself. So, for any formula F, h(F) is equal to the number of parentheses in F. For example, in the formula F= ¬(p1 v (¬p2->p1)), there are 4 pairs of parentheses, so h(F) = 4.

To prove the statement 1/2 * h(F)+1= props (F) using structural induction, we first need to define the function props, which counts the number of propositional variables in a formula. Then, we can break down the formula F into smaller parts, such as the sub-formulas within the parentheses. We can then use the recursive definition of h to prove that the statement holds for each of these smaller parts. Finally, we can use these proofs to show that the statement holds for the entire formula F.

For the second question, the tree-method is a method used to check if a set of propositions is consistent or not. It involves creating a tree diagram to explore all possible valuations of the propositions and determine if there is a counterexample.

To check if the meta-allegations are true or false, we can use the tree-method to find a counterexample if one exists. For example, for the first meta-allegation, A->B, ¬B->C |=A->C, we can create a tree diagram with all possible valuations for A, B, and C. If we find a valuation where the left side of the implication is true, but the right side is false, then we have found a counterexample and the meta-allegation is false. If we do not find any such valuation, then the meta-allegation is true.

I hope this explanation helps you understand these concepts better. Remember to take breaks and focus on your
 

1. What is structural induction in logic?

Structural induction is a proof technique used in mathematical logic to prove statements about recursively defined structures. It involves breaking down a complex structure into simpler cases and proving the statement for each case, building up to the entire structure.

2. How does structural induction differ from mathematical induction?

Structural induction is a generalization of mathematical induction, which is used to prove statements about natural numbers. While mathematical induction is applied to a single variable, structural induction is applied to recursively defined structures such as trees or graphs.

3. What is the tree-method problem in logic?

The tree-method problem, also known as the tree method of proof, is a proof technique used in logic to prove the validity of an argument. It involves constructing a tree diagram to represent the premises and conclusions of an argument and checking for the presence of any contradictions or inconsistencies.

4. What are some examples of applications of structural induction in logic?

Structural induction is commonly used in computer science, particularly in the analysis of algorithms and data structures. It is also used in mathematical logic to prove the soundness and completeness of formal systems. In addition, structural induction can be applied in various fields of mathematics, such as graph theory and set theory.

5. What are the limitations of using structural induction in logic?

While structural induction is a powerful proof technique, it is not suitable for all types of statements. It can only be applied to statements that can be defined recursively, and may not be effective for proving statements involving non-well-founded structures. Additionally, constructing and analyzing complex trees can be time-consuming and prone to error.

Similar threads

  • Engineering and Comp Sci Homework Help
Replies
9
Views
1K
  • Engineering and Comp Sci Homework Help
Replies
6
Views
1K
  • Engineering and Comp Sci Homework Help
Replies
22
Views
2K
  • Engineering and Comp Sci Homework Help
Replies
3
Views
1K
  • Engineering and Comp Sci Homework Help
Replies
1
Views
2K
  • Engineering and Comp Sci Homework Help
Replies
5
Views
2K
  • Math Proof Training and Practice
Replies
10
Views
1K
Replies
2
Views
436
  • Engineering and Comp Sci Homework Help
Replies
26
Views
2K
  • Math Proof Training and Practice
Replies
19
Views
1K
Back
Top