Mathematical Logic

By

Arnab Gupta

E-Mail: arnab.2014@outlook.com

Mathematical Logic [UG Semester IV]

2/19/2022

History

Mathematical Logic [UG Semester IV]

2/19/2022

Aristotle (384 B.C. -322 B.C.)

Syllogism

Leibnitz (1646-1716)

Mechanization of Inference

Aristotelian Logic

​

​

​

Logic is a science that studies thinking.

​

Mathematical Logic [UG Semester IV]

2/19/2022

Process of thinking

Mathematical Logic [UG Semester IV]

2/19/2022

• Logic is a science that studies rational thinking [as a domain of human thought]

​

• That can be characterized by the fact that results are out of the factor called emotion.

Mathematical Logic [UG Semester IV]

2/19/2022

Classical Logic [Bivalent Logic]

• Logic is a Sentence

​

Mathematical Logic [UG Semester IV]

2/19/2022

Principles of Logic

Mathematical Logic [UG Semester IV]

2/19/2022

Principle of Logic

Mathematical Logic [UG Semester IV]

2/19/2022

What is Mathematical Logic?�

​

• It may be defined as the analysis of reasoning, which include arguments or mathematical proofs or conclusions of scientific theories, derived from a set of hypothesis.

Mathematical Logic [UG Semester IV]

2/19/2022

• Logic tries to establish criteria to decide whether some piece of reasoning is valid or invalid.
• It is widely used in the field of computer science to verify the correctness of programs. Hardware design, computer design etc.

​

Mathematical Logic [UG Semester IV]

2/19/2022

Mathematical Logic [UG Semester IV]

2/19/2022

George Boole (1815-1864)

Mathematical Analysis of Logic

Gottlob Frege (1848-1925)

Complete Propositional Logic

​

​

​

​

​

Robinson (1930-2016)

Resolution Complete

Mathematical Logic [UG Semester IV]

2/19/2022

Mathematical Logic [UG Semester IV]

2/19/2022

Bart Selman

Min Conflict

History

Mathematical Logic [UG Semester IV]

2/19/2022

Continued…

Mathematical Logic [UG Semester IV]

2/19/2022

Propositional Logic

• It deals with assertions or statements which are either True (T) or False (F); 1 or 0 (Computer Bit); On or Off (Circuit Theory).
• Any other statements for which we cannot explain true or false are not the subject to the logic.

Mathematical Logic [UG Semester IV]

2/19/2022

Propositions or statements

Sentences

​

Mathematical Logic [UG Semester IV]

2/19/2022

Our Main concerns

​

​

• A Declarative sentence which is either true or false (called propositions or statements)
• We are dealing with two-valued logic either {T, F}, {1,0} etc.

Mathematical Logic [UG Semester IV]

2/19/2022

Mathematical Logic [UG Semester IV]

2/19/2022

Some Sample Propositions

Puppies are cuter than kittens.

Kittens are cuter than puppies.

●

●

●

Usain Bolt can outrun everyone in this

room.

CS103 is useful for cocktail parties.

The earth is made up of gold.

●

●

Mathematical Logic [UG Semester IV]

2/19/2022

More Propositions

I'm a single lady.

●

●

●

●

●

The sun will come out tomorrow.

Party rock is in the house tonight.

We can dance if we want to.

We can leave your friends behind.

Which of them are propositions?�

• May God Bless you!

(No)

• 15 is a prime number.

(Yes)

• Wish you a happy journey.

(No)

• Please wait.

(No)

• Kolkata is the capital of India.

(Yes)

• What are you doing?

(No)

​

Mathematical Logic [UG Semester IV]

2/19/2022

Is this a proposition?

​

​

• The statement is false.

​

(Semantic or Liar paradox)

Mathematical Logic [UG Semester IV]

2/19/2022

Logical connectives and propositions

• Propositional variables (statement letters):

It is an arbitrary proposition whose truth value is unspecified.

We use lower case letters p, q, r,.....for propositional variables.

Example: p: Tsunami took thousands of lives on christmas eve.

q: Alia is intelligent.

