Uma proposição é uma frase que pode ser avaliada como verdadeira (V) ou falsa (F). A frase O Estado do Acre fica na região Norte do Brasil, por exemplo, é uma proposição V, mas a frase Qual é a cor do mar? não é uma proposição, porque não pode ser avaliada nem como V nem como F. Na lógica das proposições — a lógica proposicional —, as proposições básicas são representadas por letras maiúsculas do alfabeto, tais como A, B, C etc. Os símbolos lógicos ¬, v, w e 6 são usados, respectivamente, para negar uma proposição, para realizar uma conjunção de proposições (e), para realizar uma disjunção de proposições (ou) e para realizar uma implicação entre proposições, gerando proposições compostas. Desse modo, ¬A (lê-se: não A) é F se A for V e é V se A for F; A v B (lê-se A e B) é V se A e B forem V, caso contrário, é F; A w B (lê-se: A ou B) é F se ambas as proposições, A e B, forem F, caso contrário, é V; e, finalmente, A 6B (lê-se: se A então B) é F se A for V e B for F, caso contrário, é V.

Diz-se que duas proposições compostas são equivalentes quando têm, para todas as valorações possíveis de suas proposições básicas, as mesmas avaliações V ou F.