Summary

SUMMARY

(1) A binary operation * on a non-empty set S is a rule, which associates to each ordered pair ( a , b) of elements a , b in S an unique element a *b in S .

(2) Commutative property: Any binary operation * defined on a nonempty set S is said to satisfy the commutative property, if a ∗ b = b ∗ a, ∀a , b ∈ S .

(3) Associative property: Any binary operation * defined on a nonempty set S is said to satisfy the associative property, if a ∗ (b ∗c ) = ( a ∗b ) ∗ c , ∀a , b, c ∈ S .

(4) Existence of identity property: An element e ∈ S is said to be the Identity Element of S under the binary operation * if for all a ∈ S we have that a ∗ e = a and e ∗ a = a .

(5) Existence of inverse property: If an identity element e exists and if for every a ∈ S , there exists b in S such that a ∗ b = e and b ∗ a = e then b ∈ S said to be the Inverse Element of a . In such instance, we write b = a⁻¹ .

(6) Uniqueness of Identity: In an algebraic structure the identity element (if exists) must be unique.

(7) Uniqueness of Inverse: In an algebraic structure the inverse of an element (if exists) must be unique.

(8) A Boolean Matrix is a real matrix whose entries are either 0 or 1.

(9) Modular arithmetic: Let n be a positive integer greater than 1 called the modulus. We say that two integers a and b are congruent modulo n if b − a is divisible by n. In other words a ≡ b (mod n) means a − b = n ⋅ k for some integer k and b is the least non-negative integer reminder when a is divided by n. ( 0 ≤ b ≤ n −1)

(10) Mathematical logic is a study of reasoning through mathematical symbols.

(11) Let p be a simple statement. Then the negation of p is a statement whose truth value is opposite to that of p . It is denoted by ¬ p, read as not p .The truth value of ¬p is T , if p is F, otherwise it is F .

(12) Let p and q be any two simple statements. The conjunction of p and q is obtained by connecting p and q by the word and. It is denoted by p ∧ q , read as ‘ p conjunction q ’ or ‘ p hat q ’. The truth value of p ∧ q is T , whenever both p and q are T and it is F otherwise.

(13) The disjunction of any two simple statements p and q is the compound statement obtained by connecting p and q by the word ‘or’. It is denoted by p ∨ q , read as‘ p disjunction q ’ or ‘ p cup q ’.The truth value of p ∨ q is F , whenever both p and q are F and it is T otherwise.

(14) The conditional statement of any two statements p and q is the statement, ‘If p , then q ’ and it is denoted by p → q . The statement p → q has a truth value F when q has the truth value F and p has the truth value T; otherwise it has the truth value T.

(15) The bi-conditional statement of any two statements p and q is the statement ‘ p if and only if q ’ and is denoted by p ↔ q The statement p ↔ q has the truth value T whenever both p and q have identical truth values; otherwise has the truth value F.

(16) A statement is said to be a tautology if its truth value is always T irrespective of the truth values of its component statements. It is denoted by T.

(17) A statement is said to be a contradiction if its truth value is always F irrespective of the truth values of its component statements. It is denoted by F.

(18) A statement which is neither a tautology nor a contradiction is called contingency.

(19) Any two compound statements A and B are said to be logically equivalent or simply equivalent if the columns corresponding to A and B in the truth table have identical truth values. The logical equivalence of the statements A and B is denoted by A ≡ B or A ⇔ B . Further note that if A and B are logically equivalent, then A ↔ B must be a tautology.

(20) Some laws of equivalence:

Idempotent Laws: (i) p ∨ p ≡ p (ii) p ∧ p ≡ p .

Commutative Laws: (i) p ∨ q ≡ q ∨ p (ii) p ∧ q ≡ q ∧ p .

Associative Laws: (i) p ∨ ( q ∨ r ) ≡ ( p ∨ q ) ∨ r (ii) p ∧ ( q ∧ r ) ≡ ( p ∧ q ) ∧ r .

Distributive Laws: (i) p ∨ ( q ∧ r) ≡ ( p ∨ q) ∧ ( p ∨ r)

 (ii) p ∧ ( q ∨ r) ≡ ( p ∧ q) ∨ ( p ∧ r)

Identity Laws: (i) p ∨ T ≡ T  and p ∨  ≡ p

(ii) p ∧ T ≡ p and p ∧ F ≡ F

Complement Laws : (i) p ∨ ¬p ≡ T and p ∧ ¬ p ≡ F

(ii) ¬ T ≡ F and ¬ F ≡ T

Involution Law or Double Negation Law: ¬(¬p) p

de Morgan’s Laws: (i) ¬( p ∧ q) ≡ ¬p ∨ ¬q (ii) ¬( p ∨ q) ≡ ¬p ∨ ¬q

Absorption Laws: (i) p ∨ ( p ∧ q) ≡ p (ii) p ∧ ( p ∨ q) ≡ p