1 Restrições Booleanas O domínio dos Booleanos (ou variáveis 0/1) tem especial aplicação em aplicações –Envolvendo circuitos digitais Exemplo: Circuito

1

Restrições Booleanas• O domínio dos Booleanos (ou variáveis 0/1) tem

especial aplicação em aplicações

– Envolvendo circuitos digitais

• Exemplo: Circuito semi-somador

– Em problemas envolvendo escolhas binárias

• Exemplo: Rainhas

– Em problemas que envolvam conjuntos

B

G1

G2

AC

S

2

Restrições Booleanas• Nas restrições booleanas (de igualdade) podem

ser utilizadas os habituais operadores (not, and, or, nand, nor, xor, ...).

Modelo do semi-somadorC = and(A,B)S = xor(A,B)

B

G1

G2

AC

S

3

Restrições Booleanas• As restrições (correspondentes às variáveis

Booleanas) podem ser igualmente expressas com esses operadores

Modelo das 4-rainhasor(Q1, Q2, Q3, Q4) Linha 1and(Q1,Q2) = 0 Linha 1

....and(Q1, Q6) = 0 Diagonal

Q1 Q2 Q3 Q4

Q5 Q6 Q7 Q8

Q9 Q10 Q11 Q12

Q13 Q14 Q15 Q16

4

Restrições Booleanas• A satisfação de restrições booleanas pode ser

abordada de várias formas diferentes– Simbolicamente

• Unificação booleana

– SAT• Colocação de todas as restrições na forma

clausal• Resolução construtiva (retrocesso) ou

reparativa (pesquisa local)

– Domínios finitos• O domínio 0/1 é um domínio finito com 2 valores• Resolução comum aos domínios finitos

5

Constraints and Logic Programming• In principle, all the referred problems may be solved

with logic programming (LP) alone. • After all, finite domains are a subset of the Herbrand

Universe (constants).

• Why should one move towards Constraint Logic Programming (CLP), rather than staying within LP.

• Two types of reasons

– Greater Expressiveness of CLP wrt LP• CLP regarded as an extension of LP

• Specific constraint harder in LP (e.g. Conditional constraints)

– Greater Efficiency to solve Finite Domains problems• Combinatorial nature of Problems

6

Operational Semantics of CLP

• The operational semantics of CLP can be described as a transition system on states.

• The state of a constraint solving system can be abstracted by a tuple

<G, C, S >

where

– G is a set of constraints (goals) to solve

– C is the set of active constraints

– S is a set of passive constraints

• The sets C,S are considered the Constraint Store

7


The state transitions are the following

• Handling a constraint

it is assumed that a computation rule selects constraint g among those still to be considered.

• The other transition rules require the existence of two functions, adequate to the domains that are considered, infer(C,S) and consistent(C).

c is a constraint

< G {c}, C, S > c < G , C, S {c}, >

8


• Function infer(C,S) simply converts the Constraint Store in a more convenient form.

• For example, assuming that variables A and B can take values in 1..3 and A > B, then

C = {A in 1..3, B in 1..3} , S = {A > B}

and the application of infer, i.e. C’,S’ = infer(C,S), would take into account that values A=1 and B = 3 cannot participate in any solution.

• Hence, a constraint solver for finite domains would possibly get

C’ = {A in 2..3, B in 1..2 , A > B } , S = { }

9


• Predicate consistent(C) checks whether it is possible to solve the constraints in C.

• For example, for the previous set

C = {A in 2..3, B in 1..2 , A > B }

consistent(C) would be true.

• In contrast, for a different set

C = {A in 1..3, B in 1..3 , A > B, B > A }

consistent(C) should evaluate to false. In some cases, it is not possible, or convenient, to work with such strong implementations of consistent, in which case, the constraint solver is incomplete.

10


•Given these functions the remaining state transitions are

•Processing a constraint (inferring its consequences)

• Checking consistency

(C’, S’) = infer (C,S)

< G, C, S > i < G, C’, S’ >

consistent (C)

< G, C, S > s < G, C, S >

¬ consistent (C)

< G, C, S > s fail

11


•As usual, a derivation is just a sequence of transitions.

•A state that cannot be rewritten is a final state.

•A derivation is failed if it is finite and its final state is fail.

•A derivation is successful if it is finite and processes all the constraints, i.e. it has the form

<Ø, C, S >

•A derivation flounders if it is finite and is not able to handle all the constraints, i.e. Its final state has the form

