scieee Science in your language
[en] (orig)

Parameterized prime implicant/implicate computations for regular logics

Abstract

Prime implicant/implicate generating algorithms for multiple-valued logics (MVL's) are introduced. Techniques from classical logic not requiring large normal forms or truth tables are adapted to certain "regular'' multiple-valued logics. This is accomplished by means of signed formulas, a meta-logic for multiple valued logics; the formulas are normalized in a way analogous to negation normal form. The logic of signed formulas is classical in nature. The presented method is based on path dissolution, a strongly complete inference rule. The generalization of dissolution that accommodates signed formulas is described. The method is first characterized as a procedure iterated over the truth value domain $\Delta\,=\,\{0,1, \dots ,n-1\}$ of the MVL. The computational requirements are then reduced via parameterization with respect to the elements and the cardinality of $\Delta$.

Read accessible full text

Parameterized prime implicant/implicate computations for regular logics

Author: Ramesh, Anavi,Murray, Neil V.
Publisher: Universitat Politècnica de Catalunya. Secció de Matemàtiques i Informàtica
Year: 1997
Source: https://upcommons.upc.edu/bitstream/2099/3487/1/Ramesh.pdf
      
  
   

 


   

    


      !  


      
          
          ! 
     "    #  
   $    %   &"  
           
        #  " 
   %      
      ' %     
      ( )

*

+


+

   
      % & 
       "(
  
           
           
 ! " #" $% &   "   
   '        
( " )% (        
  ' *  +" ," -"   ." / 
01 #" 21   )" 21 ."  ,1    "
,  - $" , &&& # 3  4   
% 0  5    '     6 (
7   -89!" 7   :89!"    
£
           
  !
Ý
 "          #$ %!
))
).
     !
