0
$\begingroup$

I have seen proofs of whether a set of connectives is functionally complete, but never when it is defined by a truth table. I can't quite figure out how to show that {△} is functionally complete if the propositional connective is defined by a truth table.

Here is an image of the truth table.

enter image description here

$\endgroup$

2 Answers 2

Reset to default
1
$\begingroup$

Reduce the problem to one you already know how to solve: identify which operation $\Delta$ is in your favorite method of describing them, and then use the method you already know (or reference facts you already know) to see that its functionally complete.

$\endgroup$
-1
$\begingroup$

Wikipedia describes functional completeness as follows:

In logic, a functionally complete set of logical connectives or Boolean operators is one which can be used to express all possible truth tables by combining members of the set into a Boolean expression. A well-known complete set of connectives is { AND, NOT }, consisting of binary conjunction and negation. Each of the singleton sets { NAND } and { NOR } is functionally complete.

To show that the singleton set {△} is functionally complete we need only show that the truth table of the only member of the set is the same as either NAND or NOR.

Here is Wikipedia's truth table for NOR:

enter image description here

Here is the truth table the OP presented for △:

enter image description here

Note that the only time either of these truth tables show T (or 1) for the connective is when both of the two propositions being connected are false (F or 0). Therefore △ is the same connective as NOR and since NOR is functionally complete so is △.

Wikipedia contributors. (2019, August 23). Functional completeness. In Wikipedia, The Free Encyclopedia. Retrieved 21:08, August 28, 2019, from https://en.wikipedia.org/w/index.php?title=Functional_completeness&oldid=912152343

Wikipedia contributors. (2019, February 10). Logical NOR. In Wikipedia, The Free Encyclopedia. Retrieved 21:08, August 28, 2019, from https://en.wikipedia.org/w/index.php?title=Logical_NOR&oldid=882635819

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .