Logic in Computer Science�CS 19.305

By,

Dr. Mrinal Paliwal

Unit 1

​

Introduction: Role of logic in computer science, problem representation, review of the principle of mathematical induction, the principle of structural induction, review of Boolean algebra, language, models, interpretations, validity, proof, decision problems in logic, decidability.

Role of logic in computer science

What is logic

• Logic is the base of all mathematical reasoning and of all automated reasoning
• It is a mathematical base of computer
• It is about (focus) on how to get reliability to get conclusion from the given assumptions

Any Formal System can be considered a logic if

• A well-defined syntax
• A well-defined Semantics
• A well-defined proof theory

Logic is about Reasoning:

• Validity of arguments
• Consistency among set of statements
• Matter of truth or false

Role of logic in computer science

P→Q =˥P V Q

 In logic, an argument requires a set of (at least) two declarative sentences (or "propositions") known as the "premises" (or "premisses")

Role of logic in computer science

Consistency among set of statements

• We say that a statement, or set of statements is logically consistent when it involves no logical contradiction. A logical contradiction is the conjunction of a statement S and its denial not-S.

  In logic, it is a fundamental law- the law of non contradiction- that a statement and its denial cannot both be true at the same time.  Here are some simple examples of contradictions.

• I love to watch cricket and I don't watch cricket .
• Butch is married to Barb but Barb is not married to Butch.
• The restaurant opens at five o'clock and it begins serving between four and nine.
• John Lasagna will be a little late for the party.  He died yesterday.� 

Note: A formula of the form -~F is called negation of F. A formula of the form (F ∨ G) is called disjunction of F and G, and (F ∧ G) is the conjunction of F and G.

Role of logic in computer science

Logic is Truth Preserving System of Interference

• Truth Preserving :

If the initial statements are true

then Inferred Statements will be true

​

• System:

A set of mechanism transformations based on syntax alone

​

• Inference:

The process of driving new statements from old statements

Role of logic in computer science

Role of Logic

​

The role of logic in Computer Science is to develop a language for situations we encounter as a Computer Professionals

Applications of Logic:

• Computer Architecture(Logic Gates)
• Programming Language(Semantic)
• Database(Relational Algebra)
• Artificial Intelligence(Automatic Theory Proving)

Role of logic in computer science

Logic Evolution

• In the early years of this century symbolic or formal logic became quite popular with philosophers and mathematicians because they were interested in the concept of what constitutes a correct proof in mathematics.
• Concept of logic then hinged upon what is a correct argument as opposed to a wrong (or faulty)
• Logic is the science of the correctness or incorrectness of reasoning, or the study of the evaluation of arguments.

​

Role of logic in computer science

Syntax is all about expressions: words and sentences. Examples of syntactic claims

• ‘Bertrand Russell’ is a proper noun.
• ‘likes logic’ is a verb phrase.
• ‘Bertrand Russell likes logic’ is a sentence.
• Combining a proper noun and a verb phrase in this way makes a sentence.

Semantics is all about meanings of expressions. Examples of semantic claims

• ‘Bertrand Russell’ refers to a British philosopher.
• ‘Bertrand Russell’ refers to Bertrand Russell.
• ‘likes logic’ expresses a property Russell has.
• ‘Bertrand Russell likes logic’ is true.

Any Formal System can be considered a logic if

• A well-defined syntax
• A well-defined Semantics
• A well-defined proof theory

Role of logic in computer science

Combining sentences and connectives makes new sentences.

Some complex sentences

• ‘It is not the case that’ and ‘Bertrand Russell likes logic’ make: ‘It is not the case that Bertrand Russell likes logic’.
• ‘¬’ and ‘P’ make: ‘¬P’.
• ‘Bertrand Russell likes logic’ and ‘and’ and ‘Philosophers like conceptual analysis’ make:
• ‘Bertrand Russell likes logic and philosophers like conceptual analysis’.
• ‘P’, ‘∧’ and ‘Q’ make: ‘(P ∧ Q)’

Role of logic in computer science

Mathematical Induction

• It is a method of mathematical proof typically used to establish that a given statement is true of all natural numbers.
• A method of proof
• It does not generate answers: it only can prove them

