Propositional Logic

Propositional Logic – What is Proposition?

 

PROPOSITIONSPropositional Logic

First, you have to know that what is Proposition or what is Propositional Logic?
‘An elephant weighs more than a human being.’ When you read this declarative sentence, you can immediately decide whether it is true or false. And so can anyone else. Also, it wouldn’t happen that some people say that the statement is true and some others say that it is false. Everybody would have the same answer. So this sentence is either universally true or universally false.

It is a declarative sentence which is either true or false, but not both. In mathematical logic we call such sentences statements or propositions.

Would you say that the following are propositions?
‘Watch the film.
‘How wonderful!’
‘What did you say?’
Actually, none of them are declarative sentences. (The first one is an order, the second an exclamation, and the third is a question.) And therefore, none of them are propositions.

Now for some mathematical propositions! You must have studied and created many of them while doing mathematics. Some examples are
Two plus two equals four.
Two plus two equals five.
x + y > 0 for x > 0 and y > 0.
A set with n elements has 2n subsets.
Now consider the algebraic sentence ‘x + y > 0’. Is this a proposition? Are we in a position to determine whether it is true or false? Not unless we know the values that x and y can take. For example, it is false for
x = 1, y = -2 and true if x = 1, y = 0. Therefore,
‘x + y > 0’ is not a proposition, while
‘x + y > 0 for x > 0, y > 0’ is a proposition.

 

LOGICAL CONNECTIVES

When you’re talking to someone, do you use very simple sentences only? Don’t you use more complicated ones which are joined by words like ‘and’, ‘or’, etc? In the same way, most statements in mathematical logic are combinations of simpler statements joined by words and phrases like ‘and’. ‘or’, ‘if … then’. ‘if and only if’, etc. These words and phrases are called logical connectives. There are 6 such connectives, which we shall discuss one by one.

Disjunction

The disjunction of two propositions p and q is the compound statement p or q, denoted by p ∨ q.
For example, ‘Zarina has written a book or Singh has written a book.’ Is the disjunction of p and q, where
p: Zarina has written a book, and
q: Singh has written a book.

Similarly, if p denotes ‘ 2 > 0’ and q denotes ‘2 < 5’, then p ∨ q denotes the statement
‘2 is greater than 0 or 2 is less than 5.’.

Disjunction Truth Table

Conjunction

We call the compound statement ‘p and q’ the conjunction of the statements p and q. We denote this by p ∧ q.
For instance, ‘3 + 1 ≠ 7 ∧ 2 > 0’ is the conjunction of ‘3 + 1 ≠ 7’ and ‘2 > 0’. Similarly, ‘2 + 1 = 3 ∧ 3 = 5’ is the conjunction of ‘2 + 1 = 3’ and ‘3 = 5’.

Conjunction Truth Table

Negation

The negation of a proposition p is ‘not p’, denoted by ~p.
For example, if p is ‘Dolly is at the study center.’, then ~ p is ‘Dolly is not at the study center’. Similarly, if p is ‘No person can live without oxygen.’, ~ p is ‘At least one person can live without oxygen.’.

Negation

Conditional / Implication / if-then

Given any two propositions p and q, we denote the statement ‘If p, then q’ by p → q. We also read this as ‘p implies q’. or ‘p is sufficient for q’, or ‘p only if q’. We also call p the hypothesis and q the conclusion. Further, a statement of the form p → q is called a conditional statement or a conditional proposition.
So, for example, in the conditional proposition ‘If m is in Z, then m belongs to Q.’ the hypothesis is ‘m ∈ Z’ and the conclusion is ‘m ∈ Q’.

Conditional Connectives Truth Table

Biconditional / If and only if

Let p and q be two propositions. The compound statement (p → q) ∧(q → p) is the biconditional of p and q. We denote it by p ↔ q, and read it as ‘p if and only q’.

For example, ‘Sudha will gain weight if and only if she eats regularly.’ Means that ‘Sudha will gain weight if she eats regularly and Sudha will eat regularly if she gains weight.

Biconditional Truth Table

The rule of precedence

The order of preference in which the connectives are applied in a formula of propositions that has no brackets is
i) ~
ii) ∧
iii) ∨ and ⊕
iv) → and ↔

 

LOGICAL EQUIVALENCE

We call two propositions r and s logically equivalent provided they have the same truth value for every choice of truth values of simple propositions involved in them. We denote this fact by r ≡ s.

We find out in the following table.

Logical Equivalence Example 01

So, from the above table we find that ( p → q) ≡ (~ q → ~ p).

 Example 01

Q. For any two propositions p and q, show that ~ (p ∨ q) ≡ ~ p ∧ ~ q.

Solution: Consider the following truth table

Logical Equivalence Example 1

You can see that the last two columns of the above table are identical. Thus, the truth valuesof ~ ( p ∨ q) and ~ p ∧ ~ q agree for every choice of truth values of p and q. Therefore, ~ (p ∨ q) ≡ ~ p ∧ ~ q.

The equivalence you have just seen is one of De Morgan’s laws. You might have already come across these laws in your previous studies of basic Mathematics.
The other law due to De Morgan is similar: ~ (p ∧ q) ≡ ~ p ∨ ~ q.
In fact, there are several such laws about equivalent propositions. Some of them are the following, where, as usual, p, q and r denote propositions.
a) Double negation law: ~ (~ p) ≡ p
b) Idempotent laws: p ∧ p ≡ p, p ∨ p ≡ p
c) Commutativity: p ∨ q ≡ q ∨ p, p ∧ q ≡ q ∧ p
d) Associativity: (p ∨ q) ∨ r ≡ p ∨ (q ∨ r), (p ∧ q) ∧ r ≡ p ∧ ( q ∧ r)
e) Distributivity: p ∨ ( q ∧ r) ≡ (p ∨ q) ∧ (p ∨ r), p ∧ ( q ∨ r) ≡ (p ∧ q) ∨ ( p ∧ r)

Tautology

A compound proposition that is true for all possible truth values of the simple propositions involved in it is called a tautology.

Contradiction

A proposition that is false for all possible truth values of the simple propositions that constitute it is called a contradiction.

 Example 02

Q. Verify that p ∧ q ∧ ~ p is a contradiction and p → q ↔ ~ p ∨ q is a tautology.

Solution: Let us simultaneously draw up the truth tables of these two propositions below.

Contradiction
Next Topic >>
Predicate and Quantifiers

Leave a Comment

Your email address will not be published. Required fields are marked *

0

Scroll to Top