Notesale: Turn your study into money

Document Preview

Extracts from the notes are below, to see the PDF you'll receive please use the links above

---

FE(CS) Batch 2014-15
CS-211

Propositional Logic-I

Propositional Logic-I
The handouts 2 and 3 describe fundamentals of propositional
logic
...


NED University of Engineering & Technology
Computer & Information Systems Engineering
7/6/2015

Page 1 of 4

FE(CS) Batch 2014-15
CS-211

Propositional Logic-I

One of the people present said: ‘Persuade me that logic is useful
...
– ‘Yes
...
– ‘Then how will you know if I produce a sophism?’ – He said nothing
...
’
Epictetus1 Discourses2 II xxv
...
It also provides a formalism to translate statements into
formal symbols
...
Logic helps distinguish between valid and
invalid arguments and provides use of correct reasoning
...
These rules are used in design of digital systems,
development of computer programs, proof of correctness, and in many other ways
...


Proposition
A proposition is a declarative statement which is either true or false, but not both
...

 1 + 2 = 5
...
For
example, p is the proposition label in p = all computers work on binary logic
...
(A proposition declaring a single
fact is a simple proposition)
...

1
...
However, in formal logic, the caret symbol (⋀) is used
instead
...

Example
Let,
p: I appeared in exam
q: I got through
p ⋀ q: I appeared in exam and [I] got through
...
D
...


2

Translated by Jonathan Barnes in his book
Page 2 of 4

FE(CS) Batch 2014-15
CS-211

Propositional Logic-I

2
...
However, in formal logic, the symbol (⋁) is used
...

Example 1
Let,
p: He got A in Math
...

p ⋁ q: He got A in Math OR [he] got B in English
...
Specifically, it’s true even when both

This compound proposition is true when either of
propositions are true
...

Example 2
Let,
p: He got A in Math
...

p ⊕ q: He got A in Math OR [he] got B in Math
...
However, it cannot be true when both
propositions are true
...

In the former case (example 1), when the compound proposition is true even when both propositions are true
is called inclusive-OR (⋁)
...
Negation
This is not a connective but a useful logical operator as it reverses the meaning of proposition
...

p ¬p
T
F
F
T

A propositional form that is always true is called a tautology
...

A propositional form that is always false is called a contradiction
...

A proposition that is neither a tautology nor a contradiction is called a contingency
...
Conjunctive Normal Form (CNF)
This consists of the joining of disjunctive clauses by conjunction e
...
(p ⋁ q) ⋀ (¬ q ⋁ r)
2
...
g
...
Here, p
is called the hypothesis (also called antecedent) of the implication, and q is the conclusion (also called consequent)
...

 If you passed the class, you received a certificate
...
Such propositional forms are
said to be logically equivalent, written “≡"
...

Implication does not specify a cause-&-effect relation; rather it can be well understood in terms of a pledge or a promise
...
e
...
This means that many statements that sound nonsensical in
English are true in the context of mathematics
...
g
...
When an implication is stupidly
true because the hypothesis is false, we say that it is vacuously true
...

-Bertrand Russell

Page 4 of 4



---