Mathematical Logic [UG Semester IV]

2/19/2022

Logical connectives

Mathematical Logic [UG Semester IV]

2/19/2022

Truth table:

Negation (῀):

​

​

​

Example:

p: I went to my institute yesterday.

῀p : I did not go to my institute yesterday.

Mathematical Logic [UG Semester IV]

2/19/2022

p

p

Truth table:

Conjunction (ᴧ):

​

​

​

​

Example: p: Ram went to school.

q: Gopal went to school.

pᴧq: Ram and Gopal went to school.

​

​

Mathematical Logic [UG Semester IV]

2/19/2022

Truth table:

Disjunction (ᴠ):

​

​

​

​

Example: p: There is something wrong with the teacher.

q: There is something wrong with the student.

pᴠq: There is something wrong with the teacher or with the student.

​

​

Mathematical Logic [UG Semester IV]

2/19/2022

Truth table:

Conditional (or Implication) (→):

​

​

​

​

​

• p: premises, hypothesis or antecedent

q: conclusion or consequent.

p is a sufficient condition for q

q is a necessary condition for p.

​

​

​

​

​

​

Mathematical Logic [UG Semester IV]

2/19/2022

Example:

p: The Mathematics Department gets a package of Rs. 2 Lacs

q: The Mathematics Department develops a new software lab.

p→q: If the Department gets a package of Rs. 2 Lacs then the Department will develop a new software lab.

Mathematical Logic [UG Semester IV]

2/19/2022

Truth table:

Biconditional (Bi-implication (↔):

​

​

​

​

• p is a necessary and sufficient condition for q.

​

​

​

​

Mathematical Logic [UG Semester IV]

2/19/2022

Example:

p: x is a prime number

q: x is divisible by 1 or itself

Since p and q both are true statement, p↔q is true.

Mathematical Logic [UG Semester IV]

2/19/2022

Connectives

​

​

• The symbols {῀, ᴧ ,ᴠ, →, ↔} are connectives.

​

Mathematical Logic [UG Semester IV]

2/19/2022

Classification of Statements

Mathematical Logic [UG Semester IV]

2/19/2022

Statement formula

1. All statement letters are statement formulas.
2. If A and B are statement formulas, then ῀A, AᴧB, AᴠB, A→B, A↔B are also statement formulas.
3. Only these expressions are statement formula which are determined to be so by virtue of i) and ii).

Mathematical Logic [UG Semester IV]

2/19/2022

Is every statement formula is a statement?

• NO

However, if we substitute specific statement for the statement letters in a statement formula we get a statement.

Mathematical Logic [UG Semester IV]

2/19/2022

Truth Table of statement formulas

Example: Statement formula: p→(qᴧ῀p)

Truth Table:

​

Mathematical Logic [UG Semester IV]

2/19/2022

Tautology

• A statement formula is called a Tautology iff its corresponding truth function takes only the value T.

​

• We shall denote |= A for the assertion “A is a tautology” .

Mathematical Logic [UG Semester IV]

2/19/2022

Example of tautologies

• pᴠ῀p [Law of Excluded Middle]
• [(p→q)ᴧ(q→r)]→(p→r) [Law of Syllogism]

Example: “Socretes is a man”.

“Man is immortal”.

So, “Socretes is immortal.”

• p↔῀῀p, ῀(pᴧ῀p)

Mathematical Logic [UG Semester IV]

2/19/2022

A few results on tautology

Result 1:

If |= A and |= A→B then |= B.

Result 2: (Principle of substitution)

If |= A containing as statement letters p₁,....., p_n

and B arises from A by substituting statement formulas A₁,....., A_n for p₁,....., p_n respectively then |=B.

(i.e. Substitution in a tautology is a tautology)

Mathematical Logic [UG Semester IV]

2/19/2022

Logical Consequence

​

​

• If A→B is a tautology, A is said to logically imply B or alternatively B is said to be a logical consequence of A.

Mathematical Logic [UG Semester IV]

2/19/2022

Logical Consequence

