Uma proposição é uma frase declarativa, que pode ser julgada como verdadeira — V — ou falsa — F —, mas não como V e F simultaneamente. É usual representar uma proposição pelas letras maiúsculas do alfabeto: P, Q, R etc. A construção de proposições compostas é feita usando-se os denominados símbolos lógicos e proposições previamente construídas. Parênteses, chaves e colchetes são usados para evitar ambiguidades. Uma proposição da forma P !$ \wedge !$Q, lida como “P e Q”, tem valor lógico V, se P e Q forem V e, nos demais casos, é F; uma proposição da forma P !$ \vee !$Q, lida como “P ou Q”, tem valor lógico F, se P e Q forem F e, nos demais casos, é V; uma proposição da forma P →Q, lida como “se P, então Q”, tem valor lógico F, se P for V e Q for F e, nos demais casos, é V; uma proposição da forma ¬P, lida como “não P”, é a negação de P e tem valor F quando P for V, e valor V quando P for F. Uma proposição é simples quando não existir nenhuma outra proposição que faz parte dela.

Considere todas as possíveis valorações V ou F atribuídas às proposições simples P, Q e R. Nesse caso, a proposição composta ¬[(P →R) !$ \wedge !$(Q →R)] tem exatamente os mesmos valores lógicos da proposição