<G, C, S >

12

CLP as an extension of LP

•In this context, CLP can be regarded as an extension of LP.

•Put in other words, LP can be regarded as a special instance os CLP, where the domain to be considered is the Herbrand domain (finite trees).

•The Resolution rule, can be simply considered as a special case of handling literals (as equality constraints on the Herbrand Domain).

g is a goal h B

< G {g}, C, S > r < G B, C, S {h = g} >

13


• In the case of Logic Programming, function infer(C,S) simply passes the constraint from the passive set to the active set, and performs the necessary unification of terms.

• For example, assuming the following substitutions have already been performed on X and Y and an equality of terms h/1 needs to be checked

C = {X / f(Z), Y / g(Z,W)} , S = {h(Z,W) = h(a,b)}

the application of infer, i.e. C’,S’ = infer(C,S), would implement the unification of terms.

C’ = {X / f(a), Y / g(a,b), Z/a, W = b} , S’ = {}

14


• In case of LP, predicate consistent(C), simply checks whether the unification was possible or not.

• In practice, in LP the two functions infer and consistent are performed at the same time, since the unification performed by infer either fails or not.

• For example, given

C = {X / Z, Y / Z) } , S = {h(X,Y) = h(a,b)}

• The successive application of infer and consistent would result in false and the derivation would fail.

15

CLP Solutions

• In LP, solutions of a problem should be found in the set C of the final state of a successful derivation.

<Ø, C, S >

• In all CLP domains for which the solvers are complete (not only in LP, but also booleans and rationals, to name the most common), a successful derivation implies the existence of solutions. For example, given

C = {X / f(Z), Y / g(Z, b)}

possible solutions are

X=f(b), Y= g(b,b), Z = b

or X = f(f(b)), Y= g(f(b),b), Z = f(b) ...

16

Restrições Booleanas• Para verificar a satisfação de restrições booleanas

de uma forma simbólica é conveniente converter todas as restrições de forma a usar apenas,

– os operadores

+ (ou-exclusivo) e · (conjunção),

– constantes booleanas

0 e 1 ( eoutras constantes, dependentes do domínio)

– variáveis

denotadas por letras maiúsculas

• Isto é sempre possível, já que o conjunto {0, 1, +, ·} é completo.

17

Restrições Booleanas

• Com efeito, dados os termos arbitrários a e b, todos os operadores e constantes podem ser expressos através destes operadores

a b = a · b

a b = a + b + a · b

a = 1 + a

a b = 1 + a + a · b

a b = 1 + a + b

• termos arbitrários serão denotados por minúsculas

18

Restrições Booleanas• Mais formalmente, o tuplo < A, 0, 1, +, ·>, em

que A é um qualquer domínio (contendo os elementos 0 e 1), constitui um anel booleano se se verificarem as seguintes propriedades

• Associatividadea+(b+c) = (a+b)+c a·(b·c) = (a·b)·c

• Comutatividadea + b = b + a a·b = b·a

• Distribuiçãoa+(b·c) = a·b+a·c a·(b+c) = (a+b)·(a+c)

• Elemento Neutroa+0 = a a·1 = a

• Exclusividade e Idempotência a+a = 0 a·a = a

• Elemento Absorventea·0 =0

19

Restrições Booleanas• As restrições booleanas que consideraremos

resumem-se à igualdade, já que todas as outras se podem exprimir em função da igualdade. Por exemplo, dada a equivalência

a b a b = a a b = b a restrição de inclusão de conjuntos acima pode

ser reescrita em termos de igualdade como

a+b+a·b = b

a+b+b+a·b = b+b

a+ a·b = 0

a·b = a

20


• Conjuntos

– A constante 1 corresponde ao conjunto U (Universal)

– A constante 0 corresponde ao conjunto Ø (Vazio)

– O operador + corresponde à União Exclusiva– O operador · corresponde à Intersecção

• De notar que no caso de conjuntos, uma vez definido os elementos que contém o conjunto universal, para além das constantes 0 e 1, o domínio A contém todos os subconjuntos de U.

21

Restrições Booleanas• Circuitos digitais

– A constante 1 corresponde ao H– A constante 0 corresponde ao L– O operador + corresponde ao XOR– O operador · corresponde ao AND

A

C

D

B

E

F

G

H

I

G1

G2

G3

G4

G5

• E = A+B+A·B• F = 1+B·C• G = C·D• H = 1+E·F• I = 1+F·G