• Let A₁,....., A_n , B be n+1 statement formulas and p₁,....., p_m be the totality of statement letters in A₁,....., A_n , B . The formula B is said to be a logical consequence of A₁,....., A_n (or A₁,....., A_n logically imply B) iff for every assignment of truth values to p₁,....., p_m the formula B receive the truth value T when each of A₁,....., A_n receive the truth value T.
• A₁,....., A_n |= B for the assertion B is a logical consequence of A₁,....., A_n.

​

Mathematical Logic [UG Semester IV]

2/19/2022

Some results

Result 1:

1. A|= B iff |=A→B
2. A₁,.....,A_n|=B iff A₁ᴧ.....ᴧA_n|=B
3. A₁,.....,A_n|=B iff |= A₁ᴧ.....ᴧA_n→B

Result 2:

1. A₁,.....,A_n|=A_i for i=1,2,....,n
2. A₁,.....,A_n|=B_j for j=1,2,....,m and B₁,.....,B_m|=C, then A₁,.....,A_n|=C

Mathematical Logic [UG Semester IV]

2/19/2022

Statement Bundle

• By the statement bundle [A] determined by a statement formula A we mean the set of all statement formulas which are logically equivalent to A.

Note: Logical equivalence is an equivalence relation in the set of statement formulas. Hence the set of st. formulas is partitioned into st. bundle by logical equivalence and the set of st. bundles forms an atomless Boolean algebra.

Mathematical Logic [UG Semester IV]

2/19/2022

Logical Equivalence

• If A↔B is a tautology, A and B are said to be logically equivalent. We denote the logical equivalence by A≡B. Alternatively, A≡B if they have the same truth values.

​

Example: p→q≡῀pᴠq

Mathematical Logic [UG Semester IV]

2/19/2022

Contradiction

• A statement formula is called contradiction iff its corresponding truth function takes only the value F.

|= A iff ῀A is contradiction.

Example: pᴧ῀p is a contradiction.

Mathematical Logic [UG Semester IV]

2/19/2022

Algebra of statement formulas

1. AᴠA≡A; AᴧA≡A [Idempotent Law]
2. (AᴠB)ᴠC≡ Aᴠ(BᴠC); (AᴧB)ᴧC≡ Aᴧ(BᴧC) [Associative Laws]
3. AᴠB≡ BᴠA; AᴧB≡ BᴧA [Commutative Laws]
4. Aᴠ(BᴧC)≡(AᴠB)ᴧ(AᴠC); A ᴧ(BᴠC)≡(AᴧB)ᴠ(AᴧC) [Distributive Laws]
5. AᴠF≡A, AᴠT≡T, AᴧT≡A, A ᴧF≡F [Identity Laws]

Mathematical Logic [UG Semester IV]

2/19/2022

Continued...

6. Aᴠ῀A≡T, A ᴧ῀A≡F, ῀T≡F, ῀F≡T [Complemented Laws]

῀῀A≡A [Law of Double Negation]

7. ῀(AᴠB)≡῀Aᴧ῀B; ῀(AᴧB)≡῀Aᴠ῀B [De Morgan’s Law]

8. Aᴠ(AᴧB)≡A; Aᴧ(AᴠB)≡A [Absorption Law]

9. A→B≡῀B→῀A [Contrapositive Law]

Mathematical Logic [UG Semester IV]

2/19/2022

Adequate system of connectives

We have mentioned so far one unary and four binary connectives There are many more unary and binary connectives, and also n-ary connectives, for n > 2.

• How many unary connectives?
• How many binary connectives?

​

​

Mathematical Logic [UG Semester IV]

2/19/2022

Binary and n-ary connectives

• Which binary connectives do you recognize?
• Question: How many n-ary connectives are there?
• For an n-ary connective (that involves n variables), the truth table has 2ⁿ rows, and the number of possible columns equals the number of possible binary numbers of length (height) 2ⁿ

​

Answer:

​

Mathematical Logic [UG Semester IV]

2/19/2022

Adequate set of connectives

Definition: Any set of connectives with the capability to express all truth tables is said to be adequate.

Emil Post observed in 1921 that the set of standard connectives {¬, ᴧ, ᴠ, →, ↔} is adequate.

