Results 1 to 5 of 5

Math Help - functionally complete set of connectives

  1. #1
    Newbie
    Joined
    Mar 2010
    From
    Uruguay
    Posts
    12

    functionally complete set of connectives

    I have to proof that the connective {|} is functionally complete.
    According to the definition :

    A set of connectives C is complete if whatever valuation function is definable in terms of the conectives of C

    I have that v(\phi | \psi) = 0 iff v(\phi) = v(\psi) = 1

    As a suggestion I have : Proof that (NOT \phi)eq(\phi|\phi)

    Can someone guide me?

    Thank's
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Super Member Failure's Avatar
    Joined
    Jul 2009
    From
    Zürich
    Posts
    555
    Quote Originally Posted by Jagger View Post
    I have to proof that the connective {|} is functionally complete.
    According to the definition :

    A set of connectives C is complete if whatever valuation function is definable in terms of the conectives of C

    I have that v(\phi | \psi) = 0 iff v(\phi) = v(\psi) = 1

    As a suggestion I have : Proof that (NOT \phi)eq(\phi|\phi)

    Can someone guide me?

    Thank's
    Well, I think it is obvious, that the system of connectives \wedge, \vee, \neg, that is "and", "or" and "not", is complete (proof: think of the distributive normal form of a propositional function, aka. valuation function).
    If that's agreed, I would just try to show that these three basic connectives can be defined in terms of |. I assume that | stands for the "Sheffer stroke", i.e. for a|b :\Leftrightarrow \neg(a\vee b).

    If so, negation of a can be expressed as a|a.

    a\vee b is \neg (a|b), in other words, (a|b)|(a|b).

    Similarly for a\wedge b, since a\wedge b is equivalent to \neg (\neg a \vee \neg b), you get that a\wedge b is equivalent to (a|a)|(b|b)
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Newbie
    Joined
    Mar 2010
    From
    Uruguay
    Posts
    12
    Ok thanks for your answer but I can't understand the meaning of functionally complete set of connectives.
    As you said one connective y functionally complete when you can found a propositional formula formed in terms of NOT OR AND conectives equivalent to the other one...Is this true? or how can I know exactly when a connective or a set of connectives are functionally complete?

    From the book of Dirk Van Dalen says "For each n-ary connective $ defined by its valuation function,
    there is a proposition τ, containing only p1, . . . , pn, ∨ and ¬, such that
    |= τ ↔ $(p1, . . . , pn). " but I don't understand the meaning of this Theorem
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Super Member Failure's Avatar
    Joined
    Jul 2009
    From
    Zürich
    Posts
    555
    Quote Originally Posted by Jagger View Post
    Ok thanks for your answer but I can't understand the meaning of functionally complete set of connectives.
    As you said one connective y functionally complete when you can found a propositional formula formed in terms of NOT OR AND conectives equivalent to the other one...Is this true? or how can I know exactly when a connective or a set of connectives are functionally complete?

    From the book of Dirk Van Dalen says "For each n-ary connective $ defined by its valuation function,
    there is a proposition τ, containing only p1, . . . , pn, ∨ and ¬, such that
    |= τ ↔ $(p1, . . . , pn). " but I don't understand the meaning of this Theorem
    Well an "n-ary connective" is, basically, acting like a function (aka. its valuation function) that maps n-tupes of truth values (T or F) to a single truth value. In other words, the valuation function of an n-ary connective is a function v:\{T,F\}^n\to \{T,F\}.
    Take a similar situation from a domain with which you are probably better acquainted: real numbers. To the "2-ary connective" that we call multiplication, and symbolize by \times, for example, there corresponds a 2-ary function v:\mathbb{R}^2\to \mathbb{R} defined by v(a,b) := a\times b.
    So, basically, the distinction between "n-ary connective" and "n-ary valuation function" is mainly one of notation, not substance.

    The question that you are asked to answer is whether it is possible with a certain limited set of connectives to express any such valuation function (from n-tuples of truth values to a truth value, for any natural number n) with the help of a term consisting of connectives from that set exclusively. In other words, whether it is possible to write the definition of any n-ary valuation function in terms of connectives from that set exclusively.
    So, for example, if the set of connectives is \{\wedge, \neg\}, then you have to figure out a way to express the valuation function v(a,b) := a\vee b in terms of \wedge and \neg. This works, because we know that a\vee b\Leftrightarrow\neg \neg (a\vee b)\Leftrightarrow\neg (\neg a\wedge \neg b). And thus we have shown, that this particular valuation can indeed be expressed with the help of connectives from the set \{\wedge,\neg\}, namely by defining it like this: v(a,b) := \neg (\neg a\wedge \neg b).
    Now it might be surprising, and I suppose it was indeed surprising to some people, that it is in fact possible represent any valuation function that can be defined in terms of \{\wedge,\vee,\neg\} with a connective like the Sheffer stroke | alone.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Super Member Failure's Avatar
    Joined
    Jul 2009
    From
    Zürich
    Posts
    555
    Quote Originally Posted by Jagger View Post
    Ok thanks for your answer but I can't understand the meaning of functionally complete set of connectives.
    As you said one connective y functionally complete when you can found a propositional formula formed in terms of NOT OR AND conectives equivalent to the other one...Is this true? or how can I know exactly when a connective or a set of connectives are functionally complete?
    I forgot to answer directly this particular question: If you are asked to show that a limited set of connectives is functionally complete, it suffices to show that every connective from some other set of connectives, that is already known to be functionally complete, can be expressed with a term consisting entirely of connectives from that limited set (and parentheses, and variables of course).

    Now, I suspect that your teacher / your book has already shown that the set \{\wedge,\vee,\neg\} of connectives is, indeed, functionally complete.
    This is because every n-ary valuation function can be (uniquely) defined by its so called disjunctive normal form. This is simply a disjunction of conjunctions where each of the conjunctions specifies a pattern of T/F arguments for which the n-ary valuation function assumes the value T.
    For example, v(a,b,c) := (a\wedge \neg b\wedge c)\vee (\neg a\wedge b\wedge \neg c) is the disjunctive normal form of a valuation function v, which is T if and only if a=T, b=F and c=T, or if a=F, b=T, and c=F.
    v(a,b,c) is F, according to its above disjunctive normal form, for all other patterns of arguments a,b, and c.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. [SOLVED] set of connectives
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: August 14th 2011, 11:39 AM
  2. [SOLVED] Not Functionally Complete
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: October 1st 2010, 08:33 AM
  3. Not functionally complete set of connectives
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: September 17th 2010, 04:15 AM
  4. Logic Connectives
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: September 29th 2009, 09:57 PM
  5. Basic Connectives
    Posted in the Discrete Math Forum
    Replies: 4
    Last Post: May 31st 2007, 04:34 AM

Search Tags


/mathhelpforum @mathhelpforum