Discrete Mathematics 01: Logic, Proofs, and Set Theory

Propositional Logic

• Declarative Statements and Propositions

  • Informally, a proposition is defined as a declarative sentence (a statement) in a language that is subject to being either true or false.

• Truth Values and Logical Operators

  • Negation ($\neg$):

  • Let $P$ be a proposition. The negation of $P$, denoted by $\neg P$, represents "not $P$", "It is not the case that $P$", or "$P$ is not true".

  • The proposition $\neg P$ takes the exact opposite truth value of $P$.

  • Conjunction ($\land$):

  • Let $P$ and $Q$ be propositions. The conjunction of $P$ and $Q$, denoted by $P \land Q$, represents "$P$ and $Q$".

  • The compound statement $P \land Q$ evaluates to true if both $P$ and $Q$ are true, and false otherwise.

  • Disjunction ($\lor$):

  • Let $P$ and $Q$ be propositions. The disjunction of $P$ and $Q$, denoted by $P \lor Q$, represents "$P$ or $Q$" (inclusive or, meaning maybe both).

  • The compound statement $P \lor Q$ evaluates to false if both $P$ and $Q$ are false, and true otherwise.

  • Exclusive OR ($\oplus$):

  • Let $P$ and $Q$ be propositions. The exclusive or of $P$ and $Q$, denoted by $P \oplus Q$, represents "$P$ or $Q$ but not both".

  • The compound statement $P \oplus Q$ evaluates to true if exactly one of $P$ and $Q$ is true, and false otherwise.

  • Conditional Statement or Implication ($\rightarrow$):

  • Let $P$ and $Q$ be propositions. The conditional statement or implication $P \rightarrow Q$ represents "if $P$ then $Q$" or "$P$ implies $Q$".

  • The implication $P \rightarrow Q$ evaluates to false when $P$ is true and $Q$ is false; in all other cases, it evaluates to true.

  • Related Conditional Statements:

  • Converse: For a given conditional statement $P \rightarrow Q$, its converse is defined as the conditional $Q \rightarrow P$.

  • Contrapositive: For a given conditional statement $P \rightarrow Q$, its contrapositive is defined as the conditional $\neg Q \rightarrow \neg P$.

  • Inverse: For a given conditional statement $P \rightarrow Q$, its inverse is defined as the conditional $\neg P \rightarrow \neg Q$.

  • Biconditional Statement ($\leftrightarrow$):

  • Let $P$ and $Q$ be propositions. The biconditional statement $P \leftrightarrow Q$ represents "$P$ if and only if $Q$" or "$P$ is necessary and sufficient for $Q$".

  • The statement $P \leftrightarrow Q$ evaluates to true when both $P$ and $Q$ share the same truth value (both true or both false); it evaluates to false in any other case.

• Tautologies, Contradictions, and Logical Equivalence

  • Tautology: A compound proposition that evaluates to true under all possible truth value assignments for its propositional variables.

  • Contradiction: A compound proposition that evaluates to false under all possible truth value assignments for its propositional variables.

  • Logical Equivalence ($\equiv$):

  • Let $P$ and $Q$ be propositions. $P$ and $Q$ are logically equivalent, written as $P \equiv Q$, if they have the same truth value in all possible cases.

  • Equivalently, $P$ and $Q$ are logically equivalent if the biconditional statement $P \leftrightarrow Q$ is a tautology.

  • De Morgan's Laws:

  • Let $P$ and $Q$ be propositions. Then:

    • $\neg (P \land Q) \equiv \neg P \lor \neg Q$

    • $\neg (P \lor Q) \equiv \neg P \land \neg Q$

• Digital Logic and Bit Operations

  • Bit Definition: A bit is the most basic unit of information in computing, having two possible states: $1$ (true) or $0$ (false).

  • Boolean Variables: A Boolean variable is a variable that can take two values: $\text{True}$ or $\text{False}$. Thus, a bit represents a Boolean variable.

  • Bit Operations:

  • NOT: A unary operation that performs a logical negation on a single bit (inverting its value).

  • AND: A binary operation performing a logical conjunction ($\land$) across two bits.

  • OR: A binary operation performing a logical disjunction ($\lor$) across two bits.

  • XOR: A binary operation performing a logical exclusive OR ($\oplus$) across two bits.

Predicate Logic

• Basic Definitions

  • Term: An expression that represents "an object" or "a thing".

  • Predicate: A symbol that represents a property or a relation.

  • Domain of Discourse ($U$): Informally, the domain of discourse (denoted by $U$) is the set of all objects in a theory, or the universe of possible objects that might be considered subject to predicates.

• Quantifiers

  • Universal Quantifier ($\forall$):

  • Given a predicate $P$ and a variable $x$, the statement $\forall x \, P(x)$ means that predicate $P$ is true for all elements $x$ within the domain of discourse $U$ ("For all $x$, $P(x)$").

  • Existential Quantifier ($\exists$):

  • Given a predicate $P$ and a variable $x$, the statement $\exists x \, P(x)$ means that there exists at least one element $x$ in the domain of discourse $U$ for which the predicate $P$ is true ("There exists $x$ such that $P(x)$").