​

• It works in three parts:

​

• Base case(s): show it is true for one element

​

• Inductive hypothesis: assume it is true for any given element, Must be clearly labeled!!!

​

• Show that if it true for the next highest element

Mathematical Induction

• Question: 1.1

Use mathematical induction to prove

S_n = 2 + 4 + 6 + 8 + ^{. . .} + 2n = n(n + 1)

for every positive integer n.

Step 1: Show that the formula is true when n = 1.

S₁ = n(n + 1) = 1(1 + 1) = 2 is True

Step 2: Assume the formula is valid for some integer k. Use this assumption to prove the formula is valid for the next integer, k + 1 and show that the formula

S_K+1 = (k + 1)(k + 2) is true

​

Mathematical Induction

• Mathematical induction is a legitimate method of proof for all positive integers n

​

• Principle: �

Let P_n be a statement involving n, a positive integer. If

1. P₁ is true, and

2. the truth of P_k implies the truth of P_{k + 1} for every positive k,

then P_n must be true for all positive integers n.

​

• Base Step
• Inductive Step

​

Note: Mathematical Induction is only used for natural numbers

Mathematical Induction

Let’s assume

S_k = 2 + 4 + 6 + 8 + ^{. . .} + 2k = k(k + 1) // assuming that it will hold

Now,

S_{k + 1} = 2 + 4 + 6 + 8 + ^{. . .} + 2k + [2(k + 1)]

= 2 + 4 + 6 + 8 + ^{. . .} + 2k + (2k + 2)

=S_k + (2k + 2)

= k(k + 1) + (2k + 2) Replace S_k by k(k + 1).

= k² + k + 2k + 2

= k² + 3k + 2

= (k + 1)(k + 2)

= (k + 1)((k + 1)+1)

The formula S_n = n(n + 1) is valid for all positive integer values of n.

Mathematical Induction

Question:1.2 Prove that the sum of the first n natural numbers is given by this formula:

1 + 2 + 3 + .  .  .  + n = n(n + 1)�     2

First, we will assume that the formula is true for n = k; that is, we will assume:

1 + 2 + 3 + .  .  .  + k   =  k(k + 1) �     2                   (1)

This is the induction assumption.  Assuming this, we must prove that the formula is true for its successor, n = k + 1.  That is, we must show:

1 + 2 + 3 + .  .  .  + (k + 1)  =  (k + 1)(k + 2)�         2         (2)

Mathematical Induction

To do that, we will simply add the next term  (k + 1)  to both sides of the induction assumption in equation 1

1 + 2 + 3 + .  .  .  + k+ (k+1)  =  k(k + 1) + (k+1) �     2                   

= k(k + 1) + 2(k+1)

2

= (k + 1)(k+2)

         2         

(on taking (k+1) as a common factor)

Does it corresponds to equation 2; Yes ; Its true

Mathematical Induction

Assignments

​

1.3 Prove that�1² + 2² + 3² + ... + n² = n (n + 1) (2n + 1)/ 6�For all positive integers n.

1.4 Use mathematical induction to prove that�1³ + 2³ + 3³ + ... + n³ = n² (n + 1)² / 4�for all positive integers n.

1.5 By induction prove that n² - 3n + 4 is even and it is true for all positive integers.

1.6 Prove that 3 ⁿ > n ² for n = 1, n = 2 and use the mathematical induction to prove that 3 ⁿ > n ² for n a positive integer greater than 2.

1.7 Prove that n ! > 2 ⁿ for n a positive integer greater than or equal to 4. (Note: n! is n factorial and is given by 1 * 2 * ...* (n-1)*n.)

Mathematical Induction

Mathematical Induction

Mathematical Induction

Mathematical Induction

Mathematical Induction

