A brief discussion about Logic: Part 1

Introduction

Discrete math is an important area of computer science. Because using this we can express any fact to a mathematical statement. Now first I like to talk about logic.

Logic:

Logic is necessary to check the validity of any mathematical statement. Logic has some set of rules. To learn about logic more we need to know about proposition, propositional operators and propositional operators.

1.1 Proposition

A proposition is a sentence which is true or false. Or we can say that a statement which is either true or false. For example:

1. <city><place>London is the capital of <country-region><place>UK.
2. 3+5 = 8
3. 1 – 1 = 5
4. What is today's weather forecast?

Statement 4 is not a proposition because it has neither true nor false value. Statement 1 to 3 is proposition. This type of propositions is called primitive proposition because it cannot be broken down.

1.2 Compound Proposition

Compound proposition is composed of two or more propositions. For example:

1."The sky is blue and today is hot"

We can break down this into two propositions.

a." The sky is blue" b. "Today is hot"

2."Students who know math and statistics can use this computer"

We can break down this into two propositions.

a." Students who know math can use this computer" b. "Students who know statistics can use this computer"

1.3 Negation

Negation is the alternate view of the proposition.

For example:

Proposition: "Today is a sunny day"

Negation: "Today is not Monday"

2.1 Mathematical expression & operator

We can express proposition by using some operator. For example:

p: Today is a sunny day (Primitive Proposition)

q: I like to eat ice-cream.(Primitive Proposition)

Today is a sunny day and I like to eat ice-cream (Compound Proposition)

p<shapetype id="_x0000_t75" stroked="f" filled="f" path="m@4@5l@4@11@9@11@9@5xe" o:preferrelative="t" o:spt="75" coordsize="21600,21600"> <stroke joinstyle="miter"><formulas><f eqn="if lineDrawn pixelLineWidth 0"><f eqn="sum @0 1 0"><f eqn="sum 0 0 @1"><f eqn="prod @2 1 2"><f eqn="prod @3 21600 pixelWidth"><f eqn="prod @3 21600 pixelHeight"><f eqn="sum @0 0 1"><f eqn="prod @6 1 2"><f eqn="prod @7 21600 pixelWidth"><f eqn="sum @8 21600 0"><f eqn="prod @7 21600 pixelHeight"><f eqn="sum @10 21600 0"></formulas><path o:connecttype="rect" gradientshapeok="t" o:extrusionok="f"><lock aspectratio="t" v:ext="edit"><shape id="_x0000_i1025" style="WIDTH: 11.25pt; HEIGHT: 9.75pt" type="#_x0000_t75"><imagedata src="file:///D:\DOCUME~1\NEMO~1.NAU\LOCALS~1\Temp\msohtml1\01\clip_image001.wmz">q (Mathematical expression)

There are different types of operators are used to express propositions.

2.1.1 And or conjunction operator (<shape id="_x0000_i1026" style="WIDTH: 11.25pt; HEIGHT: 9.75pt" type="#_x0000_t75"> <imagedata src="file:///D:\DOCUME~1\NEMO~1.NAU\LOCALS~1\Temp\msohtml1\01\clip_image003.wmz">)

Truth table:

p	q	pq
T	T	T
T	F	F
F	T	F
F	F	F

For example:

"Today is very sunny and we will play tennis"

p: Today is very sunny day (Primitive Proposition)

q: we will play tennis.(Primitive Proposition)

pq (Mathematical expression)

Here if p: "Today is very sunny day" statement is false or q: "we will play tennis" statement is false then the value of the compound proposition will be false.

2.1.2 Or or Disjunction (<shape id="_x0000_i1058" style="WIDTH: 11.25pt; HEIGHT: 9.75pt" type="#_x0000_t75"> <imagedata src="file:///D:\DOCUME~1\NEMO~1.NAU\LOCALS~1\Temp\msohtml1\01\clip_image004.wmz">)

Truth table:

