Logic in Mathematics and Computer Science

 
ICS 6D
Logic Overview
 
Instructor: Sandy Irani
 
What is logic?
 
Branch of mathematics in which variables and
expressions have value true (T) or false (F)
 
Particularly relevant to CS:
AI: automated reasoning
Digital logic design
 
Useful in any area in which it is important to
make precise statements and reason in a
systematic way.
 
Proposition
 
A proposition is a statement that is either true
or false:
2 + 3 = 5
3 + 4 = 6
4 is a prime number
It is raining today
It will rain tomorrow 
(unknown truth value)
Chocolate is the best flavor of ice cream 
(matter of
opinion)
 
Propositions
 
Statements that are not propositios:
How are you doing? (Question)
Have a nice day! (Command)
Bummer! (exclamation)
 
Propositional variables
Typically: p, q, r, s
Have value T or F.
 
Logical Operations: Conjunction
 
Conjunction (AND)
p
˄
q is true when p is true and q is true, false
otherwise
Truth table shows
the truth value of an
expression for every
possible combination
of truth values for the
individual propositions
In the expression.
 
p
 
q
 
p
˄
q
 
Logical Operations: Disjunction
 
Disjunction (OR)
p
˅
q is true when p is true or q is true or both are
true. p
˅
q only when p and q are both false.
 
p
 
q
 
p
 ˅ 
q
 
Inclusive vs. Exclusive OR
 
Inclusive OR 
(True if either or both propositions are true)
The patient should not take the medication if she has a
history of migraines or she has diabetes.
Exclusive OR 
(True if exactly one of the propositions is
true. False if both propositions are true)
I will drive or ride my bike to work today.
 
In logic: “OR” is 
always
 the inclusive OR unless
explicitly stated otherwise.
 
Logical Operations: Complement
 
Complement (NOT) 
p
 
p
 
p
 
Compound Propositions
 
p 
 q 
 
r
 
Order of precedence:
Complement
Conjunction
Disjunction
Good to use parens:
Except for complement, multiple 
, multiple 
 
Compound Propositions
 
p: true      q: false     r: true
 
 
 
p 
 (q 
 
r)
 
 (
p 
 q 
 
r)
 
Truth table for: 
p 
 (q 
 
r)
 
 
p 
 (q 
 
r)
 
p
 
q
 
r
 
p
 
r
 
q 
 
r
 
Logical Equivalence
 
Two compound propositions are 
logically equivalent
if they have the same truth value for every
combination of truth values for their individual
propositions.
 
 
(p 
 q) 
 
p 
 
q
 
p
 
q
 
(p 
 q)
 
p 
 
q
 
De Morgan’s Law: 
(p 
 q) 
 
p 
 
q
 
p: The applicant is over 18 years old
q: the applicant has a valid driver’s license
 
(p 
 q)
:
 
It is not true that the applicant is over 18
years old and has a valid driver’s license.
 
p 
 
q
: The applicant is not over 18 years old or
does not have a valid driver’s license.
 
 
De Morgan’s Law: 
(p 
 q) 
 
p 
 
q
 
p: the patient has a history of migraines
q: the patient has diabetes
 
(p 
 q)
:
 
It is not true that the patient has a
history of migrains or has diabetes.
 
p 
 
q
: The does not have a history of migraines
and does not have diabetes.
 
 
The conditional operation
 
“Implies” p
q
p is the “hypothesis” and q is the “conclusion”
 
p
 
q
 
p → q
“If p, then q.”
“q, if p.”
“p implies q”
 
The conditional operation
 
h
: you mow my lawn
c
: I pay you $20
h
c
: If you mow my lawn, I will pay you $20.
 
 
 
 
 
You mow
my lawn
 
You 
don’t
mow my lawn
 
I pay you $20
 
I 
don’t
 pay you $20
 
The conditional operation
 
s: Suzy studied for her test
p: Suzy passed her test
 
p → q 
 
p 
 q:
If Suzy studied for her test then she passed her
test.
Either Suzy did not study for her test or she
passed her test.
 
 
 
 
Contrapositive
 
s: Suzy studied for her test
p: Suzy passed her test
 
The 
contrapositive
 of p → q 
is 
q 
 
p.
p → q 
 
q 
 
p
If Suzy studied for her test then she passed her
test.
If Suzy did not pass her test, then she did not
study for it.
 
 
 
 
The bi-conditional operation
 
“If and only if” p
q
p ↔ 
q
 is true whenever p and q have the same
truth value.
 
p
 
q
 
p ↔ q
 
Convenient logical equivalences
 
p → q 
 
p 
 q
 
De Morgans Laws:
(p 
 q) 
 
p 
 
q
(p 
 q) 
 
p 
 
q
 
Associative Laws:
(p 
 q) 
 r 
 p 
 (q 
 r )
