Unit 1: Discrete Mathematics - Subjective Questions

Definition: A proposition is a declarative sentence that has exactly one truth value: true or false, but not both.

Examples:

• "" is a proposition and is true.
• "" is a proposition and is false.
• "Close the door" is not a proposition because it is a command.
• "What is your name?" is not a proposition because it is a question.

For , the truth table is:

Thus, the compound proposition is true only when both is true and is true.

Logical equivalence: Two propositions are logically equivalent if they have the same truth value for every possible assignment of truth values to their variables. Logical equivalence is written as .

Using the implication law:

This can also be verified by a truth table:

Since the corresponding columns are identical, and are logically equivalent.

Predicate: A predicate is a statement containing variables whose truth value depends on the values assigned to those variables. For example, may mean " is a student."

Quantifiers:

• The universal quantifier means "for every" or "for all."
• The existential quantifier means "there exists at least one."

Let mean " is a student" and mean " studies mathematics."

Translations:

• (a) Every student studies mathematics:
  
• (b) Some student does not study mathematics:
  

The implication in the first expression restricts the universal statement to students, while the conjunction in the second expression identifies an individual who is both a student and a non-mathematics student.

The principal rules for negating quantified statements are:

Consider:

Move the negation through the universal quantifier:

Apply the negation rule for implication:

Therefore, the negation is "There exists at least one for which is true and is false."

Set: A set is a well-defined collection of distinct objects, called elements.

Roster form: Elements are listed explicitly. For example, .

Set-builder form: A set is described by a property satisfied by its elements. For example:

For the given sets:

• Union:
  
• Intersection:
  
• Difference :
  
• Difference :
  

The union contains elements in either set, the intersection contains common elements, and set difference contains elements belonging to the first set but not the second.

For subsets and of a universal set , De Morgan's laws are:

and

Proof of the first law:

Let . Then:

if and only if . This means and . Therefore:

Hence, .

Proof of the second law:

if and only if . Thus, or . Therefore:

Hence, .

A relation from to is a subset of the Cartesian product . If , we write .

For a relation on a set :

• Reflexive: for every .
• Symmetric: If , then for all .
• Antisymmetric: If and , then .
• Transitive: If and , then .

Examples:

• The relation "" is reflexive, symmetric, antisymmetric, and transitive.
• The relation "" is reflexive, antisymmetric, and transitive, but it is not symmetric.
• The relation "is a sibling of" is generally symmetric but need not be transitive.
• The relation "is less than" is transitive and antisymmetric in the strict-order sense, but it is not reflexive.

Consider .

• Reflexive: Yes. The pairs , , and are all in .
• Symmetric: Yes. Whenever , ; the diagonal pairs are automatically symmetric.
• Antisymmetric: No. Both and belong to , but .
• Transitive: Yes. The nontrivial pairs are between and , and all required compositions remain in the relation. For example, and imply , which is in ; and imply , which is also in .

Therefore, is reflexive, symmetric, and transitive, but it is not antisymmetric.

A function assigns exactly one element of to each element of .

• One-to-one or injective: implies .
• Onto or surjective: For every , there exists some such that .
• Bijective: A function that is both one-to-one and onto.

For :

One-to-one: Suppose . Then:

Thus, is one-to-one.

Onto: Every output of is odd. For example, no integer can be written as for an integer . Therefore, is not onto .

Hence, is injective but not surjective, and therefore it is not bijective.

The composition of and is defined by:

It means that is applied first and then .

Given and :

Also:

A function has an inverse function if and only if it is bijective between its domain and codomain. The function is one-to-one and onto from to , so it has an inverse.

Solving for :

A relation on a set is a partial order if it is:

• Reflexive: for every .
• Antisymmetric: If and , then .
• Transitive: If and , then .

A set together with a partial order is called a partially ordered set, or poset, and is written .

A total order is a partial order in which every pair of elements is comparable. Thus, for any , either or .

Examples:

