Mathematical Logic and Propositional: Best Answers 007EH

Welcome to Lesson Six – Mathematical Logic and Propositional.

You can also join the Discrete Mathematics Forum to interact and share ideas, also you can navigate to any session using the Table of Content

Don’t forget to leave your comment, suggestions regarding the previous, and current lecture to help us improve.

Introduction to Mathematical Logic and Propositional

Proposition

A Proposition or a statement or logical sentence is a declarative sentence which is either true or false.

Example1: The following statements are all propositions:

  • Jawaharlal Nehru is the first prime minister of India.
  • It rained Yesterday.
  • If x is an integer, then x2 is a +ve integer.

Example2: The following statements are not propositions:

  • Please report at 11 a.m. sharp
  • What is your name?
  • x2=13

Propositional Variables

The lower case letters starting from P onwards are used to represent propositions

Example: p: India is in Asia
                 q: 2 + 2 = 4

Compound Statements

Statements or propositional variables can be combined by means of logical connectives (operators) to form a single statement called compound statements.

The five logical connectives are:

SymbolConnectiveName
~NotNegation
AndConjunction
OrDisjunction
Implies or if…thenImplication or conditional
If and only ifEquivalence or biconditional


Basic Logical Operations

1. Negation: It means the opposite of the original statement. If p is a statement, then the negation of p is denoted by ~p and read as ‘it is not the case that p.’ So, if p is true then ~ p is false and vice versa.

Example: If statement p is Paris is in France, then ~ p is ‘Paris is not in France’.

p~ p
TF
FT

2. Conjunction: It means Anding of two statements. If p, q are two statements, then “p and q” is a compound statement, denoted by p ∧ q and referred as the conjunction of p and q. The conjunction of p and q is true only when both p and q are true. Otherwise, it is false.

pqp ∧ q
TTT
TFF
FTF
FFF

3. Disjunction: It means Oring of two statements. If p, q are two statements, then “p or q” is a compound statement, denoted by p ∨ q and referred to as the disjunction of p and q. The disjunction of p and q is true whenever at least one of the two statements is true, and it is false only when both p and q are false.

pqp ∨ q
TTT
TFT
FTT
FFF

4. Implication / if-then (⟶): An implication p⟶q is the proposition “if p, then q.” It is false if p is true and q is false. The rest cases are true.

pqp ⟶ q
TTT
TFF
FTT
FFF

5. If and Only If (↔): p ↔ q is bi-conditional logical connective which is true when p and q are same, i.e., both are false or both are true.

pqp ↔ q
TTT
TFF
FTF
FFT

Derived Connectors

1. NAND: It means negation after ANDing of two statements. Assume p and q be two propositions. Nanding of pand q to be a proposition which is false when both p and q are true, otherwise true. It is denoted by p ↑ q.

pqp ∨ q
TTF
TFT
FTT
FFT

2. NOR or Joint Denial: It means negation after ORing of two statements. Assume p and q be two propositions. NORing of p and q to be a proposition which is true when both p and q are false, otherwise false. It is denoted by p ↑ q.

pqp ↓ q
TTF
TFF
FTF
FFT

3. XOR: Assume p and q be two propositions. XORing of p and q is true if p is true or q is true but not both and vice-versa. It is denoted by p ⨁ q.

pqp ⨁ q
TTF
TFT
FTT
FFF

Example1: Prove that X ⨁ Y ≅ (X ∧∼Y)∨(∼X∧Y).

Solution: Construct the truth table for both the propositions.

XYX⨁Y∼Y∼XX ∧∼Y∼X∧Y(X ∧∼Y)∨(∼X∧Y)
TTFFFFFF
TFTTFTFT
FTTFTFTT
FFFTTFFF

As the truth table for both the proposition is the same.

  1. X ⨁ Y ≅ (X ∧∼Y)∨(∼X∧Y). Hence Proved.  

Example2: Show that (p ⨁q) ∨(p↓q) is equivalent to p ↑ q.

Solution: Construct the truth table for both the propositions.

pqp⨁q(p↓q)(p⨁q)∨ (p↓q)p ↑ q
TTFFFF
TFTFTT
FTTFTT
FFFTTT

Conditional and BiConditional Statements

Conditional Statement

Let p and q are two statements then “if p then q” is a compound statement, denoted by p→ q and referred as a conditional statement, or implication. The implication p→ q is false only when p is true, and q is false; otherwise, it is always true. In this implication, p is called the hypothesis (or antecedent) and q is called the conclusion (or consequent).

pqp → q
TTT
TFF
FTT
FFT

For Example: The followings are conditional statements.

  1. If a = b and b = c, then a = c.
  2. If I get money, then I will purchase a computer.

Variations in Conditional Statement

Contrapositive: The proposition ~q→~p is called contrapositive of p →q.

Converse: The proposition q→p is called the converse of p →q.

Inverse: The proposition ~p→~q is called the inverse of p →q.

