Semantics of Propositional Logic
COS2661 - Formal Logic II · Introduction to Propositional Logic
Semantics of Propositional Logic
Propositional logic deals with propositions that can either be true or false. The semantics of propositional logic is concerned with the meanings of these propositions and how their truth values are determined. Understanding semantics is essential for constructing logical arguments and proofs.
Propositions
A proposition is a declarative statement that is either true (T) or false (F). For example:
- The sky is blue. (This can be true or false depending on the time of day or weather.)
- 2 + 2 = 4. (This is always true.)
- Water boils at 100 degrees Celsius. (This is true at standard atmospheric pressure.)
In propositional logic, we use letters such as P, Q, and R to represent propositions. For example, let:
P: The sky is blue.We can then construct logical statements using these propositions.
Logical Connectives
Logical connectives are symbols used to combine propositions to form more complex statements. The primary logical connectives are:
- Negation (¬): This connective reverses the truth value of a proposition. If P is true, then ¬P is false.
- Conjunction (∧): This connective is true if both propositions are true. For example, P ∧ Q is true only if both P and Q are true.
- Disjunction (∨): This connective is true if at least one of the propositions is true. For example, P ∨ Q is true if either P is true, Q is true, or both are true.
- Implication (→): This connective indicates that if P is true, then Q must also be true. P → Q is false only when P is true and Q is false.
- Biconditional (↔): This connective indicates that P and Q are equivalent; they are both true or both false. P ↔ Q is true if both P and Q have the same truth value.
Remember: The truth values of the logical connectives are defined as follows:
| Connective | Truth Table |
|---|---|
| Negation (¬P) | T if P is F, F if P is T |
| Conjunction (P ∧ Q) | T if both P and Q are T, F otherwise |
| Disjunction (P ∨ Q) | T if at least one of P or Q is T, F if both are F |
| Implication (P → Q) | T unless P is T and Q is F |
| Biconditional (P ↔ Q) | T if both have the same truth value, F otherwise |
Truth Values of Compound Propositions
To determine the truth value of a compound proposition, you can use the truth values of its components. For example, consider the compound proposition P ∧ Q, where:
P: It is raining. (True)Q: It is cold. (True)The truth value of P ∧ Q is true because both P and Q are true. Now consider:
P: It is raining. (True)Q: It is cold. (False)The truth value of P ∧ Q is false because Q is false, even though P is true.
Constructing Truth Tables
A truth table is a systematic way to display the truth values of a proposition based on its components. To create a truth table for a compound proposition, follow these steps:
- List all possible combinations of truth values for the individual propositions.
- Calculate the truth value of the compound proposition for each combination.
For example, let us construct a truth table for the proposition P ∧ Q:
| P | Q | P ∧ Q |
|---|---|---|
| T | T | T |
| T | F | F |
| F | T | F |
| F | F | F |
This table shows that P ∧ Q is only true when both P and Q are true.
Examples of Logical Connectives
Let us consider some examples using logical connectives:
Example 1: Negation
Let P represent the proposition “The sky is blue.” If P is true, then:
¬P: The sky is not blue.Here, if P is true, ¬P is false.
Example 2: Conjunction
Let P represent “It is raining” and Q represent “It is cold.” The conjunction P ∧ Q means:
It is raining and it is cold.This statement is true only if both P and Q are true.
Example 3: Disjunction
Using the same propositions, the disjunction P ∨ Q means:
It is raining or it is cold.This statement is true if either P is true, Q is true, or both are true.
Example 4: Implication
Consider P: “It is raining” and Q: “The ground is wet.” The implication P → Q means:
If it is raining, then the ground is wet.This statement is false only if it is raining and the ground is not wet.
Example 5: Biconditional
The biconditional P ↔ Q means:
It is raining if and only if the ground is wet.This statement is true if both P and Q are either true or false.
Applications of Propositional Logic
Propositional logic has many applications in computer science, mathematics, philosophy, and artificial intelligence. For example, it is used in:
- Designing digital circuits
- Developing algorithms
- Formulating logical arguments
- Creating decision-making systems
Tip: When working with propositional logic, always ensure that you clearly define your propositions and logical connectives. This clarity will help you avoid confusion in complex statements.
Common Mistakes
Watch out: A common mistake is confusing the truth values of conjunctions and disjunctions. Remember that a conjunction is only true when both propositions are true, while a disjunction is true if at least one proposition is true.
Summary
- A proposition is a statement that can be true or false.
- Logical connectives combine propositions to form compound statements.
- Truth tables help to determine the truth values of compound propositions.
- Understanding the semantics of propositional logic is crucial for constructing logical arguments.
Check your understanding
- Define a proposition and give an example.
- What is the truth value of P ∧ Q if P is true and Q is false?
- How does negation affect the truth value of a proposition?
- Provide the truth table for the biconditional connective (P ↔ Q).