1. Originally Posted by lpetrich
Originally Posted by steve_bank
Any logic function can be implemented by AND-OR or NAND-NOR. logic.
Crisp logic, at least.

However, one needs a NOT function to do so. I will prove that by finding out what happens when one only has AND and OR.

Each of those two operators is both commutative and associative, so that one can easily define multiple-argument versions of them. Also, both operators are idempotent, meaning that one can collapse repetitions of an argument to a single copy of it.

They are also monotone, meaning that (x <= y) <-> (AND(x,z) <= AND(y,z)) and (OR(x,z) <= OR(y,z)). This has the consequence that every combination is monotone, and also that every combination is bounded from below by AND(all its args) and from above by OR(all its args).

Thus, every combination of AND's and OR's returns 0 for all-0 args and 1 for all-1 args. So to get 0 for all-1's and 1 for all-0's, one needs a NOT operator. That is also true for violations of monotonicity, like X(0,others) = 1 while X(1,others) = 0.

But if one has a NAND or a NOR operator, one can get a NOT out of it with NOT(x) = NAND(x,x) = NOR(x,x), using the idempotence of AND and OR. NOT with NAND gives AND, and with DeMorgan's rules, OR, and with further negation, NOR. Likewise, one can get OR, AND, and NAND from NOR.

In fact, one can get any truth table with combinations of NOT, AND, and OR.
Yes. It is important in digital logic chips. It is more efficient use of space on chip to use and-or logic along with not or inversion. Minimization of logic to implement a logical equation is important. Abstract algebra is important.

Discreet logic chips have given way to large scale logic chips but discrete chips remain.

In a standard 14 pin IC package you can get multiple OR, AND, NOT, Exclusive OR NOR, NAND, functions.

You interconnect individual gates as they are called to implement a function. There are techniques to manually derive a set of logic equations from a truth table(inputs vs outputs), but these days it is done in software. You wire the gates in accordance with the logic equations.

In what is called programmable logic chips software takes a Boolean expression and wires the logic in the chip.

Not familiar with the term crisp logic but I get the meaning.

2. Crisp logic is traditional mathematical logic, especially for comparison to fuzzy logic.

As to implementing truth tables, one could do it by this tactic.

For each set of input values that returns 1, add NOT's to get 1's out of those that are 0, and then apply AND to them.

Once that is done, apply OR to all of them.

Thus, one can implement exclusive or as

XOR(a,b) = ((NOT a) AND b) OR (a AND (NOT b))

Though this approach can implement *any* truth table, it can easily require more operations than is necessary. Reducing that number is where comes in.

3. Fuzzy logic has a set-theory counterpart, fuzzy sets. These are sets with partial set membership. For set A and entity a, we can call the membership of a in A the function m(A,a).

The familiar set-theory operations are defined as follows:
m( A union B , a) = m(A,a) or m(B,a)
m( A intersect B , a) = m(A,a) and m(B,a)
m( A subtract B , a) = m(A,a) and not m(B,a)
m( complement A , a) = not m(A,a)

For traditional, crisp set theory, the set-membership function only has values 0 and 1, while for fuzzy set theory, it can have values in between.

4. Standard symbols for logic in electronics.

http://www.ti.com/lit/an/slva700/slva700.pdf

A part. In the truth table L is zero volts or a 0. H is a positive voltage or a logic 1.
http://ecelabs.njit.edu/student_reso...tas/74ls00.pdf

#### Posting Permissions

• You may not post new threads
• You may not post replies
• You may not post attachments
• You may not edit your posts
•