Discrete Mathematics - Terminologies (Midterms)

Set

Collection of definite and distinguishable objects adhering to certain rules and descriptions

Sets

Unordered collection of elements

George Cantor

Defined that sets are groups of elements following rules and descriptions

Roster/ Tabular Form & Set Builder Notation

Defining and representing sets can come in 2 ways, what are these?

Roster Form

What form is used when all elements are listed and enclosed by curly braces, with each element being separated with commas

Set Builder Notation

Form wherein the notation contains relations of symbols and words inside columns where each set element must first posses a property to become it becomes its member. It does not mention the elements individually directly

Variable

Set Builder Notation:

Represents x as the placeholder for any element in the set that satisfies the condition

: or |

Set Builder Notation:

Separates the variable from the conditions that define the set (read as such that).

Conditions

Set Builder Notation:

Properties that x must satisfy to be included in the set

Cardinality

Measures the number of elements in the set that determines its size (|A|)

Finite Set

A set with limited elements

Infinite Set

A set with unlimited elements

Empty or Null Set

Set with no elements

Equal Sets

Sets that have the same elements

Equivalent Sets

Sets with the same number of unique elements

Universal Set

Contains every element

Subsets

Sets where its elements are also elements of other sets

Proper Subset

If a subset does not contain all the elements of its parent set

2^n - 1

The formula to get all the elements of a subset excluding the null set

Superset

The parent set of a subset

Proper Superset

A superset wherein not all elements are contained in the subset

Power Set

A set that defines all subsets of a set

Union

Set Operations:

Denotes that a set consists all elements belonging to the defined sets (or both). Unifies all terms

Intersection

Set Operations:

Denoted by combining only like elements present in the defined sets

Complement

Set Operations:

Leaves a set of all elements that is not in the defined set but is in the universal set

Difference

Set Operations:

An operation done to remove like elements from defined sets

Cartesian Products

Set Operations:
Product of two or more sets that produces a sets of ordered pairs

Cartesian Product

Set operation that is not commutative

Symmetric Difference

Set Operations:

Consists of the union of elements done through using the difference operations simultaneously

Commutative law

Set Laws:

• Order of sets does not matter

• AUB=BUA (Union)

• A∩B=B∩A (Intersection)

Associative Law

Set Laws:

• The way the sets are grouped in terms for parenthesis does not affect the result as long as it is under the same operations

• (A∪B)∪C = A∪(B∪C)

• (A∩B)∩C = A∩(B∩C)

Idempotent Laws

Set Laws:

• Repeats the same set operation on itself, producing the same outcome

• A∪A = A

• A∩A = A

Distributive Laws

Set Laws:

• Equality relation between union and intersection

• Shows how an operation is distributed to the other

• A∩(B∪C) = (A∩B)∪(A∩C)

• A∪(B∩C) = (A∪B)∩(A∪C)

De Morgan’s Law

Set Laws:

• Explains the Unions and Intersections are related to the complements of its inverse

• (A∪B)’ = A’∩B’

• (A∩B)’ = A’∪B’

Identity Law

Set Laws:

• States the relationship between the intersections with empty sets and union with universal sets will yield the set itself

• A∪∅ = A

• A∩U = A

Domination

Set Laws:

• Also known as the Absorption Law, states that the union with an empty set and intersection with a universal set will absorb the original set and yield the null and universal respectively

• A ∪ U = U

• A ∩ ∅ = ∅

Complement Law

Set Laws:

• States that the union and the intersection of a set and its complement will yield a universal and empty set respectively

Negation Law

Set Laws:

States that the complement of a negation will yield the original set prior to negation

Proposition

Declarative statement that can either be true or false

Simple Sentence

This statement does not include other statements and propositions

Complex sentences

Consists of more logical connectives

Negation, Conjunctions, Disjunction, Conditionals, & Biconditionals

Types of complex sentences

Negation

• Reverses a statement

• truth value p is false only if -p is true, vice versa

Conjunctions

• AND sentences that put two sentences together claiming they are both true

• True if and only if A and B are true

Disjunction

• OR sentences that claim at least one is true

• False if and only if both are false

Conditionals

• Statements that are only false when the hypothesis is true and the conclusion is false

