Presentation Chapter 1:Logic
UNISZA-TAF3023-DISCRETE-MATHEMATICS-PRESENTATION-1-FORESPEC-GROUP
Logic:
Propositions & Truth Values
Definition : A proposition is a declaration statement which is either true or false, but not both simultaneously.
The truth (T) or falsity (F) of a proposition is called truth value.
The truth (T) or falsity (F) of a proposition is called truth value.
*Proposition or sometimes called "statement"
Example
- This rose is red
- Triangle have four vertices
- 9 + 2 =11
- 6 < 12
Non Example (exclamations,question or demands)
- Keep off the grass.
- Don't say that.
- Did you go to class?
- Long live the Queen!
Logic Connectives & Truth Table
Logic Connectives:
There are many types of compound statement which can be form by using AND,OR and NOT.
Logic Connectives:
Negation
whilst negation is an operation which involves only a single proposition, logical connectives are used to link pairs of propositions.
whilst negation is an operation which involves only a single proposition, logical connectives are used to link pairs of propositions.
We can summarize this in table.If p symbolizes a proposition ~p symbolizes the negation of p.
*5 commonly used logical connectives:
- Conjunction
- Inclusive Disjunction
- Exclusive Disjunction
- Conditional
- Biconditional
Conjunction
p : The sun is shining.
q : Cow eat grass.
p ^ q: The sun is shining and cow eat grass.
Inclusive Disjunction
Exclusive Disjunction
Conditional Propositions
p : I eat breakfast.
q : I don't eat lunch.
p→q :If eat breakfast then i don't eat lunch.
Biconditional Propositions
The biconditional connective is symbolized by ( ↔),and expressed by 'if and only if...then...'.Using the previous example:
p : I eat breakfast.
q : I don't eat lunch.
p↔q :If eat breakfast if and only if i don't eat lunch.
Tautologies & Contradictions
Tautologies
If p and q are two propositions p ^ q (or p.q ) symbolizes the conjunction of p and q. p q is true when both p and q are true.Otherwise the conjunction is false.For example:
p : The sun is shining.
q : Cow eat grass.
p ^ q: The sun is shining and cow eat grass.
Given the two propositions p and q, p V q symbolizes the Inclusive Disjunction of p and q. This compound propositions is true when either or both of its components are true and false otherwise.Thus the true table for p V q is given by:
Exclusive Disjunction
The exclusive disjunction of p and q is symbolizes by p V q. This compound propositions is true when exactly one of the compound is true.Example :
"Tomorrow i will go swimming or play golf" seems to suggest that will not do both and therefore points to exclusive disjunction.
The truth table for p V q is given by:
"Tomorrow i will go swimming or play golf" seems to suggest that will not do both and therefore points to exclusive disjunction.
The truth table for p V q is given by:
The conditional connective (implication) is symbolized by ( → ).The linguistic expression of a conditional proposition is normally accepted as utilizing ' if...then..' as in the following example:
p : I eat breakfast.
q : I don't eat lunch.
p→q :If eat breakfast then i don't eat lunch.
Notice that the proposition 'if p then q ' is false only when p is true and q is false.a true statement cannot imply a false one.If p is false, the compound proposition is true no matter what the truth value q .
Biconditional Propositions
The biconditional connective is symbolized by ( ↔),and expressed by 'if and only if...then...'.Using the previous example:
p : I eat breakfast.
q : I don't eat lunch.
p↔q :If eat breakfast if and only if i don't eat lunch.
Note that for p↔q to be true, p and q must both have same truth values,both must be true or both must be false.
Tautologies & Contradictions
Tautologies
A compound proposition or statement form that is true and never false for every assignment of truth values to its components.It is symbolized by (q ∨ ¬q / q or not q).
Contradictions
Contigency
A compound proposition or statement that is neither tautology nor contradiction.It is symbolized by (p ∧ q) ∨ ¬ r / p and q or not r.
Logic Equivalence & Logical Implication
A compound proposition or statement from that is false and never true for every assignment of true values of it components.It is symbolized by (q ∧ ¬q / q and not q).
A compound proposition or statement that is neither tautology nor contradiction.It is symbolized by (p ∧ q) ∨ ¬ r / p and q or not r.
Two propositions are said to be logically equivalent if they have identical truth values for every set of truth values of truth values of their components.Using P and Q to denote compound propositions, we write P ≡ Q if P and Q are logically equivalent.As with tautologies and contradictions, logical equivalence is a consequence of the structures of P and Q.
How to determine the equivalence?
How to determine the equivalence?
•One way to determine whether two propositions are equivalent is to use a truth table.
•The propositions p and q are equivalent if and only if the columns giving their truth values agree.
The Algebra of Propositions
Idempotent laws (Idem)
p ∨ p ≡ p
p ∧ p ≡ p
p ∨ p ≡ p
p ∧ p ≡ p
Commutative laws (Comm)
p ∧ q ≡ q ∧ p
p ∨ q ≡ q ∨ p
p ∨ q ≡ q ∨ p
p ↔ q ≡ q ↔ p
Associative laws(Assoc)
( p ∧ q)∧r ≡ p ∧ (q ∧ r)
(p ∨ q) ∨r ≡ p ∨ (q ∨ r)
Distributive laws(Dist)
p∧( q∨ r) ≡ (p ∧ q)∨ (p ∧ r)
p∨( q∧ r) ≡ (p∨ q)∧(p∨ r)
De Morgan's Laws(De M)
~(p∨q) ≡ ~ p ∧~q
~(p∧q) ≡ ~ p ∨~q
Identity Laws(Ident)
( p ∧ q)∧r ≡ p ∧ (q ∧ r)
(p ∨ q) ∨r ≡ p ∨ (q ∨ r)
Distributive laws(Dist)
p∧( q∨ r) ≡ (p ∧ q)∨ (p ∧ r)
p∨( q∧ r) ≡ (p∨ q)∧(p∨ r)
De Morgan's Laws(De M)
~(p∨q) ≡ ~ p ∧~q
~(p∧q) ≡ ~ p ∨~q
Identity Laws(Ident)
p∨f ≡ p
p∧t ≡ p
p∨t ≡ t
p∧f ≡ f
Definition:Predicates is study of propositional logic.
Example:
Truth Tables for Ø (p Ú q) and Ø (p ∧ q)
Truth Tables for Ø (p Ú q) and p ® q
Definition:Predicates is study of propositional logic.
Example:
“I have more than 5 candy”
The statement is “I”.
While “more than 5 candy” is predicates.
With the instruction above, we know that “I” have more than “5 candy”,it's cannot be 4 or a3,because it cannot be less.
QUANTIFIER
Here is a (true) statement about real numbers:
Every real number is either rational or irrational, I could try to translate the statement as follows: let
b = “x real number”
c = “x is irrational”
d = “x is rational”
The statement can be expressed as the implication b (c V d) but as you can see that
I’m cheating in making my translation:
“x is a real number”
Which is not uniquely specified object “x”. Which different from
“ is a real number”
Which talk a specific real number ∏. So that I can use Quantifiers to translate statement like those so as to capture this meaning.Mathematicians use two quantifier:
Example:
If “Someone likes pizza” is true
It may true that “everyone like pizza”(by assuming the set of people is nonempty)
It must be true that “Someone likes pizza”
Example Of Using Of Quantifiers In Reality
Program Verification
-proving or disproving the correctness
System Specification
-explain on function and description of the system
Logic Programming
-execute by user
0 comments:
Post a Comment