(p 
 q) 
 r 
 p 
 (q 
 r )
 
 
 
 
 
 
Disjunction/Conjunction
 
p
1
 
 p
2
 
 p
3
 
 p
4
 
 …. 
 p
n
 
 
 
 
p
1
 
 p
2
 
 p
3
 
 p
4
 
 …. 
 p
n
 
 
 
 
 
 
 
 
Predicate
 
P(x): “x is prime” is a 
predicate
 (not a proposition)
Truth value depends on the value of x.
 
P(5): “5 is prime.”  
P(5) is a proposition
.
P(6): “6 is prime.”  
P(6) is a proposition
.
 
Variable x in a predicate has a domain
Set of possible values for x.
For “x is prime” a natural domain is the set of positive
integers.
 
 
 
 
 
 
 
 
 
 
 
 
 
Predicate
 
Domain: set of students in a class:
{
Abigail, Bernice, Charlie, …, Zachary
}
 
Predicate T(x): x got an A on the test.
 
T(Bernice)
: “Bernice got an A on the test.”
T(Charlie) 
 T(Zachary)
: “Charlie and Zachary both got
an A on the test.”
T(Zachary) 
T(Bernice)
:
 
“If Zachary got an A on the
test then Bernice got an A on the test.”
(All 
propositions.)
 
 
 
 
 
 
 
 
 
 
 
 
 
Existential Quantifier
 
Domain: set of students in a class:
{
Abigail, Bernice, Charlie, …, Zachary
}
Predicate T(x): x got an A on the test.
x T(x)
“There is a student who got an A on the test.”
“Some student got and A on the test.”
“At least one student got an A on the test.”
For finite domains:
x T(x) 
  (
T(
Abigail
) 
  T(
Bernice
) 
  T(
Charlie
) 
 T(
Zachary
))
 
 
 
 
 
 
 
 
 
 
 
 
Existential Quantifier
 
x T(x)
True if T(n) is true for at least one value for x in
the domain.
False if T(n) is false for every value of x in the
domain.
 
Example:
 domain is the set of all positive integers.
x (x
2
 = x)
x (x + x = x)
 
 
 
 
 
 
 
 
 
 
 
Universal Quantifier
 
Domain: set of students in a class:
{
Abigail, Bernice, Charlie, …, Zachary
}
Predicate P(x): x passed the test.
x P(x)
“Every student passed the test.”
“All students passed the test.”
 
For finite domains:
x P(x) 
  (
P(
Abigail
) 
  P(
Bernice
) 
  P(
Charlie
) 
 P(
Zachary
))
 
 
 
 
 
 
 
 
 
 
 
 
Universal Quantifier
 
x T(x)
True if T(n) is true for every value for x in the
domain.
False if T(n) is false for at least one value for x
in the domain. 
(counterexample)
 
Example:
 domain is the set of all positive integers.
x (x
2
 = x)
x (x
2
 
 x)
x (x
2
 
>
 x)
 
 
 
 
 
 
 
 
 
 
 
 
Universal Quantifier Examples
 
P(x): x is prime.
D(x): x is odd
The domain for x is the set of all positive integers
 
x (P(x) → D(x))
 
x (P(x) → (D(x) 
 (x = 2))
)
 
x ((x < 0) → P(x))
 
 
 
 
 
 
 
 
 
 
 
Slide Note
Embed
Share

Logic is a branch of mathematics that deals with true or false values. It is essential for fields like computer science, aiding in AI, automated reasoning, and digital logic design. Propositions, logical operations like conjunction and disjunction, and the use of propositional variables are fundamental concepts in logic. Knowing how to work with compound propositions is key to making precise statements and reasoning systematically.


Uploaded on Aug 17, 2024 | 0 Views


Download Presentation

Please find below an Image/Link to download the presentation.

The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author. Download presentation by click this link. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.

E N D

