 |
|
| Science Forum Index » Mathematics Forum » What is a Closed set of Boolean Functions ? |
|
Page 1 of 1 |
|
| Author |
Message |
| dimovich |
 Posted: Mon Feb 21, 2005 6:35 am |
|
|
|
Guest
|
Subject ?
What are its aplications, and how to prove a Set of Boolean Functions
is Closed...
--
dimovich |
|
|
| Back to top |
|
|
|
| William Elliot |
| Posted: Mon Feb 21, 2005 7:09 am |
|
|
|
Guest
|
On Mon, 21 Feb 2005, dimovich wrote:
[quote:a1b3747976]Subject ?
The subject is "What is a Closed set of Boolean Functions?"[/quote:a1b3747976]
[quote:a1b3747976]What are its aplications, and how to prove a Set of Boolean Functions
is Closed...
Applications for what? Boolean Functions?[/quote:a1b3747976]
There are many, too many to describe in the subject line. |
|
|
| Back to top |
|
|
|
| Jim Spriggs |
| Posted: Mon Feb 21, 2005 12:24 pm |
|
|
|
Guest
|
Mitch Harris wrote:
[quote:21e196e32e]
dimovich wrote:
Subject ?
closed probably means closed under application.
That is, suppose you have the single operation "->" (if-then). Then
you can also get the operation "T" (= x -> x) (binary function that
always returns true), and the operation "AND" (x -> (y -> T)), but no
[/quote:21e196e32e]
Let's see
x -> (y -> T) x and y
------------------------------
T T T T T T T T
T T F T T T F F
F T T T T F F T
F T F T T F F F
Actually one doesn't need a truth table to evaluate (x -> (y -> T)).
Just remember one of the so-called paradoxes of material implication:
any proposition implies a true proposition. Also, if a Boolean
expression has the value 1 (i.e. T) in the two element algebra, then
it has the value 1 in any Boolean algebra.
[quote:21e196e32e]but no
combination of -> will get you anything else (er, any other binary
function).
[/quote:21e196e32e]
((x -> y) -> y) is (x inclusive-or y)
(x -> y) -> y x or y
------------------------------
T T T T T T T T
T F F T F T T F
F T T T T F T T
F T F F F F F F |
|
|
| Back to top |
|
|
|
| Jim Spriggs |
| Posted: Mon Feb 21, 2005 12:46 pm |
|
|
|
Guest
|
dimovich wrote:
[quote:f289e620e9]
Subject ?
What are its aplications, and how to prove a Set of Boolean Functions
is Closed...
[/quote:f289e620e9]
My guess: by a closed set of Boolean functions is meant a functionally
complete set of connectives for two-valued propositional logic. If
that's it then
{not, inclusive-or}, {not, and}, {not, if-then}, {Sheffer-stroke},
{the one that's like Sheffer stroke the name of which I've forgotten}
and the unions of any two or more of those.
Also, if constants are allowed {_|_, if-then}.
There are also weird connectives discussed in Church, like
not-(p <- q), which in combination with other things can make
functionally complete sets.
There are also connectives with three arguments (Tony Hoare discussed
one or a couple somewhere). |
|
|
| Back to top |
|
|
|
| Mitch Harris |
| Posted: Tue Feb 22, 2005 4:48 am |
|
|
|
Guest
|
Jim Spriggs wrote:
[quote:d6e67e2cd1]Mitch Harris wrote:
dimovich wrote:
Subject ?
closed probably means closed under application.
That is, suppose you have the single operation "->" (if-then). Then
you can also get the operation "T" (= x -> x) (binary function that
always returns true), and the operation "AND" (x -> (y -> T)), but no
Let's see
x -> (y -> T) x and y
------------------------------
T T T T T T T T
T T F T T T F F
F T T T T F F T
F T F T T F F F
[/quote:d6e67e2cd1]
Ah. Yes. I was an idiot. (x->(y->T)) = T.
Big mistake on my part. You cannot get AND from an arbitrary
application of "->".
The most accessible proof is by exhaustion (look at all the formulas
you can get by -> and 2 vars and see what functions come out (and you
only need to look at a few small formulas before they repeat)).
A more involved proof would be to note some properties of your set of
boolean functions and prove that every function in that set has the
properties, and that none of the functions outside the set has those
properties.
[quote:d6e67e2cd1]but no
combination of -> will get you anything else (er, any other binary
function).
((x -> y) -> y) is (x inclusive-or y)
(x -> y) -> y x or y
------------------------------
T T T T T T T T
T F F T F T T F
F T T T T F T T
F T F F F F F F
[/quote:d6e67e2cd1]
Right.
So what I (ahem) meant to say is that the set of operations {->, OR}
is closed (under application) but {->} is not (because its closure is
larger, its closure includes OR).
I made a thinko above because I confused AND and OR, and the identity
x -> (y -> z) = (x AND y) -> z.
The closure of {->, AND} is strictly larger than the closure of {->}
(the closiure of {->, AND} includes <-> which is not in the closure of
{->}.
--
Mitch Harris
(remove q to reply) |
|
|
| Back to top |
|
|
|
| Mitch Harris |
| Posted: Tue Feb 22, 2005 4:57 am |
|
|
|
Guest
|
Jim Spriggs wrote:
[quote:230000e340]dimovich wrote:
Subject ?
What are its aplications, and how to prove a Set of Boolean Functions
is Closed...
My guess: by a closed set of Boolean functions is meant a functionally
complete set of connectives for two-valued propositional logic.
[/quote:230000e340]
(as far as I know) the adjective for that is "complete" or "adequate",
enough functions whose closure is all boolean functions.
so a complete set that is also closed would be the set of boolean
functions.
[quote:230000e340]If
that's it then
{not, inclusive-or}, {not, and}, {not, if-then}, {Sheffer-stroke},
{the one that's like Sheffer stroke the name of which I've forgotten}
[/quote:230000e340]
NOR, dagger function, joint denial
[quote:230000e340]and the unions of any two or more of those.
Also, if constants are allowed {_|_, if-then}.
There are also weird connectives discussed in Church, like
not-(p <- q), which in combination with other things can make
functionally complete sets.
There are also connectives with three arguments (Tony Hoare discussed
one or a couple somewhere).
[/quote:230000e340]
so all your examples are complete, but none are closed. Some of the
examples I gave were closed but none complete.
--
Mitch Harris
(remove q to reply) |
|
|
| Back to top |
|
|
|
|
|
All times are GMT - 5 Hours
The time now is Thu Mar 18, 2010 5:30 pm
|
|