Statement P (n) is defined by 3 ⁿ > n ²�STEP 1: We first show that p (1) is true. Let n = 1 and calculate 3 ¹ and 1 ² and compare them�3 ¹ = 3�1 ² = 1 3 is greater than 1 and hence p (1) is true.�Let us also show that P(2) is true.�3 ² = 9�2 ² = 4 Hence P(2) is also true.�STEP 2: We now assume that p (k) is true�3 ^k > k ²�Multiply both sides of the above inequality by 3�3 * 3 ^k > 3 * k ²�The left side is equal to 3 ^{k + 1}. For k >, 2, we can write�k ² > 2 k and k ² > 1�We now combine the above inequalities by adding the left hand sides and the right hand sides of the two inequalities�2 k ² > 2 k + 1 We now add k ² to both sides of the above inequality to obtain the inequality�3 k ² > k ² + 2 k + 1 Factor the right side we can write�3 * k ² > (k + 1) ²�If 3 * 3 ^k > 3 * k ² and 3 * k ² > (k + 1) ^{2 then}�3 * 3 ^k > (k + 1) ²�Rewrite the left side as 3 ^{k + 1}�3 ^{k + 1} > (k + 1) ²�Which proves tha P(k + 1) is true

• Developed by English Mathematician George Boole in between 1815 - 1864.
• It is described as an algebra of logic or an algebra of two values i.e True or False.
• The term logic means a statement having binary decisions i.e True/Yes or False/No.

Boolean Algebra

APPLICATION OF BOOLEAN ALGEBRA

It is used to perform the logical operations in digital computer.

In digital computer True represent by ‘1’ (high volt) and False represent by ‘0’ (low volt)

Logical operations are performed by logical operators. The fundamental logical operators are:

1. AND (conjunction)

2. OR (disjunction)

3. NOT (negation/complement)

​

AND

It performs logical multiplication and denoted by (.) dot.

X Y X.Y

0 0 0

0 1 0

1 0 0

1 1 1

Boolean Algebra

OR

It performs logical addition and denoted by (+) plus.

X Y X+Y

0 0 0

0 1 1

1 0 1

1 1 1

NOT

It performs logical negation and denoted by (-) bar. It operates on single variable.

X X (means complement of x)

0 1

1 0

1. Evaluate the following Boolean expression using Truth Table.

(a) X’Y’+X’Y (b) X’YZ’+XY’

(c) XY’(Z+YZ’)+Z’

​

2. Verify that P+(PQ)’ is a Tautology.

3. Verify that (X+Y)’=X’Y’

​

Note:

• If the output of Boolean expression is always True or 1 is called Tautology.
• If the output of Boolean expression is always False or 0 is called Fallacy.

​

Boolean Algebra

Logic Gates

A gate is an digital circuit which operates on one or more signals and produce single output.

Gates are digital circuits because the input and output signals are denoted by either 1(high voltage) or 0(low voltage).

There are three basic gates and are:

Boolean Algebra

• The AND gate is an electronic circuit that gives a high output (1) only if all its inputs are high.
• AND gate takes two or more input signals and produce only one output signal.

Boolean Algebra

• The OR gate is an electronic circuit that gives a high output (1) if one or more of its inputs are high.
• OR gate also takes two or more input signals and produce only one output signal.

​

​

Boolean Algebra

• The NOT gate is an electronic circuit that gives a high output (1) if its input is low .
• NOT gate takes only one input signal and produce only one output signal.
• The output of NOT gate is complement of its input.
• It is also called inverter.

​

​

Boolean Algebra

AND Gate

So while going out of the house you set the "Alarm Switch" and if the burglar enters he will set the "Person switch", and tada the alarm will ring.

PRACTICAL APPLICATIONS OF LOGIC GATES

• Electronic door will only open if it detects a person and the switch is set to unlocked. 
• Microwave will only start if the start button is pressed and the door close switch is closed. 

OR Gate

You would of course want your doorbell to ring when someone presses either the front door switch or the back door switch..(nice)

PRACTICAL APPLICATIONS OF LOGIC GATES

NOT Gate

When the temperature falls below 20 degree celcius the Not gate will set on the central heating system (cool huh).

PRACTICAL APPLICATIONS OF LOGIC GATES

NAND, NOR XOR, XNOR GATES

NAND Gate

Known as a “universal” gate because ANY digital circuit can be implemented with NAND gates alone.

 NAND gates are used in Alarm circuit using LDR(Light Dependent Register), Freezer warning buzzer circuits, automatic temperature control circuits.

