Exercise Sheet5-A4-operator bases

Question

Hallo,

I am kind of confused about the first exercise on sheet 5.

The task is as follows,

Show that the set F = {<->, false, |} is a complete operator base by determining equivalent formulas over F for the following formulas. Note: Enter the result as a Boolean expression.

If the operator was not in the set, then how should I determine the formul ?

for example:  !a,,,,,,usually it is equivalent ¬a, and then the SATproblem occurs, or？ I think it should be false. But false is also an element in the set. Should this be 0 ？HOW SHOULD THIS UNVALIDE FORMULA BE TREATED？

Thanks for your help in regard.

Comments

!a and ¬a are exactly the same formula, just with different unicode characters.

And I believe that the idea is finding an equivalent formula that is restricted to the given set of operators. For example, ¬a is equivalent to a <-> false.

---

I've tried to give "false" as a solution, but it's still wrong and there is a hint:Submission is not equivalent to solution.

---

That is because !a is not equivalent to "false". As Martin wrote, it is equivalent to "a<->false" . So if a is true, "a<->false" evaluates to false (similar to !a) and if a is false, "a<->false" evaluates to true (again similar to !a).

---

now I can understand. The operator "<->" works to determine! a equivalent ,as soon as they are written.thank you!

Answer 1

Right! I guess you are confused as to what the problem is. Refer to slide 17/146 in propositional logic. There it is shown how the operators ! (negation), | (disjunction) and & (conjunction) are formulated using the entities in the set {(=>|), true, false} (i.e if-then-else operator (=>|) and boolean constants true and false). This proves that the set is a complete base (i.e. capable of formulating any boolean function).

Similarly you have to construct ! (negation), | (disjunction) and & (conjunction) using the set F = {<->, false, |}, thus proving that F is a complete base too.

Note that negation, disjunction and conjunction (denoted by ¬, v and ^ in slides) are denoted respectively by !, | and & in the exercise.

Comments

Thank you very much, I can continue to work along this thought.