Discrete Structures
Unit 1
Mathematical Reasoning (Logic and Proof)
Dr. Seema Kharb
Topics to be Covered
⚫ Proposition
⚫ Operators
⚫ Truth Tables
⚫ Predicate Logic
⚫ Natural deduction
⚫ Rules of Inference
⚫ Methods of Proofs
⚫ Use in Program Proving
⚫ Resolution
What is a Logic
Clearly distinguish the definitions of:
•the formal language
– Syntax
– Semantics
– Expressive Power
• the reasoning problem (e.g., entailment)
– Decidability
– Computational Complexity
• the problem solving procedure
– Soundness and Completeness
– (Asymptotic) Complexity
⚫ The ideal Logic
⚫ Expressive
⚫ With decidable reasoning problems
⚫ With sound and complete reasoning procedures
⚫ With efficient reasoning procedures – possibly sub-optimal
⚫ Many Logics
⚫ Propositional Logic
⚫ First Order Logic
⚫ Modal Logic
⚫ Temporal Logic
⚫ Relevant Logic
Types of Logics
⚫ Logics are characterized by what they commit to as “primitives”
⚫ Ontological commitment: what exists—facts? objects? time? beliefs?
⚫ Epistemological commitment: what states of knowledge?
Logic and Computer Science
⚫ Computer scientists design and study systems through the use of formal
languages that can themselves be interpreted by a formal system.
⚫ Formal languages of modern logic serve as a working tool for computer
science. Some of the most basic applications of this tool are:
⚫ Boolean circuits: The design of hardware built out of gates that implement
Boolean logic primitives.
⚫ Some problems seem to be so hard that computers cannot solve them no
matter how fast they are. The reason for the difficulty is a combinatorial
explosion that seem to be inherent in this problem. Logic plays a crucial role
in the development of the theory of NP-completeness, which formalize the
concept of combinatorial explosion.
⚫ Semantics: To make sure that different implementation of a programming
language yield the same results, programming languages need to have a formal
semantics. Logic provide the tool to develop such a semantics.
⚫ Design Validation and verification: to verify the correctness of a design
with a certainty beyond that of conventional testing. It uses temporal logic
.
⚫ AI: mechanized reasoning and expert systems.
⚫ Security: With increasing use of network, security has become a big issue.
Hence, the concept of “proof-carrying code” (proof of safety and
correctness)
⚫ Semantic Web: Description Logics have been used as web ontology
languages.
⚫ Logic is sometime described as the “calculus of computer science”.
Propositional Logic
■ Logic
■ Study of reasoning.
■ Specifically concerned with whether reasoning is correct.
■ Focuses on the relationship among statements, not on the content of any
particular statement.
■ Gives precise meaning to mathematical statements.
■ Propositional Logic is the logic that deals with statements
(propositions) and compound statements built from simpler
statements using so-called Boolean connectives.
■ Some applications in computer science:
■ Design of digital electronic circuits.
■ Expressing conditions in programs.
■ Queries to databases & search engines.
Definition of a Proposition
Definition: A proposition (denoted p, q, r, …) is simply:
■ a statement (i.e., a declarative sentence)
■ with some definite meaning, (not vague or
ambiguous)
■ having a truth value that’s either true (T) or false (F)
■ it is never both, neither, or somewhere “in between!”
■ However, you might not know the actual truth value,
■ and, the truth value might depend on the situation or context.
Examples of Propositions
■ (In a given situation)
It is raining.
■ New Delhi is the capital of India. (T)
(F)
■ 2 + 2 = 5.
(T)
■ 1 + 2 = 3.
■ A fact-based declaration is a proposition, even if no one
knows whether it is true
■ 11213 is prime.
■ There exists an odd perfect number.
Examples of Non-Proposition
The following are NOT propositions:
■ Who’s there? (interrogative, question)
■ Just do it! (imperative, command)
■ La la la la la. (meaningless interjection)
■ Yeah, I sorta dunno, whatever... (vague)
■ 1 + 2 (expression with a non-true/false value)
■ x + 2 = 5 (declaration about semantic tokens of
non-constant value)
Truth Tables
■ An operator or connective combines one or more
operand expressions into a larger expression. (e.g., “+” in numeric expressions.)
■ Unary operators take one operand (e.g., −3);
Binary operators take two operands (e.g. 3 × 4).
■ Propositional or Boolean operators operate on propositions (or their truth values)
instead of on numbers.
■ The Boolean domain is the set {T, F}. Either of its elements is called a Boolean value.
An n-tuple (p1,…,pn) of Boolean values is called a Boolean n-tuple.
■ An n-operand truth table is a table that assigns a Boolean value to the set of all Boolean
n-tuples.
Some Popular Boolean Operators
Formal Name Nickname Arity Symbol
Negation operator NOT Unary ¬
Conjunction operator AND Binary ∧
Disjunction operator OR Binary ∨
Exclusive-OR operator XOR Binary ⊕
Implication operator IMPLIES Binary →
Biconditional operator IFF Binary ↔
Negation Operator
■ The unary negation operator “¬”
p ~p
(NOT) transforms a proposition
into its logical negation.
■ E.g. If p = “I have brown hair.”
⚫ then ¬p = “It is not
the case that I have
brown hair” or “I do
not have brown
hair.”
Conjuction Operator
■ The binary conjunction operator “∧” (AND) p q P∧q
combines two propositions to form their
logical conjunction.
■ E.g. If p = “I will have salad for lunch.”
and
⚫q = “I will have rice for dinner.”
⚫ then, p∧q = “I will have salad for lunch and
⚫ I will have rice for dinner.”
■ Note that a conjunction p1 ∧ p2 ∧ … ∧ pn of n propositions will
have 2n rows in its truth table
Disjunction Operator
■ The binary disjunction operator “∨” (OR) p q P∨q
combines two propositions to form their
logical disjunction.
■ E.g. If p = “My car has a bad engine.” and
⚫ q = “My car has a bad carburetor.”
⚫ then, p∨q = “My car has a bad engine, or
⚫ my car has a bad carburetor.”
■ This operation is also called inclusive or, because it includes the
possibility that both p and q are true.
Ex-clusive OR Operator
■ The binary exclusive-or operator “⊕” (XOR) p q P⊕q
combines two propositions to form their logical
“exclusive or”
■ E.g. If p = “I will earn an A in this course.” and
⚫ q = “I will drop this course.”, then
⚫ p ⊕ q = “I will either earn an A in this course,
⚫ or I will drop it (but not both!)”
■ 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.
Implication Operator
■ The conditional statement (aka implication)
p → q states that p implies q. p q P −> q
■ I.e., If p is true, then q is true; but if p is not true, then q could
be either true or false.
■ E.g., let p = “You study hard.”
q = “You will get a good grade.”
p → q = “If you study hard, then you will get a good
grade.” (else, it could go either way)
■ p: hypothesis or antecedent or premise
■ q: conclusion or consequence
■ p → q is false only when p is true but q is not true.
■ p → q does not require that p or q are ever true!
■ E.g. “(1=0) → pigs can fly” is TRUE!
Bidirectional Operator
■ If and only if
p q P <−> q
■ The proposition p <-> q, read “p if and only if q”, is called
biconditional.
Tautology, Contradiction, Contingency.
⚫ A proposition is said to be a tautology if its
p ~p P ∨ ~p P∨q
truth value is T for any assignment of truth
values to its components. Example:
⚫ The proposition p _ ¬p is a tautology.
⚫ A proposition is said to be a contradiction if
its truth value is F for any assignment of truth
values to its components. Example:
⚫ The proposition p ^ ¬p is a contradiction.
⚫ A proposition that is neither a tautology nor a
contradiction is called a contingency.
Logical Equivalence
⚫ When two compound propositions have the same truth values no matter
what truth value their constituent propositions have, they are called
logically equivalent.
⚫ For instance p -> q and ¬p˅ q are logically equivalent, and we write it:
p ->q ≡ ¬p ˅ q
p q ~P ∨ q P->q
