0

Prove the following predicates are decidable knowing that $A$ and $B$ are decidable predicates: $$\lnot A$$ $$A \lor B$$

I am supposed to prove this by writing a program or using some other way that a predicate is decidable but I am not sure how to do that.

DanielV
  • 23,556
  • ... do you know how to program in the first place? – hmakholm left over Monica Apr 07 '14 at 21:07
  • This seems pretty obvious to me. If you can decide whether or not $A$ is true, then you certainly can determine whether or not $\neg A$ is true (just return the opposite decision you got from deciding $A$). Then the same for $A \vee B$. Just decide $A$ and $B$ and if either are true, then you have decided $A \vee B$ is true and if both are false, then you have decided that $A \vee B$ is false. – Jared Apr 07 '14 at 21:15
  • @Jared True, but I'm guessing the OP is supposed to write a formal proof, which requires a particular formalization of "algorithm" (i.e., some programming language or recursive functions or whatever) – fgp Apr 07 '14 at 21:19
  • Yeah, I know how to program, but as fgp said, I need to write a formal proof and I am not sure how o write it. The problem too simple that I am finding it very difficult to prove. Also, I think I should use the while language if I wanted to write a program –  Apr 08 '14 at 22:59

1 Answers1

0

You have to use at least an "abstract" model of algorithm.

Assume that you have a "machine" - call it $M_A$ - which, receiving as input one object $x$ in your domain of discourse in turn, after a finite amount of time stops and gives you the answer YES if $A$ holds for that object $x$, and NO if $A$ does not hold for $x$.

Now, having $M_A$, we can easily build up the $M_{\lnot A}$ "machine" : "run" the $M_A$ machine with input $x$ and , when it stops and ouput YES, then "add" a new instruction which translate the output into NO (and vice versa). This is the new "machine" $M_{\lnot A}$.

Mauro ALLEGRANZA
  • 94,169