ch01s3

Information about ch01s3

Published on November 19, 2007

Author: Crystal

Source: authorstream.com

Content

Formal Logic:  Formal Logic Mathematical Structures for Computer Science Chapter 1 Copyright © 2006 W.H. Freeman & Co. MSCS Slides Formal Logic Variables and Statements:  Variables and Statements Variables A variable is a symbol that stands for an individual in a collection or set. For example, the variable x may stand for one of the days. We may let x = Monday or x = Tuesday, etc. Use letters at the end of the alphabet as variables, such as x, y, z. A collection of objects is called the domain of a variable. For the above example, the days in the week is the domain of variable x. Incomplete Statements A sentence containing a variable is called an incomplete statement. An incomplete statement is about the individuals in a definite domain or set. When we replace the variable by the name of an individual in the set we obtain a statement about that individual. Example of an incomplete statement : “x has 30 days.” Here, x can be any month and substituting that, we will get a complete statement. Quantifiers and Predicates:  Quantifiers and Predicates Quantifiers: Quantifiers are phrases that refer to given quantities, such as “for some” or “for all” or “for every,” indicating how many objects have a certain property. Two kinds of quantifiers: Universal and Existential Universal Quantifier: represented by  The symbol is translated as and means “for all”, “given any”, “for each,” or “for every,” and is known as the universal quantifier. Existential Quantifier: represented by  The symbol is translated as and means variously “for some,” “there exists,” “there is a,” or “for at least one”. Quantifiers and Predicates:  Quantifiers and Predicates Predicate It is the verbal statement that describes the property of a variable. Usually represented by the letter P, the notation P(x) is used to represent some unspecified property or predicate that x may have e.g. P(x) = x has 30 days. P(April) = April has 30 days. Combining the quantifier and the predicate, we get a complete statement of the form (x)P(x) or (x)P(x). The collection of objects that satisfy the property P(x) is called the domain of interpretation. Truth value of expressions formed using quantifiers and predicates What is the truth value of (x)P(x) where x is all the months and P(x) = x has less than 32 days. Undoubtedly, the above is true since no month has 32 days. Truth value of the following expressions:  Truth value of the following expressions Truth of expression (x)P(x) P(x) is the property that x is yellow, and the domain of interpretation is the collection of all flowers: P(x) is the property that x is a plant, and the domain of interpretation is the collection of all flowers: P(x) is the property that x is positive, and the domain of interpretation consists of integers: Can you find one interpretation in which both (x)P(x) is true and (x)P(x) is false? Can you find one interpretation in which both (x)P(x) is true and (x)P(x) is false? Predicates involving properties of single variables : unary predicates Binary, ternary and n-ary predicates are also possible. (x) (y)Q(x,y) is a binary predicate. This expression reads as “for every x there exists a y such that Q(x,y).” not true not true true Case 1 as mentioned above Not possible Interpretation:  Interpretation Formal definition: An interpretation for an expression involving predicates consists of the following: A collection of objects, called the domain of interpretation, which must include at least one object. An assignment of a property of the objects in the domain to each predicate in the expression. An assignment of a particular object in the domain to each constant symbol in the expression. Predicate wffs can be built similar to propositional wffs using logical connectives with predicates and quantifiers. Examples of predicate wffs (x)[P(x)  Q(x)] (x) ((y)[P(x,y) V Q(x,y)]  R(x)) S(x,y) Λ R(x,y) Scope of a variable in an expression:  Scope of a variable in an expression Brackets are used wisely to identify the scope of the variable. (x) [(y)[P(x,y) V Q(x,y)]  R(x)] Scope of (y) is P(x,y) V Q(x,y) while the scope of (x) is the entire expression. (x)S(x) V (y)R(y) Scope of x is S(x) while the scope of y is R(y). (x)[P(x,y)  (y) Q(x,y)] Scope of variable y is not defined for P(x,y) hence y is called a free variable. Such expressions might not have a truth value at all. What is the truth of the expression (x)[A(x) Λ (y)[B(x,y)  C(y)]] in the interpretation A(x) is “x > 0” , B(x, y) is “x > y” and C(y) is “y  0” where the domain of x is positive integers and the domain of y is all integers True, x=1 is a positive integer and any integer less than x is  0 Translation: Verbal statements to symbolic form:  Translation: Verbal statements to symbolic form “Every person is nice” can be rephrased as “For any thing, if it is a person, then it is nice.” So, if P(x) is “x is a person” and Q(x) be “x is nice,” the statement can be symbolized as (x)[P(x)  Q(x)] “All persons are nice” or “Each person is nice” will also have the same symbolic form. “There is a nice person” can be rewritten as “There exists something that is both a person and nice.” In symbolic form, (x)[P(x) Λ Q(x)]. Variations: “Some persons are nice” or “There are nice persons.” What would the following form mean for the example above? (x)[P(x)  Q(x)] This will only be true if there are no persons in the world but that is not the case. Hence such a statement is false, so almost always,  goes with Λ (conjunction) and  goes with  (implication). Translation:  Translation Hint: Avoid confusion by framing the statement in different forms as possible. The word “only” can be tricky depending on its presence in the statement. X loves only Y  If X loves anything, then that thing is Y. Only X loves Y  If anything loves Y, then it is X. X only loves Y  If X does anything to Y, then it is love. Example for forming symbolic forms from predicate symbols D(x) is “x is dog”; R(x) is “x is a rabbit”; C(x,y) is “x chases y” All dogs chase all rabbits  For anything, if it is a dog, then for any other thing, if it is a rabbit, then the dog chases it  (x)[D(x)  (y)(R(y)  C(x,y)] Some dogs chase all rabbits  There is something that is a dog and for any other thing, if that thing is a rabbit, then the dog chases it  (x)[D(x) Λ (y)(R(y)  C(x,y)] Only dogs chase rabbits  For any two things, if one is a rabbit and the other chases it, then the other is a dog  (y) (x)[R(y) Λ C(x,y)  D(x)] Negation of statements:  Negation of statements A(x): Everything is fun Negation will be “it is false that everything is fun,” i.e. “something is nonfun.” In symbolic form, [(x)A(x)]  (x)[A(x)] Similarly negation of “Something is fun” is “Nothing is fun” or “Everything is boring.” Hence, [(x)A(x)]  (x)[A(x)] Class Exercise:  Class Exercise What is the negation of “Everybody loves somebody sometime.” Everybody hates somebody sometime Somebody loves everybody all the time Everybody hates everybody all the time Somebody hates everybody all the time What is the negation of the following statements? Some pictures are old and faded. All people are tall and thin. Some students eat only pizza. Only students eat pizza. Every picture is neither old nor faded. Someone is short or fat. Every student eats something that is not pizza. There is a non-student who eats pizza.  Class exercise:  Class exercise S(x): x is a student; I(x): x is intelligent; M(x): x likes music Write wffs that express the following statements: All students are intelligent. Some intelligent students like music. Everyone who likes music is a stupid student. Only intelligent students like music. For anything, if it is a student, then it is intelligent  (x)[S(x)  I (x)] There is something that is intelligent and it is a student and it likes music  (x)[I(x) Λ S(x) Λ M(x)] For anything, if that thing likes music, then it is a student and it is not intelligent  (x)(M(x)  S(x) Λ [I (x)]) For any thing, if it likes music, then it is a student and it is intelligent  (x)(M(x)  S(x) Λ I(x)) Validity:  Validity Analogous to a tautology of propositional logic. Truth of a predicate wff depends on the interpretation. A predicate wff is valid if it is true in all possible interpretations just like a propositional wff is true if it is true for all rows of the truth table. A valid predicate wff is intrinsically true. Validity examples:  Validity examples (x)P(x)  (x)P(x) This is valid because if every object of the domain has a certain property, then there exists an object of the domain that has the same property. (x)P(x)  P(a) Valid – quite obvious since is a member of the domain of x. (x)P(x)  (x)P(x) Not valid since the property cannot be valid for all objects in the domain if it is valid for some objects of than domain. Can use a mathematical context to check as well. Say P(x) = “x is even,” then there exists an integer that is even but not every integer is even. (x)[P(x) V Q(x)]  (x)P(x) V (x)Q(x) Invalid, can prove by mathematical context by taking P(x) = x is even and Q(x) = x is odd. In that case, the hypothesis is true but not the conclusion is false because it is not the case that every integer is even or that every integer is odd. Class Exercise:  Class Exercise What is the truth of the following wffs where the domain consists of integers: (x)[L(x)  O(x)] where O(x) is “x is odd” and L(x) is “x < 10”? (y)(x)(x + y = 0)? (y)(x)(x2 = y)? (x)[x < 0  (y)(y > 0 Λ x + y = 0)]? Using predicate symbols and appropriate quantifiers, write the symbolic form of the following English statement: D(x) is “x is a day” M is “Monday” T is “Tuesday” S(x) is “x is sunny” R(x) is “x is rainy” Some days are sunny and rainy. It is always a sunny day only if it is a rainy day. It rained both Monday and Tuesday. Every day that is rainy is not sunny.

Related presentations


Other presentations created by Crystal

Organic Farming
27. 12. 2007
0 views

Organic Farming

LA break out FINAL
17. 06. 2007
0 views

LA break out FINAL

011404New and Old Mexico
04. 10. 2007
0 views

011404New and Old Mexico

Course Guidelines
12. 09. 2007
0 views

Course Guidelines

NS102 21 S07 Desert Storm
12. 09. 2007
0 views

NS102 21 S07 Desert Storm

MehdiMoniri Bachelorseminar
12. 10. 2007
0 views

MehdiMoniri Bachelorseminar

ice hockey
06. 09. 2007
0 views

ice hockey

Experiencing Helsinki 06
06. 09. 2007
0 views

Experiencing Helsinki 06

yant
06. 09. 2007
0 views

yant

Hybrid Automata
08. 11. 2007
0 views

Hybrid Automata

Mud Sharks Flyer
06. 09. 2007
0 views

Mud Sharks Flyer

Peasants Revolt powerpoint
07. 12. 2007
0 views

Peasants Revolt powerpoint

Grammar Evolution2
05. 11. 2007
0 views

Grammar Evolution2

IT S A HELL OF TORNADO for web
05. 10. 2007
0 views

IT S A HELL OF TORNADO for web

McKinsey Productivity
23. 11. 2007
0 views

McKinsey Productivity

Aging Spr06 Lect13
23. 11. 2007
0 views

Aging Spr06 Lect13

1900tot1950af
12. 11. 2007
0 views

1900tot1950af

presentation 1
04. 01. 2008
0 views

presentation 1

cspin 200011
05. 11. 2007
0 views

cspin 200011

Turkey 0105
22. 11. 2007
0 views

Turkey 0105

Iowapain
07. 11. 2007
0 views

Iowapain

Ripe Arin Apnic
03. 01. 2008
0 views

Ripe Arin Apnic

chapter 5
14. 11. 2007
0 views

chapter 5

THAE0402
28. 09. 2007
0 views

THAE0402

Richard Harris
04. 12. 2007
0 views

Richard Harris

CERM Lecture 1A
04. 01. 2008
0 views

CERM Lecture 1A

bridgesFIU
26. 03. 2008
0 views

bridgesFIU

Aradhna aggarwal
27. 03. 2008
0 views

Aradhna aggarwal

EARTH SCIENCE SOL
07. 04. 2008
0 views

EARTH SCIENCE SOL

ASAHPERD PPP
27. 11. 2007
0 views

ASAHPERD PPP

Japan2007
30. 03. 2008
0 views

Japan2007

smith bob
09. 04. 2008
0 views

smith bob

Kiko Presentation II
10. 04. 2008
0 views

Kiko Presentation II

CMA GTS
27. 09. 2007
0 views

CMA GTS

NCH IR2005 AP
17. 04. 2008
0 views

NCH IR2005 AP

FM DVD Notes
22. 04. 2008
0 views

FM DVD Notes

Sleep Aging Well
01. 12. 2007
0 views

Sleep Aging Well

Weniger VATA Presentation 2007
06. 09. 2007
0 views

Weniger VATA Presentation 2007

lB 6augh away stress
17. 06. 2007
0 views

lB 6augh away stress

lazzaro nicole
17. 06. 2007
0 views

lazzaro nicole

laughter
17. 06. 2007
0 views

laughter

Last Mile
17. 06. 2007
0 views

Last Mile

language play
17. 06. 2007
0 views

language play

Rewrite
06. 09. 2007
0 views

Rewrite

2003 DNS Frisco
29. 10. 2007
0 views

2003 DNS Frisco

literary genres
17. 06. 2007
0 views

literary genres

Liking and Loving
17. 06. 2007
0 views

Liking and Loving

Lecture Summer school
17. 06. 2007
0 views

Lecture Summer school

lecture 18
17. 06. 2007
0 views

lecture 18

lecture 01
17. 06. 2007
0 views

lecture 01

lect14
17. 06. 2007
0 views

lect14

lect14 semantics
17. 06. 2007
0 views

lect14 semantics

Vincentvan Gogh
20. 11. 2007
0 views

Vincentvan Gogh

ClaytonNeighbors
28. 12. 2007
0 views

ClaytonNeighbors

Praesentation2003
31. 12. 2007
0 views

Praesentation2003

ct rus auto
16. 11. 2007
0 views

ct rus auto

Nenes GAPower03
02. 01. 2008
0 views

Nenes GAPower03

UD9 Quiz
20. 11. 2007
0 views

UD9 Quiz

Harrier Seminar Jan 2004
16. 11. 2007
0 views

Harrier Seminar Jan 2004

L14 comb
17. 06. 2007
0 views

L14 comb

Galo Molina
15. 11. 2007
0 views

Galo Molina

NATO STCU
01. 10. 2007
0 views

NATO STCU

cushmancvbb
05. 12. 2007
0 views

cushmancvbb

SP297
27. 11. 2007
0 views

SP297

Italu pristatymas
01. 11. 2007
0 views

Italu pristatymas

cfunited 06 ThomasBurleson
01. 12. 2007
0 views

cfunited 06 ThomasBurleson

group1presentation to post
01. 01. 2008
0 views

group1presentation to post

nenny soemiwinata
29. 09. 2007
0 views

nenny soemiwinata

CCAT06 Holland
15. 11. 2007
0 views

CCAT06 Holland

paper pansa
24. 11. 2007
0 views

paper pansa