NAND Gate

NOR Gate

NOR Gate

NOR

X

Y

Z

X Y Z

0 0 1

0 1 0

1 0 0

1 1 0

Z = ~(X | Y)

NOR(Z,X,Y)

These are used in combinational circuits such as multipliers, multiplexers, half and full adders, and in ripple-carry adders.

Exclusive-OR Gate

Exclusive-OR Gate

X Y Z

XOR

X

Y

Z

0 0 0

0 1 1

1 0 1

1 1 0

Z = X ^ Y

XOR(Z,X,Y)

XOR gates are used in circuits that perform arithmetic operations and calculations, especially in half-adders and adders. 

Exclusive-NOR Gate

Exclusive-NOR Gate

X Y Z

XNOR

X

Y

Z

0 0 1

0 1 0

1 0 0

1 1 1

Z = ~(X ^ Y)

Z = X ~^ Y

XNOR(Z,X,Y)

The XNOR logic gates are used in error detecting circuits which are to detect Odd parity or even parity bits in digital data transmission circuits.

Logic Gates

Basic Theorem of Boolean Algebra

T1 : Properties of 0

(a) 0 + A = A �(b) 0 * A = 0

T2 : Properties of 1

(a) 1 + A = 1 �(b) 1 * A = A

T3 : Commutative Law

• A + B = B + A
• A. B = B. A

T4 : Associate Law

• (A + B) + C = A + (B + C)
• (A. B) C = A (B. C)

T5 : Distributive Law

(a) A (B + C) = A B + A C�(b) A + (B .C) = (A + B) (A + C)

(c) A+A’B = A+B

T6 : Indempotence (Identity ) Law

(a) A + A = A �(b) A . A = A

​

T7 : Absorption (Redundance) Law

• A + A B = A
• A (A + B) = A

T8 : Complementary Law

(a) X+X’=1

(b) X.X’=0

T9 : Involution

(a) x’’ = x

T10 : De Morgan's Theorem

(a) (X+Y)’=X’.Y’

(b) (X.Y)’=X’+Y’

Boolean Expression

Example: Calculate A′B′C+A′BC′+A′BC+AB′C′+AB′C+ABC′+ABC

​

=A′B′C+A′BC′+A′BC+AB′C′+AB′C+ABC′+ABC

=A′(B′C+BC′+BC)+A(B′C′+B′C+BC′+BC)

=A′(B′C+B(C′+C))+A(B′(C′+C)+B(C′+C))

=A′(B′C+B)+A(B′+B)

=A′(B′C+B)+A

=A′(B+C)+A

=A+B+C�

Boolean Expression

Boolean Expression

Definition of a Proposition

A proposition (p, q, r, …) is simply a statement (i.e., a declarative sentence) with a definite meaning, having a truth value that’s either true (T) or false (F) (never both, neither, or somewhere in between).

​

(However, you might not know the actual truth value, and it might be situation-dependent.)

48

Topic #1 – Propositional Logic

Examples of Propositions

• “It is raining.” (In a given situation.)
• “Beijing is the capital of China.”
• “1 + 2 = 3”

But, the following are NOT propositions:

• “Who’s there?” (interrogative, question)
• “La la la la la.” (meaningless interjection)
• “Just do it!” (imperative, command)
• “Yeah, I sorta dunno, whatever...” (vague)
• “1 + 2” (expression with a non-true/false value)

49

Topic #1 – Propositional Logic

Operators / Connectives

An operator or connective combines one or more operand expressions into a larger expression.

(E.g., “+” in numeric exprs.)

​

Unary operators take 1 operand (e.g., −3); binary operators take 2 operands (eg 3 × 4).

Propositional or Boolean operators operate on propositions or truth values instead of on numbers.

50

Topic #1.0 – Propositional Logic: Operators

Some Popular Boolean Operators

51

The Negation Operator

The unary negation operator “¬” (NOT) transforms a prop. into its logical negation.

E.g. If p = “I have brown hair.”

then ¬p = “I do not have brown hair.”

Truth table for NOT:

52

T :≡ True; F :≡ False

“:≡” means “is defined as”

​