22

Unificação Booleana

• Uma restrição booleana t1 = t2 (em que os dois termos Booleanos, t1 e t2 são formados exclusivamente a partir dos operadores + e ·) pode ser satisfeita sse existir um unificador booleano para os dois termos.

• Um unificador booleano (designado através de uma letra grega) é uma substituição de variáveis por termos booleanos que garante que os dois termos tomam o mesmo valor booleano.

• Os unificadores booleanos serão designados através de letras gregas

23


• Exemplo: Os termos t1=1+A e t2 = A·B podem ser unificados com o unificador

= {A/1, B/0}

• Com efeito, denotando por t (ou simplesmente t) a aplicação da substituição ao termo t, temos

t1 = (1+A){A/1, B/0}= 0

t2 = (A·B){A/1, B/0}= 0

o que garante a satisfação da restrição t1=t2.

24

Unificação Booleana• Em geral, dados dois termos Booleanos, t1 e t2,

pode existir mais do que um unificador mais geral como pode ser visto pelo seguinte exemplo.

• Exemplo: A unificação dos termos t1=1+A·B e t2=C+D pode ser obtida por qualquer um dos seguintes unificadores mais gerais

1 = { C/1+A·B+D}

2 = { D/1+A·B+C}

3 = { A/1+C+D, B/1}

4 = { A/1, B/1+C+D }

• Com efeito, t1 1 = (1+A·B){C/1+A·B+D} = 1+A·B

t2 1 = (C+D){C/1+A·B+D}=(1+A·B+D)+D = 1+A·B

25


• Existem outros unificadores (menos gerais) que podem ser obtidos através de instâncias dos anteriores, isto é, da composição delas com outras substituições.

• Por exemplo, a substituição λ obtida pela composição de 1 com a substituição {A/0} ainda

é um unificador dos termos t1=1+A·B e t2=C+D λ = {C/1+A·B+D } o {A / 0}

= {C/1+D, A/0}

• Com efeito, t1 λ = (1+A·B) {C/1+D, A/0} = 1+0·B = 1

t2 λ = (C+D) {C/1+D, A/0} = (1+D+D) = 1

26

Algoritmo de Unificação Booleana

• Tendo em atenção que t1=t2 é equivalente a t1+t2=0, a unificação de dois termos Booleanos t1 e t2 equivale a anular o termo t1+t2.

• As condições em que um termo t se pode anular, podem ser analisadas através dos pontos seguintes.

1. O anulamento de um termo constante t é trivialmente verificável: se t=0 o termo já é nulo; se t=1 o termo não é anulável.

2. Dada a propriedade distributiva, um termo t, não constante, pode sempre ser reescrito na forma a·U+b (em que U é uma qualquer das variáveis que ocorrem em t) pondo U “em evidência”.

27


3. Um termo t=a·U+b só se pode anular, se tivermos ou a=1 ou b=0 (na situação contrária, a=0 e b=1 teremos t=10,independentemente do valor de U).

4. Essa condição (a=1 ou b=0) é garantida se se anular o termo (1+a)·b.

5. Uma vez garantida esta situação, constata-se que – se a=0 (e b=0), U pode tomar um valor arbitrário

(pois 0·U+0=0)– se a=1, então U tem de tomar o valor b

(pois 1·b+b=0)

28


6. Esta condição pode ser implementada com o recurso a uma variável booleana nova, isto é que não ocorra em t. Chamando _U a essa variável a condição anterior é equivalente à substituição

U = (1+a)·_U + b

7. Com efeito,

• se a=0 (e b=0) temos U=_U, ou seja U pode tomar um valor arbitrário, já que a variável _U é uma variável nova, que não está associada a quaisquer restrições;

• Se a=1 temos U=(1+1)·_U + b, ou seja U = b como pretendido.

29


• Estas considerações podem ser materializadas no seguinte predicado unif_bool, que recebe os termos t1 e t2 a unificar, e sucede se o predicado anular suceder, retornando a substituição retornada por este predicado.

predicado unif_bool (in: t1, t2; out: );

t t1+t2;

unif_bool anula(t,);fim predicado.

• O predicado anula é implementado a seguinte forma.

30


predicado anula (in: t; out: );caso t = 0: anula = Verdade, = {};caso t = 1: anula = Falso;

caso contrário:

A·u + B t; s (1+A)·B;

se anula(s,σ) então

anula Verdade; {U/(1+A)·_U+B} o σ

