Propositional Logic
COS1501 - Theoretical Computer Science I · Logic and Propositions
Propositional Logic
Propositional logic is a branch of logic that deals with propositions. A proposition is a statement that can either be true or false, but not both. In propositional logic, we use variables to represent propositions and connect them using logical connectives.
Propositions
Propositions can be simple or compound. A simple proposition is a single statement, while a compound proposition is formed by combining two or more simple propositions using logical connectives.
Examples of Propositions
- Simple Proposition: "It is raining." (This can be true or false.)
- Compound Proposition: "It is raining and it is cold." (This combines two simple propositions.)
Logical Connectives
Logical connectives are symbols used to connect propositions. The main logical connectives are:
- Conjunction (AND): Denoted by ∧. The compound proposition is true only if both propositions are true.
- Disjunction (OR): Denoted by ∨. The compound proposition is true if at least one of the propositions is true.
- Negation (NOT): Denoted by ¬. It reverses the truth value of a proposition.
- Implication (IF...THEN): Denoted by →. It states that if the first proposition is true, then the second proposition must also be true.
- Biconditional (IF AND ONLY IF): Denoted by ↔. It states that both propositions are either true or false together.
Example of Logical Connectives
Let P: "It is raining."
Let Q: "It is cold."
1. Conjunction: P ∧ Q
- True if both P and Q are true.
2. Disjunction: P ∨ Q
- True if at least one of P or Q is true.
3. Negation: ¬P
- True if P is false.
4. Implication: P → Q
- True unless P is true and Q is false.
5. Biconditional: P ↔ Q
- True if both P and Q are either true or false.Truth Values
Each proposition has a truth value, which can be either true (T) or false (F). The truth value of compound propositions depends on the truth values of the individual propositions and the logical connectives used.
Truth Value Table for Conjunction
| P | Q | P ∧ Q |
|---|---|---|
| T | T | T |
| T | F | F |
| F | T | F |
| F | F | F |
Truth Value Table for Disjunction
| P | Q | P ∨ Q |
|---|---|---|
| T | T | T |
| T | F | T |
| F | T | T |
| F | F | F |
Truth Value Table for Negation
| P | ¬P |
|---|---|
| T | F |
| F | T |
Truth Value Table for Implication
| P | Q | P → Q |
|---|---|---|
| T | T | T |
| T | F | F |
| F | T | T |
| F | F | T |
Truth Value Table for Biconditional
| P | Q | P ↔ Q |
|---|---|---|
| T | T | T |
| T | F | F |
| F | T | F |
| F | F | T |
Remember: The truth value of a compound proposition can be determined using truth tables. Each row of the table represents a possible combination of truth values for the propositions involved.
Logical Equivalence
Logical equivalence means that two propositions have the same truth value in every possible scenario. To show that two propositions are logically equivalent, you can use truth tables.
Example of Logical Equivalence
Consider the propositions P and Q. We can show that P → Q is logically equivalent to ¬P ∨ Q.
Truth Table for Logical Equivalence
| P | Q | P → Q | ¬P | ¬P ∨ Q |
|---|---|---|---|---|
| T | T | T | F | T |
| T | F | F | F | F |
| F | T | T | T | T |
| F | F | T | T | T |
Watch out: Be careful when interpreting implication. The statement P → Q is only false when P is true and Q is false.
Applications of Propositional Logic
Propositional logic is widely used in computer science, especially in programming and algorithm design. It helps in formulating logical statements and conditions in code. For example, in C++, you can use logical operators to control the flow of a program.
Example in C++
#include
using namespace std;
int main() {
bool raining = true;
bool cold = false;
if (raining && cold) {
cout << "Take an umbrella and wear a jacket.";
} else if (raining || cold) {
cout << "Take an umbrella or wear a jacket.";
} else {
cout << "Enjoy the weather!";
}
return 0;
}Tip: Practice writing truth tables for different propositions. This will help you understand logical relationships better.
Summary
- A proposition is a statement that can be true or false.
- Logical connectives include conjunction, disjunction, negation, implication, and biconditional.
- Truth tables help determine the truth values of compound propositions.
- Logical equivalence shows that two propositions have the same truth value.
- Propositional logic is essential in programming and algorithm design.
Check your understanding
- What is a proposition?
- How is a compound proposition formed?
- What does the implication P → Q mean?
- How can you show that two propositions are logically equivalent?