Discret Math Unit 4-6

DISCRETE MATHEMATICS
Erick Infante Covarrubias
4. Boolean Algebra.
Boolean algebra is a deductive mathematical system based on values of zero and
one (false and true). For any algebraic system there are a number of initial postulates, and
additional rules, theorems and other properties of the system.
Theorems and postulates.

Closed. Is considered closed with respect to a binary operator if for each pair of Boolean
values produces a single Boolean result.
Commutative. We say that a binary operator "" is commutative if A B = B A for all
possible values of A and B.
Associative. They say what a binary operator "" is associative if (A B) C = A (B C) for
all boolean values A, B, and C.
Distributive. Two binary operators "" and "%" are distributive if A (B% C) = (A B)% (A
C) for all boolean values A, B, and C.
Identity. A boolean value I is said to be an identity element with respect to a binary
operator "" if A I = A.
Inverse. A boolean value I is an inverse element with respect to a Boolean "" if A I = B,
and B is different from A, ie, B is the opposite value of A.
Postulates:
1- Boolean algebra is closed under the operations AND, OR and NOT.
2- The element of identity of A is one and about + is zero. Their identity element for the
NOT operator
3- The operators * and + are commutative.
4- The operators * and + are distributive with respect to one another, that is, A * (B + C) =
(A * B) + (A * C) and A + (B * C) = (A + B) * (A + C).
5- For each value A there is a value such A that A * A = 0 and A + A = 1. This value is the
logical complement of A.
6- The operators * and + are both associative, it is (AB) C = A (BC) and (A + B) + C = A + (B +
C).
Optimization of Boolean expressions.

For reduce one Boolean expression you can use the Karnaugh maps, this can reduce the
original expression to one more simple and with less logic gates.
For reduce one expression the first thing that you have to do is put the mini terms in the
Karnaugh map. Next you have to make groups of who are adjacent, each group is adjacent
(horizontally or vertically) in powers of 2 (2, 4, 8 etc). After that, you have to make the
expression of each group. Finally make the reduce Boolean expression with the
expressions of each groups using the AND gate.
Logic gates.
Mini and Max terms.
Minterm is each of the possible combinations between all the variables available, for
example with 2 variables you get 4 minterms; 3 you get 8; 4, 16 etc., as you will notice you
can find the number of minterms by 2 ^ n where n is the number of variables available.
Numeration of a minterm. Each minterm is numbered according to the combination of the
variables and their equivalent binary/decimal.
A maxterm is a logical expression of n variables consisting only logical disjunction and
negation operator or supplement. The maxterms are an actual dual expression of
minterms. Operations OR instead of using AND, operations proceed used similarly.
The complement of a minterm is their respective maxterm.
Representation of Boolean expressions with logic circuits

When you have a Boolean
expression and you want to make a
logic circuit, you have to use the
correct symbology to represent
them:
5. RELATIONS.
Basic concepts.
A relation is an association between elements or objects.
Cartesian product.- Unlike the number in an ordered pair, matter the order of the
elements. If we consider the sets A and B and form pairs or ordered pairs with elements of
A as first elements and B as second, a set called Cartesian product.
Binary relation.- Let A be a set any one; said R is a binary relation on A if R A A, that is,
if R is a subset of the Cartesian product of AxA.
Property of the relations (reflexive, unreflective, symmetric, asymmetric,

antisymmetric, transitive)
Reflective: If any element in A is related to himself.
Unreflective: If no element in A is related to himself.
Symmetrical: If when an element is linked to a second element, the second is also related
to the first.
Antisymmetric: If when an element is related to a different second element, the second is
not related to the first.
Transitive: If when an item is related to a second element and the second is related to a
third party, then the first is related to the third.
6. GRAPHS THEORY.
Elements and characteristics of graphics
One graphic G=(N,A) is a group of points N and aristas(A), in when each line is a
pair not ordered of points. One line is represented by {a,b} . Another way of
represent graphics is with circles for the points, connected by lines for the aristas.
Example 1:
The Graphics G with points N y lines S

And it writes: G(N,S) where:
N = {n1, n2, n3, n4, n5, n6, n7, n8}
A = {{n1, n2}, {n1, n5}, {n3, n4}, {n4, n7}, {n2, n6}, {n6, n2}}
The terminology will handle regularly to the use of graphs is as follows:
Path. It is a random sequence of points and lines in the next order

