Lecture Notes: Propositional Logic

1. Introduction to Logic

Logic is the study of reasoning, focusing on the relationship among statements rather than the content of any particular statement.

• Goal: To distinguish valid arguments from invalid ones using specific rules and techniques.
• Application: It is the foundation of computer science, used in automated reasoning (AI), logic gates (hardware), software verification, and programming semantics.

1.1 Propositions

A Proposition (or Statement) is a declarative sentence that is either TRUE or FALSE, but not both.

• Examples of Propositions:
  • "I can run."
  • " "
• Non-Examples:
  • "Where is University of Malaya?" (Question)
  • "Please show me your ticket." (Command)

Notation: Variables like are used to represent propositions.

2. Logical Operators

We can combine simple propositions to form compound propositions using logical operators.

2.1 Negation ()

• Definition: The negation of , denoted (or ), represents "not " or "It is not the case that ".
• Truth Table:

T	F
F	T

2.2 Conjunction / AND ()

• Definition: The conjunction of and , denoted , is true only when both and are true.
• Truth Table:

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

2.3 Disjunction / OR ()

• Definition: The disjunction of and , denoted , is false only when both and are false.
• Truth Table:

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

Operator Precedence: (Negation) (AND) (OR).

3. Conditional Statements

3.1 Conditional Proposition ()

• Form: "If , then ", denoted .
• Components: is the antecedent (hypothesis), is the consequent (conclusion).
• Truth Value: is FALSE only when is True and is False. Otherwise, it is True.
• Phrasing: implies ; is sufficient for ; if ; is necessary for .

3.2 Biconditional Proposition ()

• Form: " if and only if " (iff), denoted .
• Truth Value: True when and have the same truth values (both True or both False).

3.3 Related Conditionals

Given :

1. Converse:
2. Inverse:
3. Contrapositive:

• Note: The contrapositive is logically equivalent to the original statement ( ).

4. Logical Equivalence & Types of Propositions

4.1 Classification of Propositions

• Tautology: A proposition that is always TRUE regardless of input values (e.g., ).
• Contradiction: A proposition that is always FALSE (e.g., ).
• Contingency: A proposition that is neither a tautology nor a contradiction.

4.2 Logical Equivalence ()

Two propositions and are logically equivalent ( ) if they have the same truth values in all cases. This can be proven via Truth Tables or Laws of Logic.

Common Laws of Logic:

• De Morgan’s Laws:
• Distributive Laws:
• Implication Law:

5. Deductive Reasoning & Rules of Inference

Deductive Reasoning involves drawing a valid conclusion from a sequence of premises (hypothesis). An argument is valid if the conclusion must be true whenever the hypotheses are true.

5.1 Rules of Inference

These are standard patterns of valid arguments used in proofs.

1. Modus Ponens
   
   Example: If copper, then conducts electricity. It is copper. Therefore, conducts electricity.

2. Modus Tollens
   

3. Conjunction Elimination
   

4. Disjunction Introduction
   

5. Disjunctive Syllogism
   

6. Hypothetical Syllogism
   

7. Dilemma
   

5.2 Common Fallacies

Fallacies are invalid arguments that may look like valid rules.

1. Affirming the Consequent (Invalid)
   
   Example: If in Thailand (), then in Asia (). I am in Asia (). Therefore, I am in Thailand (). (False, you could be in Malaysia).

2. Denying the Antecedent (Invalid)