Come si esprime che esattamente una delle 2 variabili è vera:
(x1⇒¬x2)∧(¬x1⇒x2)
Come si esprime che al massimo una delle 2 variabili è vera:
(x1⇒¬x2)
Come si esprime che esattamente una delle 3 variabili è vera:
(x1->(¬x2∧¬x3))∧(¬x1⇒(x2⇒¬x3)∧(¬x2⇒x3))
Come si esprime che al massimo una delle 3 variabili è vera:
(x1->(¬x2∧¬x3))∧(¬x1⇒(x2⇒¬x3))
Come si esprime che esattamente una delle 4 variabili è vera:
(x1->(¬x2∧¬x3∧¬x4))∧(¬x1⇒(x2->(¬x3∧¬x4))∧(¬x2⇒(x3⇒¬x4)∧(¬x3⇒x4)))
Come si esprime che al massimo una delle 4 variabili è vera:
(x1->(¬x2∧¬x3∧¬x4))∧(¬x1⇒(x2->(¬x3∧¬x4))∧(¬x2⇒(x3⇒¬x4)))
Come si esprime che esattamente una delle n variabili è vera:
(x1->(¬x2∧..∧¬xn))∧(¬x1⇒...))
Come si esprime che al massimo una delle n variabili è vera:
(x1->(¬x2∧..∧¬xn))∧(¬x1⇒...))
Ex: N=3
((x0⇒(¬x1∧¬x2))∧(¬x0⇒((x1⇒¬x2)∧(¬x1⇒x2)))) ∧
((x3⇒(¬x4∧¬x5))∧(¬x3⇒((x4⇒¬x5)∧(¬x4⇒x5)))) ∧
((x6⇒(¬x7∧¬x8))∧(¬x6⇒((x7⇒¬x8)∧(¬x7⇒x8)))) ∧
Esattamente una regina per colonna:
((x0⇒(¬x3∧¬x6))∧(¬x0⇒((x3⇒¬x6)∧(¬x3⇒x6)))) ∧
((x1⇒(¬x4∧¬x7))∧(¬x1⇒((x4⇒¬x7)∧(¬x4⇒x7)))) ∧
((x2⇒(¬x5∧¬x8))∧(¬x2⇒((x5⇒¬x8)∧(¬x5⇒x8)))) ∧
Al massimo una regina per diagonale:
((x0⇒(¬x4∧¬x8))∧(¬x0⇒(x4⇒¬x8))) ∧
(x1⇒¬x5) ∧
(x3⇒¬x7) ∧
((x2⇒(¬x4∧¬x6))∧(¬x2⇒(x4⇒¬x6))) ∧
(x1⇒¬x3) ∧
(x5⇒¬x7)
La formula risultante non è soddisfacibile: il problema non ha soluzione (non si può mettere 3 regine in una scacchiera 3x3).