2

I'm trying to prove that the truth-tree method can be used to give a positive effect test for implication, and a negative effect test for non-implication. I've been given the fact that The truth-tree method gives us a positive effect test for unsatisfiability, and a negative effective test for satisfiability. I'm not asking for the proof. My problem is that I don't understand what is meant by positive and negative effect test and I can't find anywhere online that explains it.

1

Truth trees are a graphical device for a methodical search for counterexamples to a given set of premises. They are effective (for propositional logic) in the sense that the search either terminates with finding a counterexample, or with verifying that one does not exist by exhausting all options. They are more effective than truth tables because they exploit the specific structure of the premises to guide the truth value assignment, whereas the truth table just blindly tries all possible combinations. "Positive effect test for unsatisfiability" means that all the branches of the truth tree close when the premises are not satisfiable. "Negative effect test for unsatisfiability" means that there is an open branch that gives an explicit example of truth value assignments that do satisfy the premises. See Truth Trees for Propositional Logic by Suber.

What you are asked to do is rather simple. In classical logic the negation of P → Q is P ∧ ¬Q, so you can run the truth tree on P, ¬Q. If all the branches close P ∧ ¬Q is unsatisfiable, and the implication holds (positive effect). If there is an open branch it is satisfiable, and the implication is false (negative effect). Moreover, it will give you an explicit truth assignment that satisfies both P and ¬Q, which is an explicit counterexample to the implication.

This generalizes to predicate logic to an extent, but there the tree may become infinite, so the construction of an open branch may never terminate. In other words, the test is no longer effective on all inputs, see Method of analytic tableaux.

  • 1
    Thank you, I think I get it now – Noah Bensler Mar 11 at 3:56

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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