Canonical form with NOR or NAND?
Jack W.
propositional calculus (or zeroth-order logic), when it is expressed in
the usual way with the three operators AND, OR, and NOT, there is an
algorithm (a mindless procedure) that will reduce any expression to a
_canonical_ form. This means that any expressions that will produce
the same results when evaluated over the possible values of the
variables will reduce to the same form. An interesting property of the
canonical form is it makes contradiction easy to detect.
Contrary to convention, I prefer to reason with N-input operators
instead of 2-input operators. So, instead of writing p AND q, I would
like to write AND(p, q). This lets me write AND(p, q, r) instead of p
AND q AND r. More importantly, it lets me write AND(), which I think
you can see is a tautology (an expression that is true regardless of
the values of the variables). Similarly, OR() is a contradiction (an
expression that is false regardless of the values of the variables).
Adopting N-input operator language lets us dispense with having any
special constants for true and false, since we can just write AND() and
OR() respectively. Our language thus becomes simpler by the dropping
of two tokens. At the same time, it still lends itself to taking any
expression no matter how complex and reducing it to canonical form (e.
g., OR on the outside, ANDs in the middle, and all NOTs pushed all the
way to the leaves; this is the conventional canonical form at least as
I was taught in school).
The student knows very well the laws to apply in converting expressions
successively until reaching canonical form. Some of them are De
Morgan's laws, laws of distribution of AND over OR and vice versa,
idempotency laws, and associativity of AND and OR, and the facts that
AND(p, NOT p) = OR() and OR(p, NOT p) = AND().
Now consider another langauge where the only operator is NOR over any
number of inputs. Then NOR(p, q, r) for example in the new language
means what AND(NOT p, NOT q, NOT r) meant in the old language, NOR() =
AND(), and NOR(NOR()) = OR().
Is there a canonical form for the multi-input NOR language that is
pretty simple to describe, and some easy-to-understand laws to apply in
converting a complex expression in this language to its canonical form?
G. Frege
wrote:
>
> Contrary to convention, I prefer to reason with N-input operators
> instead of 2-input operators. So, instead of writing p AND q, I would
> like to write AND(p, q). This lets me write AND(p, q, r) instead of p
> AND q AND r. More importantly, it lets me write AND(), which I think
> you can see is a tautology (an expression that is true regardless of
> the values of the variables). Similarly, OR() is a contradiction (an
> expression that is false regardless of the values of the variables).
> Adopting N-input operator language lets us dispense with having any
> special constants for true and false, since we can just write AND() and
> OR() respectively. Our language thus becomes simpler by the dropping
> of two tokens.
>
There is a slight problem with this approach, I think. Consider for
example:
AND(p,q) (*)
and
AND(p, q, r). (**)
Here the function name "AND" in (*) denotes a _different_ function
than the function name "AND" in (**) (since the "AND" in (*) denotes a
function with 2 arguments, while the "AND" in (**) denotes a function
with 3 arguments). Actually, this should be made explicit (at least in
a precise logical language) by, say, some sort of an index, leading to
AND^2(p,q), AND^3(p, q, r), etc.
for example. (No "polymorphism" in our zeroth-order language!)
On the other hand, there is a simple trick, I guess, to overcome that
slight inconvenience. We might consider _sets_ of propositional
variables instead of dealing with "isolated" propositional variables
as arguments of the AND^n functions.
Then we might consider
AND({p, q}), AND({p, q, r}), etc.
HERE the AND would refer to one and the same function.
Ok... we might allow for the following simplification of our notation
(afterwards):
AND(a_1, ..., a_n) =df AND({a_1, ..., a_n}) (n e IN\{0})
and especially
AND() =df AND({}).
So, finally, this approach "converges" with your original one. :-)
(It seems.)
F.
--
E-mail: info<at>simple-line<dot>de
G. Frege
>
> On the other hand, there is a simple trick, I guess, to overcome that
> slight inconvenience. We might consider _sets_ of propositional
> variables instead of dealing with "isolated" propositional variables
> as arguments of the AND^n functions.
>
> Then we might consider
>
> AND({p, q}), AND({p, q, r}), etc.
>
> HERE the AND would refer to one and the same function.
>
> Ok... we might allow for the following simplification of our notation
> (afterwards):
>
> AND(a_1, ..., a_n) =df AND({a_1, ..., a_n}) (n e IN\{0})
>
> and especially
>
> AND() =df AND({}).
>
> So, finally, this approach "converges" with your original one. :-)
> (It seems.)
>
Of course, in this case there wouldn't be any point in proving, say,
AND(p, q) <-> AND(q, p) ,
since the "two" argument sets would be identical.
translogi
the (old) electronic logic gates.
see
http://en.wikipedia.org/wiki/Logic_gate
for example
they can have any number of inputs.
Following that lead it becomes
Nand =df= Not( And(any number of inputs))
Nor =df= Not (OR(any number of inputs))
hopes this helps, but maybe i am completely of track
On Jan 23, 6:25 pm, G. Frege <nomail@invalid> wrote:
> On Tue, 23 Jan 2007 16:54:32 +0100, G. Frege <nomail@invalid> wrote:
>
> > On the other hand, there is a simple trick, I guess, to overcome that
> > slight inconvenience. We might consider _sets_ of propositional
> > variables instead of dealing with "isolated" propositional variables
> > as arguments of the AND^n functions.
>
> > Then we might consider
>
> > AND({p, q}), AND({p, q, r}), etc.
>
> > HERE the AND would refer to one and the same function.
>
> > Ok... we might allow for the following simplification of our notation
> > (afterwards):
>
> > AND(a_1, ..., a_n) =df AND({a_1, ..., a_n}) (n e IN\{0})
>
> > and especially
>
> > AND() =df AND({}).
>
> > So, finally, this approach "converges" with your original one. :-)
> > (It seems.)Of course, in this case there wouldn't be any point in proving, say,
>
> AND(p, q) <-> AND(q, p) ,
>
> since the "two" argument sets would be identical.
>
> F.
>
> --
>
> E-mail: info<at>simple-line<dot>de- Hide quoted text -- Show quoted text -
part
important as this may produce interesting results.
On Jan 23, 8:54 pm, G. Frege <nomail@invalid> wrote:
> On 23 Jan 2007 05:58:57 -0800, "Jack W." <8e2icj...@sneakemail.com>
> wrote:
>
>
>
> > Contrary to convention, I prefer to reason with N-input operators
> > instead of 2-input operators. So, instead of writing p AND q, I would
> > like to write AND(p, q). This lets me write AND(p, q, r) instead of p
> > AND q AND r. More importantly, it lets me write AND(), which I think
> > you can see is a tautology (an expression that is true regardless of
> > the values of the variables). Similarly, OR() is a contradiction (an
> > expression that is false regardless of the values of the variables).
> > Adopting N-input operator language lets us dispense with having any
> > special constants for true and false, since we can just write AND() and
> > OR() respectively. Our language thus becomes simpler by the dropping
> > of two tokens.There is a slight problem with this approach, I think. Consider for
Mitch
> Every student of the most elementary logic knows that in the
> propositional calculus (or zeroth-order logic), when it is expressed in
> the usual way with the three operators AND, OR, and NOT, there is an
> algorithm (a mindless procedure) that will reduce any expression to a
> _canonical_ form.
> it still lends itself to taking any
> expression no matter how complex and reducing it to canonical form (e.
> g., OR on the outside, ANDs in the middle, and all NOTs pushed all the
> way to the leaves; this is the conventional canonical form at least as
> I was taught in school).
I think you 're talking about DNF, disjunctive normal form. There's
also the dual, CNF.
...
> Now consider another langauge where the only operator is NOR over any
> number of inputs. Then NOR(p, q, r) for example in the new language
> means what AND(NOT p, NOT q, NOT r) meant in the old language, NOR() =
> AND(), and NOR(NOR()) = OR().
>
> Is there a canonical form for the multi-input NOR language that is
> pretty simple to describe, and some easy-to-understand laws to apply in
> converting a complex expression in this language to its canonical form?
Sure.
AND(OR(...), OR(...),...) = NOR(NOR(...),NOR(...),...)
So if you start with a pure NOR formula, not already in canonical form,
convert to NOTs and ANDs, convert that to CNF, then use the above rule
to immediately get a 2-level normal form in NOR.
Mitch
Jack W.
> So if you start with a pure NOR formula, not already in canonical form,
> convert to NOTs and ANDs, convert that to CNF, then use the above rule
> to immediately get a 2-level normal form in NOR.
>
> Mitch
Thanks. I'd thought of that. But what motivated my question was
thinking about what representation to use for propositional formulae
in a computer program. If the procedure to conjoin some formula
(representing existing knowledge) with a new forumula (representing a
discovery) and maintain cononical form, is going to be to convert each
whole forumula from NOR form to a normal form with AND, OR, and NOT;
then conjoin the formulae in that form; then finally, convert back to
NOR form again, then I might just as well represent all formulae in
AND, OR, and NOT all the time. Nothing has been gained from adding
NOR form to the design. I'm wondering whether a simpler system could
be realized on the computer using NOR all the time vs. using AND, OR,
and NOT all the time.