senão

anula = Falso

fim se

fim caso

fim predicado.

31

Algoritmo de Unificação Booleana• Dada a sua natureza recursiva, a substituição

retornada pelo predicado anula é obtida pela composição da substituição {U/(1+A)·U+B}, com a substituição σ obtida na chamada recursiva do predicado (se este suceder).

Exemplo: Satisfazer a restrição X+X·Z=Y·Z+1, anulando o termo X+X·Z+Y·Z+1

Unifica X+X·Z e Y·Z+1

anula X+X·Z+Y·Z+1

= (1+Z)·X+Y·Z+1 % Ax·X+Bx

anula (1+(1+Z))·(Y·Z+1) % (1+Ax)·Bx

= Z·(Y·Z+1)

= Z·Y+Z % Ay·X+By

anula (1+Z)·Z %(1+Ay)·By

= 0

32

Algoritmo de Unificação BooleanaUnifica X+X·Z e Y·Z+1

anula X+X·Z+Y·Z+1 = (1+Z)·X+Y·Z+1

anula (1+(1+Z))·(Y·Z+1)=Z·Y+Z %(1+Ax)·Bx

anula (1+Z)·Z = 0 %(1+Ay)·By

σ = {}

σ = {Y/(1+Ay)·_Y+By} o {}

= {Y/(1+Z) ·_Y+Z} o {}

= {Y/(1+Z) ·_Y+Z}

σ = {X/(1+Ax)·_Y+Bx} o {Y/(1+Z)·_Y+Z}

= {X/(1+1+Z)·_X + Y·Z+1} o {Y/(1+Z)·_Y+Z}

= {X/ Z·_X +Y·Z+1} o {Y/(1+Z)·_Y+Z}

= {X/ Z·_X +((1+Z)·_Y+Z)·Z+1, Y/(1+Z)·_Y+Z}

= {X/ Z·_X +Z+1, Y/(1+Z)·_Y+Z}

= {X/ Z·_X +Z+1, Y/(1+Z)·_Y+Z}

33


• Desta forma a restrição X+X·Z = Y·Z+1 é satisfazível, já que a unificação dos termos X+X·Z e Y·Z+1 sucede retornando o unificador booleano mais geral

= {X/Z·_X +Z+1, Y/(1+Z)·_Y+Z}

• Podemos confirmar este resultado, verificando que

(X+X·Z) = (Z·_X+Z+1)+(Z·_X+Z+1)·Z= (Z·_X+Z+1)+Z·_X= Z+1

e que

(Y·Z+1) = ((1+Z)·_Y+Z)·Z+1)= Z+1

34

Restrições Booleanas• Interpretando, este resultado, podemos concluir

que a restrição X+X·Z = Y·Z+1 pode ser satisfeita independentemente do valor da variável Z, dado o unificador mais geral

= {X/Z·_X +Z+1, Y/(1+Z)·_Y+Z}

• Numa análise mais pormenorizada se Z=0 então X=1 e Y=_Y, ou seja,

X deve tomar o valor 1, e Y pode tomar qualquer valor;

se Z=1 então X=_X e Y=1, ou seja, X pode tomar qualquer valor, eY=1;

35

Aplicações• Um domínio de eleição para a utilização de

restrições booleanas é o domínio dos circuitos digitais.

• Exemplo: 1. Modelar o circuito abaixo através de um conjunto

de restrições booleanas 2. Verificar em que condições a saída toma o valor 1.

CG1

FG4

DG2

EG3

B

A

R1: C = 1+ A·B

R2: D = 1+ A·C

R3: E = 1+ B·C

R4: F = 1+ D·E

36

Aplicações1. Restrições: R1: C = 1+ A·B R2: D = 1+ A·C

R3: E = 1+ B·C R4: F = 1+ D·E

Resolução das Restrições

R1: Resolvendo R1 obtemos a substituição 1

C = 1+A·B 1 ={C/1+A·B}

R2: Aplicando 1 temos

R2’ : R2 1

: D = (1+A·C){C/1+A·B}: D = (1+A·(1+A·B))

: D = 1+A+A·B

Resolvendo R2’ obtemos a substituição 2’ = {D/1+A+A·B}

37

AplicaçõesCombinando 2

’ com 1 obtemos

2 = 1

o 2’

= {C/1+A·B} o {D/1+A+A·B}

= {C/1+A·B, D/1+A+A·B}


R3’ : R3 2

