Discrete Math Flashcards
2 ∈ {1,2,3} asserts that 2 is an element of the set {1,2,3}.
In mathematics, an element, or member, of a set is any one of the distinct objects that make up that set.
Sets
Writing A = { 1 , 2 , 3 , 4 } {\displaystyle A={1,2,3,4}} means that the elements of the set A are the numbers 1, 2, 3 and 4. Sets of elements of A, for example { 1 , 2 } {\displaystyle {1,2}} , are subsets of A.
Sets can themselves be elements. For example, consider the set B = { 1 , 2 , { 3 , 4 } } {\displaystyle B={1,2,{3,4}}} . The elements of B are not 1, 2, 3, and 4. Rather, there are only three elements of B, namely the numbers 1 and 2, and the set { 3 , 4 } {\displaystyle {3,4}} .
The elements of a set can be anything. For example, C = { r e d , g r e e n , b l u e } {\displaystyle C={\mathrm {\color {red}red} ,\mathrm {\color {green}green} ,\mathrm {\color {blue}blue} }} , is the set whose elements are the colors red, green and blue.
Notation and terminology
First usage of the symbol ∈ in the work Arithmetices principia, nova methodo exposita by Giuseppe Peano.
The relation “is an element of”, also called set membership, is denoted by the symbol “ ∈ {\displaystyle \in } “. Writing
x ∈ A {\displaystyle x\in A}
means that “x is an element of A”. Equivalent expressions are “x is a member of A”, “x belongs to A”, “x is in A” and “x lies in A”. The expressions “A includes x” and “A contains x” are also used to mean set membership, however some authors use them to mean instead “x is a subset of A”.[1] Logician George Boolos strongly urged that “contains” be used for membership only and “includes” for the subset relation only.[2]
For the relation ∈ , the converse relation ∈T may be written
A ∋ x , {\displaystyle A\ni x,} meaning “A contains x”.
The negation of set membership is denoted by the symbol “∉”. Writing
x ∉ A {\displaystyle x\notin A} means that “x is not an element of A”.
The symbol ∈ was first used by Giuseppe Peano 1889 in his work Arithmetices principia, nova methodo exposita. Here he wrote on page X:
Signum ∈ significat est. Ita a ∈ b legitur a est quoddam b; …
which means
The symbol ∈ means is. So a ∈ b is read as a is a b; …
The symbol itself is a stylized lowercase Greek letter epsilon (“ϵ”), the first letter of the word ἐστί, which means “is”.
4 ∉ {1,2,3} because 4 is not an element of the set {1,2,3}.
The negation of set membership is denoted by the symbol “∉”. Writing
x ∉ A means that “x is not an element of A”.
{ 2 , 4 , 6 , 8 , 10 }
Finite or Infinite?
In mathematics, a finite set is a set that has a finite number of elements. Informally, a finite set is a set which one could in principle count and finish counting. For example,
{ 2 , 4 , 6 , 8 , 10 }
is a finite set with five elements. The number of elements of a finite set is a natural number (a non-negative integer) and is called the cardinality of the set. A set that is not finite is called infinite. For example, the set of all positive integers is infinite:
{ 1 , 2 , 3 , … }
Finite sets are particularly important in combinatorics, the mathematical study of counting. Many arguments involving finite sets rely on the pigeonhole principle, which states that there cannot exist an injective function from a larger finite set to a smaller finite set.
{ 1 , 2 , 3 , … }
Finite or Infinite
In mathematics, a finite set is a set that has a finite number of elements. Informally, a finite set is a set which one could in principle count and finish counting. For example,
{ 2 , 4 , 6 , 8 , 10 }
is a finite set with five elements. The number of elements of a finite set is a natural number (a non-negative integer) and is called the cardinality of the set. A set that is not finite is called infinite. For example, the set of all positive integers is infinite:
{ 1 , 2 , 3 , … }
Finite sets are particularly important in combinatorics, the mathematical study of counting. Many arguments involving finite sets rely on the pigeonhole principle, which states that there cannot exist an injective function from a larger finite set to a smaller finite set.
Ø
{ }
The empty set is the set which contains no elements.
In mathematics, the empty set is the unique set having no elements; its size or cardinality (count of elements in a set) is zero.
The universe set is the set of all elements.
In set theory, a universal set is a set which contains all objects, including itself.[1] In set theory as usually formulated, the conception of a universal set leads to Russell’s Paradox and is consequently not allowed. However, some non-standard variants of set theory include a universal set.
The power set of any set A is the set of all subsets of A.
The set of real numbers.
A real number is any positive or negative number. This includes all integers and all rational and irrational numbers. Rational numbers may be expressed as a fraction (such as 7/8) and irrational numbers may be expressed by an infinite decimal representation (3.1415926535…). Real numbers that include decimal points are also called floating point numbers, since the decimal “floats” between the digits.
Real numbers are relevant to computing because computer calculations involve both integer and floating point calculations. Since integer calculations are generally more simple than floating point calculations, a computer’s processor may use a different type of logic for performing integer operations than it does for floating point operations. The floating point operations may be performed by a separate part of the CPU called the floating point unit, or FPU.
While computers can process all types of real numbers, irrational numbers (those with infinite decimal points) are generally estimated. For example, a program may limit all real numbers to a fixed number of decimal places. This helps save extra processing time, which would be required to calculate numbers with greater, but unnecessary accuracy.
The set of integers. That is, Z {. . . , −2, −1, 0, 1, 2, 3, . . .}.
An integer is a whole number (not a fraction) that can be positive, negative, or zero. Therefore, the numbers 10, 0, -25, and 5,148 are all integers. Unlike floating point numbers, integers cannot have decimal places.
Integers are a commonly used data type in computer programming. For example, whenever a number is being incremented, such as within a “for loop” or “while loop,” an integer is used. Integers are also used to determine an item’s location within an array.
When two integers are added, subtracted, or multiplied, the result is also an integer. However, when one integer is divided into another, the result may be an integer or a fraction. For example, 6 divided by 3 equals 2, which is an integer, but 6 divided by 4 equals 1.5, which contains a fraction. Decimal numbers may either be rounded or truncated to produce an integer result.
The set of integers. That is, Z+ = {1, 2, 3, . . .}.
The set of natural numbers. That is, N {0, 1, 2, 3 . . .}.
A natural number is an integer greater than 0. Natural numbers begin at 1 and increment to infinity: 1, 2, 3, 4, 5, etc.
Natural numbers are also called “counting numbers” because they are used for counting. For example, if you are timing something in seconds, you would use natural numbers (usually starting with 1). When written, natural numbers do not have a decimal point (since they are integers), but large natural numbers may include commas, e.g. 1,000 and 234,567,890. Natural numbers will never include a minus symbol (-) because they cannot be negative.
In computer science, natural numbers are commonly used when incrementing values. For example, in a for loop, the counter often increases by one with each iteration. Once the counter hits the limit (e.g., 10 in for (i=1; i<10; i++)), the loop is broken and the code after the loop is processed.
The set of rational numbers.
A rational number is any number that can be expressed as a ratio of two integers (hence the name “rational”). It can be written as a fraction in which the the top number (numerator) is divided by the bottom number (denominator).
All integers are rational numbers since they can be divided by 1, which produces a ratio of two integers. Many floating point numbers are also rational numbers since they can be expressed as fractions. For example, 1.5 is rational since it can be written as 3/2, 6/4, 9/6 or another fraction or two integers. Pi (π) is irrational since it cannot be written as a fraction.
A floating point number is rational if it meets one of the following criteria:
it has a limited number of digits after the decimal point (e.g., 5.4321)
it has an infinitely repeating number after the decimal point (e.g., 2.333333…)
it has an infinitely repeating pattern of numbers after the decimal point (e.g. 3.151515…)
If the numbers after the decimal point repeat infinitely with no pattern, the number is not rational or “irrational.” Below are examples of rational and irrational numbers.
1 - rational
- 5 - rational
- 0 - rational
√2 - irrational
3.14 - rational
π (3.14159265359…) - irrational
√4 - rational
√5 - irrational
16/9 - rational
1,000,000.0000001 - rational
In computer science, it is significant if a number is rational or irrational. A rational number can be stored as an exact numeric value, while an irrational number must be estimated.
NOTE: The number zero (0) is a rational number because it can be written as 0/1, which equals 0.
Based on the concept of real numbers, a complex number is a number of the form a + bi, where a and b are real numbers and i is an indeterminate satisfying i2 = −1. For example, 2 + 3i is a complex number.
This way, a complex number is defined as a polynomial with real coefficients in the single indeterminate i, for which the relation i2 + 1 = 0 is imposed. Based on this definition, complex numbers can be added and multiplied, using the addition and multiplication for polynomials. The relation i2 + 1 = 0 induces the equalities i4k = 1 , i4k+1 = i , i4k+2 = −1 , and i4k+3 = −i , which hold for all integers k; these allow the reduction of any polynomial that results from the addition and multiplication of complex numbers to a linear polynomial in i, again of the form a + bi with real coefficients a, b.
The real number a is called the real part of the complex number a + bi; the real number b is called its imaginary part. To emphasize, the imaginary part does not include a factor i; that is, the imaginary part is b, not bi.
Formally, the complex numbers are defined as the quotient ring of the polynomial ring in the indeterminate i, by the ideal generated by the polynomial i2 + 1 (see below).
{ x : x > 2 } is the set of all x such that x is greater than 2.
{ } = “set of”
x = “all x”
: = “such that” ( | = “such that as well”)
x > 2 = “x is greater than 2”
A ⊆ B asserts that A is a subset of B : every element of A is also an element of B.
In mathematics, a set A is a subset of a set B, or equivalently B is a superset of A, if A is contained in B. That is, all elements of A are also elements of B (note that A and B may be equal). The relationship of one set being a subset of another is called inclusion or sometimes containment. A is a subset of B may also be expressed as B includes A, or A is included in B.
The subset relation defines a partial order on sets. In fact, the subsets of a given set form a Boolean algebra under the subset relation, in which the meet and join are given by intersection and union.
The cardinality (or size) of A is the number of elements in A.
In mathematics, the cardinality of a set is a measure of the “number of elements of the set”. For example, the set A = { 2 , 4 , 6 } contains 3 elements, and therefore A has a cardinality of 3. There are two approaches to cardinality – one which compares sets directly using bijections and injections, and another which uses cardinal numbers. The cardinality of a set is also called its size, when no confusion with other notions of size is possible.
The cardinality of a set A is usually denoted | A | , with a vertical bar on each side; this is the same notation as absolute value and the meaning depends on context.
A _____ produces a result from a pair of sets.
binary operation
A _____ produces an output from a single set.
unitary operation
A∪B is the union of A and B: is the set containing all elements which are elements of A or B or both.
In set theory, the union (denoted by ∪) of a collection of sets is the set of all elements in the collection.[1] It is one of the fundamental operations through which sets can be combined and related to each other.
For explanation of the symbols used in this article, refer to the table of mathematical symbols.
A ∩ B is the intersection of A and B: the set containing all elements which are elements of both A and B.
In mathematics, the intersection of two sets A and B or “A ∩ B”, is the set that contains all elements of A that also belong to B (or equivalently, all elements of B that also belong to A), but no other elements.[1]
For an explanation of the symbols used in this article, refer to the table of mathematical symbols.
Let A = {1, 2, 3} and B = {4, 5, 6}
A ∩ B = Ø
What kind of set pair is this?
In mathematics, two sets are said to be disjoint sets if they have no element in common. Equivalently, two disjoint sets are sets whose intersection is the empty set. For example, {1, 2, 3} and {4, 5, 6} are disjoint sets, while {1, 2, 3} and {3, 4, 5} are not disjoint. A collection of more than two sets is called disjoint if any two distinct sets of the collection are disjoint.
The complement of A is the set of everything which is not an element of A.
In set theory, the complement of a set A refers to elements not in A.
When all sets under consideration are considered to be subsets of a given set U, the absolute complement of A is the set of elements in U but not in A.
The relative complement of A with respect to a set B, also termed the difference of sets A and B, written B \ A, is the set of elements in B but not in A.
What is Set Difference?
Set Difference: The relative complement or set difference of sets A and B, denoted A – B, is the set of all elements in A that are not in B.
In set-builder notation, A – B = {x ∈ U : x ∈ A and x ∉ B}= A ∩ B’. You can also use the \ notation to define a set difference. A\B is the set of elements in A but not B.
The Venn diagram for the set difference of sets A and B is shown below where the shaded region represents A – B.
Example: Let A = {a, b, c, d} and B = {b, d, e}. Then A – B = {a, c} and B – A = {e}.
Source: http://web.mnstate.edu/peil/MDEV102/U1/S6/Complement3.htm
In mathematics, the symmetric difference, also known as the disjunctive union, of two sets is the set of elements which are in either of the sets and not in their intersection. The symmetric difference of the sets A and B is commonly denoted by
A △ B ,
or
A ⊖ B ,
or
A ⊕ B .
For example, the symmetric difference of the sets { 1 , 2 , 3 } and { 3 , 4 } is { 1 , 2 , 4 }.
The power set of any set becomes an abelian group under the operation of symmetric difference, with the empty set as the neutral element of the group and every element in this group being its own inverse. The power set of any set becomes a Boolean ring with symmetric difference as the addition of the ring and intersection as the multiplication of the ring.
A ∪ B = B ∪ A
A ∩ B = B ∩ A
A ⊕ B = B ⊕ A
p ∧ q ≡ q ∧ p
p ∨ q ≡ q ∨ p
Commutative Properties
A ∪ (B ∪ C) = (A ∪ B) ∪ C
A ∩ (B ∩ C) = (A ∩ B) ∩ C
(p ∧ q) ∧ r ≡ p ∧ (q ∧ r)
(p ∨ q) ∨ r ≡ p ∨ (q ∨ r)
Associative Properties
A ∩ (B ∪ C) = (A ∩ B) ∪ (A ∩ C)
A ∪ (B ∩ C) = (A ∪ B) ∩ (A ∪ C)
p ∨ (q ∧ r) ≡ (p ∨ q) ∧ (p ∨ r)
p ∧ (q ∨ r) ≡ (p ∧ q) ∨ (p ∧ r)
Distributive Properties
What is the law described below?
∅* = U And U = *∅
A ∪ A = U
A ∩ A = ∅
A’ (double compliment) = A
Complement Laws: The union of a set A and its complement A’ gives the universal set U of which A and A’ are a subset.
A ∪ A’ = U
Also the intersection of a set A and its complement A’ gives the empty set ∅.
A ∩ A’ = ∅
For Example: If U = {1 , 2 , 3 , 4 , 5 } and A = {1 , 2 , 3 } then A’ = {4 , 5}. From this it can be seen that
A ∪ A’ = U = { 1 , 2 , 3 , 4 , 5}
Also
A ∩ A’ = ∅
Law of Double Complementation: According to this law if we take the complement of the complemented set A’ then, we get the set A itself.
(A’ )’ = A
In the previous example we can see that, if U = {1 , 2 , 3 , 4 , 5} and A = {1 , 2 ,3} then A’ ={4 , 5} . Now if take the complement of set A’ we get,
(A’ )’ = {1 , 2 , 3} = A
This gives us the set A itself.
Law of empty set and universal set:
According to this law the complement of the universal set gives us the empty set and vice-versa i.e.,
∅’ = U And U = ∅’
This law is self-explanatory.
What is the law describing this formula? What does the formula do?
In propositional logic and boolean algebra, De Morgan’s laws are a pair of transformation rules that are both valid rules of inference. They are named after Augustus De Morgan, a 19th-century British mathematician. The rules allow the expression of conjunctions and disjunctions purely in terms of each other via negation.
The rules can be expressed in English as:
the negation of a disjunction is the conjunction of the negations; and
the negation of a conjunction is the disjunction of the negations;
or
the complement of the union of two sets is the same as the intersection of their complements; and
the complement of the intersection of two sets is the same as the union of their complements.
or
not (A or B) = not A and not B; and
not (A and B) = not A or not B
In set theory and Boolean algebra, these are written formally as
(Blue Pic)
where
A and B are sets,
A is the complement of A,
∩ is the intersection, and
∪ is the union.
In formal language, the rules are written as
(White Pic)
where
P and Q are propositions,
¬ is the negation logic operator (NOT),
∧ is the conjunction logic operator (AND),
∨ is the disjunction logic operator (OR),
⟺ is a metalogical symbol meaning “can be replaced in a logical proof with”.
An ordered list of numbers that can be either finite or infinite that allows for repetition.
A sequence is an ordered list. It is a function whose domain is the natural numbers {1, 2, 3, 4, …}. You can derive the step function in either explicit or recursive form.
Explicit Formula
An explicit formula designates the nth term of the sequence, as an expression of n (where n = the term’s location). It defines the sequence as a formula in terms of n. It may be written in either subscript notation an, or in functional notation, f (n).
To do this:
- Determine if the sequence is arithmetic (Do you add, or subtract, the same amount from one term to the next?)
- Find the common difference. (The number you add or subtract.)
- Create an explicit formula using the pattern of the first term added to the product of the common difference and one less than the term number.
Formula:
an= a1 + d (n - 1)
a<sub>n</sub> = the nth term in the sequence a<sub>1</sub> = the first term in the sequence n = the term number d = the common difference.
Recursive Form
A recursive formula designates the starting term, a1, and the nth term of the sequence, an , as an expression containing the previous term (the term before it), an-1.
Arithmetic Sequence
- Determine if the sequence is arithmetic (Do you add, or subtract, the same amount from one term to the next?)
- Find the common difference. (The number you add or subtract.)
- Create a recursive formula by stating the first term, and then stating the formula to be the previous term plus the common difference.
a<sub>1</sub> = first term; a<sub>n</sub>= a<sub>n-1</sub> + d
a<sub>1</sub> = the first term in the sequence a<sub>n</sub> = the nth term in the sequence a<sub>n-1</sub> = the term before the nth term n = the term number d = the common difference.
Geometric Sequence
a<sub>1</sub> = first term; a<sub>n</sub>= r • a<sub>n-1</sub>
a<sub>1</sub> = the first term in the sequence a<sub>n</sub> = the nth term in the sequence a<sub>n-1</sub> = the term before the nth term n = the term number r = the common ratio
A ____________________ formula (or recurrence relation) for a sequence describes a term in the sequence in terms of previous term(s).
recursive formula
An ___________________ formula for a sequence describes a term in the sequence in terms of the index (term number) n
explicit formula
What is the quotient remainder theorem?
Given any integer A, and a positive integer B, there exist unique integers Q and R such that
A= B * Q + R where 0 ≤ R < B
Source: https://www.khanacademy.org/computing/computer-science/cryptography/modarithmetic/a/the-quotient-remainder-theorem
A natural number greater than 1 that cannot be formed by multiplying two smaller natural numbers.
Prime Number
Relatively Prime
Let a,b ∈ Z+
if gcd (a,b) = 1
a and b are relatively prime.
In mathematics, the greatest common divisor (gcd) of two or more integers, which are not all zero, is the largest positive integer that divides each of the integers. For example, the gcd of 8 and 12 is 4.
The greatest common divisor is also known as the greatest common factor (gcf), highest common factor (hcf), greatest common measure (gcm), or highest common divisor.
This notion can be extended to polynomials (see Polynomial greatest common divisor) and other commutative rings (see below):
𝑥3+𝑥2+𝑥+1=(𝑥3+1)⋅1+𝑥2+𝑥
𝑥3+1=(𝑥2+𝑥)⋅𝑥+(−𝑥2+1)
𝑥2+𝑥=(−𝑥2+1)⋅(−1)+𝑥+1
−𝑥2+1=(𝑥+1)⋅(−𝑥+1)
Euclidean Algorithm
In mathematics, the Euclidean algorithm,[note 1] or Euclid’s algorithm, is an efficient method for computing the greatest common divisor (GCD) of two numbers, the largest number that divides both of them without leaving a remainder. It is named after the ancient Greek mathematician Euclid, who first described it in his Elements (c. 300 BC). It is an example of an algorithm, a step-by-step procedure for performing a calculation according to well-defined rules, and is one of the oldest algorithms in common use. It can be used to reduce fractions to their simplest form, and is a part of many other number-theoretic and cryptographic calculations.
In computing, the modulo operation finds the remainder after division of one number by another (called the modulus of the operation).
Given two positive numbers, a and n, a modulo n (abbreviated as a mod n) is the remainder of the Euclidean division of a by n, where a is the dividend and n is the divisor.
For example, the expression “5 mod 2” would evaluate to 1 because 5 divided by 2 has a quotient of 2 and a remainder of 1, while “9 mod 3” would evaluate to 0 because the division of 9 by 3 has a quotient of 3 and leaves a remainder of 0; there is nothing to subtract from 9 after multiplying 3 times 3. (Doing the division with a calculator will not show the result referred to here by this operation; the quotient will be expressed as a decimal fraction.)
Although typically performed with a and n both being integers, many computing systems allow other types of numeric operands. The range of numbers for an integer modulo of n is 0 to n − 1 inclusive. (a mod 1 is always 0; a mod 0 is undefined, possibly resulting in a division by zero error in programming languages.) See modular arithmetic for an older and related convention applied in number theory.
When either a or n is negative, the naive definition breaks down and programming languages differ in how these values are defined.
Mod Solutions
Mod Solutions
A ⊂ B asserts that A is a proper subset of B: every element of A is also an element of B, but A B.
Some authors use the symbols ⊂ and ⊃ to indicate subset and superset respectively; that is, with the same meaning and instead of the symbols, ⊆ and ⊇.[2] For example, for these authors, it is true of every set A that A ⊂ A.
Other authors prefer to use the symbols ⊂ and ⊃ to indicate proper (also called strict) subset and proper superset respectively; that is, with the same meaning and instead of the symbols, ⊊ and ⊋.[3] This usage makes ⊆ and ⊂ analogous to the inequality symbols ≤ and
A × B is the Cartesian product of A and B: the set of all ordered pairs (a, b) with a ∈ A and b ∈ B.
In set theory (and, usually, in other parts of mathematics), a Cartesian product is a mathematical operation that returns a set (or product set or simply product) from multiple sets. That is, for sets A and B, the Cartesian product A × B is the set of all ordered pairs (a, b) where a ∈ A and b ∈ B. Products can be specified using set-builder notation, e.g.
A × B = { ( a , b ) ∣ a ∈ A and b ∈ B } . {\displaystyle A\times B={\,(a,b)\mid a\in A\ {\mbox{ and }}\ b\in B\,}.} [1]
A table can be created by taking the Cartesian product of a set of rows and a set of columns. If the Cartesian product rows × columns is taken, the cells of the table contain ordered pairs of the form (row value, column value).
More generally, a Cartesian product of n sets, also known as an n-fold Cartesian product, can be represented by an array of n dimensions, where each element is an n-tuple. An ordered pair is a 2-tuple or couple.
The Cartesian product is named after René Descartes,[2] whose formulation of analytic geometry gave rise to the concept, which is further generalized in terms of direct product.
A \ B is A set-minus B: the set containing all elements of A which are not elements of B.
If A is a set, then the absolute complement of A (or simply the complement of A) is the set of elements not in A, within a larger set that is implicitely defined. In other words, let U be a set that contains all the elements under study; if it is no need to mention U, either because it has been previously specified, or it is obvious and unique, then the absolute complement of A is the relative complement of A in U:[1]
The __________ of an implication P → Q is the statement ¬Q → ¬P.
The contrapositive of an implication P → Q is the statement ¬Q → ¬P. An implication and its contrapositive are logically equivalent (they are either both true or both false).
In logic, contraposition is an inference that says that a conditional statement is logically equivalent to its contrapositive. The contrapositive of the statement has its antecedent and consequent inverted and flipped: the contrapositive of P → Q is thus ¬ Q → ¬ P. For instance, the proposition “All cats are mammals” can be restated as the conditional “If something is a cat, then it is a mammal”. The law of contraposition says that statement is true if, and only if, its contrapositive “If something is not a mammal, then it is not a cat” is true.
The contrapositive can be compared with three other relationships between conditional statements:
Inversion (the inverse), ¬ P → ¬ Q
“If something is not a cat, then it is not a mammal.” Unlike the contrapositive, the inverse’s truth value is not at all dependent on whether or not the original proposition was true, as evidenced here. The inverse here is clearly not true.
Conversion (the converse), Q → P
“If something is a mammal, then it is a cat.” The converse is actually the contrapositive of the inverse and so always has the same truth value as the inverse, which is not necessarily the same as that of the original proposition.
Negation, ¬ ( P → Q )
“There exists a cat that is not a mammal. “ If the negation is true, the original proposition (and by extension the contrapositive) is false. In this example, the negation is false.
Note that if P → Q is true and we are given that Q is false, ¬ Q, it can logically be concluded that P must be false, ¬ P. This is often called the law of contrapositive, or the modus tollens rule of inference.
Intuitive explanation
Consider the Euler diagram shown. According to this diagram, if something is in A, it must be in B as well. So we can interpret “all of A is in B” as:
A → B
It is also clear that anything that is not within B (the blue region) cannot be within A, either. This statement,
¬ B → ¬ A
is the contrapositive. Therefore, we can say that
( A → B ) → ( ¬ B → ¬ A ).
Practically speaking, this makes trying to prove something easier. For example, if we want to prove that every girl in the United States (A) has brown hair (B), we can try to directly prove A → B by checking all girls in the United States to see if they all have brown hair. Alternatively, we can try to prove ¬ B → ¬ A by checking all girls without brown hair to see if they are all outside the US. This means that if we find at least one girl without brown hair within the US, we will have disproved ¬ B → ¬ A, and equivalently A → B.
To conclude, for any statement where A implies B, then not B always implies not A. Proving or disproving either one of these statements automatically proves or disproves the other. They are fully equivalent.
¬P is read “not P,” and called a negation.
¬P is true when P is false.
In logic, negation, also called the logical complement, is an operation that takes a proposition P to another proposition “not P”, written ¬ P , which is interpreted intuitively as being true when P is false, and false when P is true. Negation is thus a unary (single-argument) logical connective. It may be applied as an operation on notions, propositions, truth values, or semantic values more generally. In classical logic, negation is normally identified with the truth function that takes truth to falsity and vice versa. In intuitionistic logic, according to the Brouwer–Heyting–Kolmogorov interpretation, the negation of a proposition P is the proposition whose proofs are the refutations of P.
Definition
No agreement exists as to the possibility of defining negation, as to its logical status, function, and meaning, as to its field of applicability…, and as to the interpretation of the negative judgment, (F.H. Heinemann 1944).
Classical negation is an operation on one logical value, typically the value of a proposition, that produces a value of true when its operand is false and a value of false when its operand is true. So, if statement P is true, then ¬ P (pronounced “not P”) would therefore be false; and conversely, if ¬ P is false, then P would be true.
The truth table of ¬ P is as follows:
P ¬ P
TrueFalse
FalseTrue
Negation can be defined in terms of other logical operations. For example, ¬ P can be defined as P → ⊥ (where → is logical consequence and ⊥ is absolute falsehood). Conversely, one can define ⊥ as Q ∧ ¬ Q for any proposition Q (where ∧ is logical conjunction). The idea here is that any contradiction is false. While these ideas work in both classical and intuitionistic logic, they do not work in paraconsistent logic, where contradictions are not necessarily false. In classical logic, we also get a further identity, P → Q can be defined as ¬ P ∨ Q, where ∨ is logical disjunction.
Algebraically, classical negation corresponds to complementation in a Boolean algebra, and intuitionistic negation to pseudocomplementation in a Heyting algebra. These algebras provide a semantics for classical and intuitionistic logic respectively.
Implication
P → Q is read “if P then Q,” and called an implication or conditional.
P → Q is true when P is false or Q is true or both.
If p and q are propositions, then p→q is a conditional statementor implication which is read as “if p, then q” and has this truthtable: In p→q, p is the hypothesis (antecedent or premise) andqis theconclusion (or consequence).Implication can be expressed by disjunction and negation: p→q ≡ ¬p ∨ q
In p→q there does not need to be any connection between theantecedent or the consequent. The meaning depends only on thetruth values of p and q. This implication is perfectly fine, but would not be used in ordinary English. “If the moon is made of green cheese, then I have more money than Bill Gates.” One way to view the logical conditional is to think of an obligation or contract. “If I am elected, then I will lower taxes.”
P ∨ Q is read “P or Q,” and called a disjunction.
P ∨ Q is true when P or Q or both are true.
In logic and mathematics, or is the truth-functional operator of (inclusive) disjunction, also known as alternation; the or of a set of operands is true if and only if one or more of its operands is true. The logical connective that represents this operator is typically written as ∨ or +.
A ∨ B is true if A is true, or if B is true, or if both A and B are true.
In logic, or by itself means the inclusive or, distinguished from an exclusive or, which is false when both of its arguments are true, while an “or” is true in that case.
An operand of a disjunction is called a disjunct.
Related concepts in other fields are:
In natural language, the coordinating conjunction “or”.
In programming languages, the short-circuit or control structure.
In set theory, union.
In predicate logic, existential quantification.
Logical disjunction is an operation on two logical values, typically the values of two propositions, that has a value of false if and only if both of its operands are false. More generally, a disjunction is a logical formula that can have one or more literals separated only by ‘or’s. A single literal is often considered to be a degenerate disjunction.
The disjunctive identity is false, which is to say that the or of an expression with false has the same value as the original expression. In keeping with the concept of vacuous truth, when disjunction is defined as an operator or function of arbitrary arity, the empty disjunction (OR-ing over an empty set of operands) is generally defined as false.
P ∧ Q is read “P and Q,” and called a conjunction.
P ∧ Q is true when both P and Q are true.
In logic, mathematics and linguistics, And (∧) is the truth-functional operator of logical conjunction; the and of a set of operands is true if and only if all of its operands are true. The logical connective that represents this operator is typically written as ∧ or ⋅ .
A ∧ B {\displaystyle A\land B} is true only if A {\displaystyle A} is true and B {\displaystyle B} is true.
An operand of a conjunction is a conjunct.
The term “logical conjunction” is also used for the greatest lower bound in lattice theory.
Related concepts in other fields are:
In natural language, the coordinating conjunction “and”.
In programming languages, the short-circuit and control structure.
In set theory, intersection.
In predicate logic, universal quantification.
Logical conjunction is an operation on two logical values, typically the values of two propositions, that produces a value of true if and only if both of its operands are true.
The conjunctive identity is true, which is to say that AND-ing an expression with true will never change the value of the expression. In keeping with the concept of vacuous truth, when conjunction is defined as an operator or function of arbitrary arity, the empty conjunction (AND-ing over an empty set of operands) is often defined as having the result true.
P ↔ Q is read “P if and only if Q,” and called a biconditional.
P ↔ Q is true when P and Q are both true, or both false.
In logic and mathematics, the logical biconditional (sometimes known as the material biconditional) is the logical connective of two statements asserting “ P if and only if Q”, where P is an antecedent and Q is a consequent.[1] This is often abbreviated “ P “. The operator is denoted using a doubleheaded arrow (↔), a prefixed E “Epq” (in Łukasiewicz notation or Bocheński notation), an equality sign (=), an equivalence sign (≡), or EQV. It is logically equivalent to ( P → Q ) ∧ ( Q → P ) and to ( P ∧ Q ) ∨ ( ¬ P ∧ ¬ Q ) (or the XNOR (exclusive nor) boolean operator), meaning “both or neither”.
The only difference from material conditional is the case when the hypothesis is false but the conclusion is true. In that case, in the conditional, the result is true, yet in the biconditional the result is false.
In the conceptual interpretation, P = Q means “All P’s are Q’s and all ‘ Q’s are P’s”; in other words, the sets P and Q coincide: they are identical. This does not mean that the concepts have the same meaning. Examples: “triangle” and “trilateral”, “equiangular trilateral” and “equilateral triangle”. The antecedent is the subject and the consequent is the predicate of a universal affirmative proposition.
In the propositional interpretation, P ⇔ Q (⇔) means that P implies Q and Q implies P ; in other words, that the propositions are equivalent, that is to say, either true or false at the same time. This does not mean that they have the same meaning. Example: “The triangle ABC has two equal sides”, and “The triangle ABC has two equal angles”. The antecedent is the premise or the cause and the consequent is the consequence. When an implication is translated by a hypothetical (or conditional) judgment the antecedent is called the hypothesis (or the condition) and the consequent is called the thesis.
A common way of demonstrating a biconditional is to use its equivalence to the conjunction of two converse conditionals, demonstrating these separately.
When both members of the biconditional are propositions, it can be separated into two conditionals, of which one is called a theorem and the other its reciprocal. Thus whenever a theorem and its reciprocal are true we have a biconditional. A simple theorem gives rise to an implication whose antecedent is the hypothesis and whose consequent is the thesis of the theorem.
It is often said that the hypothesis is the sufficient condition of the thesis, and the thesis the necessary condition of the hypothesis; that is to say, it is sufficient that the hypothesis be true for the thesis to be true; while it is necessary that the thesis be true for the hypothesis to be true also. When a theorem and its reciprocal are true we say that its hypothesis is the necessary and sufficient condition of the thesis; that is to say, that it is at the same time both cause and consequence.
Logical equality (also known as biconditional) is an operation on two logical values, typically the values of two propositions, that produces a value of true if and only if both operands are false or both operands are true.
The existential quantifier is ∃ and is read “there exists” or “there is.” For example,
∃ x ( x < 0 )
asserts that “there is (∃) a number (x) less than 0.”
In predicate logic, an existential quantification is a type of quantifier, a logical constant which is interpreted as “there exists”, “there is at least one”, or “for some”. Some sources use the term existentialization to refer to existential quantification.[1] It is usually denoted by the logical operator symbol ∃, which, when used together with a predicate variable, is called an existential quantifier (“∃x” or “∃(x)”). Existential quantification is distinct from universal quantification (“for all”), which asserts that the property or relation holds for all members of the domain.
The universal quantifier is ∀ and is read “for all” or “every.” For example, ∀x ( x ≥ 0 )
asserts that every number (x) is greater than or equal to 0.
In predicate logic, a universal quantification is a type of quantifier, a logical constant which is interpreted as “given any” or “for all”. It expresses that a propositional function can be satisfied by every member of a domain of discourse. In other words, it is the predication of a property or relation to every member of the domain. It asserts that a predicate within the scope of a universal quantifier is true of every value of a predicate variable.
It is usually denoted by the turned A (∀) logical operator symbol, which, when used together with a predicate variable, is called a universal quantifier (“∀x”, “∀(x)”, or sometimes by “(x)” alone). Universal quantification is distinct from existential quantification (“there exists”), which only asserts that the property or relation holds for at least one member of the domain.
Quantification in general is covered in the article on quantification (logic). Symbols are encoded U+2200 ∀ FOR ALL (HTML ∀ · ∀ · as a mathematical symbol).
In mathematics, an indicator function or a characteristic function is a function defined on a set X that indicates membership of an element in a subset A of X, having the value 1 for all elements of A and the value 0 for all elements of X not in A. It is usually denoted by a symbol 1 or I, sometimes in boldface or blackboard boldface, with a subscript specifying the subset.
In other contexts, such as computer science, this would more often be described as a boolean predicate function (to test set inclusion).
The Dirichlet function is an example of an indicator function and is the indicator of the rationals.