Presentation Transcript


  1. ICS 6D Logic Overview Instructor: Sandy Irani

  2. What is logic? Branch of mathematics in which variables and expressions have value true (T) or false (F) Particularly relevant to CS: AI: automated reasoning Digital logic design Useful in any area in which it is important to make precise statements and reason in a systematic way.

  3. Proposition A proposition is a statement that is either true or false: 2 + 3 = 5 3 + 4 = 6 4 is a prime number It is raining today It will rain tomorrow (unknown truth value) Chocolate is the best flavor of ice cream (matter of opinion)

  4. Propositions Statements that are not propositios: How are you doing? (Question) Have a nice day! (Command) Bummer! (exclamation) Propositional variables Typically: p, q, r, s Have value T or F.

  5. Logical Operations: Conjunction Conjunction (AND) p q is true when p is true and q is true, false otherwise p q p q Truth table shows the truth value of an expression for every possible combination of truth values for the individual propositions In the expression.

  6. Logical Operations: Disjunction Disjunction (OR) p q is true when p is true or q is true or both are true. p q only when p and q are both false. p q p q

  7. Inclusive vs. Exclusive OR Inclusive OR (True if either or both propositions are true) The patient should not take the medication if she has a history of migraines or she has diabetes. Exclusive OR (True if exactly one of the propositions is true. False if both propositions are true) I will drive or ride my bike to work today. In logic: OR is always the inclusive OR unless explicitly stated otherwise.

  8. Logical Operations: Complement Complement (NOT) p p p

  9. Compound Propositions p q r Order of precedence: Complement Conjunction Disjunction Good to use parens: Except for complement, multiple , multiple

  10. Compound Propositions p: true q: false r: true p (q r) (p q r)

  11. Truth table for: p (q r) p r q r p (q r) p q r

  12. Logical Equivalence Two compound propositions are logically equivalent if they have the same truth value for every combination of truth values for their individual propositions. (p q) p q (p q) p q p q

  13. De Morgans Law: (p q) p q p: The applicant is over 18 years old q: the applicant has a valid driver s license (p q):It is not true that the applicant is over 18 years old and has a valid driver s license. p q: The applicant is not over 18 years old or does not have a valid driver s license.

  14. De Morgans Law: (p q) p q p: the patient has a history of migraines q: the patient has diabetes (p q):It is not true that the patient has a history of migrains or has diabetes. p q: The does not have a history of migraines and does not have diabetes.

  15. The conditional operation Implies p q p is the hypothesis and q is the conclusion p q p q If p, then q. q, if p. p implies q

  16. The conditional operation h: you mow my lawn c: I pay you $20 h c: If you mow my lawn, I will pay you $20. You mow my lawn You don t mow my lawn I pay you $20 I don t pay you $20

  17. The conditional operation s: Suzy studied for her test p: Suzy passed her test p q p q: If Suzy studied for her test then she passed her test. Either Suzy did not study for her test or she passed her test.

  18. Contrapositive s: Suzy studied for her test p: Suzy passed her test The contrapositiveof p q is q p. p q q p If Suzy studied for her test then she passed her test. If Suzy did not pass her test, then she did not study for it.

  19. The bi-conditional operation If and only if p p q is true whenever p and q have the same truth value. q p q p q

  20. Convenient logical equivalences p q p q De Morgans Laws: (p q) p q (p q) p q Associative Laws: (p q) r p (q r ) (p q) r p (q r )

  21. Disjunction/Conjunction p1 p2 p3 p4 . pn p1 p2 p3 p4 . pn

  22. Predicate P(x): x is prime is a predicate (not a proposition) Truth value depends on the value of x. P(5): 5 is prime. P(5) is a proposition. P(6): 6 is prime. P(6) is a proposition. Variable x in a predicate has a domain Set of possible values for x. For x is prime a natural domain is the set of positive integers.

  23. Predicate Domain: set of students in a class: {Abigail, Bernice, Charlie, , Zachary} Predicate T(x): x got an A on the test. T(Bernice): Bernice got an A on the test. T(Charlie) T(Zachary): Charlie and Zachary both got an A on the test. T(Zachary) T(Bernice): If Zachary got an A on the test then Bernice got an A on the test. (All propositions.)

  24. Existential Quantifier Domain: set of students in a class: {Abigail, Bernice, Charlie, , Zachary} Predicate T(x): x got an A on the test. x T(x) There is a student who got an A on the test. Some student got and A on the test. At least one student got an A on the test. For finite domains: x T(x) (T(Abigail) T(Bernice) T(Charlie) T(Zachary))

  25. Existential Quantifier x T(x) True if T(n) is true for at least one value for x in the domain. False if T(n) is false for every value of x in the domain. Example: domain is the set of all positive integers. x (x2 = x) x (x + x = x)

  26. Universal Quantifier Domain: set of students in a class: {Abigail, Bernice, Charlie, , Zachary} Predicate P(x): x passed the test. x P(x) Every student passed the test. All students passed the test. For finite domains: x P(x) (P(Abigail) P(Bernice) P(Charlie) P(Zachary))

  27. Universal Quantifier x T(x) True if T(n) is true for every value for x in the domain. False if T(n) is false for at least one value for x in the domain. (counterexample) Example: domain is the set of all positive integers. x (x2 = x) x (x2 x) x (x2> x)

  28. Universal Quantifier Examples P(x): x is prime. D(x): x is odd The domain for x is the set of all positive integers x (P(x) D(x)) x (P(x) (D(x) (x = 2))) x ((x < 0) P(x))

More Related Content

giItT1WQy@!-/#giItT1WQy@!-/#giItT1WQy@!-/#giItT1WQy@!-/#giItT1WQy@!-/#giItT1WQy@!-/#giItT1WQy@!-/#giItT1WQy@!-/#