Logic

Definition: Proposition

A proposition is a declarative statement that is either true or false.

Usually, propositions are condition-based. We can use logical connectives to build more complex propositions:

Negation
Conjunction
Disjunction
Exclusive or
Implication
Biconditional

Definition: Truth Table

A truth table displays the relationships between truth values of different propositions. The rows of a truth table list out all possible values of all elementary propositions.

Definition: Negation

Let be a proposition. The statement “It is not the case that ” is called the negation of , denoted by and read as “not ”.

Definition: Conjunction

Let and be propositions. The conjunction of and , denoted by , is true when both and are true and is false otherwise.

Definition: Disjunction

Let and be propositions. The disjunction of and , denoted by , is false when both and are false and is true otherwise.

Definition: Exclusive Or

Let and be propositions. The exclusive or of and , denoted by , is true when exactly one of and is true and is false otherwise.

Definition: Implication

Let and be propositions. The conditional statement (a.k.a. implication) , is the proposition “if , then ”, is false when is true and is false, and true otherwise. In , is called the hypothesis and is called the conclusion.

is read in a variety of equivalent ways:

if then
implies
is sufficient for
is necessary for
follows from
unless
only if

The converse of is .

The contrapositive of is .

The inverse of is .

Definition: Biconditional

Let and be propositions. The biconditional statement (a.k.a. bi-conditional) , is the proposition “ if and only if ”, is true when and share the same truth value, and is false otherwise.

A compound proposition that is always true for all possible truth values is called a tautology.
A compound proposition that is always false for all possible truth values is called a contradiction.
A compound proposition that is neither tautology nor contradiction is called a contingency.

Definition: Logical Equivalence

Two proposition are equivalent if they always have the same truth value.

Alternative definition: The propositions and are called logically equivalent if is a tautology, denoted by or .

Logical Equivalence Laws

Distributive Laws

De Morgan’s Laws

Identity Laws

Domination Laws

Idempotent Laws

Double Negation Laws

Commutative Laws

Distributive Laws

Absorption Laws

Negation Laws

Useful Law

Computer Representation of True and False

A bit is sufficient to represent two possible values: 0 (false) or 1 (true). A variable that takes on values 0 and 1 is called a Boolean variable. A bit string is a sequence of zero or more bits, the length of such bit strings is the number of bits in the string.

Limitations of Propositional Logic

Propositional logic is the world described in terms of elementary propositions and their logical combinations. Elementary statements typically refer to objects, their properties and relations. But there exists some limitations of it, for example: - Repeated statements for many objects. - Statements that define the property of a group of objects. To solve this, we need to: - explicitly models objects and their properties, and - allows to make statements with variables and quantify them.

Predicate Logic

Basic building blocks of the predicate logic (or first-order logic):

Constant
Variable
Predicate

Definition: Predicate

A predicate is a statement that contains variables and becomes a proposition when specific values are substituted for the variables .

The universe (or domain) of the predicate variables is the set of all values that may be substituted in place of the variables.

The truth set of is the set of all values of the predicate variables s.t. the proposition is true.

The logical connectives and corresponding rules in propositional logic are all usable in predicate logic.

There are two types of quantified statements: universal and existential.

Definition: Universal Quantification

The universal quantification of is the proposition “ is true for all values of in the universe of discourse.” Denoted by , and is expressed as “for every , .”

Definition: Existential Quantification

The existential quantification of is the proposition “ is true for some values of in the universe of discourse.” Denoted by , and is expressed as “for some , .”

Suppose that the elements in the universe can be numerated as , then: - is true iff . - is true iff .

Caution

The truth values of and depend on both the propositional function and the universe.

Caution

The quantifier has higher precedence than the logical connectives.

Tip

The universal quantifier is often paired with the implication : The seemingly correct would mean that everyone is a SUSTech student and is smart! The existential quantifier is often paired with the conjunction : while would be true even if is not a SUSTech student!

De Morgan’s Law for Quantifiers

Tip

The order of the quantifiers generally does matter. if the types of the nested quantifiers are the same, the order will have no matter at changing.

Theorems and Proofs

Definition: Axiom

An axiom and postulate is a statement or proposition which is regarded as being established, accepted, or self-evidently true.

Definition: Theorem

A theorem is a statement that can be proved to be true.

Definition: Lemma

A lemma is a statement that can be proved to be true, and is used in proving a theorem or proposition.

To show the truth value of a statement follows from other statements, we need to provide a correct supporting argument, a.k.a. proof.

Typically, a theorem looks like this:

Definition: Proof

A proof provides an argument supporting the validity of the statement, and may use premises, axioms, lemmas, results of other theorems, etc.

In formal proofs, steps follow logically from the set of premises, axioms, lemmas, and other theorems.

Some basic proof methods are:

Direct proof
Proof by contrapositive
Proof by contradiction
Proof by cases
Proof of equivalence

Consider the truth table of the implication:


T	T	T
T	F	F
F	T	T
F	F	T

Then:

direct proof proceeds by showing the first row.
proof by contradiction proceeds by showing the second row.
proof by contrapositive proceeds by showing the fourth row.

The proof by cases is based on the following logical equivalence: ### Inference Rules of Propositional Logic Every inference rule represent a tautology that allows us to infer new true statements from existing ones.

Modus Ponens

Modus Tollens

Hypothetical Syllogism

Disjunctive Syllogism

Addition

Simplification

Conjunction

Resolution

Inference Rules for Quantified Statements

Universal Instantiation

Universal Generalization

Existential Instantiation

Existential Generalization

Discrete Mathematics (H) Lecture 1-3 Notes