Logic: Structural Induction and Tree-method problem

[A.Dasher]

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!

 

[honestrosewater]

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.)

 

[Mene]

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