Classical Propositional Logic: Basic Expression Types

Basic Expression Types

Given a logical expression which contains zero, one or two logical variables, the client application may want to know from the software interface what is the type of the expression.

The task here is to identify all possible types of expressions.

The following table lists all the truth functions (F₁ to F₁₆) that can be applied to two logical variables a and b:

a				0	0	1	1
b				0	1	0	1


F₁ ( )	Contradiction	$0$	$\lnot 1$	0	0	0	0
F₂ (a, b)	Conjunction	$a \land b$		0	0	0	1
F₃ (a, b)	Negated Conditional	$a \land \lnot b$	$\lnot (a \to b)$	0	0	1	0
F₄ (a)	Identity	$a$		0	0	1	1
F₅ (a, b)	Negated Conditional	$\lnot a \land b$	$\lnot (b \to a)$	0	1	0	0
F₆ (b)	Identity	$b$		0	1	0	1
F₇ (a, b)	Exclusive Disjunction	$a \nleftrightarrow b$	$\lnot (a \leftrightarrow b)$	0	1	1	0
F₈ (a, b)	Disjunction	$a \lor b$		0	1	1	1
F₉ (a, b)	Negated Disjunction	$\lnot a \land \lnot b$	$\lnot (a \lor b)$	1	0	0	0
F₁₀ (a, b)	Biconditional	$a \leftrightarrow b$		1	0	0	1
F₁₁ (b)	Negation	$\lnot b$		1	0	1	0
F₁₂ (a, b)	Conditional	$a \lor \lnot b$	$b \to a$	1	0	1	1
F₁₃ (a)	Negation	$\lnot a$		1	1	0	0
F₁₄ (a, b)	Conditional	$\lnot a \lor b$	$a \to b$	1	1	0	1
F₁₅ (a, b)	Negated Conjunction	$\lnot a \lor \lnot b$	$\lnot (a \land b)$	1	1	1	0
F₁₆ ( )	Tautology	$1$		1	1	1	1

Each truth function can be viewed as the specification of a logical connective; the name of the connective can be used to refer to the type of the logical expression that it constructs.

The first column in the table shows which of the two logical variables the truth functions effectively depend on. Not all truth functions represent binary connectives. Truth functions F₄, F₆, F₁₁ and F₁₃ can be collapsed to represent unary connectives and truth functions F₁ and F₁₆ can be collapsed to represent connectives of zero arity, i.e. logical constants.

The second column in the table shows which terms will be used to refer to the types of logical expressions. A total of 12 terms have been identified:

Tautology	Contradiction
Identity	Negation
Conjunction	Negated Conjunction
Disjunction	Negated Disjunction
Conditional	Negated Conditional
Biconditional	Exclusive Disjunction

The terms Tautology, Contradiction, Negation, Conjunction, Disjunction, Conditional, Biconditional and Exclusive Disjunction are fairly conventional in classical propositional logic.

I don't believe that there are any conventional terms in classical propositional logic for the remaining connectives, hence the terms Identity, Negated Conjunction, Negated Disjunction and Negated Conditional are of my choice. Note that the Negated Conjunction is equivalent to the operation performed by the logic gate NAND and the Negated Disjunction is equivalent to the operation performed by the logic gate NOR.

Note the duality among the twelve logical operators. For instance the truth function of the biconditional and the truth function of the exclusive disjunction return truth values that are opposite to each other. The 12 logical operators can be seen as 6 couples of dual logical operators.

The Conditional expression of variables a and b corresponds to two truth functions $F_{12} : b \to a$ and $F_{14} : a \to b$ . This is usually referred to as the conditional operator being non commutative. In propositional logic the variable to the left of the operator is referred to as the Antecedent and the variable to the right of the operator is referred to as the Consequent.

As far as the software interface is concerned, once the client application establishes that a given expression is a conditional, it may need to further query which variable is the antecedent or which variable is the consequent, to resolve the ambiguity.

The same considerations apply to the Negated Conditional.

page_revision: 1, last_edited: 1186874852|%e %b %Y, %H:%M %Z (%O ago)

Edit Rate (0)Tags History Files Print Site tools + Options

Classical Propositional Logic

Expression Representation and Manipulation in C++