p	q	p<shape id="_x0000_i1059" style="WIDTH: 11.25pt; HEIGHT: 9.75pt" type="#_x0000_t75"> <imagedata src="file:///D:\DOCUME~1\NEMO~1.NAU\LOCALS~1\Temp\msohtml1\01\clip_image004.wmz">q
T	T	T
T	F	T
F	T	T
F	F	F

For example:

"Today we will play tennis or football"

p: Today we will play tennis (Primitive Proposition)

q: Today we will play football(Primitive Proposition)

p<shape id="_x0000_i1046" style="WIDTH: 11.25pt; HEIGHT: 9.75pt" type="#_x0000_t75"> <imagedata src="file:///D:\DOCUME~1\NEMO~1.NAU\LOCALS~1\Temp\msohtml1\01\clip_image004.wmz">q (Mathematical expression)

Here if p: "Today we will play tennis" statement is false and q: "Today we will play football" statement is false then the value of the compound proposition will be false.

2.1.3 Not (<shape id="_x0000_i1047" style="WIDTH: 12pt; HEIGHT: 8.25pt" type="#_x0000_t75"> <imagedata src="file:///D:\DOCUME~1\NEMO~1.NAU\LOCALS~1\Temp\msohtml1\01\clip_image006.wmz">)

Truth table:

p	<shape id="_x0000_i1048" style="WIDTH: 12pt; HEIGHT: 8.25pt" type="#_x0000_t75"> <imagedata src="file:///D:\DOCUME~1\NEMO~1.NAU\LOCALS~1\Temp\msohtml1\01\clip_image008.wmz"> p
T	F
T	F
F	T
F	T

For example:

"Today we will play tennis"

p: Today we will play tennis (Primitive Proposition)

<shape id="_x0000_i1049" style="WIDTH: 12pt; HEIGHT: 8.25pt" type="#_x0000_t75"><imagedata src="file:///D:\DOCUME~1\NEMO~1.NAU\LOCALS~1\Temp\msohtml1\01\clip_image006.wmz">p: Today we will not play tennis (Primitive Proposition)

2.1.4 Implication (<shape id="_x0000_i1060" style="WIDTH: 15pt; HEIGHT: 11.25pt" type="#_x0000_t75"> <imagedata src="file:///D:\DOCUME~1\NEMO~1.NAU\LOCALS~1\Temp\msohtml1\01\clip_image009.wmz">)

Truth table:

p	q	p<shape id="_x0000_i1054" style="WIDTH: 15pt; HEIGHT: 11.25pt" type="#_x0000_t75"> <imagedata src="file:///D:\DOCUME~1\NEMO~1.NAU\LOCALS~1\Temp\msohtml1\01\clip_image011.wmz">q
T	T	T
T	F	F
F	T	T
F	F	T

For example:

"If it is a sunny day then Mr. Reedtooth comes here"

p: it is a sunny day (Primitive Proposition)

q: Mr. Reedtooth comes here (Primitive Proposition)

p<shape id="_x0000_i1055" style="WIDTH: 15pt; HEIGHT: 11.25pt" type="#_x0000_t75"> <imagedata src="file:///D:\DOCUME~1\NEMO~1.NAU\LOCALS~1\Temp\msohtml1\01\clip_image012.wmz">q (Mathematical expression)(If p then q)

Here the concept of Implication (<shape id="_x0000_i1056" style="WIDTH: 15pt; HEIGHT: 11.25pt" type="#_x0000_t75"> <imagedata src="file:///D:\DOCUME~1\NEMO~1.NAU\LOCALS~1\Temp\msohtml1\01\clip_image009.wmz">) is totally different from other operators like "and"," or". Because in both cases p proposition and q proposition independently create a impact upon the compound proposition. But here p: "it is a sunny day" is totally independent .It can either true or false and the value of the compound proposition will be true. But if p is true but q is false then the total statement will be false. It is just like this-

Function STAR( )

If A>B--------------line 1

