Qui le variabili che possiamo manipolare assumono soltanto due valori: Vero o Falso. Sono variabili booleane. Così, se x è una di queste variabili, o x ha valore Vero (x = Vero), oppure x ha valore Falso (x = Falso). Per quanto elementari e limitati, questi valori consentono comunque di eseguire calcoli. A tale scopo definiamo alcune operazioni, un po’ come l’addizione o l’inverso per i numeri ordinari (non nulli).
Chi dice no, no, no… -----------------------
La prima operazione è la negazione: se x è una variabile che ha un certo valore booleano, allora ¬ x vale il «contrario» di x, nel senso che ¬Vero = Falso e ¬Falso = Vero. L’operatore ¬ si legge «Non» (quindi Non(Vero) = Falso, il che pare logico!).
Per definire la nostra seconda operazione, conviene semplificare un po’ il formalismo standard. Una 3-clausola è una terna formata da variabili o negazioni di variabili. Le variabili che compongono una 3-clausola devono essere distinte, ma l’ordine nella terna non ha alcuna importanza. Ecco alcuni esempi di 3-clausole con le variabili booleane x, y, z e t:
(x, y, t),