• is a totally ordered set because any two integers are comparable.
• The power set is generally partially ordered but not totally ordered. For example, and are incomparable because neither set is a subset of the other.

Therefore, every total order is a partial order, but every partial order is not necessarily a total order.

Under divisibility, means divides . The covering relations are:

• is covered by and .
• is covered by .
• is covered by .
• is covered by .

The Hasse diagram can be represented vertically as:

The relation is a partial order because divisibility is reflexive, antisymmetric, and transitive.

• Minimal element: .
• Maximal element: .
• Least element: , because divides every element of .
• Greatest element: , because every element of divides .

In this poset, the minimal and least elements coincide, as do the maximal and greatest elements.

Let be a subset of a poset .

• An upper bound of is an element such that for every .
• A lower bound of is an element such that for every .
• The supremum, or least upper bound, is the smallest upper bound of , if it exists.
• The infimum, or greatest lower bound, is the largest lower bound of , if it exists.
• A maximum is an element of that is greater than or equal to every element of .
• A minimum is an element of that is less than or equal to every element of .

Consider ordered by and let:

Then:

• is the maximum and supremum of .
• is the minimum and infimum of .

A supremum or infimum need not belong to the subset, whereas a maximum or minimum must belong to it.

A lattice is a partially ordered set in which every pair of elements and has:

• A greatest lower bound, called the meet and denoted by .
• A least upper bound, called the join and denoted by .

Consider ordered by . For any :

• The meet is the intersection:
  
• The join is the union:
  

Proof:

is a lower bound because and . If and , then , so it is the greatest lower bound.

Similarly, is an upper bound because and . If and , then , so it is the least upper bound.

Therefore, is a lattice.

For elements of a lattice, the basic lattice laws are:

• Idempotent laws:
  
• Commutative laws:
  
• Associative laws:
  
  
• Absorption laws:
  
  

A lattice is distributive if it also satisfies:

and

In the lattice , these laws correspond to familiar laws of union and intersection. For example, the absorption law becomes:

and

A lattice is bounded if it contains a least element and a greatest element such that:

for every element in the lattice.

A bounded lattice is complemented if for every element , there exists an element such that:

and

For ordered by inclusion:

• The least element is .
• The greatest element is .
• The complement of is .

Using meet as intersection and join as union:

and

Thus, every element has a complement. Therefore, is a complemented bounded lattice. In fact, it is also a distributive lattice.

A nonempty set together with a binary operation is called a group if it satisfies the following axioms:

• Closure: For all , .
• Associativity: For all , .
• Identity: There exists such that for every .
• Inverse: For every , there exists such that .

For :

• Closure: If , then .
• Associativity: Integer addition is associative: .
• Identity: The integer satisfies .
• Inverse: For every , and .

Therefore, is a group. It is also an abelian group because addition is commutative.

The structures differ according to the properties satisfied by the operation:

• Semigroup: A nonempty set with an associative binary operation. Example: .
• Monoid: A semigroup with an identity element. Example: , where is the identity.
• Group: A monoid in which every element has an inverse. Example: .
• Abelian group: A group whose operation is commutative. Example: .

The logical relationship is:

For instance, is a semigroup but not a monoid if excludes , because it has no identity element in the set. A group requires inverses, while an abelian group additionally requires commutativity.

Uniqueness of identity:

Suppose and are both identity elements of a group . Since is an identity:

Since is an identity:

Therefore, . Hence, the identity element is unique.

Uniqueness of inverse:

Let , and suppose and are both inverses of . Then:

and

Using associativity and the identity property:

Therefore, . Hence, every element of a group has a unique inverse.

Let:

with operation modulo .

• Closure: If , then .
• Associativity: Integer addition is associative, so:
  
• Identity: is the identity because:
  
• Inverse: The inverse of is , or equivalently when , because:
  
• Commutativity: Since integer addition is commutative:
  

All group axioms hold, and the operation is commutative. Therefore, is an abelian group.