% 8    ; (      
     889!     -89  
:89%
& <        =
        889% >  (  '  
  " 7" "  7  889
     % ? (    ( 
'(1    889"       
 ''  5-89  :89 % >    ' 
 $"  (   "     &% @(
( "   

5      
 1  5    6  $%! 0 ' 5
 )  '  5   '   ."#% 31(
   5   (   (  -89" :89"   %
&      '(   5  
% :       *     
       889% &    
    
 
"     
     % ,   ' ! "
  " 5 '    % 0  
 5  



% 9 +" 

'      <
  

A""B";

     % 0 5   C
  

'  D  C   

'    "D  +  
  



E






E

"  (%0    5
 (        '"

 % ,'(
        (" '   
 (       C'D  
  % :     ( ("
Æ    5 ( '  '(   
     5(  

% &    
      =%
?     
 

 
 
         (   889% 0
           
=% 0"     =  
 "        "   
=    "  (   
 =    %
0              
 F G

A






  % 0  5 
            (
 F% >      (      
   5       (  
    

"   , B%!%
&  +     '    
  % 0        
"#$ " %&'(%&'   & )'
)#
       , ;% & , <  
              
    '   % 0     %
& , )    (       
     (   %
  
,   '   '(HI ;'((  J A"
 '  (    % 3    
         ' *   '   
   1    %
?    !  K     ' 
  (   

 "   L  "   

 
% 9  1  "  (  

 K
E
% 3     %
B% & M   (  





 


 "
   M





 


!%
3   K   F  "     K 
  

 F* %%"       (   K%
3  M  (   MEF


F% & 
+    (      F%
?   

 ( '  F    '(    
( +    '  F!% ?  
 
 '  
+    ,E

"  ,    

    K* 


   K"   ,E


 
% ?     
'  (  5   " D3    

      ,ND 0 '( 5"   
 K        K

" 
 
* 
  E 0         !
7  7% 0       


"


%
3 '(   K

( 1   



 (   %%"  ( !    (% >     
 (            %
0       K
 
% 3 
 &  K    "     

" 
   F"    K


 
'(




E

! G



9!


" 




E

! G





!


%8
    O   '       K 
   K  K

% &(" K  


       ( 
'       % J  
)
     !
K (   5 E &






  K

" 



G



 


  K






! G

" 





! G

%
0    %
 



'  K "  3'   


  K"  





'  % 0E





E

! G

*



F E

! G
 
*









E
 
G



E

"   

*

0  +( 
Æ

F 




Æ

E

! G
 
%
¾
0 +   (      % 9" (
  






 K

 K







! G






!  (
K


*







% >'







 
( 



G









G



%
 

  
!% 


E




E

'   
K

* 


E




E









!E
 


E




E









!E

¾

"
 
?(     K

 K

    

E

"

 
  K* %%"   (       % & "  
   K5  (      '  
  F  % & " "   K 5

E

 '  '( + % P  (     
=   %%"  !"   (  (
     '  
 
  '(HI B% &("
      (   "     '
(        *  "  B%
9 +"  (    








  
 
 '  +   % H



! G 

Q!
 







 



% 3

  "   '     
 (   6  , )%
-     


"




E



 






!






!!% 3         K5
6  , )! K 


G




E


 



E


!






E
"#$ " %&'(%&'   & )'
)$




E




E

!



E

!





E





E




E

!!



E

 


E



E




E



E

 


E

9 E 889   




;

E


!!% 8    






  7
 7" 



 F%


' (  % ?    

! 
 '( 

 E &


  K"




!G






! G

* "




! G

% 0     
'   K(   1     
%
%


E
 


E

" 

G F


B%




E





E


!





E


 


E


%
;%




E





E


!





E


 


E


%
<%


E



G



E

 



E





E


  %%% K(%
  
3 '           % 3
    '"  +       
  5    '1 % 9   
+ "  $%
0   K

    
  
889!E
0 (    7  7% ,889 
(        


% 3
  
      



" 
"      7    "    
 7    % ?    
 
!

  




 (  
 
!

  *  ' (' 
     '% 9 +"  9 "      
( (   %
:7 !  ( (" 7 ! 
(% R("  ( S '      
 889      "            
 % 0  '   

+ 7

.A
     !


E

 


E



E



E

 


E



E

 


E




E



E

9 BE ,'
   !E



E
 

E
 

E


"



E
 

E
 

E


"



E
 

E
 

E
 

E


"



E
 

E


%
 ("



     "  

G 
 
!

  


G



G

!







"( 

  




"  






% & 9 "


E

  



E

"


E

"


E

"


E

"    


E

% 3

  
      (  "  



        (   (  *
( 

%
?  

 '     ( '  
    

 '      (  
  % ,        1
      K        


 1!    F 1!% 8     
  "          (
% & K

" " 1   ( '(% ,  
       ' 7"   
 
 '  
    S (   * ( 
 
%
9 +   '  


E




E

   1"  





G

"  (    1%
3    ' !   (  (  ! 
' !"    !  ' !   (  
  1 1!%
&     '    +*  "  (
 "  1  +        +( 
   % ? 


   ' 

        

% 0 +  9        9 B*  ' 
  



E
 

E
 

E


     %
8  (  ! 


 '     ! 

%
3 ( '

     '(   ' 

%
0 (     '

 

*



 '
   % 9     '"  $%
"#$ " %&'(%&'   & )'
.
 
 
 
 
   
  

  
 
9 ;E - 
  
&  "            
 1% 4  

"       
(    1 
!


!  
  


% H 
   '" 

 '   ( 
!


!  
* %%"   ( 
!


!   ( 7%
?            1 
9 ;% 0       '(    1

 


    %
0    5" '      " 
"  6      1    %
     '    1% H  
    1"   ( 



 
7 '



"  (%?     1

 


9 ;"


G
 



G

 

%
0
 
3

" 


 
!"   '
 

    

       

*

 


   

" 
 "

 
!"   '
   

    



%0 
 



!      1    




 
!!
     



!      

 
 


!    


 
!

 "

 
!!     




'   

!% 0

  1

 

  '
#
" 
$


 

#
!"    ' 


 
!
  


 
!
 "

 
!
3 ( " 5   !  % 9"
 '    '( (  '    
 1% 0   '      1  
.B
     !
% 9 ' "    "  ( " 
% ,'  (        1" 
    '( *   (   1
 "      '% 3(     
        % &   '  
   % 0     $     
  %
   
,          
  1% , 


E




E

  7 '



% 0      



 



E
 

E


% ?  
 
 '    
7   '    +(    '


E




E

% H"     ' E 0 
 1  '   '(    





!E

"'(  J
%
9(" 
#
G



" 


E

 




E

 

%0
 

%
G



E
 

E





$

% #
! G




E
 
!

 "



E
 
!



E


    




E
 
!
 "



E
 
!

 "



E
 
!



E










!E

0 '        





G

"
 7      % , " " 
*   '     (     1% 01
    "        %
-   
   
, !E



&



   1 


&




3 ,  

     '(    
   % @  
 "



E
 
!

 "



E
 
! 
 '(     +  (     
  3% 3  "  ,        
 ' % 0" ( (  ' ' '('
 ,     !  (  1 5 % 8 
 (    (      1   %
?       +% -  K
  9 <"  F G

A



B

% ? 



B

E


A



E


%
0     9 )%
&       1 "   
9 .!% ,      (    J
"#$ " %&'(%&'   & )'
.;



E


A



E

 



B

E





E


A



E

 

A

E

9 <E



E


A



E

 



B

E


A



E




E

    



E


A



E




E



A

E

9 )E



E


A



E




E

    

A

E


A



E




E

9 .E 3   
#A
     !
  
#
" 


GA
/

G


%! 9 +" 



B

<

E


 
;

E


'   


;

E
!
% 0       
<






B!



;

;!  <




<

<!



;

;!%
&  (         


'  %
 

)
'  "






'       



E
!
"






'      



" 
#





E
!
%
0 (    






  
)
%
%&

+
'      






"  
#
'     
% R(   K 
+
  A  

Q% &


+
! G A"
 '(


+
!



!
!%
,  


+
! G

Q% 0

  ( 





/

!   
  * 







!

/

%


'     K
* '( 





E


! G
 






Q
  /

 


%
H






E
!
!

"


!
!


Q "  J   
)
%
¾
 
, 
)
     
+
   
)
"

2
   
+
%0       








 '
+
%
%&

+
G
2







/

!










/

!"  
#
G


E







E


" 


       



/

%
#

 

2



E
!
  ' ' '(   



E








E











(
#

!" 






" 




%
8    
+




¼
    
2








/


!











/


!







/


/


 

(


% 0  '  
   






 
(
 
+

'
+
%
¾
 

)
'   "  

G
Ë











%

'   
     

  ' '( % 0

  
    
)
%
%&
9 (  0 <  )%
¾
?                 
)
%
 
,



%
 
9 

" 


B  A" 
 
9

"      



E
!
%
 
9


"          
  



E
!
%
 
3 

     


 ' '(
    

%
3    , B"

 +(    
)
%0 
      0 .%

"#$ " %&'(%&'   & )'
#
 " #
 F G

A



B

    E

G 




!






!!









! ,

G;" , B '  ( '  

G 

A* 
 

G   %
0     




E

"     E




E

G




E




!






!!









!
G




E




!






!!




E






!
G 




E




!




E




!!






E


 



E


!
G 




E





!


1




!!




E





!


1




!!!



B

E


 
B

E


!
G 




E





!




E
1




!!




E





!




E
1




!!!



B

E


 
B

E


!
G


A

E




B

E


!




A

E




B

E


!!



B

E


 
B

E


!
G 



E





E


!



B

E



B

E


!
8     '      J "     
'   *    (% 3  " 




 ' 





!   %
@    "  K  ' E



E



B

E






E



B

E


0 (  1 



E




B

E



*  7(!   1
    %



E






E


 
B

E






E


 
B

E






B

E


8     ' 



E




B

E


 

'(  J % 0        
%



E



B

E



B

E


  



E





E



B

E






B

E


#B
     !
8   '        % 8  
     '  "     

%
B B B










!


B

B!


B

B!










!




!


B

B!






B!
8 , B  '    

G A*        ( 
     K %

A



E





B

E


  

A



E





B

E


:    1

A



E






B

E



    
 


A

E

%

A



E




A



E


 


B

E




A



E


 


B

E


&  "       (*   
 '   J %

A



E



A



E





B

E





B

E


   

A



E





E



A



E





B

E


?     '(    '" 
 ' '(  % 0        '  1
 ' '(   ( 

% &   +"  %
0  

"


"

       , B     '
' %
"#$ " %&'(%&'   & )'
#;





E








E





E


  





E





E








E


9 E :   

 
Ë





&

½



&

¿




½
'

(



¿
'

( 



½
'

(



¿
'

(



&

¾



&

½




¾
'

(



½
'

( 



¾
'

(



½
'

(





&

¿



¿
'

(



¿
'

(



&

¾



&

¿




¾
'

(



¿
'

( 



¾
'

(



¿
'

(






&

½





&

¿




½
'

(



¿
'

( 



½
'

(



¿
'

(





&

¾





&

½




¾
'

(



½
'

( 



¾
'

(



½
'

(



¿
'

(





&

¾





&

¿




¾
'

(



¿
'

( 



¾
'

(



¿
'

(




½
'

(



¿
'

(




¾
'

(



½
'

(




¾
'

(



¿
'

(
0       

     
!
%
 $%
0        ( ' ( %
- , B      ' % @(   
  

"  



     % H" 
 (     '

( '    "   K 5
 '      (    

% 0  
           , )%  
   %! 3  CD    '  ( 
<%
&  + ' "       K 
  9 %
R   "  J   '      7%
0    ' 





      


B%
9 ("    '(



B

%
#<
     !
,     7 








E














E

%




G







Q!  



G










!% 0 '( 
J "   +  7 








E

%8
 

GA"



GA* 

G

"



G


% 3" 



 


"








E

G

E

G

%
8   7 





 


E











 


E

% 



G









! 



G







!% 0 7  '
 








E

%H" 

G

"



GA* 

GA"



G


%
3" 



 


"








E

G

E

GFE

G
 
%8 









E

G 

A





 



Q




!E

%
0"   (  J    7    
 "           A


 
'   (  % ,(" (  J   
7      "      
  '( (  !      A


% &  ( 
" "     , )%"  


   '   +
  



% ,     '   + 
 



"  E
 


'      "  F G

A



B




"



'   K 5



E

  '(    '
    % 


'     (  J
 


  '% 0


 "    


 ' 
+   






  " 




 
+   



%
¾
3  '  '   (    S 
Æ(!       
   
%
0      (      % &
        (   
    J % J  
#
G



"


E

 




E

 

" 
 
   1



E
 

E









E
 
!

 "



E
 
!



E


    




E
 
!
 "



E
 
!

 "



E
 
!



E










!E

8   ( '         
   





!E

% @   (


E




E

"'(  J
%
0    '       





    '   +% U  "





 '      (% @     1 
"#$ " %&'(%&'   & )'
#)
   



   % 0  (
        " ( +
     ( S E




E
 
!

 "



E
 
!



E


    




E
 
!
 "



E
 
!

 "



E
 
!



E






E




E

0      1 +     %
0             
1E
 "



E
 
!   7  


E

  7* (

 "



E
 
!% 0  7      7
      1"       
1  ( '  '    (  (
7% ,          J 
 ( "        %




E
 
!
 "



E
 
!
    




E
 
!
 "



E
 
!
 "



E
 
!
H  (       (   
        1% @   +(   
 1  J  '       1% 9 
     "       
- 

%
>'     '       5%
0 (          
 % &  "  ( '   ( 
C( D ( (        1  
     '  ("  +% 0  
     " "   ' %
0             
     1% & " ,   (  
 % @(  +( '       1" 
 '  ,  "       %
H"  '  '     '  11%
R("   1    J   ( '
 ' % 0  '  (      
(      1*    '     7
  (  % H"   1    J
   '   '( (  *  J
   '  '      % 0
      J   '    1%

#.
     !
 
9    " (    
1   (    "    1  
J     (%
%&
?     ,   '1E 


'  '1
     J   '"  



  % @(  (   1   
,   


"   ,  


"    


%
,  ,      (  "


 ' 
(    '   %
¾
&  '     '    
  1  '        1% & 
 "       ("   " 
    "   %
&      '        '
         K    
' *   ( '   +   



" 
A




% 3  "      0 E



'       "  F G

A



B




%



'       K 5



E

"   '( 
(    '     "   '(
( (  % 


'     (  J
 


  '% 0


 "    


 ' 
+   






  " 




 
+   



%
¾
?               
  
)
%
 
,



%
 
-
!

"      K 5



E
!
%
 
-
!

'( (  J  
!

  '%
 
9 

" 


B  A" 
 
9

"      
!

%
 
9


"           
 
!

%
 
3 

    


 ' '(   
 

%
3    , <"

 +(    
)
%0 
      0 $%
"#$ " %&'(%&'   & )'
##
8    '  "       +
 +("    % &     ("  
    , B       " 
     % >'       
 '  , <%B     % H" (    
5        
!

   ' '( 
% 0 7         
 



E
!
%
-   K   9 "   
 J %



B

E





E


  



B

E





E


8   1



B

E


!




E



   " 
   7! (  %



B

E






B

E


 

Q




E






B

E


 

Q




E






B

E


 

Q




E


,  J     ( 1 " ( 
 "    "    1 

G;%




E







E


 

Q

B

E







E


 

Q

B

E





B

E


0  , ;   "  (    
     

G    A% ( 

  
'          , B   
% 0   "   "   
 "   "       

%
0    '     '  %
    
0  (  "     1   
     '   ' ("  ' 
#
     !
     % &     , B   
 "      ( '      +
        ( F% 3  '
  '        
    % 0  '      
    %
3    5       5  '  +
  (%   5  '     
(  (% 0 +     '
    %%"  !   ' 
% 3     '   (    (
5    '  +% 3("'(  ("
      F  '   %
!
 3" -%% 0 34   '% & :%- J
"
( .  
" 8 H $<" B.
B%
B HI" J% U  '    %
%
   * .  / 
" &RRR -
 , ( " " @-" ( B.B$" $$" B;B<)%
; HI" J%
0 1  / 
%&
,    - ," % A% >+ U("
$$<%
< HI" J% (   +  %
0 
  0  * 
" B;"<!EB;OB.<" :% $$<%
) 21" %"  " 2% -  &%
%  
A

* (  0 1
" /" ?%
4(" 2(" $$A% &
   0  * 
% ,1"
%!" ," % <<$" )<;))#%
. 21" % -   (%
%  


* (  0 1
", ,"
8P" 2" $$B% &
   0  * 
":% /" %!"
," % .A#" B);B.#%
# /" 3%"  01" 4% 3      
=%
2  .$ (
$$A!" )BA.%
 /" 3%"  01" 4% 3 '    
(%
( * 
!
8% $$B!" B<%
"#$ " %&'(%&'   & )'
#$
$ (" 8%%"  J" R% :E 1  %
2,0(
"!
2( $$;!" )A<);)%
A (" 8%%"  J" R% J     
 %
%   * .  
 *  .
" -" 8-" >'  .$" $$% &
 
 0  * 
" V% J W % V1" %!" ," %
)<B" )#A)#$%
 (" 8%%"  J" R% C3 - & 05
   U , 9%D
) *
!
,% $$<!" B;#B);%
B 8" J%2%" ,   "
2, .$ 
"
"
$))!"
A)A%
; 8" 0% 3       %
%
  *2(0*34
"  /" -' (" 9" 3" $$;"
<.)%
< J" 3%" @1" 4%"  (" 8%% C-89  :89 - H
  -  &=&%D 0"
2  0

%
) J" J%   /" 2% 9  '  
 (E (  %
%  
.

 (
 0  * 
"  /" ," ?3" 2( B#" $#"
;%
. ," 2%J%" -" -%%"  " J%-%0% 3    
 %
*555   (+
# $
$#A!" ;A<
;A%
# , &&& ?%J%    % & :%- J "
( .  
" 8 H $<" BB#B.#%
 ,1"0%(      %
2  (

$$B!" ;#.;%
$ , ,%P%H  - %0%" -    %
& :%- J "
( .  
" 8 H
$<" $)BB.%