Chap
1: The Foundations- Logics and Proofs
1.1 Proposition
Logic
DEFINITIONS:
①
Propositional is a declarative
sentence that is either true or false, but not both. It normally uses
lower case roman letters (p, q, r,…) to denote its propositional variables
(statement variables), denoted by T when the statement is true and F for false
statement.
②
Logic means the study of either
of proposition logic or first-order predicate logic.
p/s: Logic encompasses the following attributes:
l Syntax : Define the
syntactically acceptable object of language. Also
known as formulae
l Semantics : Formulae of
logic associate each formula with a meaning.
l Proof-theory : Manipulating
formulae according to the perceived reasoning.
③
Atomic proposition is a truth
or falsity that does not depend on the truth or falsity of any other
proposition.
EXAMPLES
1. The wing-flaps are down.
2. 3+5=8
3. Cat is an animal.
4. Madam Elissa teaches Discrete Maths.
1. How are you today? ※ A question.
2. x+y=1 ※ Contains unknown
3. 3+5 ※ A expression
4. Fill in the blanks. ※ An instruction
PROPOSITIONAL LOGIC
² NEGATION (NOT)
If p is an
arbitrary proposition, then the negation of p is written as ¬p and it holds
the opposite truth values of p.
p
|
¬p
|
T
|
F
|
F
|
T
|
Example:
• Find the negation of the proposition
“Vandana’s smartphone has at least 32GB
of memory”
and express
this in simple English.
•
Solution: The negation is
“It is not
the case that Vandana’s smartphone has at least 32GB of memory.”
This negation
can also be expressed as
“Vandana’s smartphone does not have at
least 32GB of memory”
or even more simply as
“Vandana’s
smartphone has less than 32GB of memory.”
² CONJUNCTION (AND)
p and q are
arbitrary propositions, then the conjuction of p and q is written pʌq (p AND q), Kpq, p & q, or p.q
and will be true if both p and q are true and will be false otherwise.
Logical Conjunction
|
||
p
|
q
|
p ∧ q
|
T
|
T
|
T
|
T
|
F
|
F
|
F
|
T
|
F
|
F
|
F
|
F
|
Example:
•
Find the conjunction of the propositions p and q where
p is the proposition “Rebecca’s PC has more than 16 GB free hard disk space”
q is the proposition “The processor in Rebecca’s PC runs faster than 1 GHz.”
•
Solution: The conjunction of
these propositions, p ∧ q, is the
proposition “Rebecca’s PC has more than 16 GB free hard disk
space, and the processor in Rebecca’s PC runs faster than 1GHz.”
This
conjunction can be expressed more simply as “Rebecca’s PC has more than 16 GB
free hard disk space, and its processor runs faster than 1 GHz.” For this conjunction
to be true,both conditions given must be true. It is false, when one or both of
these conditions are false.
² DISJUNCTION (OR)
p and q are
arbitrary propositions, then the disconjuction of p and q is written p ᴠ q (p OR q), Apq, p || q, or p + q and
will be false only when both p and q are false, otherwise it will be
true.
Logical Disjunction
|
||
p
|
q
|
p ∨ q
|
T
|
T
|
T
|
T
|
F
|
T
|
F
|
T
|
T
|
F
|
F
|
F
|
Example:
Consider the
following variables and cases,
p= Alex is
sleeping
q= Alex is
playing computer games
The logical
disjunction between these two statements is “Either Alex is sleeping OR he is playing computer games.”
² IMPLICATION
(IF…THEN)
p and q are
arbitrary propositions, then the conditional of p and q is written p ⇒ q or Cpq or “if p then q” and it will be false when
p is true and q is false. Otherwise, it is true for all other truth values.
In this case, p is called the hypothesis and q is conclusion.
Ways to express the conditional statement.
“if p, then q” “p implies q”
“if p, q” “p only if q”
“p is sufficient for q”
“a sufficient condition for q is p”
“q if p” “q whenever p”
“q when p” “q is necessary for p”
“a necessary condition for p is q”
“q follows from p”
“q unless ￢p”
Logical Implication
|
||
p
|
q
|
p → q
|
T
|
T
|
T
|
T
|
F
|
F
|
F
|
T
|
T
|
F
|
F
|
T
|
Example:
Consider the
following cases:
p= Syafiq is
starving now.
q= Syafiq
wants to treat himself at a five star restaurant.
Hence the
relationship p→ q can be stated
as “If Syafiq is starving now, then he wants to treat himself at a five star
restaurant.”
² BICONDITIONAL
(XNOR)
p and q are
arbitrary propositions, then the biconditional of p and q is written p↔q,
Epq, p = q, or p ≡ q and will be true when p and
q have the same truth value and false otherwise.
Ways to
express biconditional:
“p if and only if q”
“p is necessary and
sufficient for q”
“if p then q, and
conversely”
“p iff q.”
Logical Equality
|
||
p
|
q
|
p ≡ q
|
T
|
T
|
T
|
T
|
F
|
F
|
F
|
T
|
F
|
F
|
F
|
T
|
Example:
Let p be the
statement “I’ve overworked.” and q be the statement “I got a handful of heavy tasks.”
Then, p ↔
q can be written as “I’ve
overworked if and only if I got a handful of heavy tasks.”
which also
means,
I.
I’ve overworked if I got a
handful of heavy tasks.
II.
I’ve overworked only if I got a
handful of heavy tasks.
² EXCLUSIVE
DISJUNCTION (XOR)
p and q are
arbitrary propositions, p and q is written p ⊕ q, Jpq, or p ≠ q and will
be true when both operands have different truth values.
Exclusive Disjunction
|
||
p
|
q
|
p ⊕ q
|
T
|
T
|
F
|
T
|
F
|
T
|
F
|
T
|
T
|
F
|
F
|
F
|
Example:
Using the
previous example, we can describe the two statements using exclusive
disjunction that will return a true value by writing:
“I’ve overworked or I do not have get a handful of
heavy tasks.”
² NAND
p and q are
arbitrary propositions, p and q is written p ↑ q and will produces a value of false if
both operand are true and true for other truth values.
Logical NAND
|
||
P
|
q
|
p ↑ q
|
T
|
T
|
F
|
T
|
F
|
T
|
F
|
T
|
T
|
F
|
F
|
T
|
You can also
say that NAND is the combination of both NOT and AND propositions by showing
that they both are logically equivalent (see topic 1.2).
NOT + AND = NAND
p
|
q
|
p ∧ q
|
¬(p ∧ q)
|
¬p
|
q
|
(¬p) ∨ (¬q)
|
T
|
T
|
T
|
F
|
F
|
F
|
F
|
T
|
F
|
F
|
T
|
F
|
T
|
T
|
F
|
T
|
F
|
T
|
T
|
F
|
T
|
F
|
F
|
F
|
T
|
T
|
T
|
T
|
² NOR
p and q are
arbitrary propositions, p and q is written p ↓ q and will produce a
value of true if both operand are false and produce a value of false otherwise.
Logical NOR
|
||
p
|
q
|
p ↓ q
|
T
|
T
|
F
|
T
|
F
|
F
|
F
|
T
|
F
|
F
|
F
|
T
|
Also, notice
that NOR is the combination of both NOT and OR proposition.
NOT +
OR = NOR
p
|
q
|
p ∨ q
|
¬(p ∨ q)
|
¬p
|
¬q
|
(¬p) ∧ (¬q)
|
T
|
T
|
T
|
F
|
F
|
F
|
F
|
T
|
F
|
T
|
F
|
F
|
T
|
F
|
F
|
T
|
T
|
F
|
T
|
F
|
F
|
F
|
F
|
F
|
T
|
T
|
T
|
T
|
PRECEDENCE OF LOGIC OPERATION
Operator
|
Precedence
|
¬
|
1
|
∧
∨
|
2
3
|
→
↔
|
4
5
|
EXERCISE:
Construct the truth table of the
compound proposition
No comments:
Post a Comment