CS 25 PPT 2-Proposition and Logical Connectives-Part 1
Proposition & Logical Connectives (Part 1)
Presented by Luzviminda T. Orilla, PhD
Topic 1: Proposition
Definition of Proposition
A proposition is a declarative sentence that can only be true or false, not both.
The truth value indicates its truth or falsity.
Examples of Statements
Statement: "Manila is the capital of the Philippines."
Truth Value: True
Statement: "What day is it today?"
Truth Value: Cannot be determined (not a statement)
More Examples of Statements
Non-statement: "Help me, please."
Cannot be true or false.
Non-statement: "He is handsome."
Lacks specificity, not a propositional statement.
Topic 2: Logical Connectives
Definition of Logic
Logic is the science or study of evaluating arguments.
Used in mathematics to prove theorems and in computer science to verify program correctness.
Definition of Mathematical Logic
Branch of mathematics related to computer science, focusing on the study and applications of formal logic.
Key divisions include:
Set Theory
Model Theory
Recursion Theory
Proof Theory
Propositional Variables
Variables like p, q, r represent statements.
A compound statement consists of multiple statements connected by logical connectives such as "and", "or", "if then", "if and only if", and "exclusive-or".
Main Logical Connectives
Conjunction
Disjunction
Negation
Conditional
Biconditional
Exclusive-Or
Conjunction
Definition
The conjunction of statements P and Q forms the compound statement "P and Q" represented symbolically as P Ù Q.
Properties
Truth Value: True only if both P and Q are true.
Truth Table for Conjunction
P | Q | P Ù Q |
|---|---|---|
T | T | T |
T | F | F |
F | T | F |
F | F | F |
Disjunction
Definition
The disjunction of P and Q forms the compound statement "P or Q" represented as P Ú Q.
Properties
Truth Value: True if at least one of P or Q is true.
Truth Table for Disjunction
P | Q | P Ú Q |
|---|---|---|
T | T | T |
T | F | T |
F | T | T |
F | F | F |
Negation
Definition
The negation of P is represented as ~P (not P).
Properties
Truth Value: Opposite of the truth value of P.
Truth Value of Negation
P | ~P |
|---|---|
T | F |
F | T |
Example
P: "3 + 5 = 8"; ~P: "3 + 5 ≠ 8"
P: "John is not here"; ~P: "John is here"
Conditional
Definition
A conditional statement "If P, then Q" is represented as P ® Q.
Properties
Truth Value: False only when P is true and Q is false.
Truth Table for Conditional
P | Q | P ® Q |
|---|---|---|
T | T | T |
T | F | F |
F | T | T |
F | F | T |
Examples for Truth Values
"If vinegar is sweet, then sugar is sour."
"2 + 5 = 7 is a sufficient condition for 5 + 6 = 1."
Biconditional
Definition
A biconditional statement "P if and only if Q" is represented as P « Q.
Properties
Truth Value: True if both P and Q are true or both are false.
Truth Table for Biconditional
P | Q | P « Q |
|---|---|---|
T | T | T |
T | F | F |
F | T | F |
F | F | T |
Examples for Truth Values
"2 + 8 = 10 if and only if 6 - 3 = 3."
Exclusive-Or
Definition
The exclusive-or of P and Q is represented as P Å Q.
Properties
Truth Value: True if one of P or Q is true, but not both.
Truth Table for Exclusive-Or
P | Q | P Å Q |
|---|---|---|
T | T | F |
T | F | T |
F | T | T |
F | F | F |
Important Classes of Compound Statements
Tautology: Always true.
Contradiction: Always false.
Contingency: Can be true or false based on values.
Example of Tautology
Statement: (~P Ù Q) ® Q shown to yield all true.
Example of Contingency
Statement: (P ® Q) Ù (P ® ~Q) shown to include false values.
Example of Contradiction
Statement: (~P Ú Q) Å (P ® Q) shown to yield all false.