Chapter 1: Formal Logic
Section 1.1 Statements, Symbolic Representation and Tautologies
Translating English Statements into Propositional Logic
Translating English Statements into Propositional Logic
| English Word | Logical Connective | Logical Expression |
|---|---|---|
| and; but; also; in addition; moreover | Conjunction | \(A ∧ B\) |
| or | Disjunction | \(A ∨ B\) |
| Either A or B, but not both A or B, but not both One of A or B A or B exclusively A and B are different |
Exclusive Disjunction | \(A ⊕ B\) |
| If A, then B. A implies B. A, therefore B. A only if B. B follows from A. A is a sufficient condition for B. B is a necessary condition for A |
Implication | \(A → B\) |
| A if and only if B. A is necessary and sufficient for B |
Equivalence | \(A ↔ B\) |
| not A. It is false that A ... It is not true that A ... |
Negation | \(A'\) |
Some Sample Propositions
A: There is a velociraptor outside my apartment.B: Velociraptors can open windows.
C: I am in my apartment right now.
D: My apartment has windows.
E: I am going to be eaten by a velociraptor.
Please translate the following English to propositional logic:
(1) I won't be eaten by a velociraptor if there isn't a velociraptor outside my apartment. ¬A → ¬E
The statement can be interpreted as:
If there is not a velociraptor outside my apartment, then I won't be eaten by a velociraptor.(2) If there is a velociraptor outside my apartment, but it can't open windows, I am not going to be eaten by a velociraptor. A ∧ ¬B → ¬E
The statement can be interpreted as:
If there is a velociraptor outside my apartment and it can't open windows, then I am not going to be eaten by a velociraptor.(3) I am only in my apartment when there are no velociraptors outside. C → ¬A
The statement can be interpreted as:
I am only in my apartment if there are no velociraptors outside.
More Examples
(1) Please rewrite the following each statement in if-then form:a. If the rain continues, then the river will flood.
b. A sufficient condition for network failure is that the central switch goes down.
c. The avocados are ripe only if they are dark and soft.
d. A good diet is a necessary condition for a healthy cat.
(2) Expressing the negation of a statement must be done with care, especially for a compound statement. Table 3 gives some examples.
| Table 3 | ||
|---|---|---|
| Statement | correct negation | Incorrect negation |
| It will rain tomorrow. | It is false that it will rain tomorrow. It will not rain tomorrow. |
|
| Peter is tall and thin. | It is false that Peter is tall and thin. Peter is not tall or he is not thin. Peter is short or fat. |
Peter is short and fat. Too strong a statement. Peter fails to have both properties (tallness and thinness) but may still have one property. |
| The river is shallow or polluted. | It is false that the river is shallow or polluted. The river is neither shallow nor polluted. The river is deep and unpolluted. |
The river is not shallow or not polluted. Too weak a statement. The river fails to have either property, not just fails to have one property. |
(3) Which of the following represents \( A' \) if \( A \) is the statement "Julie likes butter but hates cream"?
a. Julie hates butter and cream.
b. Julie does not like butter or cream.
c. Julie dislikes butter but loves cream.
d. Julie hates butter or likes cream.
Well-formed formula
Well-formed formula (wff)
An expression that is a legitimate string is called a well-formed formula or wff . A well-formed formula (wff) is a syntactically correct logical expression composed of propositions and logical connectives that follow the rules of propositional logic.A well-formed formula (WFF) is a key concept in formal logic, particularly in propositional logic. A well-formed formula is a syntactically correct arrangement of symbols and operators according to the rules of the logical system. It represents a meaningful expression within the system that can be evaluated as true or false.
It must be constructed using the allowed symbols (such as variables, logical connectives, and parentheses) in a way that adheres to the formation rules of that system. Parentheses are used in WFFs to indicate the order of operations and ensure that the formula is unambiguous.
For example:
\( (A → B)∧(B → A) \) is legal
\( A)) ∧∧ → B) \) is not legal
When evaluating well-formed formulas in propositional logic, it is important to follow a specific order of precedence to reduce the need for parentheses and ensure the correct interpretation of expressions. To reduce the number of parentheses required in a well-formed formula, we stipulate an order in which connectivies are applied. This order of precedence is:
1. connectives within parentheses, innermost parentheses first
2. not: ¬
3. and: ∧
4. or: ∨
5. xor: ⊕
6. implies: →
7: equivalence: ↔
This means that the expression \(A ∨ B'\) stands for \(A ∨ (B')\), not \((A ∨ B)'\). Similarly, \(A ∨ B → C\) means \((A ∨ B) → C\), not \(A ∨ (B → C)\). However, we often use parentheses anyway, just to be sure there is no confusion.
When multiple instances of the same logical connective appear in an expression, the default evaluation order is determined by the left-associative nature of the connective, meaning the expression is evaluated from left to right. If a different evaluation order is needed, parentheses can be used to explicitly specify the desired order.
main connective
In a wff with a number of connectives, the connective to be applied last is the main connective . In,the main connective is →. Capital letters near the end of the alphabet, such as \(P, Q, R, and S\) are used to represent wffs. Thus \(P\) could represent a single statement letter, which is the simplest kind of wff, or a more complex wff. We might represent
as
if we want to hide some of the details for the moment and only concentrate on the main connective.
Truth table for any wff
Wffs composed of statement letters and connectives have truth values that depend on the truth values assigned to their statement letters. We write the truth table for any wff by building up the component parts, just as we did for \((A → B) ∧ (B → A)\). The main connective is addressed in the last column of the table.The truth table for the wff \(A ∨ B' → (A ∨ B)'\) is given in Table 2. The main connective, acorrding to the rules of precedence, is implication (\(→\))
| Table 2 | ||||||
|---|---|---|---|---|---|---|
| A | B | B' | A ∨ B' | A ∨ B | (A ∨ B)' | A ∨ B' → (A ∨ B)' |
| T | T | F | T | T | F | F |
| T | F | T | T | T | F | F |
| F | T | F | F | T | F | T |
| F | F | T | T | F | T | T |
Practice Examples
Please construct truth tables for the following wffs.(1) (\(A → B\)) ↔ (B → A)
(2) \( (A ∨ A') → (B ∧ B') \)
(3) \( [(A ∧ B') → C']' \)
(4)\( (A → B) ↔ (B' → A') \)
Application
Here are just a few examples, spanning the entire range of computing applications, from practical to theory:Computer Networks:
• Firewall rules and access control lists are often based on propositional logic. Rules are defined using logical expressions to allow or deny traffic based on conditions like source IP, destination IP, and protocol.Example:
A firewall rule might state: "Allow traffic if it is from IP 192.168.1.1 AND it is using port 80." In propositional logic, this can be represented as IP = 192.168.1.1 AND Port = 80.
Artificial Intelligence
• In artificial intelligence, formal logic is sometimes used to simulate intelligent thought processes. People don't do their ordinary reasoning using mathematical logic, but logic is a convenient tool for implementing certain forms of reasoning. Propositional logic is used in AI search algorithms to represent and explore possible states in problem-solving scenarios.Example:
In a puzzle-solving AI, each possible move can be represented as a logical statement. The AI evaluates these statements to determine which moves lead to a solution.