Example1: Show that p →q and its contrapositive ~q→~p are logically equivalent.

Solution: Construct the truth table for both the propositions:

pq~p~qp →q~q→~p
TTFFTT
TFFTFF
FTTFTT
FFTTTT

As, the values in both cases are same, hence both propositions are equivalent.

Example2: Show that proposition q→p, and ~p→~q is not equivalent to p →q.

Solution: Construct the truth table for all the above propositions:

pq~p~qp →qq→p~p→~q
TTFFTTT
TFFTFTT
FTTFTFF
FFTTTTT

As, the values of p →q in a table is not equal to q→p and ~p→~q as in fig. So both of them are not equal to p →q, but they are themselves logically equivalent.

BiConditional Statement

If p and q are two statements then “p if and only if q” is a compound statement, denoted as p ↔ q and referred as a biconditional statement or an equivalence. The equivalence p ↔ q is true only when both p and q are true or when both p and q are false.

pqp ↔ q
TTT
TFF
FTF
FFT

For Example: (i) Two lines are parallel if and only if they have the same slope.
(ii) You will pass the exam if and only if you will work hard.

Example: Prove that p ↔ q is equivalent to (p →q) ∧(q→p).

Solution: Construct the truth table for both the propositions:

pqp ↔ q
TTT
TFF
FTF
FFT
pqp →qq→p(p →q)∧(q→p)
TTTTT
TFFTF
FTTFF
FFTTT

Since, the truth tables are the same, hence they are logically equivalent. Hence Proved.

Principle of Duality

Two formulas A1 and A2 are said to be duals of each other if either one can be obtained from the other by replacing ∧ (AND) by ∨ (OR) by ∧ (AND). Also if the formula contains T (True) or F (False), then we replace T by F and F by T to obtain the dual.

Note1: The two connectives ∧ and ∨ are called dual of each other.
2. Like AND and OR, ↑ (NAND) and ↓ (NOR) are dual of each other.
3. If any formula of the proposition is valid, then it’s dual of each other.

Equivalence of Propositions

Two propositions are said to be logically equivalent if they have exactly the same truth values under all circumstances.

The table1 contains the fundamental logical equivalent expressions:

Laws of the algebra of propositions

Idempotent laws(i) p ∨ p≅p(ii) p ∧ p≅p
Associative laws(i) (p ∨ q) ∨ r ≅ p∨ (q ∨ r)(ii) (p ∧ q) ∧ r ≅ p ∧ (q ∧ r)
Commutative laws(i) p ∨ q ≅ q ∨ p(ii) p ∧ q ≅ q ∧ p
Distributive laws(i) p ∨ (q ∧ r) ≅ (p ∨ q) ∧ (p ∨ r)(ii) p ∧ (q ∨ r) ≅ (p ∧ q) ∨ (p ∧ r)
Identity laws(i)p ∨ F ≅ p
(iv) p ∧ F≅F
(ii) p ∧ T≅ p
(iii) p ∨ T ≅ T
Involution laws(i) ¬¬p ≅ p
Complement laws(i) p ∨ ¬p ≅ T(ii) p ∧ ¬p ≅ T
DeMorgan’s laws:(i) ¬(p ∨ q) ≅ ¬p ∧ ¬q(ii) ¬(p ∧ q) ≅¬p ∨ ¬q

Example: Consider the following propositions

  1. ~p∨∼q and ∼(p∧q).  

Are they equivalent?

Solution: Construct the truth table for both

pq~p~q~p∨∼qp∧q~(p∧q)
TTFFFTF
TFFTTFT
FTTFTFT
FFTTTFT

Tautologies and Contradiction

Tautologies

A proposition P is a tautology if it is true under all circumstances. It means it contains the only T in the final column of its truth table.

Example: Prove that the statement (p⟶q) ↔(∼q⟶∼p) is a tautology.

Solution: Make the truth table of the above statement:

pqp→q~q~p~q⟶∼p(p→q)⟷( ~q⟶~p)
TTTFFTT
TFFTFFT
FTTFTTT
FFTTTTT

As the final column contains all T’s, so it is a tautology.

Contradiction:

A statement that is always false is known as a contradiction.

Example: Show that the statement p ∧∼p is a contradiction.

Solution:

p∼pp ∧∼p
TFF
FTF

Since, the last column contains all F’s, so it’s a contradiction.

Contingency:

A statement that can be either true or false depending on the truth values of its variables is called a contingency.

pqp →qp∧q(p →q)⟶ (p∧q )
TTTTT
TFFFT
FTTFF
FFTFF


Predicate Logic

Predicate Logic deals with predicates, which are propositions, consist of variables.

Predicate Logic – Definition

A predicate is an expression of one or more variables determined on some specific domain. A predicate with variables can be made a proposition by either authorizing a value to the variable or by quantifying the variable.The following are some examples of predicates.

  • Consider E(x, y) denote “x = y”
  • Consider X(a, b, c) denote “a + b + c = 0”
  • Consider M(x, y) denote “x is married to y.”