V1,S1,V2,S2,V3,S3,V4. Sequence of points V1,V2,V3,V4 or sequence of
lines S1,S2,S3
Length of Path. Is the number of segment in this path.
Trail. Its a path in all the segments are different.
Trajectory. Is the path in all the points are different.
Simple Path. Is when all the points, except the first and the last, are
different.
Simple cycle. Is a simple path whit length at least of 1, who start and finish
in the same point.
Types of Graphs
A directed graph is a graph with an address assigned to each segment.
We call arcs to targeted segments and are written as an ordered set of vertices (v,
w) where V is the initial vertex and W is the terminal vertex of the arc.
Connectivity graph. A graph G is connected if and only if there is a simple way in
any two nodes of G.
Complete graphs. A graph is complete if every node is connected to another node.
When complete graph of n nodes will be denoted Kn.
Regular graph. The one with the same degree in all vertices. If this degree is k will
call k-regulate.
Bipartite graph. A graph is one whose vertices can be formed with two disjoint sets
so that no adjacencies between vertices belonging to the same group.
Representation of graphs
Matrix adjacencies. The adjacency matrix is a square matrix that is used as a way
to represent binary relations.
Matrix construction from a graph
It creates zero matrix whose columns and rows represent the nodes of the graph.
For each edge joining two nodes, adds 1 to the value currently in the
corresponding location in the array.
If such ridge is a loop and undirected graph is then added 2 instead of 1.
Finally, a matrix representing the number of edges (relationships) between each
pair of nodes (elements) is obtained.
Matrix Incidents. The incidence matrix is a binary matrix (elements may be only 1
or 0) which is used as a way of representing binary relations.
Binary relation described by an incidence matrix, and by a graph
1. The columns of the matrix represent the edges of the graph.
2. The rows represent the different nodes.
3. For each node connected by an edge, put a one (1) into place, and fill the rest of
the locations with zeros (0).
Trees
Graph Tree. A tree is defined as a type of graph

that contains no cycles. This is the case of the
following graph where one can see that none
contains repetitions (cycles).
A tree graph fulfills with:

a) Each pair of nodes is connected by one exactly trajectory
b) Is connected, but if any of its segments is removed the resulting graph is
disconnected
c) It is free of cycles, but if you add to the graph any segment the resulting graph
has exactly one cycle.
d) It is free of cycles and has n-1 segments
e) Is connected and has n-1 segments.
f) A non trivial finite tree has at least two suspension nodes (nodes of degree 1)
g) In a non trivial tree, each node is pendant or a cutoff.
Routes of a tree:
By visiting the nodes of a tree there are some useful ways that can systematically
order the nodes of a tree. The most important systems are called: preorder, postorder and in-order and are recursively defined as follows:
Route PRE-ORDER:
Visit the root
Traveling the left subtree in pre-order
Traveling the right subtree in pre-order
Route IN-ORDER:
Traveling the left subtree in -order
Visit the root
Traveling the right subtree in -order
Route POST-ORDER:
Traveling the left subtree in post-order
Traveling the right subtree in post-order
Visit the root

Discret Math Unit 4-6

Uploaded by

Copyright:

Available Formats

Discret Math Unit 4-6

Uploaded by

Document Information

Original Description:

Copyright

Available Formats

Share this document

Share or Embed Document

Sharing Options

Did you find this document useful?

Is this content inappropriate?

Copyright:

Available Formats

Discret Math Unit 4-6

Uploaded by

Copyright:

Available Formats

DISCRETE MATHEMATICS

Erick Infante Covarrubias

Theorems and postulates.

Optimization of Boolean expressions.

Representation of Boolean expressions with logic circuits

Property of the relations (reflexive, unreflective, symmetric, asymmetric,

The Graphics G with points N y lines S

The terminology will handle regularly to the use of graphs is as follows:

Path. It is a random sequence of points and lines in the next order

Length of Path. Is the number of segment in this path.

Trail. Its a path in all the segments are different.

Trajectory. Is the path in all the points are different.

Graph Tree. A tree is defined as a type of graph

A tree graph fulfills with:

You might also like