: E = (1+B·C) {D/1+A+A·B, C/1+A·B}

: E = 1+B·(1+A·B)

: E = 1+B+A·B

Resolvendo R3’ obtemos a substituição 3’ = {E/1+B+A·B}

Combinando 3’ com 2

obtemos

3 = 2

o 3’

= {E/1+B+A·B} o {D/1+A+A·B} o {C/1+A·B}

= {E/1+B+A·B, D/1+A+A·B, C/1+A·B}

38

AplicaçõesR4: Aplicando 3 temos

R4’: R4 3

: F = (1+D·E) {E/1+B+A·B, D/1+A+A·B, C/1+A·B}

: F = 1+(1+A+A·B)·(1+B+A·B)

: F = 1+1+B+A·B+A+A·B+A·B+A·B+A·B+A·B

: F = A+B

Resolvendo R4’ obtemos a substituição 4’ = {F/A+B}


obtemos

4 = 3

o 4’

= {E/1+B+A·B, D/1+A+A·B, C/1+A·B}o{F/A+B}

= {E/1+B+A·B, D/1+A+A·B, C/1+A·B, F/A+B}

Interpretando 4 concluímos que o circuito com 4

portas nand implementa um ou-exclusivo, já que F/A+B

39

Aplicações2. Saída igual a 1

Para representar esta situação acrescenta-se a restrição R5: F = 1.


R5’ :R5 4

:(F = 1) {E/1+B+A·B, D/1+A+A·B, C/1+A·B, F/A+B} : A+B = 1

Resolvendo R5’ obtemos a substituição 5’ = {A/1+B}


obtemos

5 = 4 o 5

’

= {E/1+B+A·B, D/1+A+A·B, C/1+A·B, F/A+B}o{A/1+B}= {E/1+B, D/B, C/1, F/1, A/1+B}

Interpretando o resultado concluímos que para o circuito ter uma saída 1, as suas entradas devem ser complementares. Com efeito a substituição A/1+B permite concluir que

se B=0 então A=1; ese B=1 então A=0 e

40

Restrições Booleanas no SICStus PrologUma vez carregado o SICStus Prolog o módulo de Restrições Booleanas, através da directiva

use_module(library(clpb))As restrições Booleanas podem ser verificadas através do predicado sat(E) , em que a igualdade é representada por ‘=:=’ e os operadores + e · através de # e *, respectivamente.

