Propositional Logic#
Propositional logic is concerned with statements to which the truth values, true and false, can be assigned. The purpose is to analyze these statements either individually or in a composite manner.
Definition#
A proposition is a collection of declarative statements that has either a truth value true or false. A propositional consists of propositional variables and connectives. We denote the propositional variables by capital letters (\(A\), \(B\), etc). The connectives must connect the propositional variables.
Example
“Man is Mortal”: it returns truth value true
“12 + 9 = 32”: it returns truth value false
The following is not a proposition:
“\(A\) is less than 2”: It is because unless we give a specific value of \(A\), we cannot say whether the statement is true or false.
Connectives#
Logical connectives are symbols or words used to combine simple propositions into complex compound statements.
In propositional logic, generally we use five connectives, which are:
Disjunction (\(∨\))#
The logical-OR operation of two propositions \(A\) and \(B\) (written as \(A ∨ B\)) is true if at least any of the propositional variable \(A\) or \(B\) is true.
The truth table is as follows:
\(A\) |
\(B\) |
\(A ∨ B\) |
|---|---|---|
true |
true |
true |
true |
false |
true |
false |
true |
true |
false |
false |
false |
Conjunction (\(∧\))#
The logical-AND operation of two propositions \(A\) and \(B\) (written as \(A ∧ B\)) is true if both the propositional variable \(A\) and \(B\) is true.
The truth table is as follows:
\(A\) |
\(B\) |
\(A ∧ B\) |
|---|---|---|
true |
true |
true |
true |
false |
false |
false |
true |
false |
false |
false |
false |
Negation (\(¬\))#
The negation of a proposition \(A\) (written as \(¬A\)) is false when \(A\) is true, and is true when \(A\) is false.
The truth table is as follows:
\(A\) |
\(¬A\) |
|---|---|
true |
false |
false |
true |
Implication (\(→\))#
An implication \(A → B\) is the proposition if \(A\), then \(B\). It is false if \(A\) is true and \(B\) is false. The rest cases are true.
The truth table is as follows:
\(A\) |
\(B\) |
\(A → B\) |
|---|---|---|
true |
true |
true |
true |
false |
false |
false |
true |
true |
false |
false |
true |
Biconditional (\(⇔\))#
\(A ⇔ B\) is biconditional logical connective which is true when \(p\) and \(q\) are same, i.e. both are false or both are true.
The truth table is as follows:
\(A\) |
\(B\) |
\(A ⇔ B\) |
|---|---|---|
true |
true |
true |
true |
false |
false |
false |
true |
false |
false |
false |
true |
Tautology#
A tautology is a formula which is always true for every value of its propositional variables.
Example
Prove \([(A → B) ∧ A] → B\) is a tautology:
\(A\) |
\(B\) |
\(A → B\) |
\((A → B) ∧ A\) |
\([(A → B) ∧ A] → B\) |
|---|---|---|---|---|
true |
true |
true |
true |
true |
true |
false |
false |
false |
true |
false |
true |
true |
false |
true |
false |
false |
true |
false |
true |
As we can see, every value of \([(A → B) ∧ A] → B\) is true. Therefore, it is a tautology.
Contradictions#
A contradiction is a formula which is always false for every value of its propositional variables.
Example
Prove \((A ∨ B) ∧ [(¬A) ∧ (¬B)]\) is a contradiction:
\(A\) |
\(B\) |
\(A ∨ B\) |
\(¬A\) |
\(¬B\) |
\((¬ A) ∧ ( ¬ B)\) |
\((A ∨ B) ∧ [( ¬ A) ∧ (¬ B)]\) |
|---|---|---|---|---|---|---|
true |
true |
true |
false |
false |
false |
false |
true |
false |
true |
false |
true |
false |
false |
false |
true |
true |
true |
false |
false |
false |
false |
false |
false |
true |
true |
true |
false |
As we can see, every value of \((A ∨ B) ∧ [( ¬ A) ∧ (¬ B)]\) is false. Therefore, it is a contradiction.
Contingency#
A contingency is a formula which has both some true and some false values for every value of its propositional variables.
Example
Prove \((A ∨ B) ∧ (¬A)\) is a contingency.
\(A\) |
\(B\) |
\(A ∨ B\) |
\(¬A\) |
\((A ∨ B) ∧ (¬ A)\) |
|---|---|---|---|---|
true |
true |
true |
false |
false |
true |
false |
true |
false |
false |
false |
true |
true |
true |
true |
false |
false |
false |
true |
false |
As we can see, every value of \((A ∨ B) ∧ (¬A)\) has both true and false. Therefore, it is a contingency.
Propositional Equivalences#
Two statements \(A\) and \(B\) are logically equivalent if any of the following two conditions hold:
the truth tables of each statement have the same truth values; or,
the biconditional statement \(A ⇔ B\) is a tautology.
Example
Prove \(¬(A ∨ B)\) and \([(¬A) ∧ (¬B)]\) are equivalent.
Method 1: Matching truth table
\(A\) |
\(B\) |
\(A ∨ B\) |
\(¬ (A ∨ B)\) |
\(¬A\) |
\(¬ B\) |
\([(¬A) ∧ (¬B)]\) |
|---|---|---|---|---|---|---|
true |
true |
true |
false |
false |
false |
false |
true |
false |
true |
false |
false |
true |
false |
false |
true |
true |
false |
true |
false |
false |
false |
false |
false |
true |
true |
true |
true |
Here, we can see the truth values of \(¬(A ∨ B)\) and \([(¬A) ∧ (¬B)]\) are the same, hence the statements are equivalent.
Method 2: Biconditionality
\(A\) |
\(B\) |
\(¬ (A ∨ B )\) |
\([(¬ A) ∧ (¬ B)]\) |
\(¬(A ∨ B) ⇔ [(¬A) ∧ (¬B)]\) |
|---|---|---|---|---|
true |
true |
false |
false |
true |
true |
false |
false |
false |
true |
false |
true |
false |
false |
true |
false |
false |
false |
true |
true |
As \(¬(A ∨ B) ⇔ [(¬A) ∧ (¬B)]\) is a tautology, the statements are equivalent.
Inverse, Converse, and Contra-positive#
Implication is also called a conditional statement. It has two parts:
Hypothesis, \(P\); and,
Conclusion, \(Q\).
Note
As mentioned earlier, it is denoted as \(P → Q\).
Example
“If you do your homework, you will not be punished.”
Here, “you do your homework” is the hypothesis, and “you will not be punished” is the conclusion.
An inverse of the conditional statement is the negation of both hypothesis and the conclusion. The inverse of \(P → Q\) is \(¬P → ¬Q\).
Example
The inverse of…
“If you do your homework, you will not be punished.”
is…
“If you do not do your homework, you will be punished.”
The converse of the conditional statement is computed by interchanging the hypothesis and the conclusion. The converse of \(P → Q\) is \(Q → P\).
Example
The converse of…
“If you do your homework, you will not be punished.”
is…
“If you will not be punished, you do your homework.”
The contra-positive of the conditional is computed by interchanging the hypothesis and the conclusion of the inverse statement. The contra-positive of \(P → Q\) is \(¬Q → ¬P\).
Example
The contra-positive of…
“If you do your homework, you will not be pubished.”
is…
“If you are punished, you did not do your homework.”
De Morgan’s Laws#
De Morgan’s Laws are a pair of logical equivalence rules that show how negation interacts with conjunction and disjunction.
\(\neg(P \wedge Q)\) is logically equivalent to \(\neg P \vee \neg Q\).\(\neg(P \vee Q)\) is logically equivalent to \(\neg P \wedge \neg Q\).
Implications are Disjunctions#
Every implication can be written as a disjunction:
\(P → Q\) is logically equivalent to \(\neg P \vee Q\).
Double Negation#
\(\neg \neg P\) is logically equivalent to \(P\)
Negation of an Implication#
The negation of an implication is a conjunction:
\(\neg(P \rightarrow Q)\) is logically equivalent to \(P \wedge \neg Q\).
That is, the only way for an implication to be false is for the hypothesis to be true AND the conclusion to be false.
SubTopics