# Basic Terms

Again Basic Terms of TOC is the important topic of the Subject Theory Of Computation.

**Set:** Set defined as a collection of objects. These objects called elements of the set. All the elements enclosed in a curly brackets ‘{’ and ‘}’ and every element separated by commas.

**Subset:** The set A called a subset of set B if every element of set A present in set B but the reverse not true.

**Complement:** A complement of a set A the set A’ of everything that is not an element of A. This makes sense only in the context of some “Universal Set” U containing all the elements. For Ex :- A’ = { x U | x A }

**Set Difference**: Considering two sets A and B. The difference A – B the set of everything in A but not in B. For Eg. :- A – B = { x | x A and x B }

**Symmetric Difference**: For the two set A and B the symmetric difference can give as the A For Ex:- A B = (A – B) (B – A)

**Proposition:** A preposition is a declarative statement that is sufficiently objective, meaningful and precise to have a truth value. For Ex:- Fourteen is an even integer.

**Conjunction:** The conjunction p of p and q is read as “p and q”. It denoted by.** Basic Terms: Truth table of Conjunction**

**Disjunction:** The disjunction p q of p and q is read as “p or q”. It denoted by.

** Basic Terms: Truth table of Disjunction **

**Negation:** The negation p of p is read as the “not p”. It is denoted by** ¬ Basic Terms: Truth table of Negation **

**Conditional:** The proposition p q is commonly read as “if p then q”. **Truth table of conditional **

**Tautology:** If all the entries of the truth table for any compound proposition are true then the proposition is termed as the tautology.

**Onto function / subjective / surjection:** For the function *f* : A B, if *f*(A) = B (the range and codomain of *f* equal and every element of the codomain actually one of the values of the functions), the function *f * said to be a onto function.

**One to one function / injective / injunction: **For the function *f *: A B, we say *f *is one-to-one if no single element y of B can be *f*(x) for more than one x in A.

**Bijection function:** For the function *f*: A B, f is bijection if f is one-to-one as well onto function.

**Composite function:** Suppose we have function *f* : A → B and *g *: B → the function h : A → C defined by *h*(x) = g (f(x)) called the composite of g and f.

**Inverse function:** For *f*: A → B, then for any y B there is at least one x A with *f(x)* = y and *f *is onto function and for any y B there is at most one x A with *f*(x) = y where *f *is one-to-one.Therefore for any y B, it makes sense to speak of the element x A for which *f*(x = y) We denote it x by *f *^{-1} (y). For Eg.:- *f* : A → B *f ^{ -1}* : B → A

**Relation:** A relation R on a set A is a subset of A × A.

**Equivalence relation:** Assume that R a relation on a set A; in other words, R⊆ A × A Then

- R is
__reflexive__if for every a ∈ A, aRa. - Also, R is
__symmetric__if for every a and b in A if aRb then bRa - R is
__transitive__if for every a, b and c in A if aRb and bRc then aRc. R is__equivalence__on A if R is reflective, symmetric and transitive

**Related Terms**

## Leave a Reply