Quantifier:

The variable of predicates is quantified by quantifiers. There are two types of quantifier in predicate logic – Existential Quantifier and Universal Quantifier.

Existential Quantifier:

If p(x) is a proposition over the universe U. Then it is denoted as ∃x p(x) and read as “There exists at least one value in the universe of variable x such that p(x) is true. The quantifier ∃ is called the existential quantifier.

There are several ways to write a proposition, with an existential quantifier, i.e.,

(∃x∈A)p(x)    or    ∃x∈A    such that p (x)    or    (∃x)p(x)    or    p(x) is true for some x ∈A.

Universal Quantifier:

If p(x) is a proposition over the universe U. Then it is denoted as ∀x,p(x) and read as “For every x∈U,p(x) is true.” The quantifier ∀ is called the Universal Quantifier.

There are several ways to write a proposition, with a universal quantifier.

∀x∈A,p(x)    or    p(x), ∀x ∈A      Or    ∀x,p(x)    or    p(x) is true for all x ∈A.

Negation of Quantified Propositions:

When we negate a quantified proposition, i.e., when a universally quantified proposition is negated, we obtain an existentially quantified proposition,and when an existentially quantified proposition is negated, we obtain a universally quantified proposition.

The two rules for negation of quantified proposition are as follows. These are also called DeMorgan’s Law.

Example: Negate each of the following propositions:

1.∀x p(x)∧ ∃ y q(y)

Sol: ~.∀x p(x)∧ ∃ y q(y))
      ≅~∀ x p(x)∨∼∃yq (y)        (∴∼(p∧q)=∼p∨∼q)
      ≅ ∃ x ~p(x)∨∀y∼q(y)

2. (∃x∈U) (x+6=25)

Sol: ~( ∃ x∈U) (x+6=25)
      ≅∀ x∈U~ (x+6)=25
      ≅(∀ x∈U) (x+6)≠25

3. ~( ∃ x p(x)∨∀ y q(y)

Sol: ~( ∃ x p(x)∨∀ y q(y))
      ≅~∃ x p(x)∧~∀ y q(y)        (∴~(p∨q)= ∼p∧∼q)
      ≅ ∀ x ∼ p(x)∧∃y~q(y))

Propositions with Multiple Quantifiers:

The proposition having more than one variable can be quantified with multiple quantifiers. The multiple universal quantifiers can be arranged in any order without altering the meaning of the resulting proposition. Also, the multiple existential quantifiers can be arranged in any order without altering the meaning of the proposition.

The proposition which contains both universal and existential quantifiers, the order of those quantifiers can’t be exchanged without altering the meaning of the proposition, e.g., the proposition ∃x ∀ y p(x,y) means “There exists some x such that p (x, y) is true for every y.”

Example: Write the negation for each of the following. Determine whether the resulting statement is true or false. Assume U = R.

1.∀ x ∃ m(x2<m)

Sol: Negation of ∀ x ∃ m(x2<m) is ∃ x ∀ m (x2≥m). The meaning of ∃ x ∀ m (x2≥m) is that there exists for some x such that x2≥m, for every m. The statement is true as there is some greater x such that x2≥m, for every m.

2. ∃ m∀ x(x2<m)

Sol: Negation of ∃ m ∀ x (x2<m) is ∀ m∃x (x2≥m). The meaning of ∀ m∃x (x2≥m) is that for every m, there exists for some x such that x2≥m. The statement is true as for every m, there exists for some greater x such that x2≥m.


Normal Forms

The problem of finding whether a given statement is tautology or contradiction or satisfiable in a finite number of steps is called the Decision Problem. For Decision Problem, construction of truth table may not be practical always. We consider an alternate procedure known as the reduction to normal forms.

There are two such forms:

  1. Disjunctive Normal Form (DNF)
  2. Conjunctive Normal Form

Disjunctive Normal Form (DNF): If p, q are two statements, then “p or q” is a compound statement, denoted by p ∨ q and referred as the disjunction of p and q. The disjunction of p and q is true whenever at least one of the two statements is true, and it is false only when both p and q are false

pqp ∨ q
TTT
TFT
FTT
FFF

Example: – if p is “4 is a positive integer” and q is “√5 is a rational number”, then p ∨ q is true as statement p is true, although statement q is false.

Conjunctive Normal Form: If p, q are two statements, then “p and q” is a compound statement, denoted by p ∧ q and referred as the conjunction of p and q. The conjunction of p and q is true only when both p and q are true, otherwise, it is false

pqp ∧ q
TTT
TFF
FTF
FFF

Example: if statement p is “6<7” and statement q is “-3>-4” then the conjunction of p and q is true as both p and q are true statements.


Discrete Mathematics Forum

https://eduraryhub.com/forums/forum/discrete-mathematics-forum/

Related Articles

Responses