Mathematics-Online lexicon: Relations between logical operations

	[home] [lexicon] [problems] [tests] [courses] [auxiliaries] [notes] [staff]
	Mathematics-Online lexicon:
	Relations between logical operations

A B C D E F G H I J K L M N O P Q R S T U V W X Y Z

overview

The following rules apply to logical operations:

Associative Laws:

$\displaystyle (A\land B)\land C$ $\displaystyle =$ $\displaystyle A \land (B \land C)$

$\displaystyle (A\lor B)\lor C$ $\displaystyle =$ $\displaystyle A \lor (B \lor C)$
Commutative Laws:

$\displaystyle A\land B$ $\displaystyle =$ $\displaystyle B \land A$

$\displaystyle A\lor B$ $\displaystyle =$ $\displaystyle B \lor A$
De Morgan's Laws:

$\displaystyle \lnot(A\land B)$ $\displaystyle =$ $\displaystyle (\lnot A) \lor (\lnot B)$

$\displaystyle \lnot(A\lor B)$ $\displaystyle =$ $\displaystyle (\lnot A) \land (\lnot B)$
Distributive Laws:

$\displaystyle (A\land B)\lor C$ $\displaystyle =$ $\displaystyle (A\lor C) \land (B\lor C)$

$\displaystyle (A\lor B)\land C$ $\displaystyle =$ $\displaystyle (A\land C) \lor (B\land C)$
Further:

$\displaystyle \lnot(\lnot A)$ $\displaystyle =$ $\displaystyle A$

$\displaystyle A\land A$ $\displaystyle =$ $\displaystyle A$

$\displaystyle A\lor A$ $\displaystyle =$ $\displaystyle A$
Alternative representations:

$\displaystyle \textrm{Implication:}\quad$ $\displaystyle A \Rightarrow B$ $\displaystyle \quad =\quad \lnot A \lor B \quad =\quad \lnot A \Leftarrow \lnot B$

$\displaystyle \textrm{Equivalence:}\quad$ $\displaystyle A \Leftrightarrow B$ $\displaystyle \quad =\quad (A \land B) \lor (\lnot A \land \lnot B)$

$\displaystyle \textrm{Antivalence:}\quad$ $\displaystyle A \not\equiv B$ $\displaystyle \quad =\quad (A \land \lnot B) \lor (\lnot A \land B)$

These alternative representations are often used in proofs.

A logical formula, the truth value of which is independent from the truth values of the statements involved, is called a tautology if it is always true, or a contradiction if it is always false. Such a formula may be replaced by t (also symbolized by ) or f (also symbolized by 0) respectively. In particular the following identities hold:

$\displaystyle A \lor \lnot A = \mathrm{w}$	$\displaystyle \textrm{and}$	$\displaystyle A\land \lnot A = \mathrm{f}\,,$
$\displaystyle A \lor \mathrm{w} = \mathrm{w}$	$\displaystyle \textrm{and}$	$\displaystyle A\land \mathrm{w} = A\,,$
$\displaystyle A \lor \mathrm{f} = A$	$\displaystyle \textrm{and}$	$\displaystyle A\land \mathrm{f} = \mathrm{f}\,.$

(Authors: Höllig/Hörner/Abele)

Annotation:

Proof of laws

[Examples] [Links]

automatically generated 6/19/2007

$\displaystyle (A\land B)\land C$	$\displaystyle =$	$\displaystyle A \land (B \land C)$
$\displaystyle (A\lor B)\lor C$	$\displaystyle =$	$\displaystyle A \lor (B \lor C)$

$\displaystyle A\land B$	$\displaystyle =$	$\displaystyle B \land A$
$\displaystyle A\lor B$	$\displaystyle =$	$\displaystyle B \lor A$

$\displaystyle \lnot(A\land B)$	$\displaystyle =$	$\displaystyle (\lnot A) \lor (\lnot B)$
$\displaystyle \lnot(A\lor B)$	$\displaystyle =$	$\displaystyle (\lnot A) \land (\lnot B)$

$\displaystyle (A\land B)\lor C$	$\displaystyle =$	$\displaystyle (A\lor C) \land (B\lor C)$
$\displaystyle (A\lor B)\land C$	$\displaystyle =$	$\displaystyle (A\land C) \lor (B\land C)$

$\displaystyle \lnot(\lnot A)$	$\displaystyle =$	$\displaystyle A$
$\displaystyle A\land A$	$\displaystyle =$	$\displaystyle A$
$\displaystyle A\lor A$	$\displaystyle =$	$\displaystyle A$

$\displaystyle \textrm{Implication:}\quad$	$\displaystyle A \Rightarrow B$	$\displaystyle \quad =\quad \lnot A \lor B \quad =\quad \lnot A \Leftarrow \lnot B$
$\displaystyle \textrm{Equivalence:}\quad$	$\displaystyle A \Leftrightarrow B$	$\displaystyle \quad =\quad (A \land B) \lor (\lnot A \land \lnot B)$
$\displaystyle \textrm{Antivalence:}\quad$	$\displaystyle A \not\equiv B$	$\displaystyle \quad =\quad (A \land \lnot B) \lor (\lnot A \land B)$