Discrete Structures

Logic

Science or study of how to evaluate arguments and reasoning

Mathematical Logic

Covers the study of proofs system and provided symbols to express the inductive or deductive ways of reasoning

Propositions

Basic building blocks of logic

Propositions

Declarative sentence that is either true or false, but not both

Compound Propositions

New propositions

Compound Propositions

Are formed from existing propositions using logical operators

Logical Operators

Also called Connectives

Conjunction

^

Conjuction

Only true when both p and q are true and is false otherwise

Disjunction

v

Disjunction

It is true when at least one of p or q is true.

Exclusive Or

Denoted by a circle that is split in four

Exclusive Or

It is true when exactly one of p and q is true and is false otherwise

Negation

A logical operation that inverts the truth value of a proposition, turning true to false and false to true.

Negation

Denoted by a “gun” facing left

Conditional Statement

Denoted by an arrow to the right

Condition Statement

It is false when p is true and q is false and true otherwise

p (Condition Statement)

Hypothesis

q (Conditional Statement)

Conclusion or a consequence

Conditional Statement

Also called an implication

Converse of p → q

Proposition q → p

Proposition not q → not p

Contrapositive of p → q

Inverse of p → q

Proposition not p → not q

Biconditional Statements

Denoted by an arrow pointing to both left and right

Biconditional Statement

Bi-implications

Biconditional Statement

It is true when p and q have the same truth values, and is false otherwise

Truth Tables

Are used to determine the truth values of compound propositions

Classes of Compound Propositions

Tautology, Contradiction, and Contingency

Tautology

Compound propositions that is true for all possible combination of the truth values of the compound variables

Tautology

Also called logically true

Contradiction

Compound propositions that is false for all possible combinations of the truth values of its propositional variables

Contradiction

Also called logically false or absurdity

Contingency

Compound propositions that can either be