0

T is an axiomatized formal theory whose wff's are constructed from "p", "q", and "r" and the familiar propositional connectives, and whose underlying logic is the standard propositional deduction system. The theory has the following axioms:

  1. ~p
  2. q
  3. ~r

How can one prove that T is negation-complete, that is every wff or its negation is a theorem of the system. Thanks for all guidance, AM

Duncan Ramage
  • 6,928
  • 1
  • 20
  • 38

1 Answers1

1

Without any rules of inference you cannot prove much. So since you said the "underlying logic is the standard propositional deduction system", I'm assuming we have the common rules such as modus ponens, 'from $A$ and $B$ deduce $A\land B$', etc., and tautologies of propositional logic such as $A\rightarrow A\lor B$ and $A\land B\rightarrow A$ as axioms of the system.

Since $p$, $q$, $r$ are the only propositional variables, the given set of axioms acts like a truth assignment. So they make every formula either true or false. To decide whether a formula is a theorem or not, first turn it into a CNF (or DNF) and then evaluate it using the "truth assignment". And then construct the proof based on the result of evaluation.

Example: $\phi = (p\lor q)\rightarrow r$

CNF: $(\neg p\lor r)\land (\neg q\lor r)$

Since the "truth assignment" makes $\phi$ false, it makes $\neg \phi$ true. We can construct the proof of CNF (or DNF) of $\neg \phi$ using the three axioms, modus ponens and the axioms $A\rightarrow A\lor B$ and $A\land B\rightarrow A$. Proof of $\neg\phi$ from its CNF (or DNF) can be done in a straightforward way as well (although it may be long).

LoMaPh
  • 1,361