Implicant: Difference between revisions
imported>Chipmunkdavis m Llm generated SDs of very variable quality |
imported>Steel1943 m →{{anchor|Essential prime implicant}}Prime implicant: fix common MOS:REFSPACE spacing errors, replaced: /ref> <ref → /ref><ref |
||
| Line 1: | Line 1: | ||
{{Use dmy dates|date=May 2019|cs1-dates=y}} | {{Use dmy dates|date=May 2019|cs1-dates=y}} | ||
In [[Boolean logic]], the term '''implicant''' has either a generic or a particular | In [[Boolean logic]], the term '''implicant''' has either a generic or a particular use. In the generic use, it refers to the hypothesis of an implication ([[wiktionary:implicant|implicant]]). In the particular use, a [[product term]] (i.e., a conjunction of literals) ''P'' is an '''implicant''' of a Boolean function ''F'', denoted <math> P \le F</math>, if ''P'' implies ''F'' (i.e., whenever ''P'' takes the value 1 so does ''F''). | ||
For instance, implicants of the function | For instance, implicants of the function | ||
:<math>f(x,y,z,w)=xy+yz+w</math> | :<math>f(x,y,z,w)=xy+yz+w</math> | ||
| Line 7: | Line 7: | ||
== {{anchor|Essential prime implicant}}Prime implicant ==<!-- Section header "Prime implicant" used by redirects --> | == {{anchor|Essential prime implicant}}Prime implicant ==<!-- Section header "Prime implicant" used by redirects --> | ||
A '''prime implicant''' of a function is an implicant (in the above particular sense) that cannot be covered by a more general | A '''prime implicant''' of a function is an implicant (in the above particular sense) that cannot be covered by a more general (more reduced, meaning with fewer [[literal (computer programming)|literal]]s) implicant. [[W. V. Quine]] defined a ''prime implicant'' to be an implicant that is minimal—that is, the removal of any literal from ''P'' results in a non-implicant for ''F''. A '''essential prime implicant''' (also known as '''core prime implicant''') is a prime implicant that covers an input combination, for which the function is true (i.e. outputs 1), that no combination of other prime implicants is able to cover.<ref>{{cite web | url=https://cse.sc.edu/~hoskinsw/classes/csce211/LecturesF15/Lecture8.pdf | title=Lecture 8}}</ref><ref>{{cite web | url=https://philosophy-question.com/library/lecture/read/207320-what-are-the-essential-prime-implicants | title=What are the essential prime implicants? }}</ref> | ||
Using the example above, one can easily see that while <math>xy</math> (and others) is a prime implicant, <math>xyz</math> and <math>xyzw</math> are not. From the latter, multiple literals can be removed to make it prime: | Using the example above, one can easily see that while <math>xy</math> (and others) is a prime implicant, <math>xyz</math> and <math>xyzw</math> are not. From the latter, multiple literals can be removed to make it prime: | ||
Latest revision as of 02:08, 13 November 2025
Template:Use dmy dates In Boolean logic, the term implicant has either a generic or a particular use. In the generic use, it refers to the hypothesis of an implication (implicant). In the particular use, a product term (i.e., a conjunction of literals) P is an implicant of a Boolean function F, denoted , if P implies F (i.e., whenever P takes the value 1 so does F). For instance, implicants of the function
include the terms , , , , as well as some others.
Script error: No such module "anchor".Prime implicant
A prime implicant of a function is an implicant (in the above particular sense) that cannot be covered by a more general (more reduced, meaning with fewer literals) implicant. W. V. Quine defined a prime implicant to be an implicant that is minimal—that is, the removal of any literal from P results in a non-implicant for F. A essential prime implicant (also known as core prime implicant) is a prime implicant that covers an input combination, for which the function is true (i.e. outputs 1), that no combination of other prime implicants is able to cover.[1][2]
Using the example above, one can easily see that while (and others) is a prime implicant, and are not. From the latter, multiple literals can be removed to make it prime:
- , and can be removed, yielding .
- Alternatively, and can be removed, yielding .
- Finally, and can be removed, yielding .
The process of removing literals from a Boolean term is called expanding the term. Expanding by one literal doubles the number of input combinations for which the term is true (in binary Boolean algebra). Using the example function above, we may expand to or to without changing the cover of .[3]
The sum of all prime implicants of a Boolean function is called its complete sum, minimal covering sum, or Blake canonical form.
See also
References
<templatestyles src="Reflist/styles.css" />
Script error: No such module "Check for unknown parameters".