Boolean Algebra

ShareIn this tutorial we will cover Equivalence Laws.

Two statements are said to be equivalent if they have the same truth value.

Example

Following are two statements.

p = It is false that he is a singer or he is a dancer.

q = He is not a singer and he is not a dancer.

The first statement p consists of negation of two simple proposition

a = He is a singer.

b = He is a dancer.

They are connected by an OR operator (connective)

so we can write,

p = ~(a ∨ b)

The second statement q consists of two simple proposition

which are negation of a and b

~a = He is not a singer.

~b = He is not a dancer.

They are connected by an AND operator (connective)

so we can write,

q = ~a ∧ ~b

We have,

p = ~(a ∨ b)

q = ~a ∧ ~b

following are the truth tables for p and q

We can see that the truth values are same for both the statements. So, p and q are equivalent statements.

Now we will cover some equivalence laws.

If x is a statement then,

0 + x = x

0 . x = 0

where + is the OR operator and

. is the AND operator

Truth table

If x is a statement then,

1 + x = 1

1 . x = x

where + is the OR operator and

. is the AND operator

Truth table

If p is a statement then,

~(~p) = p

where ~ is the NOT operator

Truth table

If p is a statement then,

p + p = p

p . p = p

where + is the OR operator and

. is the AND operator

Truth table

If p and q are two statements then,

p + (p.q) = p

p . (p + q) = p

where + is the OR operator and

. is the AND operator

Truth table

If p is a statement then,

p + (~p) = 1

p . (~p) = 0

where + is the OR operator,

. is the AND operator and

~ is the NOT operator

Truth table

If p and q are two statements then,

p + q = q + p

p . q = q . p

where + is the OR operator and

. is the AND operator

If p, q and r are three statements then,

(p + q) + r = p + (q + r)

(p . q) . r = p . (q . r)

where + is the OR operator and

. is the AND operator

If p, q and r are three statements then,

p . (q + r) = (p . q) + (p . r)

p + (q . r) = (p + q) . (p + r)

p + (~p . q) = p + q

where + is the OR operator,

. is the AND operator and

~ is the NOT operator

If p and q are two statements then,

~(p + q) = ~p . ~q

~(p . q) = ~p + ~q

where + is the OR operator,

. is the AND operator and

~ is the NOT operator

Truth table

If p and q are two statements then,

p ⇒ q = ~p + q

where + is the OR operator and

~ is the NOT operator

If p and q are two statements then,

p ⇔ q = (p . q) + (~p . ~q)

where + is the OR operator,

. is the AND operator and

~ is the NOT operator

- Maximum subarray problem - Kadane's Algorithm Programming
- Maximum subarray problem Programming
- Find median of an array Programming
- Find the minimum and maximum number in an array using Tournament Method Programming
- Find the minimum and maximum number in an array Programming
- Reverse a string Programming
- Design Patterns - Strategy Pattern Design Patterns
- PostgreSQL - SELECT FROM Table PostgreSQL
- PostgreSQL - INSERT INTO Table PostgreSQL
- PostgreSQL - CREATE Table PostgreSQL