65.9K
CodeProject is changing. Read more.
Home

A brief discussion about Logic: Part 1

starIcon
emptyStarIcon
starIcon
emptyStarIconemptyStarIconemptyStarIcon

1.50/5 (2 votes)

Sep 10, 2007

5 min read

viewsIcon

15370

This article gives a brief discussion about Proposition, Proposition operator and Logical Equivalence.

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. London is the capital of 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 <formulas></formulas>q (Mathematical expression)

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

2.1.1 And or conjunction operator (Screenshot - and.gif )

Truth table:

p

q

pScreenshot - and.gifq

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)

pScreenshot - and.gifq (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 (Screenshot - or.gif )

Truth table:

p

q

pScreenshot - or.gif 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 Screenshot - or.gifq (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 (Screenshot - not.gif )

Truth table:

p

Screenshot - not.gif

p

T

F

T

F

F

T

F

T

For example:

"Today we will play tennis"

p: Today we will play tennis (Primitive Proposition)

p: Today we will not play tennis (Primitive Proposition)

2.1.4 Implication ( Screenshot - implication.gif)

Truth table:

p

q

pScreenshot - implication.gif 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 Screenshot - implication.gifq (Mathematical expression)(If p then q)

Here the concept of Implication ( ) 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 (Screenshot - converse.gif )

Truth table:

q

p

pScreenshot - converse.gif q

T

T

T

T

F

F

F

T

T

F

F

T

Converse is just the opposite of Implication ( ). For example:

"If it is a sunny day then Mr. Reedtooth comes here" (p Screenshot - implication.gifq)

"If Mr. Reedtooth comes here then it is a sunny day" (p Screenshot - converse.gifq) (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 (Screenshot - equivalence.gif)

Truth table:

p

q

pScreenshot - equivalence.gifq

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 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 (Screenshot - equivalence.gif ) operator.

Logical Equivalence:

A statement P(a1, b1) and another statement Q(a2, b2) and if they are logically equivalent then P(a1, b1) Screenshot - equivalence.gif Q(a2, b2)

From De Morgan's law we know that

Screenshot - demorgan.gif

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.