TR1413: Discrete Mathematics For Computer Science : TR1413: Discrete Mathematics For Computer Science Lecture 3: Formal approach to propositional logic
Introduction : Introduction A proof is a logical argument that consists of a series of steps using propositions in such a way that the truth of the theorem is established.
To establish a valid proof, we have to understand the concept of mathematical logic.
Introduction : Introduction We have discussed the concept of logic in TR1313.
However, the discussion in TR1313 was done information, mainly by using truth tables.
Most of the problems in mathematics and computer science cannot be proved by using the informal approach.
In this course, we will consider a formal approach to logic.
Mathematical System : Mathematical System Informally, a mathematical system consists of
Undefined terms
Definitions
Axioms
Formal Mathematical System : Formal Mathematical System Formally, a mathematical system consists of four sets of objects:
An alphabet
A set of wffs
A set of axioms
A set of rules of deduction
Alphabet : Alphabet This set consists of the symbols used by the system.
This include:
A subset of propositional variables.
A subset of punctuation symbols
A subset of logical operators.
wff : wff A set of formulae that are syntactically correct.
The formulae use only the symbols defined by the alphabet.
Axioms : Axioms These are basic formulae from which theorems are derived.
Accepted without proof.
Rules of Deduction : Rules of Deduction Rules which enable new wffs to be derived in the system from existing wffs.
Proof and deduction : Proof and deduction Need to differentiate between proof and deduction.
A proof in a formal system is defined to be a sequence of wffs of that system such that each wff is either
An instance of an axiom of the system
A derivable from earlier wffs in the sequence using one of the rules of the system
A deduction in a formal system : A deduction in a formal system A deduction, on the other hand, starts from certain additional premises or hypotheses in additions to the axioms.
Formally, a deduction in a given system can formally be defined to be a sequence of wffs on that system such that each wff is either
An instance of an axiom
One of the additional hypotheses
Derivable from earlier wffs in the sequence using one of the rules of the system.
A deduction in a formal system : A deduction in a formal system Notation
P1,P2,…,Pn ᅡQ
Meaning: wff Q is deducible from the set of wffs {P1,P2,…,Pn}
The set {P1,P2,…,Pn} are the hypotheses.
Q is the consequent.
A deduction in a formal system : A deduction in a formal system Sometimes, notation
TᅡQ
is used.
Meaning: wff Q is deducible from the hypotheses in set T.
If T is an empty set, then
ᅡQ
is used to indicate Q is a theorem in the system.
Interpretation : Interpretation Interpretation of a wff in a formal system is an assignment of truth-values to each propositional variable of the formula.
A tautology is a formula which has truth-value T for all possible interpretation.
Deductive Reasoning : Deductive Reasoning Consider the following sequence of proposition:
The bug is either in module 17 or in module 81
The bug is a numerical error
Module 81 has no numerical error
Conclusion:
The bug is in module 17
Example 1.4.11 Represent the argument : Example 1.4.11 Represent the argument If 2 = 3, then I ate my hat
I ate my hat
Therefore 2 = 3
Example 1.4.12 : Example 1.4.12 Which rule of inference is used?
If the computer has 32 megabytes of storage, then it can run “Blast’em”. If the computer can run “Blast’em”, then the sonics will be impressive. Therefore, if the computer has 32 megabytes of storage, then the sonics will be impressive.