Symbolic Logic
A proposition is a statement which can be classified as true or false.
Examples:
- Washington, D.C. is the capital of the United States of America
- The Thames is the longest river in the world
- 2 + 3 = 6
The first statement is true, while the second and third are false. They are all propositions because they can be evaluated as true or false.
The following are not propositions:
- Read this carefully (a command, and cannot be true or false)
- What are you doing? (a question, and cannot be true or false)
- A + B = C (an algebraic expression that needs further information to determine its truth value)
The truth value of a proposition is shown by T for true, and F for false.
Logical Operations
Propositions are commonly denoted by p and q, and we will use these symbols consistently throughout this page.
Conjunction: The proposition 'p and q' denoted by 'p ∧ q' is true when both p and q are true and is false otherwise. The proposition p ∧ q is called the conjunction of p and q.
| p | q | p ∧ q | |
|---|---|---|---|
| T | T | T | |
| T | F | F | |
| F | T | F | |
| F | F | F |
Example: Evaluating a Conjunction
The statement: "Today is the 21st day of the month of May."
The statement is true only if it is both the 21st day of the month, and the month is May.
The proposition is false if any of the following are true:
- It is not May, and it is not the 21st day of the month.
- It is the month of May but not the 21st day.
- It is the 21st day of the month but not the month of May.
Disjunction: The proposition 'p or q', denoted by 'p ∨ q' is the proposition that is false when p and q are both false and true otherwise. The proposition 'p ∨ q' is called disjunction.
| p | q | p ∨ q | |
|---|---|---|---|
| T | T | T | |
| T | F | T | |
| F | T | T | |
| F | F | F |
Example: Evaluating a Disjunction
Suppose:
- p: "It is a Sunday"
- q: "It is a rainy day"
The statement "p ∨ q" is true if it is Sunday, rainy, or both.
The statement is false only if it is neither Sunday nor rainy.
Negation: Let p be a proposition. 'Not p' is another proposition called Negation of p. The negation of p is denoted by ~p. The proposition ~p is read as 'not p'.
~p represents the opposite of the truth value of p
| p | ~p | |
|---|---|---|
| T | F | |
| F | T |
Example: Understanding Negation ~p
p is the proposition "Today is a Sunday".
The negation ~p is "Today is not a Sunday".
The negation can also be expressed as "It is not true that today is a Sunday".
Conditional Operator: The implication p→q is the proposition that is only false when p is true and q is false and true otherwise.
In this implication, p is called the hypothesis (or antecedent or premise) and q is called the conclusion (or consequence).
| p | q | p→q | |
|---|---|---|---|
| T | T | T | |
| T | F | F | |
| F | T | T | |
| F | F | T |
The proposition 'p implies q', written as 'p → q', is true except when p is true and q is false. It's like a promise that if the first thing (p) happens, then the second thing (q) will definitely happen. We sometimes simply say 'If p, then q'.
The proposition p→q is used a lot in mathematical reasoning, and is expressed in many ways, such as:
- If p, then q
- p implies q
- p only if q
- p is sufficient for q
- q if p
- q is necessary for p
Example: Conditional Statements
Examples:
- If ABC is a right-angled triangle with the right angle at A, then a2 = b2 + c2 (Pythagorean theorem)
- If x = y and y = z, then x = z
- If an integer is a multiple of 4, then it is even.
Let's dive more deeply into an example:
Example: Password (Conditional)
If the password is correct, then grant access.
Four possible cases:
- (TT) The password is correct and access is granted (what we expect)
- (TF) The password is correct but access is not granted (an error!)
- (FT) The password is incorrect but access is still granted (this seems wrong, but does not violate our conditional statement which is only about the true condition)
- (FF) The password is incorrect and access is denied (what we expect)
The FT case may seem strange, but read on about the biconditional below.
Biconditional operator: Let p and q be two propositions. The biconditional p↔q is the proposition that is true when p and q have the same truth values and is false otherwise.
| p | q | p↔q | |
|---|---|---|---|
| T | T | T | |
| T | F | F | |
| F | T | F | |
| F | F | T |
The biconditional p↔q is true when both p→q and q→p are true.
It is usually expressed as:
- p if and only if q
- p is necessary and sufficient for q
- 'if p then q' and conversely
Examples:
- Two lines are parallel if and only if they have the same slope.
- Two triangles are congruent if and only if they have the same size and shape, which means their corresponding sides and angles match.
Example: Password (Biconditional)
If and only if the password is correct, then grant access.
A biconditional relationship means that the 'if' and 'then' parts of the statement are both true or both false. Let's look at the same password scenario with this in mind:
- (TT) The password is correct and access is granted (what we expect)
- (TF) The password is correct but access is not granted (an error!)
- (FT) The password is incorrect but access is still granted (also an error!)
- (FF) The password is incorrect and access is denied (what we expect)
With the biconditional relationship, both the password being correct and access being granted are tightly linked: they must both happen or not happen together.
Converse, Inverse and Contrapositive.
The converse of a statement switches the hypothesis and conclusion. For example, the converse of 'If it rains, the ground gets wet' is 'If the ground gets wet, it rains.' This is not necessarily true because there are other reasons the ground could be wet.
Let p and q be two propositions. p→q is a conditional proposition. The proposition q→p is called the converse of the proposition p→q. The proposition ~p→~q is called the inverse of the proposition. The proposition ~q→~p is called the contrapositive of the proposition p→q.
| p |
q |
p→q Conditional |
q→p Converse |
~p → ~q Inverse |
~q → ~p Contrapositive |
|
|---|---|---|---|---|---|---|
| T | T | T | T | T | T | |
| T | F | F | T | T | F | |
| F | T | T | F | F | T | |
| F | F | T | T | T | T |
A conditional proposition and its inverse have different truth values in some cases. However, a conditional proposition and its contrapositive always share the same truth value, which makes them logically equivalent. This means they are either both true or both false under the same conditions
Example: Analyzing Implications
p: A is a square.
q: A is a rectangle.
- p → q: If A is a square, then A is a rectangle.
- q → p: If A is a rectangle, then A is a square.
The implication p → q is true, but q → p is false.
Example: Understanding Contrapositives
p: x2 is odd.
q: x is odd.
~p: x2 is even.
~q: x is even.
In logic, a contrapositive of a conditional statement "If p, then q" is "If ~q, then ~p." Importantly, a statement and its contrapositive are logically equivalent, meaning if one is true, so is the other.
Let's break it down:
- The original statement p → q means: "If x2 is odd (p), then x is odd (q)." This statement suggests that an odd square implies an odd base number.
- The contrapositive ~q → ~p means: "If x is even (~q), then x2 is even (~p)." This is logically equivalent to the original statement and is easier to see as true.
Why is the contrapositive easier to verify? Consider:
- If x is even, then multiplying it by itself keeps it even (e.g., 22 = 4, 4 is even).
- Thus, "If x is even, then x2 is even" is clearly true.
Therefore, since the contrapositive ~q → ~p is true, the original proposition p → q is also true by logical equivalence.
Tautology and Contradiction
A compound proposition that is always true, no matter what the truth values of the propositions that occur is called Tautology.
A compound proposition that is always false is called a Contradiction.
A proposition that is neither tautology nor a contradiction is called Contingency.
Example: Tautology
The statement 'It is raining or it is not raining' is a tautology because it is always true.
Example: Contradiction
The statement 'A square is a circle' is a contradiction because it is always false.