• Logical Equivalence and Negation in Predicate Logic

  • Logical Equivalence: Two statements involving predicates and quantifiers are logically equivalent if they always have the same truth value, regardless of what predicates are substituted in the statements and what domain of discourse $U$ is being used.

  • Negation of Quantifiers:

  • Let $P$ be a predicate in some domain of discourse $U$. Then:

    • $\neg \forall x \, P(x) \equiv \exists x \, \neg P(x)$

    • $\neg \exists x \, P(x) \equiv \forall x \, \neg P(x)$

Deductive Reasoning and Rules of Inference

• Structure of Deduction

  • Deductive Principle: Let $A_1, \dots, A_n$ and $Q$ be propositions. If $(A_1 \land \dots \land A_n) \implies Q$ is a tautology and all premises $A_1, \dots, A_n$ are true, then $Q$ must be true.

  • Deductive Deduction: Through this structure, $Q$ can be formally deduced from the premises $A_1, \dots, A_n$

• Rules of Inference

  • Definition: A tautology of the form $(A_1 \land \dots \land A_n) \implies Q$ is called a rule of inference in propositional logic, allowing arguments to be conducted in a way that is always logically valid.

Proof Technique: Mathematical Induction

• Principle of Mathematical Induction

  • Theorem: Let $P$ be a predicate defined for the natural numbers $\mathbb{N}$. If:

  • Basis step: $P(0)$ holds true, and

  • Inductive step: $P(k) \implies P(k + 1)$ holds for an arbitrary $k$,

  • Then $P(n)$ is true for every $n \in \mathbb{N}$.

• Principle of Strong Induction

  • Theorem: Let $P$ be a predicate defined for the natural numbers $\mathbb{N}$. If:

  • Basis step: $P(0)$ holds true, and

  • Inductive step: $(P(0) \land P(1) \land \dots \land P(k)) \implies P(k + 1)$ holds for an arbitrary $k$,

  • Then $P(n)$ is true for every $n \in \mathbb{N}$.

Fundamental Set Theory

• Definitions and Basic Properties

  • Set Definition: Intuitively, a set is a collection of objects.

  • Elements / Members: The objects contained in a set are said to be its elements or members. If $a$ is an element of a set $A$, write $a \in A$. If not, write $a \notin A$

  • Structural Properties of Sets:

  • Unordered: A set is defined entirely by the elements belonging to it, meaning element order does not matter.

  • No Repeated Elements: A set cannot contain repeated elements. If an element belongs to a set, it already belongs; it does not make sense to "belong twice".

  • Empty Set ($\emptyset$): The empty set is defined as the unique set containing no elements, denoted by $\emptyset$

• Relations Between Sets

  • Equal Sets ($=$):

  • Two sets $A$ and $B$ are said to be equal if they have the exact same elements.

  • Formally: $\forall x \, (x \in A \iff x \in B)$. Written as $A = B$

  • Inclusion / Subset ($\subseteq$):

  • A set $A$ is a subset of a set $B$ if every element of $A$ is an element of $B$. Written as $A \subseteq B$

  • Observation on Subsets:

  • For every set $A$, the empty set is a subset of $A$ ($\emptyset \subseteq A$

  • For every set $A$, the set $A$ is a subset of itself ($A \subseteq A$

• Set Operations

  • Union ($\cup$):

  • Let $A$ and $B$ be sets. The union of $A$ and $B$, denoted $A \cup B$, is the set containing all elements that are either in $A$ or in $B$ (or in both).

  • Set-builder notation: $A \cup B = \{x \mid x \in A \lor x \in B\}$

  • Intersection ($\cap$):

  • Let $A$ and $B$ be sets. The intersection of $A$ and $B$, denoted $A \cap B$, is the set containing all elements that are in both $A$ and $B$

  • Set-builder notation: $A \cap B = \{x \mid x \in A \land x \in B\}$

  • Disjoint Sets: If two sets have an empty intersection ($A \cap B = \emptyset$), they are said to be disjoint.

  • Difference / Relative Complement ($-$, $\setminus$):

  • Let $A$ and $B$ be sets. The difference of $A$ and $B$ (also called the complement of $B$ relative to $A$), denoted $A - B$, is the set of all elements of $A$ that are not elements of $B$

  • Set-builder notation: $A - B = \{x \mid x \in A \land x \notin B\}$

  • Power Set ($\mathcal{P}(A)$):

  • Let $A$ be a set. The power set of $A$, denoted by $P(A)$ or $\mathcal{P}(A)$, is the set of all subsets of $A$

  • Cartesian Product ($\times$):

  • Let $A$ and $B$ be sets. The Cartesian product of $A$ and $B$, denoted $A \times B$, is the set of all ordered pairs $(a, b)$ where $a \in A$ and $b \in B$

  • Set-builder notation: $A \times B = \{(a, b) \mid a \in A \land b \in B\}$