is a collection of objects called elements of the set. Why not use the word ``collection'' and eliminate the word ``set'', thereby having fewer words to worry about? ``Collection'' is a common word whose generic meaning is understood by most people. The use of the word ``set'' means that there is also a method to determine whether or not a particular object belongs in the set. We then say that the set is well-defined. For example, it is easy to decide that the number 8 is not in the set consisting of the integers 1 through 5. After all, there are only five objects to consider and it is clear that 8 is not one of them by simply checking all five.
A basic problem here is now to indicate sets on paper and verbally. As seen above, a set could be described with a phrase such as ``the integers 1 through 5'' and the speaker hopes that it is understood. Symbollically, we use two common methods to write sets. The roster notation is a complete or implied listing of all the elements of the set. So A= {a,b,c,d} and B= {2,4,6,8,....,40} are examples of roster notation defining sets with 4 and 20 elements respectively. Sequences and Tuples
A sequence is an ordered list of objects (or events). Like a set, it contains members(also called elements or terms), and the number of terms (possibly infinite) is called the length of the sequence. Unlike a set, order matters, and exactly the same elements can appear multiple times at different positions in the sequence. A sequence is a discretefunction.
For example, (C, R, Y) is a sequence of letters that differs from (Y, C, R), as the ordering matters. Sequences can be finite, as in this example, or infinite, such as the sequence of all even positive integers (2, 4, 6,...). Finite sequences are sometimes known as strings or words and infinite sequences as streams. The empty sequence ( ) is included in most notions of sequence, but may be excluded depending on the context.
There are various and quite different notions of sequences in mathematics, some of which (e.g., exact sequence) are not covered by the notations introduced below.
In addition to identifying the elements of a sequence by their position, such as "the 3rd element", elements may be given names for convenient referencing. For example a sequence might be written as (a1, a2, a2, … ), or (b0, b1, b2, … ), or (c0, c2, c4, … ), depending on what is useful in the application.
A sequence is an ordered list of objects (or events). Like a set, it contains members(also called elements or terms), and the number of terms (possibly infinite) is called the length of the sequence. Unlike a set, order matters, and exactly the same elements can appear multiple times at different positions in the sequence. A sequence is a discretefunction.
For example, (C, R, Y) is a sequence of letters that differs from (Y, C, R), as the ordering matters. Sequences can be finite, as in this example, or infinite, such as the sequence of all even positive integers (2, 4, 6,...). Finite sequences are sometimes known as strings or words and infinite sequences as streams. The empty sequence ( ) is included in most notions of sequence, but may be excluded depending on the context.
There are various and quite different notions of sequences in mathematics, some of which (e.g., exact sequence) are not covered by the notations introduced below.
In addition to identifying the elements of a sequence by their position, such as "the 3rd element", elements may be given names for convenient referencing. For example a sequence might be written as (a1, a2, a2, … ), or (b0, b1, b2, … ), or (c0, c2, c4, … ), depending on what is useful in the application.
A tuple is an ordered list of elements. In set theory, an (ordered) n-tuple is a sequence (or ordered list) of n elements, where n is a positive integer. There is also one 0-tuple, an empty sequence. An n-tuple is defined inductively using the construction of an ordered pair. Tuples are usually written by listing the elements within parentheses "( )" and separated by commas; for example, (2,7,4,1,7) denotes a 5-tuple. Sometimes other delimiters are used, such as square brackets "[ ]" or angle brackets "
". Braces "{}" are almost never used for tuples, as they are the standard notation for sets.
". Braces "{}" are almost never used for tuples, as they are the standard notation for sets. Tuples are often used to describe other mathematical objects. In algebra, for example, a ring is commonly defined as a 3-tuple 
, where E is some set, and " + ", and "
" are functions mapping the Cartesian product 
to E with specific properties. In computer science, tuples are directly implemented as product types in most functional programming languages. More commonly, they are implemented as record types, where the components are labeled instead of being identified by position alone. This approach is also used inrelational algebra.
, where E is some set, and " + ", and "" are functions mapping the Cartesian product to E with specific properties. In computer science, tuples are directly implemented as product types in most functional programming languages. More commonly, they are implemented as record types, where the components are labeled instead of being identified by position alone. This approach is also used inrelational algebra.Functions and Relations
A function is one kind of interrelationship among objects. For every finite sequence of objects (called the arguments), a function associates a unique object (called the value). More formally, a function is defined as a set of finite lists of objects, one for each combination of possible arguments. In each list, the initial elements are the arguments, and the final element is the value. For example, the 
function contains the list 
, indicating that integer successor of 
is 
.
A relation is another kind of interrelationship among objects in the universe of discourse. More formally, a relation is an arbitrary set of finite lists of objects (of possibly varying lengths). Each list is a selection of objects that jointly satisfy the relation. For example, the < relation on numbers contains the list , indicating that is less than .
, indicating that is less than . Note that both functions and relations are defined as sets of lists. In fact, every function is a relation. However, not every relation is a function. In a function, there cannot be two lists that disagree on only the last element. This would be tantamount to the function having two values for one combination of arguments. By contrast, in a relation, there can be any number of lists that agree on all but the last element. For example, the list is a member of the function, and there is no other list of length 2 with as its first argument, i.e. there is only one successor for . By contrast, the < relation contains the lists , 
, and so forth, indicating that is less than , 
, and so forth.
is a member of the function, and there is no other list of length 2 with as its first argument, i.e. there is only one successor for . By contrast, the < relation contains the lists , , and so forth, indicating that is less than , , and so forth.Graph
is an abstract representation of a set of objects where some pairs of the objects are connected by links. The interconnected objects are represented by mathematical abstractions called vertices, and the links that connect some pairs of vertices are called edges. Typically, a graph is depicted in diagrammatic form as a set of dots for the vertices, joined by lines or curves for the edges. Graphs are one of the objects of study indiscrete mathematics.
The edges may be directed (asymmetric) or undirected (symmetric). For example, if the vertices represent people at a party, and there is an edge between two people if they shake hands, then this is an undirected graph, because if person A shook hands with person B, then person B also shook hands with person A. On the other hand, if the vertices represent people at a party, and there is an edge from person A to person B when person A knows of person B, then this graph is directed, because knowing of someone is not necessarily asymmetric relation (that is, one person knowing of another person does not necessarily imply the reverse; for example, many fans may know of a celebrity, but the celebrity is unlikely to know of all their fans). This latter type of graph is called a directed graph and the edges are called directed edges or arcs; in contrast, a graph where the edges are not directed is called undirected.
Vertices are also called nodes or points, and edges are also called lines. Graphs are the basic subject studied by graph theory. The word "graph" was first used in this sense by James Joseph Sylvester in 1878.[1]
Strings and Languages
Strings
• A string is a finite sequence of symbols from an alphabet written in juxtaposition.
– thecatinthehat
– ablewasiereisawelba
– καoσ
– helloworld!
– 01001000100001
• The string containing no symbols is the empty string, denoted by .
• The set of all strings over alphabet Σ is denoted by Σ∗.
String Operations
• The length of a string is its length as a sequence.
– length of abracadabra is 11
– denoted by absolute values:|abracadabra| = 11
– | | = 0.
Languages
• Let Σ be an alphabet.
• A language over Σ is a set of strings.
• Examples
– Σ∗,
– ∅,
– the palindromes over {0, 1},
– the set of strings over {a, b} that start with a.
• closure If L is a language, then L∗ is the set of all strings formed by concatenating zero or more strings from L.
L∗= ∪∞i=0Li
• positive closure If L is a language, then L+ is the set of all strings formed by concatenating one or more strings from L.
L+ = ∪∞ i=1Li
Boolean logic
is the most commonly used logic system nowadays. This is due mostly to the prevalence of computers, which base all of their calculations on Boolean logic. Boolean logic is a binary logic system, meaning that it takes into account two possible states: 0 and 1. These can then be translated into other, more useful meanings. For example, 0 could represent the state "false" and 1 could be "true". Thus one could use Boolean logic to assess the validity of a statement. 0 and 1 can also represent on and off, yes and no, or basically any other pair of opposite states.
Boolean logic is really just a set of rules for the manipulation of given inputs. It consists of a set of "logic gates", each of which is a different set of rules. The three main logic gates are AND, OR, and NOT. AND and OR require two inputs, whereas NOT only requires one. Here is an explanation of each gate:
Sometimes, it is also written like this: Ç (ie. "p AND q" can also be written as "p Ç q")
When two inputs are entered into the AND gate, the output is always 0 unless both inputs are 1. Here is a truth table for the AND gate:
| p | q | p AND q |
| 1 | 1 | |
| 1 | 0 | |
| 0 | 1 | |
| 0 | 0 |
Sometimes, it is also written like this: È (ie. "p OR q" can also be written "p È q")
When two inputs are entered into the OR gate, the output is always 1 unless both inputs are 0. Here is a truth table for the OR gate:
| p | q | p OR q |
| 1 | 1 | |
| 1 | 0 | |
| 0 | 1 | |
| 0 | 0 |
Sometimes, it is also written like this: - (ie. "NOT p" can also be written as "-p")
When an input is entered into the NOT gate, the output is the opposite of that input. In other words, if the input is 1, the output is 0. And if the input is 0, the output is 1.
Since both the input and output for a gate are ones and zeros, the output from one gate can serve as the input for another. Two or more gates linked in this fashion are called a logic network. The truth table still functions the same way. For example, consider the network below.
Walang komento:
Mag-post ng isang Komento