Chapter 1: Formal Logic
Section 1.2 Propositional Logic
Propositional Logic
Propositional Logic
In Section 1.1, we used the notation of formal logic to represent statements in symbolic form as wffs; because statements are sometimes called propositions , these wffs are also called propositional wffs .Now we want to use tools from formal logic to see how to reach logical conclusion based on given statements. The formal system that uses propositional wffs is called propositional logic, statement logic .
Propositional Logic as a Tool for argument representation:
This branch of formal logic deals with propositions (or statements) and their relationships. It uses symbols to represent logical operators (like AND, OR, NOT, etc.) and propositions, allowing complex arguments to be expressed in a precise and unambiguous way.
Well-Formed Formulas (wffs):
These are expressions in propositional logic that are syntactically correct. Arguments are constructed using these wffs, where each wff represents a proposition or a logical combination of propositions.
Valid Arguments
Understanding arguments is crucial in computer science because they are the foundation of all decision-making, problem-solving, and automation that computers perform. Logic is the essential tool that structures and evaluates these arguments, ensuring that computers operate correctly and efficiently.In propositional logic, an argument consists of hypotheses and a conclusion. These are all expressed as wffs. Propositional logic allows arguments to be written in symbolic form, making the logical structure of the argument clear.
An argument can be represented in symbolic form as:
where \(P_1, P_2, ..., P_n\) are the given statements, called the hypotheses , of the argument, and \(Q\) is the conclusion of the argument. As usual, the \(P's\) and the \(Q\) represent wffs, not merely statement letters. When should this be considered a valid argument?
Definition:
The propositional well-formed formula (wff):is a valid argument when it is a tautology.
A tautology is a wff that is true under every possible interpretation of its component propositions. In other words, no matter what truth values the individual propositions \( P_1, P_2, ..., P_n \) and \(Q\) take, the entire expression \( P_1 ∧ P_2 ∧ P_3 ∧ ... ∧ P_n → Q \) will always evaluate to true.
Example
• Example 1:George Washington was the first president of the United States. Thomas Jefferson wrote the Declaration of Independence. Therefore, every day has 24 hours.
This argument has two hypotheses:
A: George Washington was the first president of the United States.
B: Thomas Jefferson wrote the Declaration of Independence.
and the conclusion:
C: Every day has 24 hours.
The argument would be symbolized as:
Even though each of the individual hypotheses, as well as the conclusion, is a true statement, we would not consider this argument valid, since it is NOT a tautology.
| A | B | C | A ∧ B | A ∧ B → C |
|---|---|---|---|---|
| F | F | F | F | T |
| F | F | T | F | T |
| F | T | T | F | T |
| F | T | F | F | T |
| T | F | T | F | T |
| T | F | F | F | T |
| T | T | T | T | T |
| T | T | F | T | F |
• Example 2:
If George Washington was the first president of the United States, then John Adams was the first vice president. George Washington was the first president of the United States. Therefore John Adams was the first vice president.
This argument has the two hypotheses:
\(A → B\): If George Washington was the first president of the United States, then John Adams was the first vice president.
\(A\): George Washington was the first president of the United States.
and the conclusion:
\(B\): John Adams was the first vice president.
The argument would be symbolized as:
The truth table establishes that this argument is a tautology. The argument is valid; its from is such that conculsion follows inevitably from the hypotheses.
| \(A\) | \(B\) | \(A → B\) | \( (A → B) ∧ A \) | \( (A → B) ∧ A → B \) |
|---|---|---|---|---|
| T | T | T | T | T |
| T | F | F | F | T |
| F | T | T | F | T |
| F | F | T | F | T |
To test whether a wff \(P_1 ∧ P_2 ∧ P_3 ∧ ... ∧ P_n → Q\) is a tautology, we could build a truth table or use the algorithm TautologTest. Instead, we will trun to formal logic, which uses a system of derivation rules that manipulate wffs in a truth-preserving manner. You begin with the hypotheses \(P_1, ..., P_n\) (assumed true) and attempt to apply the manipulation rules in such a way as to end up with the conclusion \(Q\).
By using formal logic and derivation rules, you can test whether a wff is a tautology without needing to list out all possibilities in a truth table. This method is often more elegant and efficient, especially for more complex logical statements.
Proof Sequence
A proof sequence is a sequence of wffs in which each wff is either a hypothesis or the result of applying one of the formal system's derivation rules to earlier wffs in the sequence.Using formal logic to prove that \(Q\) is a valid conclusion from \(P_1, ..., P_n\), we must produce a proof sequence of the form:
\(P_1\) (hypothesis)
\(P_2\) (hypothesis)
.
.
.
\(P_n\) (hypothesis)
\(wff_1\) (obtained by applying a derivation rule to earlier wffs.)
\(wff_2\) (obtained by applying a derivation rule to earlier wffs.)
.
.
.
\(Q\) (obtained by applying a derivation rule to earlier wffs.)