Mathematical Logic [UG Semester IV]

2/19/2022

Continued..

Mathematical Logic [UG Semester IV]

2/19/2022

Emil Posts, 1897-1954

In 1921 that the set of standard connectives {¬, ᴧ, ᴠ, →, ↔} is adequate.

Proving adequacy of connective set

• We can show that a new set S of connectives is adequate if we can express all standard connectives in terms of S .
• This is achieved by “translating" all the standard connectives in terms of the new connectives in S , by using tautological equivalences.

Mathematical Logic [UG Semester IV]

2/19/2022

Continued..

• Example: A→B and ¬AᴠB are tautologically equivalent.
• This means that → is definable in terms of (“is

reducible to"; “can be expressed in terms of") ¬ and ᴠ.

• Similarly ᴠ is definable in terms of ¬ and → because AᴠB is tautologically equivalent to ¬A→B.

Mathematical Logic [UG Semester IV]

2/19/2022

Results on adequate system of connectives

Theorem: {¬, ᴧ, ᴠ} are adequate system of connectives.

Proof: Sketch-

¬A is tautologically equivalent to A

AᴧB is tautologically equivalent to AᴧB

AᴠB is tautologically equivalent to AᴠB

A→B is tautologically equivalent to ¬AᴠB

A↔B is tautologically equivalent to (¬AᴠB)ᴧ(¬BᴠA)

​

• All the five standard connectives can be expressed in terms of

¬, ᴧ, ᴠ therefore {¬, ᴧ, ᴠ} is an adequate set of connectives.

​

​

Mathematical Logic [UG Semester IV]

2/19/2022

Corollary

{¬, ᴧ}, {¬, ᴠ} and {¬, →} are adequate.

​

Questions:

1. Is {ᴧ, →} adequate?
2. Is {ᴧ, ᴠ, →, ↔} adequate?
3. Is {¬, ↔} adequate?
4. Is {ᴧ} adequate?

Mathematical Logic [UG Semester IV]

2/19/2022

Peirce arrow (↓)

Mathematical Logic [UG Semester IV]

2/19/2022

C. S. Peirce (1839-1914)

Truth table for Peirce arrow ↓

Mathematical Logic [UG Semester IV]

2/19/2022

The Peirce arrow, “↓", has the property that each of the standard

connectives is definable in terms of “↓".

Proof that Peirce arrow is adequate

We can express the standard connectives in terms of the Peirce ↓ by

¬p≡p↓p, pᴧq≡(p↓p)↓(q↓q)

pᴠq≡(p↓q)↓ (p↓q)

p→q≡((p↓p)↓q)↓ ((p↓p)↓q)

p↔q≡((p↓p)↓q)↓ ((q↓p)↓q)

Thus it follows that the set consisting of a single connective, the

Peirce arrow, “↓”(also called NOR) is adequate.

Note: Thus, to test a new set of connectives S for being adequate, it suffices to test if ↓ can be expressed by S .

Mathematical Logic [UG Semester IV]

2/19/2022

Sheffer stroke |�

​

​

​

​

​

​

Mathematical Logic [UG Semester IV]

2/19/2022

H.M.Sheffer (1882-1964

Truth table for sheffer stroke |

Mathematical Logic [UG Semester IV]

2/19/2022

One can show that the Sheffer stroke “|” also has the property that

each of the standard connectives is definable in terms of “|”.

Adequacy of Sheffer’s stroke |

¬p≡p|p, pᴠq≡(p|p)|(q|q)

​

Note :The set of connectives consisting of only one connective, the Sheffer stroke, “|”, (also called NAND), is adequate.

Mathematical Logic [UG Semester IV]

2/19/2022

Theorem

​

• The only one element adequate system of binary connectives are {↓} and {|}.

Mathematical Logic [UG Semester IV]

2/19/2022

Powerful connectives in decreasing order

​

↔

→

ᴠ

ᴧ

¬

Mathematical Logic [UG Semester IV]

2/19/2022

Mathematical Logic [UG Semester IV]

2/19/2022

Thank You