Exemplos: 1. ?- sat(A#B=:=F).

sat(A=:=B#F)?

% A restrição A+B=F é satisfazível, com a substituição

A/B+F

41

Restrições Booleanas no SICStus Prolog2. ?- sat(A*B=:=1#C*D).

sat(A=\=C*D#B)?

% A restrição A·B=1+C·D é satisfazível, com substituição A/1+C·D+B

3. ?- sat(A#B=:=1#C*D), sat(C#D=:=B).

sat(B=:=C#D),

sat(A=\=C*D#C#D) ?

% As restrições A+B=1+C·D e B=C+D são satisfeitas com a substituição {A/1+C·D+C+D, B/C+D}

Nota: Atenção à notação das respostas. A=:= Exp corresponde a A/Exp

A=\= Exp corresponde a A/1+Exp

42

Restrições Booleanas no SICStus PrologUm exemplo mais completo, relativo ao circuito anterior

:- use_module(library(clpb)).

nand_gate(X,Y,Z):-

sat(X*Y =:= 1#Z).

circuit(A,B,[C,D,E],F):-

nand_gate(A,B,C),

nand_gate(A,C,D),

nand_gate(B,C,E),

nand_gate(D,E,F).

CG1

FG4

DG2

EG3

B

A

43

Restrições Booleanas no SICStus PrologAlguma interacção com o sistema| ?- circuit(A,B,[C,D,E],1).C = 1,E = A,sat(B=\=A),sat(D=\=A) ?

Esta resposta pode ser comparada com 5 anterior, constatando-se que são “variantes” do unificador mais geral {E/1+B, D/B, C/1, F/1, A/1+B}

CG1

FG4

DG2

EG3

B

A

44

Restrições Booleanas no SICStus PrologOutra interacção| ?- circuit(A,B,[C,D,E],F).sat(C=:=_A*F#F#_A),sat(A=\=_A*F#_B*F#F#_A),sat(B=\=_A*F#_B*F#_A),sat(D=\=_B*F),sat(E=\=_B*F#F) ? ;

A comparação com 4 anterior é um pouco menos

óbvia ... { E/1+B+A·B, D/1+A+A·B, C/1+A·B, F/A+B} 1+A·B = 1+ (1+_A·F+_B·F+F+_A)· (1+_A·F+_B·F+_A)

= 1+((1+_A·F+_B·F+_A)+F)·(1+_A·F+_B·F+_A)= 1+(1+_A·F+_B·F+_A)+(1+_A·F+_B·F+_A)·F= 1+ 1+_A·F+_B·F+_A + F+_A·F+_B·F+_A·F= F+_A+_A·F= C

CG1

FG4

DG2

EG3

B

A

45

Restrições Booleanas no SICStus PrologN Rainhas

Para modelar o problemas das rainhas há que garantir

– Em todas as linhas há exactamente uma rainha• Em todas as linhas há uma ou mais rainhas• Em todas as linhas há uma ou menos rainhas

– Em todas as colunas há exactamente uma rainha• Em todas as colunas há uma ou mais rainhas• Em todas as colunas há uma ou menos rainhas

– Em todas as diagonais há uma ou menos rainhas

46

Restrições Booleanas no SICStus Prolog

rainhas_3([Q1, Q2, Q3,

Q4, Q5, Q6,

Q7, Q8, Q9]):-

um_ou_mais( [Q1, Q2, Q3]), % linha 1

um_ou_menos([Q1, Q2, Q3]), ... um_ou_mais( [Q1, Q4, Q7]), % coluna 1

um_ou_menos([Q1, Q4, Q7]),...

um_ou_menos([Q2,Q6]),

um_ou_menos([Q1, Q5, Q9]), % diagonais \



um_ou_menos([Q3, Q5, Q7]), % diagonais /

um_ou_menos([Q6,Q8]).

47

Restrições Booleanas no SICStus Prolog% Uma ou mais rainhas

um_ou_mais(L):- % L = [A,B,C,...,Z]

or_exp(L, Exp), % Exp = A+B+C+...+Z

sat(Exp =:= 1). % A+B+C+...+Z = 1

or_exp([H], H).

or_exp([H|T], H + T_exp):-

or_exp(T, T_exp).

% Uma ou menos rainhas

um_ou_menos([_]).

um_ou_menos([H1,H2|T]):-

sat(H1 * H2 =:= 0), % A1*A2 = 0

um_ou_menos([H1|T]), % idem para outros pares com A1

um_ou_menos([H2|T]). % idem para outros pares sem A1

48


Padrões de Teste de Avarias (Stuck-at-0/1)

•Há que garantir uma saída diferente entre– o circuito correcto e – o circuito com falhas

tp(F, [I1, I2]):-

semi_somador([],[I1, I2], [S1,C1]),

semi_somador(F, [I1, I2], [S2,C2]),

gate(xor, [S1, S2], S),

gate(xor, [C1, C2], C),

gate(or,[S,C],1).

1

I1

I2

S2

C2

S1

C1

S

C

B

G1

G2

AC

S

49

Restrições Booleanas no SICStus PrologHá naturalmente que definir o que é um circuito em termos das suas componentes, que podem estar avariadas (Stuck-at-0/1)

semi_somador(F, [I1,I2],[S,C]):- % F é o conjunto gate(1, F, and, [I1,I2], C), % de falhas gate(2, F, xor, [I1,I2], S).

Na definição do comportamento de cada gate há que prever a possibilidade dessas falhas

gate(N,F,_,_,0):- member(N/0, F), !.gate(N,F,_,_,1):- member(N/1, F), !.gate(_,_,T,I,O):- gate(T,I,O).

member(H,[H|_]).member(H,[H|T]):- member(H,T).

50


Finalmente há que definir o comportamento de cada gate (sem falhas) por intermédio da correspondente restrição booleana

gate(or, [I1,I2],O):- sat(I1+I2 =:= O).

gate(nor, [I1,I2],O):-sat(I1+I2 =\= O).

gate(xor, [I1,I2],O):-sat(I1#I2 =:= O).

gate(and, [I1,I2],O):-sat(I1*I2 =:= O).

gate(nand,[I1,I2],O):-sat(I1*I2 =\= O).

gate(not,[I1],O):- sat(I1 =\= O).

Documents

1 Restrições Booleanas O domínio dos Booleanos (ou variáveis 0/1) tem especial aplicação em aplicações –Envolvendo circuitos digitais Exemplo: Circuito