Inverse

Types of Conditionals:

Negates the hypothesis and conclusion

Converse

Types of Conditionals:

Changes the position of the conclusion and hypothesis

Contrapositive

Types of Conditionals:

Inverse of the Converse

Sufficient

Conditional that is enough on its own to satisfy the truth

Necessary

Condition that needs to be true to prove something else to be true

If

Used to introduce the condition

Then

Used to introduce the result

Biconditional

Statements that are both sufficient and necessary for something elese

Syntax

Refers to the form of the expression

Unary Propositional Operator / Negation

-

Conjunction

∧

Disjunction

∨

Conditional

→

Biconditional

↔

Semantics

Refers to the meaning of expressions

Truth Tables

Shows all the possible truths in a given proposition

Tautology

Nature of Propositions:

Proposition that is always true for all possible truth values

Contradiction

Nature of Propositions:

Proposition that is always false for all possible truth values

Contingency

Nature of Propositions:

Proposition that contains both true and false values

Logically Equivalent Sentences

What do you call when both propositional statements have the same truth values?

Propositional Equivalence

Replacement of a statement with another equal statement of equal truth value

Compound Propositions

A term used to define propositional variables with logical operators

Logical Equivalence

Compound Propositions with the same truth values in all cases

De Morgans

Key Logical Laws:

• Named after Augustus De Morgan, an English Mathematician in the mid-19th Century

• Dictates the negation of a disjunction is the conjunction of its components, and vice versa

Associative Law

Key Logical Laws:

Propositions with only conjunctions and disjunctions that have grouping (parenthesis) does not affect the truth value

Idempotent Law

Key Logical Laws:

Applying the same logical operation on itself does not change the value

Commutative

Key Logical Laws:

Placement does not affect the result

Distributive

Key Logical Laws:

Rearranges the expression by factoring the propositions AND and OR

Material Equivalence

Key Logical Laws:

Refers to a logical relationship that is either true together or false together

Involution

Key Logical Laws:

Applying Negation twice returns it to its original proposition

Material Implication

Key Logical Laws:

States that if the hypothesis is true then the conclusion must be true

Exportation

Key Logical Laws:

Shows that a conditional statement with a conjunction can be rewritten as a nested conditional

Identity

Key Logical Laws:

True is a Proposition that is always true and False is a proposition that is always false

Predicate Logic

Fundamental extension of propositional logic that allows more flexible expressions by incorporating variables, quantifiers, and predicates

Lack of Expressiveness

Limitations of Propositional Logic:

Can’t handle statements with variables, relationships, or generalizations

Cannot infer truth

Limitations of Propositional Logic:

Cannot establish the truth of a proposition that isn’t given a premise or can’t be inferred by laws of inference

No Quantifiers

Limitations of Propositional Logic:

Cannot express specific instances through universal or existential quantifiers, therefore they cannot represent all or some

Cannot Represent Relationships

Limitations of Propositional Logic:

Propositional statements treats statements as atomic units, no relationships

Cannot Represent Relationships

Limitations of Propositional Logic:

Cant provide formal and structured ways of expressing relationships between multiple objects

• Variables

• Express relationships

• Quantifiers

What does predicate logic introduce?

Predicate

• Function that maps objects to truth values

• A statement that applies a property or description

• Predicate(Domain) = P(x)

Variables

Represents unspecified objects from the domain

Constants

Represent specific objects from the domain

Quantifiers

• States the domain in which the predicate holds true

• Used with predicates to know what extent is the range of elements

Universal Quantifier

Denoted by symbol ∀ that expresses that the predicate applies to all elements int he domain (reads “for all”)

Existential Quantifier

Denoted by ∃ that tells the amount or quantity that there is at least one or some

Nested Quantifiers

Quantifiers that occur within the scope of quantifiers

Universal Universal

∀x∀yP(x,y)

Universal Existential

∀x∃yP(x,y)

Existential Universal

∃x∀yP(x,y)

Existential Existential

∃x∃yP(x,y)

Rules of Inference

The standards in which we consider certain arguments are valid if it only uses given hypotheses together

Universal Instantiation

Says that c is true for every element of the domain, we name an element by c so c is true for all these things