PRINT "HELLO"--------line 2

Function STAR () is mathematically valid until line 1 and line 2 execute perfectly. If line 1 is true then machine automatically execute line 2. If machine does not execute 2 then Function STAR () is in valid.

2.1.5 Converse (<shape id="_x0000_i1028" style="WIDTH: 15pt; HEIGHT: 11.25pt" type="#_x0000_t75"> <imagedata src="file:///D:\DOCUME~1\NEMO~1.NAU\LOCALS~1\Temp\msohtml1\01\clip_image013.wmz">)

Truth table:

q	p	p<shape id="_x0000_i1029" style="WIDTH: 15pt; HEIGHT: 11.25pt" type="#_x0000_t75"> <imagedata src="file:///D:\DOCUME~1\NEMO~1.NAU\LOCALS~1\Temp\msohtml1\01\clip_image015.wmz">q
T	T	T
T	F	F
F	T	T
F	F	T

Converse is just the opposite of Implication (<shape id="_x0000_i1030" style="WIDTH: 15pt; HEIGHT: 11.25pt" type="#_x0000_t75"> <imagedata src="file:///D:\DOCUME~1\NEMO~1.NAU\LOCALS~1\Temp\msohtml1\01\clip_image009.wmz">). For example:

"If it is a sunny day then Mr. Reedtooth comes here" (p<shape id="_x0000_i1031" style="WIDTH: 15pt; HEIGHT: 11.25pt" type="#_x0000_t75"> <imagedata src="file:///D:\DOCUME~1\NEMO~1.NAU\LOCALS~1\Temp\msohtml1\01\clip_image012.wmz">q)

"If Mr. Reedtooth comes here then it is a sunny day" (p<shape id="_x0000_i1032" style="WIDTH: 15pt; HEIGHT: 11.25pt" type="#_x0000_t75"> <imagedata src="file:///D:\DOCUME~1\NEMO~1.NAU\LOCALS~1\Temp\msohtml1\01\clip_image015.wmz">q) (If q then p)

p: it is a sunny day (Primitive Proposition)

q: Mr. Reedtooth comes here (Primitive Proposition)

Here q is independent.

2.1.5 Biconditional ()

Truth table:

p	q	pq
T	T	T
T	F	F
F	T	T
F	F	T

For example:

"It is raining and the match is postponed"

p: It is raining (Primitive Proposition)

q: the match is postponed (Primitive Proposition)

p<shape id="_x0000_i1050" style="WIDTH: 15.75pt; HEIGHT: 11.25pt" type="#_x0000_t75"> <imagedata src="file:///D:\DOCUME~1\NEMO~1.NAU\LOCALS~1\Temp\msohtml1\01\clip_image016.wmz">q (Mathematical expression)(If p then q)

Here if p is true then q is true or we can say if q is true then p must be true. So in this case we use this Biconditional (<shape id="_x0000_i1051" style="WIDTH: 15.75pt; HEIGHT: 11.25pt" type="#_x0000_t75"> <imagedata src="file:///D:\DOCUME~1\NEMO~1.NAU\LOCALS~1\Temp\msohtml1\01\clip_image016.wmz">) operator.

Logical Equivalence:

A statement P(a1, b1) and another statement Q(a2, b2) and if they are logically equivalent then P(a1, b1) <shape id="_x0000_i1033" style="WIDTH: 17.25pt; HEIGHT: 12pt" type="#_x0000_t75"><imagedata src="file:///D:\DOCUME~1\NEMO~1.NAU\LOCALS~1\Temp\msohtml1\01\clip_image019.wmz"> Q(a2, b2)

From De Morgan's law we know that

If you want , using a truth table you can check this.

So today I want to stop here. I am not very expert about these things so if anyone has any questions or suggestions then please make a comment. Thank you.

To prepare this article I take help from two books.1)Discrete mathematics and its applications by Kenneth H.Rosen 2)Discrete Mathmatics by Schaum`s outlines.