Propositions : A proposition is a declarative sentence (that is, a sentence that declares a fact) that is either true or false, but not both.
Washington, D.C., is the capital of the United States of America.
Toronto is the capital of Canada.
1 + 1 = 2.
Propositions 1 and 3 are true, whereas 2 and 4 are false.
The truth value of a proposition is true, denoted by T, if it is a true proposition, and the truth value of a proposition is false, denoted by F, if it is a false proposition.
The area of logic that deals with propositions is called the propositional calculus or propositional logic.
New propositions, called compound propositions, are formed from existing propositions using logical operators.
Let p be a proposition. The negation of p, denoted by ¬p (also denoted by p'), is the statement. The proposition ¬p is read “not p.” The truth value of the negation of p, ¬p, is the opposite of the truth value of p.
Truth Table for Negation P
| P | ¬P |
|---|---|
| 0 | 1 |
| 1 | 0 |
Let p and q be propositions. The conjunction of p and q, denoted by p ∧ q, is the proposition “p and q.”
The conjunction p ∧ q is true when both p and q are true and is false otherwise.
Note that in logic the word “but” sometimes is used instead of “and” in a conjunction.
For example : the statement “The sun is shining, but it is raining” is another way of saying “The sun is shining and it is raining.”
Truth Table for Conjunction : p ∧ q
| P | Q | p ∧ q |
|---|---|---|
| T | T | T |
| T | F | F |
| F | T | F |
| F | F | F |
Let p and q be propositions. The disjunction of p and q, denoted by p ∨ q, is the proposition “p or q.” The disjunction p ∨ q is false when both p and q are false and is true otherwise.
The use of the connective or in a disjunction corresponds to one of the two ways the word or is used in English, namely, as an inclusive or.
Example : “Students who have taken calculus or computer science can take this class.”
Here, we mean that students who have taken both calculus and computer science can take the class, as well as the students who have taken only one of the two subjects. On the other hand, we are using the exclusive or when we say
Example : “Students who have taken calculus or computer science, but not both, can enroll in this class.”
Here, we mean that students who have taken both calculus and a computer science course cannot take the class. Only those who have taken exactly one of the two courses can take the class.
Truth Table for Disjunction : p ∨ q
| P | Q | p ∨ q |
|---|---|---|
| T | T | T |
| T | F | T |
| F | T | T |
| F | F | F |
Let p and q be propositions. The exclusive or of p and q, denoted by p ⊕ q, is the proposition that is true when exactly one of p and q is true and is false otherwise.
The Truth Table for the Exclusive Or of Two Propositions : p ⊕ q
| P | Q | p ⊕ q |
|---|---|---|
| T | T | F |
| T | F | T |
| F | T | T |
| F | F | F |
Let p and q be propositions. The conditional statement p → q is the proposition “if p, then q.” The conditional statement p → q is false when p is true and q is false, and true otherwise.
In the conditional statement p → q, p is called the hypothesis (or antecedent or premise) and q is called the conclusion (or consequence).
The statement p → q is called a conditional statement because p → q asserts that q is true on the condition that p holds. A conditional statement is also called an implication.
Note : that the statement p → q is true when both p and q are true and when p is false (no matter what truth value q has).
Following ways to express this conditional statement :
“if p, then q” “p implies q” “if p, q” “p only if q” “p is sufficient for q” “a sufficient condition for q is p” “q if p” “q whenever p” “q when p” “q is necessary for p” “a necessary condition for p is q” “q follows from p” “q unless ¬p”
Example : “If I am elected, then I will lower taxes.”
If the politician is elected, voters would expect this politician to lower taxes.
Furthermore, if the politician is not elected, then voters will not have any expectation that this person will lower taxes, although the person may have sufficient influence to cause those in power to lower taxes.
It is only when the politician is elected but does not lower taxes that voters can say that the politician has broken the campaign pledge. This last scenario corresponds to the case when p is true but q is false in p → q.
The Truth Table for the Conditional Statement : p → q
| P | Q | p → q |
|---|---|---|
| T | T | T |
| T | F | F |
| F | T | T |
| F | F | T |
We can form some new conditional statements starting with a conditional statement p → q :
The proposition q → p is called the converse of p → q
The contrapositive of p → q is the proposition ¬q → ¬p.
The proposition ¬p → ¬q is called the inverse of p → q.
Of these three conditional statements formed from p → q, only the contra-positive always has the same truth value as p → q.
When two compound propositions always have the same truth value we call them equivalent, so that a conditional statement and its contrapositive are equivalent.
The converse and the inverse of a conditional statement are also equivalent.
Q : What are the contrapositive, the converse, and the inverse of the conditional statement “The home team wins whenever it is raining?”
Because “q whenever p” is one of the ways to express the conditional statement p → q, the original statement can be rewritten as “If it is raining, then the home team wins.”
Consequently, the contrapositive of this conditional statement is “If the home team does not win, then it is not raining.”
The converse is “If the home team wins, then it is raining.”
The inverse is “If it is not raining, then the home team does not win.” Only the contrapositive is equivalent to the original statement.
Let p and q be propositions. The biconditional statement p ↔ q is the proposition “p if and only if q.” The biconditional statement p ↔ q is true when p and q have the same truth values, and is false otherwise. Biconditional statements are also called bi-implications.
Note : that the statement p ↔ q is true when both the conditional statements p → q and q → p are true and is false otherwise.
Common ways to express p ↔ q:
“p is necessary and sufficient for q” “if p then q, and conversely” “p iff q.”
The last way of expressing the biconditional statement p ↔ q uses the abbreviation “iff” for “if and only if.” Note that p ↔ q has exactly the same truth value as (p → q) ∧ (q → p).
The Truth Table for the Biconditional p ↔ q.
| P | Q | p ↔ q |
|---|---|---|
| T | T | T |
| T | F | F |
| F | T | F |
| F | F | T |
Q. Let p be the statement “You can take the flight,” and let q be the statement “You buy a ticket.” Then p ↔ q is the statement
“You can take the flight if and only if you buy a ticket.”
This statement is true if p and q are either both true or both false, that is, if you buy a ticket and can take the flight or if you do not buy a ticket and you cannot take the flight.
It is false when p and q have opposite truth values, that is, when you do not buy a ticket, but you can take the flight and when you buy a ticket but you cannot take the flight.
Q. Construct the truth table of the compound proposition (p ∨ ¬q) → (p ∧ q).
The truth values of the compound proposition for each combination of truth values of the propositional variables in it is found in the final column of the table.
Because this truth table involves two propositional variables p and q, there are four rows in this truth table, one for each of the pairs of truth values TT, TF, FT, and FF.
The Truth Table of (p ∨¬q) → (p ∧ q).
| P | Q | ¬Q | (p ∨¬q) | (p ∧ q) | (p ∨¬q) → (p ∧ q) |
|---|---|---|---|---|---|
| T | T | F | T | T | T |
| T | F | T | T | F | F |
| F | T | F | F | F | T |
| F | F | T | T | F | F |
We will generally use parentheses i.e. () to specify the order in which logical operators in a compound proposition are to be applied.
Order of precedence without parenthesis is :-
Precedence of Logical Operators.
| Operator | Precedence |
|---|---|
| ¬ | 1 |
| ∧ | 2 |
| ∨ | 3 |
| → | 4 |
| ↔ | 5 |