Transcript DISCRETE COMPUTATIONAL STRUCTURES INTRODUCTION

DISCRETE COMPUTATIONAL
STRUCTURES
Propositional Logic
Hazırlayan
DOÇ. DR. YUSUF OYSAL
DISCRETE COMPUTATIONAL STRUCTURES – Propositional Logic
Quick Overview
Discrete Math is essentially that branch of mathematics that does not
depend on limits; in this sense, it is the anti-thesis of Calculus.
As computers are discrete object operating one jumpy, discontinuous step
at a time, Discrete Math is the right framework for describing precisely
Computer Science Concepts.
Discrete Math helps provide…
…the machinery necessary for creating sophisticated algorithms
…the tools for analyzing their efficiency
…the means of proving their validity
DISCRETE COMPUTATIONAL STRUCTURES – Propositional Logic
Topics
•
Logic
 Make notions you’re already used to from programming a little more
rigorous (operators)
 Fundamental to all mathematical disciplines
 Useful for digital circuits, hardware design
•
Proofs (especially induction)
 If you want to debug a program beyond a doubt, prove that it’s bugfree
 Proof-theory has recently also been shown to be useful in
discovering bugs in pre-production hardware
DISCRETE COMPUTATIONAL STRUCTURES – Propositional Logic
Topics
•
Elementary Number Theory
 Get to rediscover the old reliable number and find out some
surprising facts
 Very useful in crypto-systems
•
Finite State Machines and Turign Machines
 Important for Computation Theory
 Very useful in a new computer language design
 Useful for sequential digital circuit and hardware designs
DISCRETE COMPUTATIONAL STRUCTURES – Propositional Logic
Topics
•
Graph Theory
 Many clever data-structures for organizing information and making
programs highly efficient are based on graph theory
 Very useful in describing problems in
 Databases
 Operating Systems
 Networks
 Every Computer Science Discipline!!!!
DISCRETE COMPUTATIONAL STRUCTURES – Propositional Logic
Propositional Logic
We intuitively know that Truth and Falsehood are opposites. That
statements describe the world and can be true/false. That the world is
made up of objects and that objects can be organized to form collections.
The foundations of logic mimic our intuitions by setting down constructs
that behave analogously.
A proposition is a statement that is true or false.
Propositional Logic – we associate atoms with propositions / assertions
about the world (therefore propositional logic).
DISCRETE COMPUTATIONAL STRUCTURES – Propositional Logic
Propositions
Primitive propositions --- statements like:
Barış loves Ayşe
Ayşe loves Barış
P
Q
propositional symbols
(atomic propositions)
Compound propositions
Barış loves Ayşe and Ayşe loves Barış
P  Q
( - stands for and)
DISCRETE COMPUTATIONAL STRUCTURES – Propositional Logic
Logical Connectives
Operator
Symbol
Usage
Java
Negation

not
!
Conjunction

and
&&
Disjunction

or
||
Exclusive or

xor
(p||q)&&(!p||!q)
Conditional

if,then
p?q:true
Biconditional

iff
(p&&q)||(!p&&!q)
DISCRETE COMPUTATIONAL STRUCTURES – Propositional Logic
Syntax of Propositions
•
Syntax of Well Formed Formulas (wffs) or sentences
– Atomic sentences are wffs:
Propositional symbol (atom)
Examples: p, q, r (small letters)
– Complex or compound wffs.
Given w1 and w2 wffs:
 w1
(w1  w2)
(w1  w2)
(w1  w2)
(w1  w2)
(negation)
(conjunction)
(disjunction)
(implication; w1 is the antecedent; w2 is the consequent)
(biconditional)
DISCRETE COMPUTATIONAL STRUCTURES – Propositional Logic
Semantic of Propositions
Semantics has to do with “meaning”: it associates the elements of a
logical language with the elements of a “domain of discourse” (“the
world”).
Interpretation or Truth Assignment:
Assignment of truth values (True or False) to every proposition
(atom).
So if for n atomic propositions, there are 2n truth assignments or
interpretations.
This makes the representation powerful: the propositions implicitly
capture 2n possible states of the world.
DISCRETE COMPUTATIONAL STRUCTURES – Propositional Logic
Truth table for connectives (semantics)
DISCRETE COMPUTATIONAL STRUCTURES – Propositional Logic
Satisfiability and Models
DISCRETE COMPUTATIONAL STRUCTURES – Propositional Logic
Tautologies, contradictions, contingencies
A compound proposition is called a tautology if no matter what truth
values its atomic propositions have, its own truth value is T.
EG: p  ¬p (Law of excluded middle)
The opposite to a tautology, is a compound proposition that’s always
false is a contradiction.
EG: p  ¬p
On the other hand, a compound proposition whose truth value isn’t
constant is called a contingency.
EG: p  ¬p
DISCRETE COMPUTATIONAL STRUCTURES – Propositional Logic
Tautologies and contradictions
p
F
T
p
T
F
p p
T
T
p
F
T
p
T
F
p p
F
F
DISCRETE COMPUTATIONAL STRUCTURES – Propositional Logic
Tautology example
Part 1
Demonstrate that
[¬p (p q )]q
is a tautology in two ways:
1.
Using a truth table – show that
[¬p (p q )]q is always true
2. Using a proof (will get to this later).
DISCRETE COMPUTATIONAL STRUCTURES – Propositional Logic
Tautology by truth table
p q ¬p p q
¬p (p q )
[¬p (p q )]q
T T
F
T
F
T
T F
F
T
F
T
F T
T
T
T
T
F F
T
F
F
T
DISCRETE COMPUTATIONAL STRUCTURES – Propositional Logic
Logical Equivalences
Two compound propositions p, q are logically equivalent if their
bi-conditional joining p  q is a tautology. Logical equivalence is
denoted by p  q.
EG: The contrapositive of a logical implication is the reversal of the
implication, while negating both components. I.e. the contrapositive of
p q is ¬q ¬p . As we’ll see next: p q  ¬q ¬p
DISCRETE COMPUTATIONAL STRUCTURES – Propositional Logic
Logical Equivalence of Conditional and
Contrapositive
p
T
T
F
F
q
T
F
T
F
p q
T
F
T
T
p
T
T
F
F
q
T
F
T
F
¬q
F
T
F
T
¬p
F
F
T
T
¬q¬p
T
F
T
T
DISCRETE COMPUTATIONAL STRUCTURES – Propositional Logic
Derivational Proof Techniques
When compound propositions involve more and more atomic
components, the size of the truth table for the compound
propositions increases.
Q1: How many rows are required to construct the truth-table
of:
( (q(pr ))  ((sr)t) )  (qr )
Q2: How many rows are required to construct the truth-table
of a proposition involving n atomic components?
DISCRETE COMPUTATIONAL STRUCTURES – Propositional Logic
Tautology example
Part 2
Demonstrate that
[¬p (p q )]q
is a tautology in two ways:
1.
Using a truth table (did before)
2.
Using a proof relying on Tables 5 and 6 of Rosen, derive True
through a series of logical equivalences
21
Tautology by proof
[¬p (p q )]q
 [(¬p p)(¬p q)]q
 [ F  (¬p q)]q
 [¬p q ]q
 ¬ [¬p q ]  q
 [¬(¬p) ¬q ]  q
 [p  ¬q ]  q
 p  [¬q q ]
 p  [q ¬q ]
pT
T
Distributive
ULE
Identity
ULE
DeMorgan
Double Negation
Associative
Commutative
ULE
Domination
22