Mathematics-Online course: Prepcourse Mathematics-Basics-Propositional Logic-Laws for Logical Operations

	[home] [lexicon] [problems] [tests] [courses] [auxiliaries] [notes] [staff]
	Mathematics-Online course: Prepcourse Mathematics - Basics - Propositional Logic
	Laws for Logical Operations

[previous page] [next page]

[table of contents][page 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)

De Morgan's Laws as well as distributive laws can be proved by setting up truth tables, that is investigating all possible truth values of statements.

The following table is such an example of a truth table that proves the first of De Morgan's Laws.

		$A\land B$	$\lnot A$	$\lnot B$	$\lnot(A\land B)$ , $(\lnot A)\lor(\lnot B)$
t	t	t	f	f	f
t	f	f	f	t	t
f	t	f	t	f	t
f	f	f	t	t	t

Equivalent descriptions of implication, equivalence and antivalence follow directly from their definitions.

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

For illustration purposes let's apply some of the above laws to the statement

$\displaystyle \underbrace{\vert x-1\vert>1}_{A} \Longrightarrow \underbrace{(x<0)\lor(x>1)}_{B}$

According to de Morgan's Laws

$\displaystyle \lnot B = \lnot(x<0) \land \lnot(x>1) = (x\ge0)\land(x\le 1) \,.$

Consequently, the implication $A\Rightarrow B$ is equivalent to

$\displaystyle \vert x-1\vert\le1 \Longleftarrow 0\le x\le 1 \,.$

The same result is obtained by replacing the implication with

$\displaystyle (\lnot A)\lor B = \vert x-1\vert\le 1 \lor \lnot(0\le x\le 1)$

(by definition).

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

This content is only available in German at the moment.

[previous page] [next page]

[table of contents][page overview]

automatically generated 10/23/2009

$\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)$