Unit I: Mathematical Logic

Course: Discrete Mathematics
Code: CADSC102

Statements and Notations

Mathematical logic begins with the concept of a statement (or proposition). A statement is a declarative sentence that is either true or false, but not both.

Notations

• Propositions are usually denoted by lowercase letters such as p, q, r, s.
• The truth value of a statement is denoted by T (True) or F (False).

Connectives

Connectives are used to combine simple statements into compound statements.

Equivalences and Normal Forms

Logical Equivalences

Two statements are logically equivalent if they have the same truth value in every possible scenario. This is denoted by the symbol ≡.

Normal Forms

Normal forms are standardized ways of representing logical expressions.

• Disjunctive Normal Form (DNF): A sum of products (e.g., (p ^ q) v (~p ^ r)).
• Conjunctive Normal Form (CNF): A product of sums (e.g., (p v q) ^ (~p v r)).

Predicate Calculus and Quantifiers

Predicate calculus extends propositional logic to include variables and quantifiers.

Predicate: A property or relation assigned to objects in a domain (e.g., P(x) where x is an integer).

Quantifiers

• Universal Quantifier (∀): Read as "For all x". It means the property is true for every element in the domain.
• Existential Quantifier (∃): Read as "There exists an x". It means the property is true for at least one element in the domain.

Inference Theory

Inference theory provides the rules for mathematical reasoning and for arriving at logical conclusions from given premises.

• Modus Ponens: If p and (p → q) are true, then q is true.
• Modus Tollens: If ~q and (p → q) are true, then ~p is true.