Discrete Mathematics : Propositional Logic
Logic models reasoning
Puzzle: A beautiful princess and an intelligent philosopher were in love. After learning the relationship between the princess and the philosopher, the king vowed to give the philosopher a death sentence. The next day, the philosopher was brought to the court. The king asked the philosopher to give one sentence.The death options for the philosopher were as follows:
- If the sentence is true, then he would be hanged.
- If the sentence is false, then he would be beheaded.
- If the sentence cannot be assigned a truth value, then he would be fed to lions.
- If the sentence is inherently self-contradictory, then he would be shot with an arrow.
- If the sentence is an unproven mathematical statement, then he would be left to die from starvation.
- If the sentence is not stated within ten minutes, then he would be poisoned.
- If the sentence cannot be understood easily, then he would thrown from a tall mountain.
The philosopher was ready to face death for his love. He used his extraordinary philosophic acumen and came up with a sentence. The sentence is so profound that the king let the philosopher free, united the princess and the philosopher, and finally made the philosopher his successor to the throne.
What was the philosopher’s sentence?
What is logic?
Logic is a branch of mathematics that deals with the verification of truth/falsity of mathematical statements/assertions.Scope: Study of valid arguments, inference (induction + deduction), proofs, proof techniques, proving theorems, and, paradoxes and fallacies.
Why care for logic?
- [Everyday life.]
To reduce problems caused by ignorance. - [Philosophy.]
Logic models reasoning.
“Why study logic?” = “Why know truth?” - [Remove ambiguity.]
English is ambiguous:- “The cat chased the mouse until it fell.”
- “My mother never made cake, which we hated.”
- “Let’s stop controlling people.”
- “Time flies like an arrow, fruit flies like a peanut.”
(Can you think of some examples for ambiguous math statements or computer programs?) - [Mathematics.]
To prove theorems. - [Computer science.]
- To prove correctness of software/hardware.
- Used in computer circuit design.
- Used in modeling programming languages.
- Used in the design of expert systems, robots, and artificial intelligence.
What is a statement?
A statement or proposition is a sentence for which a truth value (either true or false) can be assigned.Classes of statements:
- True statements. “The atomic number of Oxygen is 8.”
- False statements. $1 + 1 = 3$
- Not propositions.
$x + y = 5$
$A \times B = 0$ implies $A = 0$ or $B = 0$
Natasha is beautiful. - Truth value currently unknown. Goldbach’s conjecture.
- Truth values change with time/scenarios. “Today is Sunday.” written on a paper slip.
- Logical paradoxes. “This statement is false.”.
- $x+y=5$.
Not a proposition - $x+y=5$ for some real numbers $x$ and $y$.
True proposition - $x+y=5$ for all real numbers $x$ and $y$.
False proposition
What is a propositional variable?
A propositional variable is a lowercase letter such as $p$, $q$, or $r$ used to represent a proposition.A propositional variable can be true (T) or false (F)
Algebra uses numeric variables; Logic uses propositional variables
What is a compound statement?
A compound statement is a complex sentence that is obtained by joining propositional variables using logical connectives.| Logical operator | Notation | Read as |
|---|---|---|
| Negation | $\sim p$ | not p |
| Conjunction | $p \land q$ | $p$ and $q$ |
| Disjunction | $p \lor q$ | $p$ or $q$ |
| Conditional | $p \rightarrow q$ | if $p$, then $q$ |
| Biconditional | $p \leftrightarrow q$ | $p$ if and only if $q$ |
Negation ($\sim p$)
Negation of a statement $p$, denoted by $\sim p$, is a statement obtained by changing the truth value of $p$.| $p$ | $\sim p$ |
|---|---|
| $T$ | $F$ |
| $F$ | $T$ |
Examples:
$p$ : “$x$ is a real number such that $x < 4$.”
$\sim p$ : “$x$ is a real number such that $x \ge 4$.”
Conjunction ($p \land q$)
Conjunction of statements $p$ and $q$, denoted by $p \land q$, is a statement such that it is true if both $p$ and $q$ are true and it is false, otherwise.| $p$ | $q$ | $p \land q$ |
|---|---|---|
| $T$ | $T$ | $T$ |
| $T$ | $F$ | $F$ |
| $F$ | $T$ | $F$ |
| $F$ | $F$ | $F$ |
Examples:
$p$ : “I will get an accept from MIT.”
$q$ : “I will get an accept from Stanford.”
$p \land q$ : “I will get accepts from both MIT and Stanford.”
Disjunction ($p \lor q$)
Disjunction of statements $p$ and $q$, denoted by $p \lor q$, is a statement such that it is false if both $p$ and $q$ are false and it is true, otherwise.| $p$ | $q$ | $p \land q$ |
|---|---|---|
| $T$ | $T$ | $T$ |
| $T$ | $F$ | $F$ |
| $F$ | $T$ | $F$ |
| $F$ | $F$ | $F$ |
Examples:
$p$ : “I will get an accept from MIT.”
$q$ : “I will get an accept from Stanford.”
$p \lor q$ : “I will get an accept from MIT or Stanford.”
Exclusive or ($p \oplus q$)
Exclusive or of statements $p$ and $q$, denoted by $p \oplus q$, is defined as $p$ or $q$ but not both. It is computed as $(p \lor q) \land \sim (p \land q)$.| $p$ | $q$ | $p \lor q$ | $p \land q$ | $\sim (p \land q)$ | $p \oplus q \equiv (p \lor q) \land \sim (p \land q)$ |
|---|---|---|---|---|---|
| $T$ | $T$ | $T$ | $T$ | $F$ | $F$ |
| $T$ | $F$ | $T$ | $F$ | $T$ | $T$ |
| $F$ | $T$ | $T$ | $F$ | $T$ | $T$ |
| $F$ | $F$ | $F$ | $F$ | $T$ | $F$ |
Examples:
$p$ : “I will get admitted to MIT.”
$q$ : “I will get admitted to Stanford.”
$p \oplus q$ : “I will get admitted to MIT or Stanford.”
What is a statement form?
Statement form or propositional form is a compound statement with propositional variables (such as $p$, $q$, $r$) and logical connectives (such as $\sim$, $\land$, $\lor$).| $p$ | $q$ | $p \lor q$ | $p \land q$ | $\sim (p \land q)$ | $p \oplus q \equiv (p \lor q) \land \sim (p \land q)$ |
|---|---|---|---|---|---|
| $T$ | $T$ | $T$ | $T$ | $F$ | $F$ |
| $T$ | $F$ | $T$ | $F$ | $T$ | $T$ |
| $F$ | $T$ | $T$ | $F$ | $T$ | $T$ |
| $F$ | $F$ | $F$ | $F$ | $T$ | $F$ |
Examples:
$(p \lor q) \land \sim( \sim p \land r)$
$(\sim p \land q \land r) \lor (q \lor \sim r)$
Precedance of logical operators
| Priority | Operator | Comments |
|---|---|---|
| 1 | $\sim$ | Evaluate $\sim$ first |
| 2 | $\land$ $\lor$ | Evaluate $\land$ and $\lor$ next; Use parenthesis to avoid ambiguity |
| 3 | $\rightarrow$ $\leftrightarrow$ | Evaluate $\rightarrow$ and $\leftrightarrow$ next; Use parenthesis to avoid ambiguity |
| 4 | $\equiv$ | Evaluate $\equiv$ last |
What is logical equivalence ($p \equiv q$)?
Two statement forms $p$ and $q$ are logically equivalent, denoted by $p \equiv q$, if and only if they have the same truth values for all possible combination of truth values for the propositional variables.Construct truth tables to check logical equivalence
Logical equivalence: Example
| $p$ | $q$ | $r$ | $q \lor r$ | $p \land q$ | $p \land (q \lor r)$ | $(p \land q) \lor r$ |
|---|---|---|---|---|---|---|
| $T$ | $T$ | $T$ | $T$ | $T$ | $T$ | $T$ |
| $T$ | $T$ | $F$ | $T$ | $T$ | $T$ | $T$ |
| $T$ | $F$ | $T$ | $T$ | $F$ | $T$ | $T$ |
| $T$ | $F$ | $F$ | $F$ | $F$ | $F$ | $F$ |
| $F$ | $T$ | $T$ | $T$ | $F$ | $F$ | $T$ |
| $F$ | $T$ | $F$ | $T$ | $F$ | $F$ | $F$ |
| $F$ | $F$ | $T$ | $T$ | $F$ | $F$ | $T$ |
| $F$ | $F$ | $F$ | $F$ | $F$ | $F$ | $F$ |
$6$th and $7$th columns are different at rows $5$ and $7$.
So, $p \land (q \lor r) \not\equiv (p \land q) \lor r$.
Logical equivalence: Example
| $p$ | $q$ | $r$ | $q \lor r$ | $p \land q$ | $p \land r$ | $p \land (q \lor r)$ | $(p \land q) \lor (p \land r)$ |
|---|---|---|---|---|---|---|---|
| $T$ | $T$ | $T$ | $T$ | $T$ | $T$ | $T$ | $T$ |
| $T$ | $T$ | $F$ | $T$ | $T$ | $F$ | $T$ | $T$ |
| $T$ | $F$ | $T$ | $T$ | $F$ | $T$ | $T$ | $T$ |
| $T$ | $F$ | $F$ | $F$ | $F$ | $F$ | $F$ | $F$ |
| $F$ | $T$ | $T$ | $T$ | $F$ | $F$ | $F$ | $F$ |
| $F$ | $T$ | $F$ | $T$ | $F$ | $F$ | $F$ | $F$ |
| $F$ | $F$ | $T$ | $T$ | $F$ | $F$ | $F$ | $F$ |
| $F$ | $F$ | $F$ | $F$ | $F$ | $F$ | $F$ | $F$ |
$7$th and $8$th columns are the same.
So, $p \land (q \lor r) \equiv (p \land q) \lor (p \land r)$.
What are tautology and contradiction?
A tautology is a statement form that is always true regardless of the truth values of the individual statements substituted for its statement variables.A contradication is a statement form that is always false regardless of the truth values of the individual statements substituted for its statement variables.
Examples:
$p \lor \sim p$ is tautology
$p \land \sim p$ is contradiction
Logical equivalences
| Laws | Formula | Formula |
|---|---|---|
| Commutative laws | $p \land q \equiv q \land p$ | $p \lor q \equiv q \lor p$ |
| Associative laws | $(p \land q) \land r \equiv p \land (q \land r)$ | $(p \lor q) \lor r \equiv p \lor (q \lor r)$ |
| Distributive laws | $p \land (q \lor r) \equiv (p \land q) \lor (p \land r)$ | $p \lor (q \land r) \equiv (p \lor q) \land (p \lor r)$ |
| Identity laws | $p \land \mathbf{t} \equiv p$ | $p \lor \mathbf{c} \equiv p$ |
| Negation laws | $p \land \sim p \equiv \mathbf{t}$ | $p \lor \sim p \equiv \mathbf{c}$ |
| Double negation law | $\sim(\sim p) \equiv p $ | |
| Idempotent laws | $p \land p \equiv p$ | $p \lor p \equiv p$ |
| Uni. bound laws | $p \land \mathbf{t} \equiv \mathbf{t}$ | $p \lor \mathbf{c} \equiv \mathbf{c}$ |
| De Morgan’s laws | $\sim (p \land q) \equiv \sim p \lor \sim q$ | $\sim (p \lor q) \equiv \sim p \land \sim q$ |
| Absorption laws | $p \land (p \lor q) \equiv p$ | $p \lor (p \land q) \equiv p$ |
| Negations | $\sim \mathbf{t} \equiv \mathbf{c}$ | $\sim \mathbf{c} \equiv \mathbf{t}$ |
Conditional statement ($p \rightarrow q$)
Conditional or implication is a compound statement of the form “if $p$, then $q$”. It is denoted by $p \rightarrow q$ and read as “$p$ implies $q$”. It is false when $p$ is true and $q$ is false, and it is true, otherwise.
| $p$ | $q$ | $p \rightarrow q$ |
|---|---|---|
| $T$ | $T$ | $T$ |
| $T$ | $F$ | $F$ |
| $F$ | $T$ | $T$ |
| $F$ | $F$ | $T$ |
Examples:
“If $b^2 − 4ac > 0$, then $ax^2 + bx + c = 0$ has two distinct real solutions.”
Write “All polynomials are differentiable.” as an implication: “If $P$ is a polynomial, then $P$ is differentiable.”
In $p \rightarrow q$,
$p$ is called hypothesis/premise/antecendent, and
$q$ is called conclusion/consequence.
$p \rightarrow q$ is called conditional because the truth of $q$ is conditioned upon the truth of $p$
$p \rightarrow q$ is also called:
| “if $p$, then $q$” “$p$ only if $q$” “$q$ follows from $p$” “not $p$ unless $q$” “$p$ is sufficient for $q$” “$q$ is necessary for $p$” | “$p$ implies $q$” “if $p$, $q$” “$q$, provided that $p$” “$q$ if/when/whenever $q$” “a sufficient condition for $q$ is $p$” “a necessary condition for $p$ is $q$” |
Conditional statement is like a promise
Under what circumstances is the promise kept/broken?
Example: A father promises his kids,
“If tomorrow is sunny, we will go to the beach.”
| $p$ | $q$ | $p \rightarrow q$ |
|---|---|---|
| Tomo is sunny | Go to the beach | Promise is kept ($T$) |
| Tomo is sunny | Did not go to the beach | Promise is broken ($F$) |
| Tomo is not sunny | Go to the beach | Promise is not broken ($T$) |
| Tomo is not sunny | Did not go to the beach | Promise is not broken ($T$) |
$p \rightarrow q$ being true because $p$ is false is called vacuously true or true by default
Contrapositive, converse, and inverse
Contrapositive of $p \rightarrow q$ is $\sim q \rightarrow \sim p$
Converse of $p \rightarrow q$ is $q \rightarrow p$
Inverse of $p \rightarrow q$ is $\sim p \rightarrow \sim q$
Identities:
Conditional $\equiv$ Contrapositive
Conditional $\not\equiv$ Converse
Conditional $\not\equiv$ Inverse
Converse $\equiv$ inverse
Formulas:
$(p \rightarrow q) \equiv (\sim q \rightarrow \sim p)$
$(p \rightarrow q) \not\equiv (q \rightarrow p)$
$(p \rightarrow q) \not\equiv (\sim p \rightarrow \sim q)$
$(q \rightarrow p) \equiv (\sim p \rightarrow \sim q)$
Conditional ≡ Contrapositive.
“If tomorrow is sunny, we will go to the beach.”
“If we don’t go to the beach tomorrow, then it is not sunny.”
Converse ≡ Inverse.
“If we go to the beach tomorrow, then it is sunny.”
“If tomorrow is not sunny, then we will not go to the beach.”
Conditional ≡ Contrapositive.
| “If $x > 2$, then $x^2 > 4$.” | ◃ true |
|---|---|
| “If $x^2 ≤4$, then $x ≤2$.” | ◃ true |
Converse ≡ Inverse.
| “If $x^2 > 4$, then $x > 2$.” | ◃ false |
|---|---|
| “If $x ≤2$, then $x^2 ≤4$.” | ◃ false |
Sufficient condition, necessary condition, and only if
$p$ is a sufficient condition for $q$ means if $p$ then $q$
$p$ is a necessary condition for $q$ means if $\sim p$ then $\sim q$, which is equivalent to if $q$ then $p$
$p$ only if $q$ means if $\sim q$ then $\sim p$, which is equivalent to if $p$ then $q$
Example
For real $x$, $x = 1$ is a sufficient condition for $x^2 = 1$ i.e., If $x = 1$ then $x^2 = 1$ ◃ true
For real $x$, $x^2 = 1$ is a necessary condition for $x = 1$ i.e., If $x^2 \neq 1$ then $x \neq 1$ ◃ true
For real $x$, $x = 1$ only if $x^2 = 1$ i.e., If $x^2 \neq 1$, then $x \neq 1$ ◃ true
Biconditional statement ($p \leftrightarrow q$)
The biconditional of $p$ and $q$ is of the form “$p$ if and only if $q$” and is denoted by $p \leftrightarrow q$. It is true when $p$ and $q$ have the same truth value, and it is false, otherwise. That is, $p \leftrightarrow q$ ≡ $(p\rightarrow q) \land (q \rightarrow p)$
| $p$ | $q$ | ($p\rightarrow q$) | ($q \rightarrow p$) | ($p\rightarrow q$) ∧($q \rightarrow p$) |
|---|---|---|---|---|
| $T$ | $T$ | $T$ | $T$ | $T$ |
| $T$ | $F$ | $F$ | $T$ | $F$ |
| $F$ | $T$ | $T$ | $F$ | $F$ |
| $F$ | $F$ | $T$ | $T$ | $T$ |
Examples:
Assume $x$ and $y$ are real numbers.
“$x^2 + y^2 = 0$ if and only if $x = 0$ and $y = 0$.”
A polygon is a triangle if and only if it has exactly three sides.”
Logical Arguments
What is a logical argument?
Definitions:
Logical argument. Sequence of statements aimed at demonstrating the truth of an assertion
Conclusion. Last statement in an argument
Premises. Last-but-one statements in an argument
Formal logic. The framework for determining the validity or invalidity of arguments
Proof/Derivation/Logical deduction. A valid sequence of statements used for establishing new mathematical truths (or conclusions or propositions or theorems) from acceptable/established mathematical truths (premises or axioms or assumptions)
Argument
Premise1
Premise2
.
.
.
Premisem
∴ Conclusion
If Premise1 and Premise2 and··· and Premisem, then Conclusion.
What is a valid argument?
An argument is valid if the conclusion follows necessarily from the premises. An argument is invalid if the conclusion does not follow necessarily from the premises.
Example 1:
- Socrates is a man, then Socrates is mortal.
Socrates is a man.
Therefore, Socrates is mortal. ◃ Valid argument - If Socrates is a man, then Socrates is mortal.
Socrates is mortal.
Therefore, Socrates is a man. ◃ Invalid argument - If Socrates is a man, then Socrates is mortal.
Socrates is not mortal.
Therefore, Socrates is not a man. ◃ Valid argument - If Socrates is a man, then Socrates is mortal.
Socrates is not a man.
Therefore, Socrates is not mortal. ◃ Invalid argument
Example 2:
- If it is raining, then it is cloudy.
It is raining.
Therefore, it is cloudy. ◃ Valid argument - If it is raining, then it is cloudy.
It is cloudy.
Therefore, it is raining. ◃ Invalid argument - If it is raining, then it is cloudy.
It is not cloudy.
Therefore, it is not raining. ◃ Valid argument - If it is raining, then it is cloudy.
It is not raining.
Therefore, it is not cloudy. ◃ Invalid argument
Example 3:
- If $x > 2$, then $x^2 > 4$.
$x > 2$.
Therefore, $x^2 > 4$. ◃ Valid argument - If $x > 2$, then $x^2 > 4$.
$x^2 > 4$.
Therefore, $x > 2$. ◃ Invalid argument - If $x > 2$, then $x^2 > 4$.
$x^2 \le 4$.
Therefore, $x \le 2$. ◃ Valid argument - If $x > 2$, then $x^2 > 4$.
$x \le 2$.
Therefore, $x^2 \le 4$. ◃ Invalid argument
General format:
- If $p$, then $q$.
$p$.
Therefore, $q$. ◃ Valid argument - If $p$, then $q$.
$q$.
Therefore, $p$. ◃ Invalid argument - If $p$, then $q$.
$\sim q$.
Therefore, $\sim p$. ◃ Valid argument - If $p$, then $q$.
$\sim p$.
Therefore, $\sim q$. ◃ Invalid argument
How to determine if an argument is valid/invalid?
Use truth tables
- Identify the premises and conclusion
- Construct a truth table for premises and conclusion
- A row of the truth table in which all the premises are true is called a critical row.
- If there is a critical row in which the conclusion is false, then the argument is invalid.
- If the conclusion in every critical row is true, then the argument is valid.
Determine the validity of the argument:
$p \rightarrow q \vee ∼r$
$q \rightarrow p \wedge r$
∴ $p \rightarrow r$
| $p$ | $q$ | $r$ | $∼r$ | $q \vee \sim r$ | $p \wedge r$ | $p \rightarrow (q \vee \sim r)$ | $q \rightarrow (p \wedge r)$ | $p \rightarrow r$ |
|---|---|---|---|---|---|---|---|---|
| $T$ | $T$ | $T$ | $F$ | $T$ | $T$ | $T$ | $T$ | $T$ |
| $T$ | $T$ | $F$ | $T$ | $T$ | $F$ | $T$ | $F$ | |
| $T$ | $F$ | $T$ | $F$ | $F$ | $T$ | $F$ | $T$ | |
| $T$ | $F$ | $F$ | $T$ | $T$ | $F$ | $T$ | $T$ | $F$ |
| $F$ | $T$ | $T$ | $F$ | $T$ | $F$ | $T$ | $F$ | |
| $F$ | $T$ | $F$ | $T$ | $T$ | $F$ | $T$ | $F$ | |
| $F$ | $F$ | $T$ | $F$ | $F$ | $F$ | $T$ | $T$ | $T$ |
| $F$ | $F$ | $F$ | $T$ | $T$ | $F$ | $T$ | $T$ | $T$ |
4th row (a critical row) has false conclusion. Invalid argument.
What is a rule of inference?
A rule of inference is a valid argument form that can be used to establish logical deductions
| Name | Rule | Name | Rule | |
|---|---|---|---|---|
| Modus Ponens | $p \rightarrow q$ $p$ $\therefore q$ | Elimination | $p \vee q$ $\sim q$ $\therefore p$ | $p \vee q$ $\sim p$ $\therefore q$ |
| Modus Tollens | $p \rightarrow q$ $\sim q$ $\therefore \sim p$ | Transitivity | $p \rightarrow q$ $q \rightarrow r$ $\therefore p \rightarrow r$ | |
| Proof by division into cases | $p \vee q$ $p \rightarrow r$ $q \rightarrow r$ $\therefore r$ | Generalization Specialization | $p$ $\therefore p \vee q$ $p \wedge q$ $\therefore p$ | $q$ $\therefore p \vee q$ $p \wedge q$ $\therefore q$ |
| Conjunction | $p$ $q$ $\therefore p \wedge q$ | Contradiction | $\sim p \rightarrow c$ $\therefore p$ |
What is a syllogism?
A syllogism is a rule of inference with two premises and a conclusion.
Argument:
Premise1 (Major premise)
Premise2 (Minor premise)
∴ Conclusion
Examples:
- Modus ponens
- Modus tollens
Rule of inference: Modus ponens
It has the form:
If $p$, then $q$
$p$
∴ $q$
The term modus ponens in Latin means “method of affirming”
| $p$ | $q$ | $p \rightarrow q$ | $p$ | $q$ |
|---|---|---|---|---|
| $T$ | $T$ | $T$ | $T$ | $T$ |
| $T$ | $F$ | $F$ | $T$ | |
| $F$ | $T$ | $T$ | $F$ | |
| $F$ | $F$ | $T$ | $F$ |
Example:
If the sum of the digits of 371,487 is divisible by 3, then 371,487 is divisible by 3.
The sum of the digits of 371,487 is divisible by 3.
∴ 371,487 is divisible by 3.
Rule of inference: Modus tollens
It has the form:
If $p$, then $q$
$~q$
∴$~p$
The term modus tollens in Latin means “method of denying”
| $p$ | $q$ | $p \rightarrow q$ | $\sim q$ | $\sim p$ |
|---|---|---|---|---|
| $T$ | $T$ | $T$ | $F$ | |
| $T$ | $F$ | $F$ | $T$ | |
| $F$ | $T$ | $T$ | $F$ | |
| $F$ | $F$ | $T$ | $T$ | $T$ |
Example:
If Zeus is human, then Zeus is mortal.
Zeus is not mortal.
∴ Zeus is not human.
Rule of inference: Generalization
It has the form:
$p$
∴ $p \vee q$
| $p$ | $q$ | $p$ | $p \vee q$ |
|---|---|---|---|
| $T$ | $T$ | $T$ | $T$ |
| $T$ | $F$ | $T$ | $T$ |
| $F$ | $T$ | $F$ | |
| $F$ | $F$ | $F$ |
Example:
35 is odd.
∴ (more generally) 35 is odd or 35 is even.
Rule of inference: Specialization
It has the form:
$p \wedge q$
$\therefore p$
| $p$ | $q$ | $p \wedge q$ | $p$ |
|---|---|---|---|
| $T$ | $T$ | $T$ | $T$ |
| $T$ | $F$ | $F$ | |
| $F$ | $T$ | $F$ | |
| $F$ | $F$ | $F$ |
Example:
Ana knows numerical analysis and Ana knows graph algorithms.
∴ (in particular) Ana knows graph algorithms
Rule of inference: Conjunction
It has the form:
$p$
$q$
∴ $p \wedge q$
| $p$ | $q$ | $p \wedge q$ |
|---|---|---|
| $T$ | $T$ | $T$ |
| $T$ | $F$ | |
| $F$ | $T$ | |
| $F$ | $F$ |
Example:
Lily loves mathematics.
Lily loves algorithms.
∴ Lily loves both mathematics and algorithms.
Rule of inference: Elimination
It has the form:
$p \vee q$
$\sim q$
$\therefore p$
Intuition: When you have only two possibilities and you can rule one out, the other must be the case
| $p$ | $q$ | $p \vee q$ | $\sim q$ | $p$ |
|---|---|---|---|---|
| $T$ | $T$ | $T$ | $F$ | |
| $T$ | $F$ | $T$ | $T$ | $T$ |
| $F$ | $T$ | $T$ | $F$ | |
| $F$ | $F$ | $F$ | $T$ |
Example:
Suppose $x-3 = 0$ or $x + 2 = 0$.
Also, suppose $x$ is nonnegative.
∴ $x$ = 3.
Rule of inference: Transitivity
It has the form:
$p \rightarrow q$
$q \rightarrow r$
$\therefore p \rightarrow r$
Can be generalized to a chain with any number of conditionals
Example:
If 18,486 is divisible by 18, then 18,486 is divisible by 9.
If 18,486 is divisible by 9, then the sum of the digits of 18,486 is divisible by 9.
∴ If 18,486 is divisible by 18, then the sum of the digits of 18,486 is divisible by 9.
Rule of inference: Division into cases
It has the form:
$p \vee q$
$p \rightarrow r$
$q \rightarrow r$
$\therefore r$
Example:
$x$ is positive or $x$ is negative.
If $x$ is positive, then $x^2 > 0$.
If $x$ is negative, then $x^2 > 0$.
∴ $x^2 > 0$.
Rule of inference: Contradiction rule
It has the form:
$\sim p \rightarrow c$
$\therefore p$
Intuition: If an assumption leads to a contradiction, then that assumption must be false
Extensively used in a proof technique called proof by contradiction.
| $p$ | $\sim p$ | $c$ | $\sim p \rightarrow c$ | $p$ |
|---|---|---|---|---|
| $T$ | $F$ | $F$ | $T$ | $T$ |
| $F$ | $T$ | $F$ | $F$ |
What is a fallacy?
A fallacy is an error in reasoning that results in an invalid argument
Types:
1. Using ambiguous premises, and treating them as if they were unambiguous
2. Circular reasoning (assuming what is to be proved without having derived it from the premises)
3. Jumping to a conclusion (without adequate grounds)
4. Converse error
5. Inverse error
Fallacy: Converse error
It has the form:
$p \rightarrow q$
$q$
$\therefore p$
Intuition: A conditional is not equivalent to its converse
Also known as the fallacy of affirming the consequent
Superficially resembles modus ponens but is invalid
| $p$ | $q$ | $p \rightarrow q$ | $q$ | $p$ |
|---|---|---|---|---|
| $T$ | $T$ | $T$ | $T$ | $T$ |
| $T$ | $F$ | $F$ | $F$ | $T$ |
| $F$ | $T$ | $T$ | $T$ | $F$ |
| $F$ | $F$ | $T$ | $F$ | $F$ |
Example:
If $x > 2$, then $x^2 > 4$.
$x^2 > 4$.
∴ $x > 2$.
Fallacy: Inverse error
It has the form:
$p \rightarrow q$
$\sim p$
$\therefore \sim q$
Intuition: A conditional is not equivalent to its inverse
Also known as the fallacy of denying the antecedent
Superficially resembles modus tollens but is invalid
| $p$ | $q$ | $p \rightarrow q$ | $\sim p$ | $\sim q$ |
|---|---|---|---|---|
| $T$ | $T$ | $T$ | $F$ | $F$ |
| $T$ | $F$ | $F$ | $F$ | $T$ |
| $F$ | $T$ | $T$ | $T$ | $F$ |
| $F$ | $F$ | $T$ | $T$ | $T$ |
Example
If $x > 2$, then $x^2 > 4$.
$x \leq 2$.
∴ $x^2 \leq 4$.
Validity $\ne$ Truthfulness; Invalidity $\ne$ Falsity
- A valid argument can have a false conclusion
- An invalid argument can have a true conclusion
Examples:
Valid argument with false conclusion (Modus ponens)
If Isaac Newton was a scientist, then Albert Einstein was not a scientist.
Isaac Newton was a scientist.
∴ Albert Einstein was not a scientist.
Invalid argument with true conclusion (Converse error)
If New York is a big city, then New York has tall buildings.
New York has tall buildings.
∴ New York is a big city.
What is a sound argument?
A sound argument is an argument that is valid and has true premises
Validity shows that an argument is logical
Soundness shows that an argument is truthful
Examples:
Valid argument with true premises (Modus ponens)
If Isaac Newton was a scientist, then Albert Einstein was a scientist.
Isaac Newton was a scientist.
∴ Albert Einstein was a scientist.
Example: Where are my glasses?
You are about to leave for school in the morning and discover that you don’t have your glasses. You know the following statements are true:
(a) If I was reading the newspaper in the kitchen, then my glasses are on the kitchen table.
(b) If my glasses are on the kitchen table, then I saw them at breakfast.
(c) I did not see my glasses at breakfast.
(d) I was reading the newspaper in the living room or I was reading the newspaper in the kitchen.
(e) If I was reading the newspaper in the living room then my glasses are on the coffee table.
Where are the glasses?
Let:
RK = I was reading the newspaper in the kitchen.
GK = My glasses are on the kitchen table.
SB = I saw my glasses at breakfast.
RL = I was reading the newspaper in the living room.
GC = My glasses are on the coffee table.
Given statements:
(a) RK $\rightarrow$ GK
(b) GK $\rightarrow$ SB
(c) ~SB
(d) RL $\vee$ RK
(e) RL $\rightarrow$ GC
Sequence of steps to draw the conclusion:
1. RK $\rightarrow$ GK ◃ by (a)
GK $\rightarrow$ SB ◃ by (b)
$\therefore$ RK $\rightarrow$ SB ◃ by transitivity
2. RK $\rightarrow$ SB ◃ by the conclusion of (1)
~ SB ◃ by ($c$)
$\therefore$ ~ RK ◃ by modus tollens
3. RL $\vee$ RK ◃ by (d)
~ RK ◃ by the conclusion of (2)
$\therefore$ RL ◃ by elimination
4. RL $\rightarrow$ GC ◃ by (e)
RL ◃ by the conclusion of (3)
$\therefore$ GC ◃ by modus ponens
Thus, the glasses are on the coffee table.
Example: Truth tellers and liars
There is an island containing two types of people: truth tellers who always tell the truth and liars who always lie. You visit the island and are approached by two natives who speak to you as follows:
A says: B is a truth teller.
B says: A and I are of opposite type.
What are A and B?
Suppose $A$ is a truth teller.
$\therefore$ What $A$ says is true. ▷ by definition of truth teller
$\therefore$ $B$ is also a truth teller. ▷ That’s what $A$ said.
$\therefore$ What $B$ says is true. ▷ by definition of truth teller
$\therefore$ $A$ and $B$ are of opposite types. ▷ That’s what $B$ said.
$\therefore$ Contradiction: $A$ and $B$ are both truth tellers and $A$ and $B$ are of opposite type.
$\therefore$ Initial assumption is false. ▷ by the contradiction rule
$\therefore$ $A$ is not a truth teller. ▷ negation of assumption
$\therefore$ $A$ is a liar. ▷ by elimination: All inhabitants are truth tellers or liars, so since $A$ is not a truth teller, $A$ is a liar.
$\therefore$ What $A$ says is false.
$\therefore$ $B$ is not a truth teller.
$\therefore$ $B$ is also a liar. ▷ by elimination
$\therefore$ Final answer: $A$ and $B$ are both liars
Digital Logic Circuits
Idea: Circuits and logic are related
Series circuit = AND
| Switches | Light bulb | |
|---|---|---|
| $P$ | $Q$ | State |
| closed | closed | on |
| closed | open | off |
| open | closed | off |
| open | open | off |
Parallel circuit = OR
| Switches | Light bulb | |
|---|---|---|
| $P$ | $Q$ | State |
| closed | closed | on |
| closed | open | on |
| open | closed | on |
| open | open | off |
Birth of digital logic circuits
History
- 1930s: Physical switches were used in circuit design. (Physical states: closed and open)
- Late 1930s: Great idea that mathematical logic (or logical algebra) can be used to analyze switches
- 1940s and 1950s: Electronic switcheswere used in circuit design. (Electronic states: high and low)
Application
- This technology led to the development of electronic computers, electronic telephone switching systems, traffic light controls, electronic calculators, and the control mechanisms
- Electronic switches to implement logic is the fundamental concept that underlies all electronic digital computers.
Complicated logic gates as black boxes
| Input | Output | ||
|---|---|---|---|
| $P$ | $Q$ | $R$ | $S$ |
| 1 | 1 | 1 | 1 |
| 1 | 1 | 0 | 0 |
| 1 | 0 | 1 | 1 |
| 1 | 0 | 0 | 1 |
| 0 | 1 | 1 | 0 |
| 0 | 1 | 0 | 0 |
| 0 | 0 | 1 | 0 |
| 0 | 0 | 0 | 0 |
A black box focuses on the functionality and ignores the hardware implementation details
Simple logic gates
Complicated logic gates can be built using a collection of simple logic gates such as NOT-gate, AND-gate, and OR-gate
NOT-Gate: $R \equiv \sim P$
| Input | Output |
|---|---|
| $P$ | $R$ |
| 1 | 0 |
| 0 | 1 |
AND-Gate: $R \equiv P \wedge Q$
| Input | Output | |
|---|---|---|
| $P$ | $Q$ | $R$ |
| 1 | 1 | 1 |
| 1 | 0 | 0 |
| 0 | 1 | 0 |
| 0 | 0 | 0 |
OR-Gate: $R \equiv P \vee Q$
| Input | Output | |
|---|---|---|
| $P$ | $Q$ | $R$ |
| 1 | 1 | 1 |
| 1 | 0 | 1 |
| 0 | 1 | 1 |
| 0 | 0 | 0 |
What is a combinational circuit
A combinational circuit is a circuit designed by combining logic gates such that the output at any given time depends only on the input at that time and not on previous inputs.
Rules
1. Never combine two input wires.
2. A single input wire can be split partway and used as input for two separate gates.
3. An output wire can be used as input.
4. No output of a gate can eventually feed back into that gate.
Other types of circuits
1. A sequential circuit violates the 4th rule and hence its output depends on previous inputs, too.
Problem-solving in digital logic circuits
Problem: Circuit $\rightarrow$ Table
Solution:
1. Logic circuit $\rightarrow$ Logical expression
2. Simplify logical expression
3. Logical expression $\rightarrow$ Input-output table
Problem: Table $\rightarrow$ Circuit
Solution
1. Input-output table $\rightarrow$ Logical expression
2. Simplify logical expression
3. Logical expression $\rightarrow$ Logic circuit
Circuit $\rightarrow$ Table
Determine the input-output table for the given logic circuit.
Solution:
Step 1. Circuit $\rightarrow$ expression
Step 2. Simplify expression
$(P \vee Q)∧∼(P ∧ Q) ≡P ⊕ Q$ ◃ Exclusive or
Step 3. Expression $\rightarrow$ table
| $P$ | $Q$ | $P\vee Q$ | $P\wedge Q$ | $\sim(P\wedge Q)$ | $(P\vee Q)\wedge\sim(P\wedge Q)$ |
|---|---|---|---|---|---|
| 1 | 1 | 1 | 1 | 0 | 0 |
| 1 | 0 | 1 | 0 | 1 | 1 |
| 0 | 1 | 1 | 0 | 1 | 1 |
| 0 | 0 | 0 | 0 | 1 | 0 |
Table $\rightarrow$ Circuit
Determine the logic circuit for the given input-output table.| Input | Output | ||
|---|---|---|---|
| $P$ | $Q$ | $R$ | $S$ |
| 1 | 1 | 1 | 1 |
| 1 | 1 | 0 | 0 |
| 1 | 0 | 1 | 1 |
| 1 | 0 | 0 | 1 |
| 0 | 1 | 1 | 0 |
| 0 | 1 | 0 | 0 |
| 0 | 0 | 1 | 0 |
| 0 | 0 | 0 | 0 |
Solution:
Step 1. Table $\rightarrow$ expression
$(P \wedge Q \wedge R) \vee (P \wedge \sim Q \wedge R) \vee (P \wedge \sim Q \wedge \sim R)$
Disjunctive normal form or sum-of-products form
| Input | Output | Expression | ||
|---|---|---|---|---|
| $P$ | $Q$ | $R$ | $S$ | $S$ |
| 1 | 1 | 1 | 1 | $P \wedge Q \wedge R$ |
| 1 | 1 | 0 | 0 | $P \wedge Q \wedge \sim R$ |
| 1 | 0 | 1 | 1 | $P \wedge \sim Q \wedge R$ |
| 1 | 0 | 0 | 1 | $P \wedge \sim Q \wedge \sim R$ |
| 0 | 1 | 1 | 0 | $\sim P \wedge Q \wedge R$ |
| 0 | 1 | 0 | 0 | $\sim P \wedge Q \wedge \sim R$ |
| 0 | 0 | 1 | 0 | $\sim P \wedge \sim Q \wedge R$ |
| 0 | 0 | 0 | 0 | $\sim P \wedge \sim Q \wedge \sim R$ |
Step 2. Expression $\rightarrow$ circuit
Solution (better version)
Step 1. Table $\rightarrow$ expression
As before.
Step 2. Simplify expression
$(P \wedge Q \wedge R) \vee (P \wedge \sim Q \wedge R) \vee (P \wedge \sim Q \wedge \sim R)$$\equiv P \wedge (\sim Q \vee R)$◃ How?
\begin{align*} & (P \wedge Q \wedge R) \vee (P \wedge \sim Q \wedge R) \vee (P \wedge \sim Q \wedge \sim R) \\ \equiv & \; [P \wedge R \wedge (Q \vee \sim Q)] \vee (P \wedge \sim Q \wedge \sim R) \quad & \text{(Distributive law)}\\ \equiv & \; (P \wedge R) \vee (P \wedge \sim Q \wedge \sim R) \quad & \text{(Negation law: } Q \vee \sim Q \equiv \text{True)}\\ \equiv & \; P \wedge [R \vee (\sim Q \wedge \sim R)] \quad & \text{(Distributive law)}\\ \equiv & \; P \wedge [(R \vee \sim Q) \wedge (R \vee \sim R)] \quad & \text{(Distributive law)}\\ \equiv & \; P \wedge [(R \vee \sim Q) \wedge \text{True}] \quad & \text{(Negation law: } R \vee \sim R \equiv \text{True)}\\ \equiv & \; P \wedge (R \vee \sim Q) \quad & \text{(Identity law)}\\ \end{align*}
Step 3. Expression $\rightarrow$ circuit
What is a recognizer circuit?
A recognizer is a circuit that outputs a 1 for exactly one particular combination of input signals and outputs 0’s for all other combinations.
| Input | Output | ||
|---|---|---|---|
| $P$ | $Q$ | $R$ | $(P \wedge Q) \wedge \sim R$ |
| 1 | 1 | 1 | 0 |
| 1 | 1 | 0 | 1 |
| 1 | 0 | 1 | 0 |
| 1 | 0 | 0 | 0 |
| 0 | 1 | 1 | 0 |
| 0 | 1 | 0 | 0 |
| 0 | 0 | 1 | 0 |
| 0 | 0 | 0 | 0 |
Equivalence of logic circuits
Two digital logic circuits are called equivalent if and only if their input-output tables are identical
Approach: Simplify the logical expression
NAND and NOR gates
| NAND: $P ~|~ Q \equiv \sim ( P ∧ Q)$ | ◃ Sheffer stroke |
|---|---|
| NOR: $P ↓ Q \equiv ∼(P ∨ Q)$ | ◃ Pierce arrow |
Any logical expression is equivalent to an expression written entirely with NAND gates or written entirely with NOR gates. This is the reason these gates are called Universal gates.
NAND-Gate: $P ~|~ Q$
| Input | Output | |
|---|---|---|
| $P$ | $Q$ | $R= P ~|~ Q$ |
| 1 | 1 | 0 |
| 1 | 0 | 1 |
| 0 | 1 | 1 |
| 0 | 0 | 1 |
NOR-Gate: $P ↓ Q$
| Input | Output | |
|---|---|---|
| $P$ | $Q$ | $R= P ↓ Q$ |
| 1 | 1 | 0 |
| 1 | 0 | 0 |
| 0 | 1 | 0 |
| 0 | 0 | 1 |
Universal logic gates: NAND and NOR
| Expression | Using NAND gates only | Using NOR gates only |
|---|---|---|
| $∼P$ | $≡P ~|~P$ | $≡P ↓P$ |
| $P \wedge Q$ | $≡(P ~|~Q) ~|~(P ~|~Q)$ | $≡(P ↓P ) ↓(Q ↓Q)$ |
| $P \vee Q$ | $≡(P ~|~P ) ~|~(Q ~|~Q)$ | $≡(P ↓Q) ↓(P ↓Q)$ |
| $P \rightarrow Q$ | $≡P ~|~(P ~|~Q) ≡P ~|~(Q ~|~Q)$ | $≡((P ↓P ) ↓Q) ↓((P ↓P ) ↓Q)$ |
| $P \leftrightarrow Q$ | $≡(P ~|~Q) ~|~((P ~|~P ) ~|~(Q ~|~Q))$ | $≡( P ↓(P ↓Q) ) ↓( Q ↓(P ↓Q) )$ |
Take-Home Lessons
Logic models programming
Problem:
Are these two computer programs equivalent?
if ((a == b+1 && c < d) ||
((a-1 != b || c >= d) && (a == c || b == c)))
{...}if ((a == b+1 && c < d) || (a == c || b == c))
{...}Reason.
Let $p : (a == b+1 ~\& \&~ c < d)$ and $q : (a == c ~||~ b == c)$
$p \vee (~ p \wedge q) \equiv p \vee q$
Problem:
What is the output of this computer program?
if ((a < b || c == d) && (a >= b || c == d) &&
(a < b || c != d) && (a >= b || c != d))
print "Hi"
else
print "Hey"Reason. Let $p : (a < b)$ and $q : (c == d)$
$((p \vee q) \wedge(\sim p \vee q) \wedge (p \vee \sim q) \wedge (\sim p \vee \sim q)) \equiv p \wedge \sim p \equiv c$
Problem:
Is the second computer program simplified/optimized version of the first computer program?
if (a < b && a < c && b < c)
{...}if (a < b && b < c)
{...}Reason. Let $p : (a < b)$, $q : (a < c)$, and $r : (b < c)$
$p ∧ q ∧ r ≢ p ∧r$. (Counterexample: $p= T , q= F , r = T$ .)
Incorrect answer and incorrect reasoning. What’s wrong?
Logic models circuit design
Problem:
Lily, an intern of circuit design, thinks that the following circuit present in the design of the next-generation laptop can be replaced by an OR gate. Is Lily right?
Solution:
Answer. No.
Reason. The circuit is equivalent to an AND gate.
Logic models reasoning
Problem:
Steve: If it is raining, then it is cloudy.
Natasha: It is cloudy.
John: So, it is raining.
Is John’s conclusion logical?
Solution:
Answer. No.
Reason. Logical fallacy: Converse error.
Problem:
Steve: If it is raining, then it is cloudy.
Natasha: It is raining.
John: So, it is cloudy.
Is John’s conclusion logical?
Solution:
Answer. Yes.
Reason. Rule of inference: Modus ponens.
Problem:
Steve: If it is raining, then it is cloudy.
Natasha: It is not raining.
John: So, it is not cloudy.
Is John’s conclusion logical?
Solution:
Answer. No.
Reason. Logical fallacy: Inverse error.
Problem:
Steve: If it is raining, then it is cloudy.
Natasha: It is not cloudy.
John: So, it is not raining.
Is John’s conclusion logical?
Solution:
Answer. Yes.
Reason. Rule of inference: Modus tollens.
Learning expectations
Expectations- Understand logical expressions
- Understand negations, conditionals, and equivalence laws
- Construct truth tables
- Check equivalence of logical expressions
- Understand valid/logical and invalid/illogical arguments
- Solve problems using valid arguments
- Understand sound/truthful and unsound/false arguments
- Convert circuit diagrams to I/O tables and vice versa
- Check equivalence of circuit diagrams