Operand�column

​

Result�column

Topic #1.0 – Propositional Logic: Operators

The Conjunction Operator

The binary conjunction operator “∧” (AND) combines two propositions to form their logical conjunction.

​

E.g. If p=“I will have biryani for lunch.” and q=“I will have salad for dinner.”, then

​

p ∧q =“I will have biryani for lunch and I will have salad for dinner.”

53

Remember: “∧” points up like an “A”, and it means “AND”

Topic #1.0 – Propositional Logic: Operators

Conjunction Truth Table

• Note that a conjunction�p₁ ∧ p₂ ∧ … ∧ p_n�of n propositions�will have 2ⁿ rows�in its truth table.

​

​

​

• Also: ¬ and ∧ operations together are sufficient to express any Boolean truth table!

54

Topic #1.0 – Propositional Logic: Operators

The Disjunction Operator

The binary disjunction operator “∨” (OR) combines two propositions to form their logical disjunction.

​

p=“My car has a bad engine.”

q=“My car has a bad carburetor.”

p∨q=“Either my car has a bad engine or � my car has a bad carburetor.”

55

After the downward-�pointing “axe” of “∨”�splits the wood, you�can take 1 piece OR the other, or both.

Topic #1.0 – Propositional Logic: Operators

Meaning is like “and/or” in English.

Disjunction Truth Table

• Note that p∨q means�that p is true, or q is�true, or both are true!
• So, this operation is�also called inclusive or,�because it includes the�possibility that both p and q are true.
• “¬” and “∨” together are also universal.

56

Note�difference�from AND

Topic #1.0 – Propositional Logic: Operators

Nested Propositional Expressions

• Use parentheses to group sub-expressions:

�“I just saw my old friend (f), and either he’s grown (g) or I’ve shrunk (s).” = f ∧ (g ∨ s)

• (f ∧ g) ∨ s would mean something different
• f ∧ g ∨ s would be ambiguous

​

• By convention, “¬” takes precedence over both “∧” and “∨”.
• ¬s ∧ f means (¬s) ∧ f , not ¬ (s ∧ f)

57

Topic #1.0 – Propositional Logic: Operators

A Simple Exercise

Let p=“It rained last night”, � q=“The sprinklers came on last night,” � r=“The lawn was wet this morning.”

Translate each of the following into English:

¬p =

​

r ∧ ¬p =

​

¬ r ∨ p ∨ q =

58

Topic #1.0 – Propositional Logic: Operators

The Exclusive Or Operator

​

The binary exclusive-or operator “⊕” (XOR) combines two propositions to form their logical “exclusive or” (exjunction?).

​

p = “I will earn an A in this course,”

q = “I will drop this course,”

p ⊕ q = “I will either earn an A for this course, or I will drop it”

(but not both!)

59

Topic #1.0 – Propositional Logic: Operators

Exclusive-Or Truth Table

• Note that p⊕q means�that p is true, or q is�true, but not both!
• This operation is�called exclusive or,�because it excludes the�possibility that both p and q are true.
• “¬” and “⊕” together are not universal.

60

Note�difference�from OR.

Topic #1.0 – Propositional Logic: Operators

Natural Language is Ambiguous

Note that English “or” can be ambiguous regarding the “both” case!

“Pat is a singer or�Raju is a writer.” –

​

“Raju is a man or�Raju is a woman.” -

​

Need context to disambiguate the meaning!

For this class, assume “or” means inclusive.

61

∨

⊕

Topic #1.0 – Propositional Logic: Operators

Set Theory

Set Theory

Set Theory

Set Theory

Set Theory

Set Theory

Set Theory

Decidability

In logic, decidable refers to the question of whether there is an effective method for deciding membership in a set of formulas (or judgments in type theory). Here we take an effective method to be given by any of the equivalent formal characterizations (general recursion?, Turing machines, lambda calculus) that according to the Church-Turing thesis capture the informal notion.

Decidability of a logical system

A logical system is decidable if there is an algorithm deciding whether a given formula is a theorem of the system.

In this sense, propositional logic and monadic predicate logic? are decidable, whereas first-order logic and higher-order logic are undecidable.