Here you can ask questions and find or give answers to organizational, academic and other questions about studying computer science.

1.1k questions

1.2k answers


543 users

0 votes


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.

in * Other Teaching Fields by (190 points)
!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!

1 Answer

+2 votes
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.
by (2.5k points)
Thank you very much, I can continue to work along this thought.

Related questions

+1 vote
1 answer
asked Jun 3, 2020 in * Other Teaching Fields by wei (190 points)
0 votes
1 answer
asked Aug 22, 2020 in * Other Teaching Fields by davidschulz (410 points)
0 votes
1 answer
asked Aug 21, 2020 in * Other Teaching Fields by Eichi (200 points)
0 votes
1 answer
asked Aug 21, 2020 in * Other Teaching Fields by Eichi (200 points)
0 votes
1 answer
Imprint | Privacy Policy